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:[EMAIL PROTECTED]
Sent: Tuesday, February 07, 2006 05:43
To: [email protected]
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 <cassert> // for assert()
#include <cstddef> // for ptrdiff_t, size_t
#include <algorithm> // for stable_sort()
#include <memory> // for get_temporary_buffer()
#include <utility> // for pair
#include <rw_new.h> // 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<int*, std::ptrdiff_t> tmpbuf =
std::get_temporary_buffer<int>(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);
}
/***************************************************************************
*
* 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
#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 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;
}
/**************************************************************************/
/* 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::%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 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);
}
}
/**************************************************************************/
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);
}
/***************************************************************************
*
* 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 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 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 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_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::%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_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);
}
