test for lib.alg.partitions

[Anton Pevtsov <an...@moscow.vdiweb.com>]

The attached file contains my attempt to update lib.alg.partiton and
lib.alg.stable_partiton tests and port them to new test driver.

I suspect a bug in the stable_partiton algorithm implementation.
Suppose that for all elements of an array the predicate is true.
The stable_partition should return "last" in this case.
But call of the stable_partiton on this array fails with the following
assertion:
    stdlib\tests\src\alg_test.cpp:135: __thiscall X::~X(void):
Assertion 'id_ && id_ <= id_gen_' failed.
In the debugger you can see that the id_ of the deleting X object is
equal to 0 (I suppose that this X is invalid), but the "this" looks
good.
What do you think about this issue?

I plan investigate this more deeply.
Current test version includes the tests on which stable_partiton fails
and these tests are marked using comments.

Also, there is another intresting thing with the stable_partition
algorithm.
Suppose that an array contains only one element. According to the
standard the complexity in this case should be equal to 0 swaps. Actually
there are 0 swaps, but there is 1 assignment. I guess this is not a bug
(the standard talks nothing about the assignments), but may be there are
unnecessary assignment operations in the stable_partitions
implementation.
What do you think about it?

With best wishes,
Anton Pevtsov

Re: test for lib.alg.partitions

[Martin Sebor <se...@roguewave.com>]

Anton Pevtsov wrote:
> The attached file contains my attempt to update lib.alg.partiton and
> lib.alg.stable_partiton tests and port them to new test driver.

I think we should rewrite the test and hardcode the initial and
partitioned sequences. I don't think we can sufficiently exercise
the interesting/corner cases by generating the sequence. Also, I
think we should be able to eliminate one of the two predicates.
It's sufficient to exercise the algorithm with just one so long
as we exhaustively verify all the requirements. Let me know if
this makes sense to you and/or if you have any questions.

> 
> I suspect a bug in the stable_partiton algorithm implementation.
> Suppose that for all elements of an array the predicate is true.
> The stable_partition should return "last" in this case.
> But call of the stable_partiton on this array fails with the following
> assertion:
>    stdlib\tests\src\alg_test.cpp:135: __thiscall X::~X(void):
> Assertion 'id_ && id_ <= id_gen_' failed.
> In the debugger you can see that the id_ of the deleting X object is
> equal to 0 (I suppose that this X is invalid), but the "this" looks
> good.

Yes, the id_ member is reset in the dtor to indicate that the
object has already been destroyed (no valid id_ is ever 0).

> What do you think about this issue?

It's certainly possible that there is a bug in the algorithm, but
I would be more inclined to suspect the test before the algorithm
just because you just made making non-trivial changes to it.

> 
> I plan investigate this more deeply.

A simple test case would be helpful.

> Current test version includes the tests on which stable_partiton fails
> and these tests are marked using comments.
> 
> Also, there is another intresting thing with the stable_partition
> algorithm.
> Suppose that an array contains only one element. According to the
> standard the complexity in this case should be equal to 0 swaps. Actually
> there are 0 swaps, but there is 1 assignment. I guess this is not a bug
> (the standard talks nothing about the assignments), but may be there are
> unnecessary assignment operations in the stable_partitions
> implementation.
> What do you think about it?

There is no reason to do anything if there's only one element in
the range, but if the standard allows it we don't need to go to
heroic measures eliminating it. That said, if it's an easy change
we should definitely do it.

A few more comments below...

> 
> With best wishes,
> Anton Pevtsov
> 
> 
> ------------------------------------------------------------------------
[...]
> template <class T>
> struct LessThanPredicate : ComparePredicateBase
> {
>     LessThanPredicate (const int value) : ComparePredicateBase (value) {}
> 
>     // return a type other than bool but one that is implicitly
>     // convertible to bool to detect incorrect assumptions
>     ConvertibleToBool operator() (const T &arg) {

Let's replace the type with the canned conv_to_bool type defined
in alg_test.h.

[...]
> // exercises std::partition() and std::stable_partition()
> template <class T, class Iterator, class Predicate>
> void test_partitions (const std::size_t line, const std::size_t N,

line should be int to match the type of the __LINE__ macro.

>                       const Iterator& it, const Predicate& pr, 
>                       const T* , int val, bool stable)
> {
>     _RWSTD_UNUSED(pr);
> 
>     const char* const itname = type_name (it, (T*)0);
>     const char* const fname = 
>         stable ? "stable_partition" : "partition";
>     const char* const funname = Predicate::name();
> 
>     rw_info (0, 0, 0,
>              "%s %s (%1$s, %1$s, %s)",
>              itname, fname, funname);
> 
>     // create an array of T 
>     T::gen_ = gen_seq;
>     T *buf = new T[N]; 
> 
>     for (std::size_t i = 0; i < N; ++i) {
> 
>         const Iterator first = make_iter (buf, buf, buf + i + 1, it);

The end pointer above should be (buf + i), not (buf + i + 1). (This is
true in general for all these tests. I corrected this in the others but
forgot to mention it.)

Martin