Return-Path: Delivered-To: apmail-incubator-stdcxx-commits-archive@www.apache.org Received: (qmail 94207 invoked from network); 7 Feb 2006 23:43:37 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199) by minotaur.apache.org with SMTP; 7 Feb 2006 23:43:37 -0000 Received: (qmail 80186 invoked by uid 500); 7 Feb 2006 23:43:37 -0000 Delivered-To: apmail-incubator-stdcxx-commits-archive@incubator.apache.org Received: (qmail 80160 invoked by uid 500); 7 Feb 2006 23:43:36 -0000 Mailing-List: contact stdcxx-commits-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-commits@incubator.apache.org Received: (qmail 80149 invoked by uid 500); 7 Feb 2006 23:43:36 -0000 Delivered-To: apmail-incubator-stdcxx-cvs@incubator.apache.org Received: (qmail 80146 invoked by uid 99); 7 Feb 2006 23:43:36 -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 15:43:36 -0800 X-ASF-Spam-Status: No, hits=-9.4 required=10.0 tests=ALL_TRUSTED,NO_REAL_NAME X-Spam-Check-By: apache.org Received: from [209.237.227.194] (HELO minotaur.apache.org) (209.237.227.194) by apache.org (qpsmtpd/0.29) with SMTP; Tue, 07 Feb 2006 15:43:34 -0800 Received: (qmail 94095 invoked by uid 65534); 7 Feb 2006 23:43:13 -0000 Message-ID: <20060207234313.94079.qmail@minotaur.apache.org> Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r375776 - in /incubator/stdcxx/trunk/tests/algorithms: 25.partial.sort.cpp 25.sort.cpp Date: Tue, 07 Feb 2006 23:43:09 -0000 To: stdcxx-cvs@incubator.apache.org From: sebor@apache.org X-Mailer: svnmailer-1.0.6 X-Virus-Checked: Checked by ClamAV on apache.org X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N Author: sebor Date: Tue Feb 7 15:43:05 2006 New Revision: 375776 URL: http://svn.apache.org/viewcvs?rev=375776&view=rev Log: 2006-02-07 Anton Pevtsov STDCXX-4 * 25.sort.cpp: New test exercising lib.sort and lib.stable.sort. * 25.partial.sort.cpp: New test exercising lib.partial.sort and lib.partial.sort.copy. Added: incubator/stdcxx/trunk/tests/algorithms/25.partial.sort.cpp (with props) incubator/stdcxx/trunk/tests/algorithms/25.sort.cpp (with props) Added: incubator/stdcxx/trunk/tests/algorithms/25.partial.sort.cpp URL: http://svn.apache.org/viewcvs/incubator/stdcxx/trunk/tests/algorithms/25.partial.sort.cpp?rev=375776&view=auto ============================================================================== --- incubator/stdcxx/trunk/tests/algorithms/25.partial.sort.cpp (added) +++ incubator/stdcxx/trunk/tests/algorithms/25.partial.sort.cpp Tue Feb 7 15:43:05 2006 @@ -0,0 +1,479 @@ +/*************************************************************************** + * + * 25.partial.sort.cpp - test exercising [lib.partial.sort] + * + * $Id$ + * + *************************************************************************** + * + * 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 Less +{ + static std::size_t funcalls_; + + // dummy arguments provided to prevent the class from being + // default constructible and implicit conversion from int + Less (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 "Less"; } + +private: + void operator= (Less&); // not assignable +}; + +template std::size_t Less::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; + + const Iterator first = make_iter (xsrc, xsrc, xsrc_end, it); + const Iterator middle = make_iter (xsrc + mid, xsrc, xsrc_end, it); + const 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::partial_sort%{?}_copy%{;} (%1$s%{?}, %1$s%{;}, %1$s" + "%{?}, %3$s, %3$s%{;}%{?}, %5$s%{;})", + copy ? "InputIterator" : "RandomAccessIterator", + copy, "RandomAccessIterator", ppred, "StrictWeakComp", + copy ? "RandomAccessIterator" : "void", + copy, !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, (Less*)0, copy); + + if (rw_opt_no_predicate) { + rw_note (0, __FILE__, __LINE__, + "std::partial_sort%{?}_copy%{;} predicate test disabled", + copy); + } + else { + const Less 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.partial.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); +} Propchange: incubator/stdcxx/trunk/tests/algorithms/25.partial.sort.cpp ------------------------------------------------------------------------------ svn:eol-style = native Propchange: incubator/stdcxx/trunk/tests/algorithms/25.partial.sort.cpp ------------------------------------------------------------------------------ svn:keywords = Id Added: incubator/stdcxx/trunk/tests/algorithms/25.sort.cpp URL: http://svn.apache.org/viewcvs/incubator/stdcxx/trunk/tests/algorithms/25.sort.cpp?rev=375776&view=auto ============================================================================== --- incubator/stdcxx/trunk/tests/algorithms/25.sort.cpp (added) +++ incubator/stdcxx/trunk/tests/algorithms/25.sort.cpp Tue Feb 7 15:43:05 2006 @@ -0,0 +1,408 @@ +/*************************************************************************** + * + * 25.sort.cpp - test exercising lib.sort and lib.stable.sort + * + * $Id$ + * + *************************************************************************** + * + * 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 Less +{ + static std::size_t funcalls_; + + // dummy arguments provided to prevent the class from being + // default constructible and implicit conversion from int + Less (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 "Less"; } + +private: + void operator= (Less&); // not assignable +}; + +template std::size_t Less::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) + const std::size_t n_ops = + ppred ? Predicate::funcalls_ : T::n_total_op_lt_ - last_n_op_lt; + + const 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::%{?}stable_%{;}sort (%1$s, %1$s%{?}, %3$s%{;})" + "%{?} with memory allocation%{;}", + "RandomAccessIterator", ppred, "StrictWeakComp", + stable, 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, (Less*)0, stable, alloc); + + if (rw_opt_no_predicate) { + rw_note (0, __FILE__, __LINE__, + "std::%{?}stable_%{;}sort predicate test disabled", + stable); + } + else { + const Less 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.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); +} Propchange: incubator/stdcxx/trunk/tests/algorithms/25.sort.cpp ------------------------------------------------------------------------------ svn:eol-style = native Propchange: incubator/stdcxx/trunk/tests/algorithms/25.sort.cpp ------------------------------------------------------------------------------ svn:keywords = Id