Return-Path: Delivered-To: apmail-incubator-stdcxx-dev-archive@www.apache.org Received: (qmail 36156 invoked from network); 7 Feb 2006 16:21:23 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199) by minotaur.apache.org with SMTP; 7 Feb 2006 16:21:23 -0000 Received: (qmail 58800 invoked by uid 500); 7 Feb 2006 16:21:22 -0000 Delivered-To: apmail-incubator-stdcxx-dev-archive@incubator.apache.org Received: (qmail 58785 invoked by uid 500); 7 Feb 2006 16:21:22 -0000 Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: stdcxx-dev@incubator.apache.org Delivered-To: mailing list stdcxx-dev@incubator.apache.org Received: (qmail 58761 invoked by uid 99); 7 Feb 2006 16:21:22 -0000 Received: from asf.osuosl.org (HELO asf.osuosl.org) (140.211.166.49) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 07 Feb 2006 08:21:21 -0800 X-ASF-Spam-Status: No, hits=-0.0 required=10.0 tests=SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (asf.osuosl.org: domain of AntonP@moscow.vdiweb.com designates 195.210.189.132 as permitted sender) Received: from [195.210.189.132] (HELO exmsk.moscow.vdiweb.com) (195.210.189.132) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 07 Feb 2006 08:21:19 -0800 Received: from [10.11.0.166] ([10.11.0.166]) by exmsk.moscow.vdiweb.com with Microsoft SMTPSVC(6.0.3790.1830); Tue, 7 Feb 2006 19:20:55 +0300 Message-ID: <43E8C8E1.8040401@moscow.vdiweb.com> Date: Tue, 07 Feb 2006 19:20:49 +0300 From: Anton Pevtsov User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.7) Gecko/20040514 X-Accept-Language: en-us, en MIME-Version: 1.0 To: stdcxx-dev@incubator.apache.org Subject: Re: Re: test for lib.alg.sort Content-Type: multipart/mixed; boundary="------------010908050403040407040506" X-OriginalArrivalTime: 07 Feb 2006 16:20:55.0800 (UTC) FILETIME=[78FC5F80:01C62C02] X-Virus-Checked: Checked by ClamAV on apache.org X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N --------------010908050403040407040506 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Martin Sebor wrote: > <>> It looks to me like the sort and stable_sort tests are completel > <>independent of the partial sort tests, correct? If that's so, could you > please split the test into two? It will make them easier to > > maintain and prevent errors in one from affecting the results of the > other. Yes, the attached files contains separated tests for sort and partial_sort algorithms. Martin Sebor wrote: > <>[...] > <>> Here's a little program that should demonstrate what I mean. Note that > the replacement operator new and delete don't work across shared library > <>boundaries on AIX and Windows. It would be > nice to find an > equivalent solution that does work there (or at least on Windows). Some > kind of malloc() hook maybe -- any ideas? > Hmm, hooks seems to be a tricky and platform-dependent solution. May be it is possible to add the "logged" (as in the test driver) new and delete operators into the library itself and switch to them using some define? With best wishes, Anton Pevtsov > <> > -----Original Message----- > From: Martin Sebor [mailto:sebor@roguewave.com] > Sent: Tuesday, February 07, 2006 05:43 > To: stdcxx-dev@incubator.apache.org > Subject: Re: test for lib.alg.sort > > > Anton Pevtsov wrote: >> The attached file contains tests for the lib.alg.sort, >> lib.alg.stable_sort, lib.alg.partitial_sort and >> lib.alg.partitial_sort_copy algorithms. > > It looks to me like the sort and stable_sort tests are completely independent of the partial sort tests, correct? If that's so, could you please split the test into two? It will make them easier to maintain and prevent errors in one from affecting the results of the other. >> Here I check the algotithms correctness using the hardcoded sequences > > Good! >> and verify the complexity using the random-generated sequences. The >> upper estimated value for algorithms was left without changes, but may > > >> be we should open a jira issue about the complexity checks. > > I agree, let's do. >> >> Martin Sebor wrote: >> [...] >> >Be sure to verify this in the test itself (i.e., the test should >> issue >an error when it can't force the algorithm to use dynamically >> allocated >memory. [...] >> >> I am not sure that I understand your completely, but I added the test >> with forced dynamically memory allocation for stable_sort. > > What I meant was that after calling get_temporary_buffer() first in order to force stable sort to use dynamically allocated storage the test should use the replacement operator to detect whether the algorithm in fact does use it. Here's a little program that should demonstrate what I mean. Note that the replacement operator new and delete don't work across shared library boundaries on AIX and Windows. It would be nice to find an equivalent solution that does work there (or at least on Windows). Some kind of malloc() hook maybe -- any ideas? Martin #include // for assert() #include // for ptrdiff_t, size_t #include // for stable_sort() #include // for get_temporary_buffer() #include // for pair #include // for rwt_free_store, rwt_checkpoint() int main () { // prevent stable_sort from using the temporary buffer // and force the algorithm to dynamically allocate storage // instead const std::pair tmpbuf = std::get_temporary_buffer(1000); rwt_free_store state [2]; // save the initial state of the dynamic store in state[0] state [0] = *rwt_get_free_store (0); int a[] = { 0, 1, 2 }; std::stable_sort (a, a + sizeof a / sizeof *a); // save the current state of the dynamic store in state[1] rwt_get_free_store (state + 1); // compute the difference between state[1] and state[0] const rwt_free_store* const pdiff = rwt_checkpoint (state, state + 1); // assert that the two states are different assert (0 != pdiff); // compute the number of calls to operators new and delete, // and the amount of outstanding dynamic storage between // the two checkpoints const std::size_t new_calls = pdiff->new_calls_ [0] + pdiff->new_calls_ [1]; const std::size_t delete_calls = pdiff->delete_calls_ [0] + pdiff->delete_calls_ [1]; const std::size_t leaked_blocks = pdiff->blocks_ [0] + pdiff->blocks_ [1]; const std::size_t leaked_bytes = pdiff->bytes_ [0] + pdiff->bytes_ [1]; // assert that the algorithm used dynamic storage and that // that it made at least as many calls to delete as it did // to new (it may have called operator delete (0)) assert (0 < new_calls); assert (new_calls <= delete_calls); // assert that the algorithm released all dynamically allocated // storage assert (0 == leaked_blocks); assert (0 == leaked_bytes); } --------------010908050403040407040506 Content-Type: text/plain; name="25.sort.cpp" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="25.sort.cpp" /*************************************************************************** * * sort.cpp - test exercising 25.3.1-3 [lib.alg.sort] * * $Id: //stdlib/dev/tests/stdlib/algorithm/sort.cpp#21 $ * *************************************************************************** * * Copyright (c) 1994-2005 Quovadx, Inc., acting through its Rogue Wave * Software division. Licensed under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance with the * License. You may obtain a copy of the License at * http://www.apache.org/licenses/LICENSE-2.0. Unless required by * applicable law or agreed to in writing, software distributed under * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR * CONDITIONS OF ANY KIND, either express or implied. See the License * for the specific language governing permissions and limitations under * the License. * **************************************************************************/ #include // for sort, stable_sort #include // for strlen, size_t #include // for ptrdiff_t #include #include // for rw_test() _RWSTD_NAMESPACE (std) { // disable explicit instantiation for compilers (like MSVC) // that can't handle it #ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION template void sort (RandomAccessIter > > >, RandomAccessIter > > >); template void sort (RandomAccessIter > > >, RandomAccessIter > > >, binary_predicate > > >); template void stable_sort (RandomAccessIter > > >, RandomAccessIter > > >); template void stable_sort (RandomAccessIter > > >, RandomAccessIter > > >, binary_predicate > > >); #endif // _RWSTD_NO_EXPLICIT_INSTANTIATION } // namespace std /**************************************************************************/ template struct StrictWeakLess { static std::size_t funcalls_; // dummy arguments provided to prevent the class from being // default constructible and implicit conversion from int StrictWeakLess (int /* dummy */, int /* dummy */) { funcalls_ = 0; } // return a type other than bool but one that is implicitly // convertible to bool to detect incorrect assumptions conv_to_bool operator() (const T &x, const T &y) /* non-const */ { ++funcalls_; return conv_to_bool::make (x.val_ < y.val_); } static const char* name () { return "StrictWeakLess"; } private: void operator= (StrictWeakLess&); // not assignable }; template std::size_t StrictWeakLess::funcalls_; /**************************************************************************/ template void test_sort (int line, const char *src, const std::size_t N, const T*, const Predicate *ppred, bool stable, bool alloc) { typedef RandomAccessIter RandIter; const RandIter it(0, 0, 0); const char* const itname = "RandomAccessIterator"; const char* const fname = stable ? "stable_sort" : "sort"; const char* const funname = ppred ? Predicate::name() : "operator<()"; // generate random values for each default constructed T T::gen_ = gen_rnd; const std::size_t nsrc = src ? std::strlen (src) : N; T* const xsrc = src ? T::from_char (src, nsrc) : new T[nsrc]; T* const xsrc_end = xsrc + nsrc; RandIter first = make_iter (xsrc, xsrc, xsrc_end, it); RandIter last = make_iter (xsrc_end, xsrc, xsrc_end, it); const Predicate pred(0, 0); std::size_t last_n_op_lt = T::n_total_op_lt_; std::size_t last_n_op_cpy = T::n_total_op_assign_ + T::n_total_copy_ctor_; _RWSTD_UNUSED (last_n_op_cpy); if (stable) { std::pair dummy; if (alloc) { dummy = std::_GET_TEMP_BUFFER (T, nsrc + 1); rw_assert (0 != dummy.first, 0, 0, "line %d: %s<%s%{?}, %s%{;}> (): " "memory allocation failed for %zu elements", __LINE__, fname, itname, ppred, funname, nsrc); } if (ppred) std::stable_sort (first, last, pred); else std::stable_sort (first, last); if (alloc && dummy.first) std::return_temporary_buffer (dummy.first); } else { if (ppred) std::sort (first, last, pred); else std::sort (first, last); } // some tracing goes here /* if (! stable) { // number of comparison operations std::size_t ops = std::size_t (T::n_total_op_lt_ - last_n_op_lt); // number of copy ctor and assignmen operator calls std::size_t cpy = std::size_t (T::n_total_op_assign_ + T::n_total_copy_ctor_) - std::size_t (last_n_op_cpy); // expected complexity (number opf comparisons) std::size_t cmplx = (nsrc + 1) * ilog2 (nsrc + 2); double x = double (ops) / cmplx; // max and min T static double x_max = 0.0; static double x_min = 1.0; if (x > x_max) x_max = x; if (nsrc > 16 && x < x_min) x_min = x; // complexity: X * N * log (N), ideally with X approaching 1 if (!(nsrc % 20)) { rw_info (0, 0, 0, "\n+------+------+------+------+------+------+------+\n" "| N | COMP | COPY |N lg N| X | max X| min X|\n" "+======+======+======+======+======+======+======+\n"); // # | comp | assign | exp. complexity | X | max X | rw_info (0, 0, 0, "\n|%6d|%6d|%6d|%6d|%6.2f|%6.2f|%6.2f|\n", nsrc + 1, ops, cpy, cmplx, x, x_max, x_min); } } */ // check that the array is sorted bool success = is_sorted_lt (xsrc, xsrc_end); if (src) { rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}> (\"%s\", ...) ==> " "\"%{X=*.*}\" not sorted", __LINE__, fname, itname, ppred, funname, src, int (nsrc), -1, xsrc); } else { rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}> (%zu, ...): " "not sorted", __LINE__, fname, itname, ppred, funname, nsrc); } // verify 25.3.1.1, p2 and 25.3.1.2, p3 // the complexity of our implementation is no worse than // 3.33 * N * log (N) (hence the magic 7 and 2) std::size_t n_ops = ppred ? Predicate::funcalls_ : T::n_total_op_lt_ - last_n_op_lt; std::size_t exp_ops = 7 * nsrc * ::ilog2 (nsrc); success = 2 * n_ops <= exp_ops; rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}> (): complexity for " "length %zu is %zu, expected no more than %zu", __LINE__, fname, itname, ppred, funname, nsrc, n_ops, exp_ops / 2); // verify 25.3.1.2 p2 if (stable) { std::size_t j = 1; for ( ; j < N; j++) { if (xsrc[j - 1].val_ == xsrc[j].val_) success = xsrc[j - 1].origin_ < xsrc[j].origin_; if (!success) break; } // to avoid errors in --trace mode j = j < nsrc ? j : nsrc - 1; if (src) { rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}> (\"%s\", ...) ==> " "\"%{X=*.*}\" relative order is broken at %zu: " "got ids %zu and %zu for values %#c and %#c", __LINE__, fname, itname, ppred, funname, src, int (nsrc), -1, xsrc, j, xsrc[j - 1].origin_, xsrc[j].origin_, xsrc[j - 1].val_, xsrc[j].val_); } else { rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}> (): relative order " "is broken for %zu at %zu: got ids %zu and %zu " "for values %d and %d", __LINE__, fname, itname, ppred, funname, nsrc, j, xsrc[j - 1].origin_, xsrc[j].origin_, xsrc[j - 1].val_, xsrc[j].val_); } } delete[] xsrc; } /**************************************************************************/ /* extern */ int rw_opt_nloops = 256; // --nloops=# /* extern */ int rw_opt_no_sort; // --no-sort /* extern */ int rw_opt_no_stable_sort; // --no-stable_sort /* extern */ int rw_opt_no_predicate; // --no-predicate /* extern */ int rw_opt_no_complexity; // --no-complexity /**************************************************************************/ template void test_sort (const std::size_t N, const T*, const Predicate *ppred, bool stable, bool alloc) { rw_info (0, 0, 0, "template " "void std::%s (%1$s, %1$s%{?}, %3$s%{;})" "%{?} with memory allocation%{;}", "RandomAccessIterator", ppred, "StrictWeakComp", stable ? "stable_sort" : "sort", ppred, stable && alloc); const char* const itname = "RandomAccessIterator"; const char* const fname = stable ? "stable_sort" : "sort"; const char* const funname = ppred ? Predicate::name() : "operator<()"; rw_info (0, 0, 0, "std::%s (%s, %2$s%{?}, %s%{;})", fname, itname, ppred, funname); #define TEST(src) \ test_sort (__LINE__, src, 0, (T*)0, ppred, stable, alloc) TEST ("a"); TEST ("ba"); TEST ("cba"); TEST ("dcba"); TEST ("edcba"); TEST ("fedcba"); TEST ("gfedcba"); TEST ("hgfedcba"); TEST ("ihgfedcba"); TEST ("jihgfedcba"); TEST ("ab"); TEST ("abc"); TEST ("abcd"); TEST ("abcde"); TEST ("abcdef"); TEST ("abcdefg"); TEST ("abcdefgh"); TEST ("abcdefghi"); TEST ("abcdefghij"); TEST ("aa"); TEST ("aabb"); TEST ("bbccaa"); TEST ("ddbbccaa"); TEST ("ddeebbccaa"); TEST ("aaaaaaaaaa"); TEST ("ababababab"); TEST ("bababababa"); #undef TEST if (rw_opt_no_complexity) { rw_note (0, 0, 0, "std::%s (%s, %2$s%{?}, %s%{;}) complexity test disabled", fname, itname, ppred, funname); } else { rw_info (0, 0, 0, "std::%s (%s, %2$s%{?}, %s%{;}) : complexity test", fname, itname, ppred, funname); for (std::size_t i = 1; i < N; i++) test_sort (__LINE__, 0, i, (T*)0, ppred, stable, alloc); } } /**************************************************************************/ template void test_sort (const std::size_t N, const T* , bool stable, bool alloc) { test_sort (N, (T*)0, (StrictWeakLess*)0, stable, alloc); if (rw_opt_no_predicate) { rw_note (0, __FILE__, __LINE__, "std::%s predicate test disabled", stable ? "stable_sort" : "sort"); } else { const StrictWeakLess pred(0, 0); test_sort (N, (T*)0, &pred, stable, alloc); } } /**************************************************************************/ static int run_test (int, char*[]) { const std::size_t N = std::size_t (rw_opt_nloops); if (rw_opt_no_sort) { rw_note (0, __FILE__, __LINE__, "std::sort test disabled"); } else { test_sort (N, (X*)0, false, false); } if (rw_opt_no_stable_sort) { rw_note (0, __FILE__, __LINE__, "std::stable_sort test disabled"); } else { test_sort (N, (X*)0, true, false); // test with memory reallocation test_sort (N, (X*)0, true, true); } return 0; } /**************************************************************************/ int main (int argc, char *argv[]) { return rw_test (argc, argv, __FILE__, "lib.alg.sort", 0 /* no comment */, run_test, "|-nloops#0 " // must be non-negative "|-no-sort# " "|-no-stable_sort# " "|-no-predicate", &rw_opt_nloops, &rw_opt_no_sort, &rw_opt_no_stable_sort, &rw_opt_no_predicate, &rw_opt_no_complexity); } --------------010908050403040407040506 Content-Type: text/plain; name="25.partial.sort.cpp" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="25.partial.sort.cpp" /*************************************************************************** * * sort.cpp - test exercising 25.3.1-3 [lib.alg.sort] * * $Id: //stdlib/dev/tests/stdlib/algorithm/sort.cpp#21 $ * *************************************************************************** * * Copyright (c) 1994-2005 Quovadx, Inc., acting through its Rogue Wave * Software division. Licensed under the Apache License, Version 2.0 (the * "License"); you may not use this file except in compliance with the * License. You may obtain a copy of the License at * http://www.apache.org/licenses/LICENSE-2.0. Unless required by * applicable law or agreed to in writing, software distributed under * the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR * CONDITIONS OF ANY KIND, either express or implied. See the License * for the specific language governing permissions and limitations under * the License. * **************************************************************************/ #include // for partial_sort, partial_sort_copy #include // for strlen, size_t #include #include // for rw_test() _RWSTD_NAMESPACE (std) { // disable explicit instantiation for compilers (like MSVC) // that can't handle it #ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION template void partial_sort (RandomAccessIter > > >, RandomAccessIter > > >, RandomAccessIter > > >); template void partial_sort (RandomAccessIter > > >, RandomAccessIter > > >, RandomAccessIter > > >, binary_predicate > > >); template RandomAccessIter > > > partial_sort_copy (InputIter > > >, InputIter > > >, RandomAccessIter > > >, RandomAccessIter > > >); template RandomAccessIter > > > partial_sort_copy (InputIter > > >, InputIter > > >, RandomAccessIter > > >, RandomAccessIter > > >, binary_predicate > > >); #endif // _RWSTD_NO_EXPLICIT_INSTANTIATION } // namespace std /**************************************************************************/ template struct StrictWeakLess { static std::size_t funcalls_; // dummy arguments provided to prevent the class from being // default constructible and implicit conversion from int StrictWeakLess (int /* dummy */, int /* dummy */) { funcalls_ = 0; } // return a type other than bool but one that is implicitly // convertible to bool to detect incorrect assumptions conv_to_bool operator() (const T &x, const T &y) /* non-const */ { ++funcalls_; return conv_to_bool::make (x.val_ < y.val_); } static const char* name () { return "StrictWeakLess"; } private: void operator= (StrictWeakLess&); // not assignable }; template std::size_t StrictWeakLess::funcalls_; /**************************************************************************/ template void test_partial_sort (int line, const char *src, const std::size_t N, const std::size_t mid, const Iterator &it, const CopyIterator &itc, const T* , const Predicate *ppred, bool copy) { typedef RandomAccessIter RandIter; const RandIter rand_it(0, 0, 0); const char* const itname = copy ? type_name (itc, (T*)0) : type_name (it, (T*)0); const char* const outname = "RandomAccessIterator"; const char* const fname = copy ? "partial_sort_copy" : "partial_sort"; const char* const funname = ppred ? Predicate::name() : "operator<()"; // generate random values for each default constructed T T::gen_ = gen_rnd; const std::size_t nsrc = src ? std::strlen (src) : N; T* const xsrc = src ? T::from_char (src, nsrc) : new T[nsrc]; T* const xdst = new T [mid]; T* res_x = copy ? xdst : xsrc; T* const xsrc_end = xsrc + nsrc; T* const xdst_end = xdst + mid; Iterator first = make_iter (xsrc, xsrc, xsrc_end, it); Iterator middle = make_iter (xsrc + mid, xsrc, xsrc_end, it); Iterator last = make_iter (xsrc_end, xsrc, xsrc_end, it); CopyIterator first_c = make_iter (xsrc, xsrc, xsrc_end, itc); CopyIterator last_c = make_iter (xsrc_end, xsrc, xsrc_end, itc); RandIter res_first = make_iter (xdst, xdst, xdst_end, rand_it); RandIter res_last = make_iter (xdst_end, xdst, xdst_end, rand_it); const Predicate pred(0, 0); RandIter result(0, 0, 0); std::size_t last_n_op_lt = T::n_total_op_lt_; if (copy) { if (ppred) result = std::partial_sort_copy ( first_c, last_c, res_first, res_last, pred); else result = std::partial_sort_copy ( first_c, last_c, res_first, res_last); } else { if (ppred) std::partial_sort (first, middle, last, pred); else std::partial_sort (first, middle, last); } bool success = true; // check the returned iterator for copy version if (copy) { success = result.cur_ == res_first.cur_ + mid; rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}%{?}, %s%{;}> (): " "returned iterator it is invalid: got result + %td, " "expected result + %zu", __LINE__, fname, itname, copy, outname, ppred, funname, result.cur_ - res_first.cur_, mid); } // check that the array is sorted success = is_sorted_lt (res_x, res_x + mid); if (src) { rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}%{?}, %s%{;}> " "(\"%s\", %zu, ...): ==> \"%{X=*.*}\" not sorted", __LINE__, fname, itname, copy, outname, ppred, funname, src, mid, int (mid), -1, res_x); } else { rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}%{?}, %s%{;}> " "(%zu, %zu, ...): not sorted", __LINE__, fname, itname, copy, outname, ppred, funname, nsrc, mid); } // check that any element in the sorted range <= that any element // in the rest part of the array int max_el = res_x[0].val_; std::size_t j = 1; for ( ; j < mid; j++) max_el = max_el < res_x[j].val_ ? res_x[j].val_ : max_el; if (copy) { std::size_t tmp = 0; for (j = 0; j < nsrc; j++) if (max_el > xsrc[j].val_) tmp++; success = tmp <= mid; } else { for (j = mid; j < nsrc; j++) { success = max_el <= xsrc[j].val_; if (! success) break; } } // to avoid error in trace mode j = j < nsrc ? j : nsrc - 1; if (src) { rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}%{?}, %s%{;}> " "(\"%s\", %zu, ...): ==> \"%{X=*.*}\" got less element " "%{?}%#c%{;} in the unsorted part", __LINE__, fname, itname, copy, outname, ppred, funname, src, mid, int (copy ? mid : nsrc), -1, res_x, !copy, xsrc[j].val_); } else { rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}%{?}, %s%{;}> " "(%zu, %zu, ...): got less element in the unsorted part", __LINE__, fname, itname, copy, outname, ppred, funname, nsrc, mid); } // verify 25.3.1.1, p2 and 25.3.1.2, p3 // the complexity of our implementation is no worse than // 3.33 * N * log (N) (hence the magic 7 and 2) std::size_t n_ops = ppred ? Predicate::funcalls_ : T::n_total_op_lt_ - last_n_op_lt; std::size_t exp_ops = 7 * nsrc * ::ilog2 (mid > 1 ? mid : 2); success = 2 * n_ops <= exp_ops; rw_assert (success, 0, line, "line %d: %s<%s%{?}, %s%{;}%{?}, %s%{;}> (): complexity " "for length %zu is %zu, expected no more than %zu", __LINE__, fname, itname, copy, outname, ppred, funname, nsrc, n_ops, exp_ops / 2); delete[] xsrc; delete[] xdst; } /**************************************************************************/ /* extern */ int rw_opt_nloops = 256; // --nloops=# /* extern */ int rw_opt_no_partial_sort; // --no-partial_sort /* extern */ int rw_opt_no_partial_sort_copy; // --no-partial_sort_copy /* extern */ int rw_opt_no_predicate; // --no-predicate /* extern */ int rw_opt_no_complexity; // --no-complexity /* extern */ int rw_opt_no_input_iter; // --no-InputIterator /* extern */ int rw_opt_no_fwd_iter; // --no-ForwardIterator /* extern */ int rw_opt_no_bidir_iter; // --no-BidirectionalIterator /* extern */ int rw_opt_no_rnd_iter; // --no-RandomAccessIterator /**************************************************************************/ template void test_partial_sort (const std::size_t N, const Iterator &it, const CopyIterator &itc, const T* , const Predicate *ppred, bool copy) { const char* const itname = copy ? type_name (itc, (T*)0) : type_name (it, (T*)0); const char* const outname = "RandomAccessIterator"; const char* const fname = copy ? "partial_sort_copy" : "partial_sort"; const char* const funname = ppred ? Predicate::name() : "operator<()"; rw_info (0, 0, 0, "%{?}%s %{;}std::%s (%s, %4$s, %s%{?}, %2$s%{;}%{?}, %s%{;})", copy, outname, fname, itname, copy ? outname : itname, copy, ppred, funname); #define TEST(src, mid) \ test_partial_sort (__LINE__, src, 0, mid, it, itc, (T*)0, ppred, copy) TEST ("a", 1); TEST ("ba", 1); TEST ("cba", 1); TEST ("dcba", 2); TEST ("edcba", 2); TEST ("fedcba", 3); TEST ("gfedcba", 3); TEST ("hgfedcba", 4); TEST ("ihgfedcba", 4); TEST ("jihgfedcba", 5); TEST ("ab", 1); TEST ("abc", 1); TEST ("abcd", 2); TEST ("abcde", 2); TEST ("abcdef", 3); TEST ("abcdefg", 3); TEST ("abcdefgh", 4); TEST ("abcdefghi", 4); TEST ("abcdefghij", 5); TEST ("aa", 1); TEST ("aabb", 2); TEST ("bbccaa", 3); TEST ("ddbbccaa", 4); TEST ("ddeebbccaa", 5); TEST ("aa", 2); TEST ("aabb", 4); TEST ("bbccaa", 6); TEST ("ddbbccaa", 8); TEST ("ddeebbccaa", 10); TEST ("aaaaaaaaaa", 5); TEST ("ababababab", 4); TEST ("bababababa", 4); #undef TEST if (rw_opt_no_complexity) { rw_note (0, 0, 0, "%{?}%s %{;}std::%s (%s, %4$s, %s%{?}, %2$s%{;}%{?}, %s%{;})" ": complexity test disabled", copy, outname, fname, itname, copy ? outname : itname, copy, ppred, funname); } else { rw_info (0, 0, 0, "%{?}%s %{;}std::%s (%s, %4$s, %s%{?}, %2$s%{;}%{?}, %s%{;}) : " "complexity test", copy, outname, fname, itname, copy ? outname : itname, copy, ppred, funname); for (std::size_t i = 1; i < N; i++) test_partial_sort (__LINE__, 0, i, i > 1 ? i / 2 : 1, it, itc, (T*)0, ppred, copy); } } /**************************************************************************/ template void test_partial_sort (const std::size_t N, const T* , const Predicate *ppred, bool copy) { rw_info (0, 0, 0, "template " "%s std::%s (%1$s%{?}, %1$s%{;}, %1$s" "%{?}, %3$s, %3$s%{;}%{?}, %5$s%{;})", copy ? "InputIterator" : "RandomAccessIterator", copy, "RandomAccessIterator", ppred, "StrictWeakComp", copy ? "RandomAccessIterator" : "void", copy ? "partial_sort_copy" : "partial_sort", !copy, copy, ppred); static const InputIter input_iter (0, 0, 0); static const FwdIter fwd_iter (0, 0, 0); static const BidirIter bidir_iter (0, 0, 0); static const RandomAccessIter rand_iter (0, 0, 0); if (! copy) { test_partial_sort (N, rand_iter, rand_iter, (T*)0, ppred, false); return; } if (rw_opt_no_input_iter) { rw_note (0, __FILE__, __LINE__, "InputIterator test disabled"); } else { test_partial_sort (N, rand_iter, input_iter, (T*)0, ppred, true); } if (rw_opt_no_fwd_iter) { rw_note (0, __FILE__, __LINE__, "ForwardIterator test disabled"); } else { test_partial_sort (N, rand_iter, fwd_iter, (T*)0, ppred, true); } if (rw_opt_no_bidir_iter) { rw_note (0, __FILE__, __LINE__, "BidirectionalIterator test disabled"); } else { test_partial_sort (N, rand_iter, bidir_iter, (T*)0, ppred, true); } if (rw_opt_no_rnd_iter) { rw_note (0, __FILE__, __LINE__, "RandomAccessIterator test disabled"); } else { test_partial_sort (N, rand_iter, rand_iter, (T*)0, ppred, true); } } template void test_partial_sort (const std::size_t N, const T* , bool copy) { test_partial_sort (N, (T*)0, (StrictWeakLess*)0, copy); if (rw_opt_no_predicate) { rw_note (0, __FILE__, __LINE__, "std::%s predicate test disabled", copy ? "partial_sort_copy" : "partial_sort"); } else { const StrictWeakLess pred(0, 0); test_partial_sort (N, (T*)0, &pred, copy); } } /**************************************************************************/ static int run_test (int, char*[]) { const std::size_t N = std::size_t (rw_opt_nloops); if (rw_opt_no_partial_sort) { rw_note (0, __FILE__, __LINE__, "std::partial_sort test disabled"); } else { test_partial_sort (N, (X*)0, false); } if (rw_opt_no_partial_sort_copy) { rw_note (0, __FILE__, __LINE__, "std::partial_sort_copy test disabled"); } else { test_partial_sort (N, (X*)0, true); } return 0; } /**************************************************************************/ int main (int argc, char *argv[]) { return rw_test (argc, argv, __FILE__, "lib.alg.sort", 0 /* no comment */, run_test, "|-nloops#0 " // must be non-negative "|-no-partial_sort# " "|-no-partial_sort_copy# " "|-no-InputIterator# " "|-no-ForwardIterator# " "|-no-BidirectionalIterator# " "|-no-RandomAccessIterator# " "|-no-predicate", &rw_opt_nloops, &rw_opt_no_partial_sort, &rw_opt_no_partial_sort_copy, &rw_opt_no_input_iter, &rw_opt_no_fwd_iter, &rw_opt_no_bidir_iter, &rw_opt_no_rnd_iter, &rw_opt_no_predicate, &rw_opt_no_complexity); } --------------010908050403040407040506--