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 <[EMAIL PROTECTED]>
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 <algorithm> // for partial_sort, partial_sort_copy
+#include <cstring> // for strlen, size_t
+
+#include <alg_test.h>
+#include <driver.h> // 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<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >);
+
+template
+void
+partial_sort (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);
+
+template
+RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >
+partial_sort_copy (InputIter<lt_comp<assign<base<cpy_ctor> > > >,
+ InputIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >);
+
+template
+RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >
+partial_sort_copy (InputIter<lt_comp<assign<base<cpy_ctor> > > >,
+ InputIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);
+
+#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION
+
+} // namespace std
+
+/**************************************************************************/
+
+template <class T>
+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<class T> std::size_t Less<T>::funcalls_;
+
+/**************************************************************************/
+
+template <class Iterator, class CopyIterator, class T, class Predicate>
+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<T> 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 <class Iterator, class CopyIterator, class T, class Predicate>
+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 <class T, class Predicate>
+void test_partial_sort (const std::size_t N,
+ const T* ,
+ const Predicate *ppred,
+ bool copy)
+{
+ rw_info (0, 0, 0,
+ "template <class %s%{?}, class %s%{;}%{?}, class %s%{;}> "
+ "%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<T> input_iter (0, 0, 0);
+ static const FwdIter<T> fwd_iter (0, 0, 0);
+ static const BidirIter<T> bidir_iter (0, 0, 0);
+ static const RandomAccessIter<T> 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 <class T>
+void test_partial_sort (const std::size_t N,
+ const T* ,
+ bool copy)
+{
+ test_partial_sort (N, (T*)0, (Less<T>*)0, copy);
+
+ if (rw_opt_no_predicate) {
+ rw_note (0, __FILE__, __LINE__,
+ "std::partial_sort%{?}_copy%{;} predicate test disabled",
+ copy);
+ }
+ else {
+ const Less<T> 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 <algorithm> // for sort, stable_sort
+#include <cstring> // for strlen, size_t
+#include <cstddef> // for ptrdiff_t
+
+#include <alg_test.h>
+#include <driver.h> // 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<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >);
+
+template
+void
+sort (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);
+
+template
+void
+stable_sort (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >);
+
+template
+void
+stable_sort (RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ RandomAccessIter<lt_comp<assign<base<cpy_ctor> > > >,
+ binary_predicate<lt_comp<assign<base<cpy_ctor> > > >);
+
+#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION
+
+} // namespace std
+
+/**************************************************************************/
+
+template <class T>
+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<class T> std::size_t Less<T>::funcalls_;
+
+/**************************************************************************/
+
+template <class T, class Predicate>
+void test_sort (int line,
+ const char *src,
+ const std::size_t N,
+ const T*,
+ const Predicate *ppred,
+ bool stable,
+ bool alloc)
+{
+ typedef RandomAccessIter<T> 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<X*, std::ptrdiff_t> 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 <class T, class Predicate>
+void test_sort (const std::size_t N,
+ const T*,
+ const Predicate *ppred,
+ bool stable,
+ bool alloc)
+{
+ rw_info (0, 0, 0,
+ "template <class %s%{?}, class %s%{;}> "
+ "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 <class T>
+void test_sort (const std::size_t N,
+ const T*,
+ bool stable,
+ bool alloc)
+{
+ test_sort (N, (T*)0, (Less<T>*)0, stable, alloc);
+
+ if (rw_opt_no_predicate) {
+ rw_note (0, __FILE__, __LINE__,
+ "std::%{?}stable_%{;}sort predicate test disabled",
+ stable);
+ }
+ else {
+ const Less<T> 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
