Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: stdcxx-dev@incubator.apache.org
Received-SPF: pass (asf.osuosl.org: domain of AntonP@moscow.vdiweb.com
 designates 195.210.189.132 as permitted sender)
Message-ID: <43D8F942.9080006@moscow.vdiweb.com>
Date: Thu, 26 Jan 2006 19:30:58 +0300
From: Anton Pevtsov <antonp@moscow.vdiweb.com>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US;
 rv:1.7) Gecko/20040514
MIME-Version: 1.0
To: stdcxx-dev@incubator.apache.org
Subject: test for lib.alg.partitions
Content-Type: multipart/mixed;
 boundary="------------070805050005090802070603"

--------------070805050005090802070603
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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

--------------070805050005090802070603
Content-Type: text/plain;
 name="25.partitions.cpp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="25.partitions.cpp"

/***************************************************************************
 *
 * partitions.cpp - test exercising 25.2.12 [lib.alg.partitions]
 *
 * $Id: //stdlib/dev/tests/stdlib/algorithm/partitions.cpp#18 $
 *
 ***************************************************************************
 *
 * 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 partition, stable_partition
#include <cstddef>      // for 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
BidirIter<assign<base<cpy_ctor> > >
partition (BidirIter<assign<base<cpy_ctor> > >,
           BidirIter<assign<base<cpy_ctor> > >,
           predicate<assign<base<cpy_ctor> > >);

template
BidirIter<assign<base<cpy_ctor> > >
stable_partition (BidirIter<assign<base<cpy_ctor> > >,
                  BidirIter<assign<base<cpy_ctor> > >,
                  predicate<assign<base<cpy_ctor> > >);

#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION

}   // namespace std

/**************************************************************************/

struct ComparePredicateBase
{
    static std::size_t funcalls_;

    ComparePredicateBase (const int value) : value_(value) {
        funcalls_ = 0;
    }

    class ConvertibleToBool {
        bool result_;
    public:
        ConvertibleToBool (bool res): result_ (res) { /* empty */ }
        operator bool() const { return result_; }
    };

    const int value_;
};

std::size_t ComparePredicateBase::funcalls_;

template <class T>
struct GreaterThanPredicate : ComparePredicateBase
{
    GreaterThanPredicate (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) {
        ++funcalls_;
        return ConvertibleToBool (arg.val_ > value_);
    }

    bool isLess () { 
        return false; 
    }

    static const char* name () { return "GreaterThanPredicate"; }

private:
    void operator= (GreaterThanPredicate&);
};

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) {
        ++funcalls_;
        return ConvertibleToBool (arg.val_ < value_);
    }

    bool isLess () { 
        return true; 
    }

    static const char* name () { return "LessThanPredicate"; }

private:
    void operator= (LessThanPredicate&);
};

/**************************************************************************/

// 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,
                      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);
        const Iterator last = make_iter (buf + i + 1, buf, buf + i + 1, it);

        const std::size_t last_n_op_assign = T::n_total_op_assign_;

        const int value = val != 0 ? val : buf [i / 2].val_;
        Predicate pred(value);
        bool less = pred.isLess();

        const Iterator res = 
            stable ? std::stable_partition (first, last, pred) 
                   : std::partition (first, last, pred);

        // check that the returned iterator is valid and it is safe
        // to use it to check the algorithm results
        bool success = first.cur_ <= res.cur_ && res.cur_ <= last.cur_;
        rw_assert (success, 0, line,
                   "line %d: std::%s <%s, %s>(): returned iterator it "
                   "is invalid: got first + %td, expected "
                   "first <= it <= first + %zu",
                   __LINE__, fname, itname, funname, 
                   res.cur_ - first.cur_, i + 1);

        // check 25.2.12, p2 & p5
        // "left" part of the array there the predicate should be true
        int j = 0;
        for ( ; j < res.cur_ - first.cur_; j++) {
            success = 
                less ? buf[j].val_ < value : buf[j].val_ > value;
            if (!success)
                break;
        }

        rw_assert (success, 0, line,
                   "line %d: std::%s <%s, %s>(): %d %s %d at %zu",
                   __LINE__, fname, itname, funname, buf[j].val_, 
                   less ? "!<" : "!>", value, j + 1);

        if (!success)
            break;

        // "right" part of the array there the predicate should be false
        for ( ; j < last.cur_ - first.cur_; j++) {
            success = 
                less ? buf[j].val_ >= value : buf[j].val_ <= value;
            if (!success)
                break;
        }

        rw_assert (success, 0, line,
                   "line %d: std::%s <%s, %s>(): %d %s %d at %zu",
                   __LINE__, fname, itname, funname, buf[j].val_, 
                   less ? "!>=" : "!<=", value, j + 1);

        if (!success)
            break;

        // check the complexity, 25.2.12 p3 & p6
        // first check number of swaps, 2 assignments per swap

        // add 1 in case of stable_partition to avoid the assertion failing
        // when i == 0 (only one element presents in the sequence)
        // is this one extra assignment an algorithm bug??
        // the standard talks about swaps only, not about assignments
        // and there are 0 swaps (1 swap equals 2 assignments) in this case...
        std::size_t exp_assigns = 
            stable ? 2 * (i + 1) * ::ilog2 (i + 1) + 1
                   : i + 1;
        std::size_t op_assigns = T::n_total_op_assign_ - last_n_op_assign;

        success = op_assigns <= exp_assigns;
        rw_assert (success, 0, line,
                   "line %d: std::%s <%s, %s>(): complexity: "
                   "got %zu assignments, expected no more than %zu",
                    __LINE__, fname, itname, funname, 
                    op_assigns, exp_assigns);

        // second check the number of the predicate calls
        success = Predicate::funcalls_ == i + 1;
        rw_assert (success, 0, line,
                   "line %d: std::%s <%s, %s>(): complexity: "
                   "got %zu applications of the predicate, "
                   "expected no more than %zu",
                    __LINE__, fname, itname, funname, 
                    Predicate::funcalls_, i + 1);

        if (!success)
            break;

        // check the stable_partition is really stable 25.2.12, p5
        if (stable) {
            for (j = 1; j < last.cur_ - first.cur_; j++) {
                if (j == res.cur_ - first.cur_)
                    continue;

                success = buf[j - 1].val_ < buf[j].val_;
                if (!success)
                    break;
            }

            rw_assert (success, 0, line,
                       "line %d: std::%s <%s, %s>(): realtive order "
                       "broken at %zu, %d !< %d",
                        __LINE__, fname, itname, funname, j, 
                        buf[j - 1].val_, buf[j].val_);
        }

        // reinitialize the buffer for the next test
        for (std::size_t t = 0; t != i + 1; ++t)
            (buf + t)->val_ = t + 1;
    }

    delete[] buf;
}


template <class T, class Iterator>
void test_partitions (const std::size_t N, const Iterator& it, 
                      const T* , bool stable)
{
    // test partitions algorithms against different predicates
    // and different "middle" element

    // some sequence
    test_partitions (__LINE__, N, it, GreaterThanPredicate<T>(0), 
                    (T*) 0, 0, stable);

    // there is nothing to do here, all elements match the predicate
    // stable_partition fails on this test!
    test_partitions (__LINE__, N, it, GreaterThanPredicate<T>(0), 
                    (T*) 0, -1, stable);

    // there is nothing to do here, all elements don't match the predicate
    test_partitions (__LINE__, N, it, GreaterThanPredicate<T>(0), 
                    (T*) 0, _RWSTD_INT_MAX, stable);

    // some sequence
    test_partitions (__LINE__, N, it, LessThanPredicate<T>(0), 
                    (T*) 0, 0, stable);

    // there is nothing to do here, all elements don't match the predicate
    test_partitions (__LINE__, N, it, LessThanPredicate<T>(0), 
                    (T*) 0, -1, stable);

    // there is nothing to do here, all elements match the predicate
    // stable_partition fails on this test!
    test_partitions (__LINE__, N, it, LessThanPredicate<T>(0), 
                    (T*) 0, _RWSTD_INT_MAX, stable);
}

/**************************************************************************/

/* extern */ int rw_opt_nloops = 32;            // --nloops=#
/* extern */ int rw_opt_no_partition;           // --no-partition
/* extern */ int rw_opt_no_stable_partition;    // --no-stable_partition
/* extern */ int rw_opt_no_bidir_iter;          // --no-BidirectionalIterator
/* extern */ int rw_opt_no_rnd_iter;            // --no-RandomAccessIterator


template <class T>
void test_partitions (const std::size_t N, const T* , bool stable)
{
    rw_info (0, 0, 0, 
             "template <class %s, class %s> %1$s %s (%1$s, %1$s, %2$s)",
             "BidirectionalIterator", "Predicate", 
             stable ? "stable_partition" : "partition");

    if (rw_opt_no_bidir_iter) {
        rw_note (0, __FILE__, __LINE__, "BidirectionalIterator test disabled");
    }
    else {
        test_partitions (N, BidirIter<T>(), (T*) 0, stable); 
    }

    if (rw_opt_no_rnd_iter) {
        rw_note (0, __FILE__, __LINE__, "RandomAccessIterator test disabled");
    }
    else {
        test_partitions (N, RandomAccessIter<T>(), (T*) 0, stable);  
    }
}

static int run_test (int, char*[])
{
    const std::size_t N = std::size_t (rw_opt_nloops);

    if (rw_opt_no_partition) {
        rw_note (0, __FILE__, __LINE__, "std::partition test disabled");
    }
    else {
        test_partitions (N, (X*) 0, false);
    }

    if (rw_opt_no_stable_partition) {
        rw_note (0, __FILE__, __LINE__, 
                 "std::stable_partition test disabled");
    }
    else {
        test_partitions (N, (X*) 0, true);
    }

    return 0;
}

/**************************************************************************/

int main (int argc, char *argv[])
{
    return rw_test (argc, argv, __FILE__,
                    "lib.alg.partitions",
                    0 /* no comment */, run_test,
                    "|-nloops#0 "   // must be non-negative
                    "|-no-partition# "
                    "|-no-stable_partition# "
                    "|-no-BidirectionalIterator# "
                    "|-no-RandomAccessIterator", 
                    &rw_opt_nloops,
                    &rw_opt_no_partition,
                    &rw_opt_no_stable_partition,
                    &rw_opt_no_bidir_iter,
                    &rw_opt_no_rnd_iter);
}

--------------070805050005090802070603--