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.
Here I check the algotithms correctness using the hardcoded sequences
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.
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.
With best wishes,
Anton Pevtsov
-----Original Message-----
From: Martin Sebor [mailto:[EMAIL PROTECTED]
Sent: Wednesday, February 01, 2006 05:04
To: [email protected]
Subject: Re: test for lib.alg.sort
Anton Pevtsov wrote:
>> I am porting tests for lib.alg.sort algorithms (sort, stable_sort,
>> partial_sort and partial_copy_sort) and I have several questions about
>> these tests:
>>
>> 1. Current test version contains code for some tracing:
>> ...
>> if (!(i % 20))
>> TRACE
>> ("+------+------+------+------+------+------+------+\n"
>> "| N | COMP | COPY |N lg N| X | max X|
min
>> X|\n"
>>
>> "+======+======+======+======+======+======+======+\n");
>>
>> // # | comp | assign | exp. complexity | X | max X |
>> TRACE ("|%6d|%6d|%6d|%6d|%6.2f|%6.2f|%6.2f|\n",
>> i + 1, ops, cpy, cmplx, x, x_max, x_min); ...
>>
>> Do we need to keep this trace in new version ?
Feel free to disable it but please leave the code in so that it can be
enabled if need be.
>>
>> 2. Current test version doesn't exercise stable_sort, partial_sort and
>> partial_copy_sort at all. I'll add tests for these algorithms.
That'll be great!
>> As a part
>> of them I'll need to verify their complexity. For the sort algorithm I
>> found the upper estimate value in the code (3.33 * N * log N). Is this
>> the correct upper estimate value for stable_sort, partial_sort and
>> partial_sort_copy too?
Not really, it's just something that happened to work for the test as
well as our implementation. I never did like it. I don't think we can
use a general formula to test the complexity.
>> The standard talks about O(N * log M), M <= N
>> for these algorithms, but this is not enough for strict tests.
I see O(N * log N) for sort() but I don't see how we can reliably test
the complexity requirements. The original sort implementation used the
quicksort algorithm which has quadratic worst case behavior. The only
semi-reliable way to verify the implementation performs in log time on
average is to do a whole bunch of runs on random data and check we're in
the ballpark.
We've been using the introsort algorithm which has a guaranteed
logarithmic complexity but even with this algorithm the only way to test
the complexity is over a large number of runs.
>> (Of
>> course, I suppose here that stable_sort uses additional memory).
>>
>> 3. I think it is necessary to verify the complexity of stable_sort in
>> case then no additional memory is available. Is it possible to disable
>> the memory allocation in this algorithm? (I think that the using of
>> huge arrays is not a right way to do it).
AFAIK, the algorithm uses the std::get_temporary_buffer() function
template. While it's not guaranteed, in our implementation, each
specialization of the template manages just one buffer (or maybe all of
them share the same buffer, either way). So if you grab the buffer by
calling std::get_temporary_buffer() before invoking the algorithm you
should prevent it from using it too and force get_temporary_buffer to
dynamically allocate the memory requested by the algorithm. 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.
You might want to look at rw_new.h and new.cpp to see if you could
exploit the replacement operator new for this purpose. Be aware that the
replacement operator new doesn't work across shared library boundaries
on AIX and Windows.
>>
>> 4. I assume to use random-generated sequences for these algorithms
>> tests. Of course, it is possible to use hardcoded sequences like it is
>> done in almost all other tests, but this will result in difficulties
>> with the complexity tests (to test the complexity correctly we are
>> needed in large sequences). May be, it would be good to verify the
>> algorithms correctness on the hardcoded sequences and use
>> random-generated arrays to verify the complexity. What do you think
>> about it?
That sounds like a very reasonable approach.
Martin
/***************************************************************************
*
* 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 <algorithm> // for sort, stable_sort, partitial_sort,
// partital_sort_copy
#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> > > >);
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 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<class T> std::size_t StrictWeakLess<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)
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;
}
/**************************************************************************/
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;
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_sort; // --no-sort
/* extern */ int rw_opt_no_stable_sort; // --no-stable_sort
/* 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 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::%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 <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%{;}, %4$s%{?}, %2$s, "
"%2$s, %{;}%{?}, %s%{;})",
copy, outname, fname, itname, !copy, 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%{;}, %4$s%{?}, %2$s, "
"%2$s, %{;}%{?}, %s%{;}) : complexity test disabled",
copy, outname, fname, itname, !copy, copy, ppred, funname);
}
else {
rw_info (0, 0, 0,
"%{?}%s %{;}std::%s (%s%{?}, %4$s%{;}, %4$s%{?}, %2$s, "
"%2$s, %{;}%{?}, %s%{;}): complexity test",
copy, outname, fname, itname, !copy, 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>
void test_sort (const std::size_t N,
const T* ,
bool stable,
bool alloc)
{
test_sort (N, (T*)0, (StrictWeakLess<T>*)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<T> pred(0, 0);
test_sort (N, (T*)0, &pred, stable, alloc);
}
}
/**************************************************************************/
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::%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<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, (StrictWeakLess<T>*)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<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_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);
}
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-sort# "
"|-no-stable_sort# "
"|-no-partial_sort# "
"|-no-partial_sort_copy# "
"|-no-InputIterator# "
"|-no-ForwardIterator# "
"|-no-BidirectionalIterator# "
"|-no-RandomAccessIterator# "
"|-no-predicate",
&rw_opt_nloops,
&rw_opt_no_sort,
&rw_opt_no_stable_sort,
&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);
}
