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: <438C7F83.1090802@moscow.vdiweb.com>
Date: Tue, 29 Nov 2005 19:19:15 +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: Re: [jira] Created: (STDCXX-72) [25.adjacent.find.cpp] predicate
 form of std::adjacent_find not exercised
References: <4D6A8407B7AC6F4D95B0E55C4E7C4C6202F31074@exmsk.moscow.vdiweb.com>
In-Reply-To: 
 <4D6A8407B7AC6F4D95B0E55C4E7C4C6202F31074@exmsk.moscow.vdiweb.com>
Content-Type: multipart/mixed;
 boundary="------------010706020209090505050208"

--------------010706020209090505050208
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

The attached file contains my attempt to fix this problem - I added test
for the predicate version of adjacent_find.


With best wishes,
Anton Pevtsov

>-----Original Message-----
>From: Martin Sebor (JIRA) [mailto:jira@apache.org] 
>Sent: Friday, November 25, 2005 22:18
>To: stdcxx-dev@incubator.apache.org
>Subject: [jira] Created: (STDCXX-72) [25.adjacent.find.cpp] predicate
>form of std::adjacent_find not exercised
>
>
>[25.adjacent.find.cpp] predicate form of std::adjacent_find not
>exercised
>------------------------------------------------------------------------
>-
>
>         Key: STDCXX-72
>         URL: http://issues.apache.org/jira/browse/STDCXX-72
>     Project: STDCXX
>        Type: Improvement
>  Components: Tests  
>    Versions: 4.1.2    
> Environment: all
>    Reporter: Martin Sebor
>    Priority: Critical
>     Fix For: 4.1.3
>
>
>The 25.adjacent.find.cpp test doesn't exercise the predicate form of the
>algorithm. See http://svn.apache.org/viewcvs.cgi?rev=345300&view=rev.
>
>  
>


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

/***************************************************************************
 *
 * adjacent_find.cpp - test exercising 25.1.5 [lib.alg.adjacent.find]
 *
 * $Id: 25.adjacent.find.cpp 349024 2005-11-25 20:38:23Z sebor $
 *
 ***************************************************************************
 *
 * 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 adjacent_find
#include <functional>  // for equal_to
#include <cstddef>     // for size_t

#include <alg_test.h>
#include <driver.h>

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

// used to initialize an array of objects of type X
static const char *xinit_begin;

int xinit ()
{
    typedef unsigned char UChar;

    static const char *cur = 0;

    if (!cur || !*cur)
        cur = xinit_begin;

    return UChar (*cur++);
}


// exercises std::adjacent_find()
template <class ForwardIterator, class T>
void do_test (int         line,     // line number of test case
              const char *src,      // source sequence
              std::size_t resoff,   // offset of result
              ForwardIterator    dummy_iter,
              const T*,
              const char* predicate)
{
    static const char* const itname = type_name (dummy_iter, (T*)0);

    const std::size_t nsrc = std::strlen (src);

    if (std::size_t (-1) == resoff)
        resoff = nsrc;

    // have the X default ctor initialize objects from `src'
    xinit_begin = src;
    X::gen_     = xinit;

    X* const xsrc = new X [nsrc];

    const ForwardIterator first =
        make_iter (xsrc, xsrc, xsrc + nsrc, dummy_iter);

    const ForwardIterator last =
        make_iter (xsrc + nsrc, xsrc, xsrc + nsrc, dummy_iter);

    // compute the number of invocations of the predicate
    std::size_t n_total_pred = X::n_total_op_eq_;

    ForwardIterator res;

    if (predicate)
        res = std::adjacent_find (first, last, std::equal_to<X>());
    else
        res = std::adjacent_find (first, last);

    // silence a bogus EDG eccp remark #550-D:
    // variable "res" was set but never used
    _RWSTD_UNUSED (res);

    n_total_pred = X::n_total_op_eq_ - n_total_pred;

    // verify that the returned iterator is set as expected
    int success = res.cur_ == first.cur_ + resoff;
    rw_assert (success, 0, line, 
               "line %d: adjacent_find<%s>(it = \"%s\", ...)"
               " == (it + %zu), got (it + %td)",
               __LINE__, itname, src,
               resoff, res.cur_ - first.cur_);

    // verify the number of applications of the predicate (lwg issue 240):
    // Complexity: For a nonempty range, exactly
    //             min((i - first) + 1, (last - first) - 1)
    // applications of the corresponding predicate, where i is
    // adjacent_find's return value.

    // compute the expected number of invocations of the predicate
    std::size_t n_expect_pred = 0;

    if (nsrc) {
        // test iterators are guaranteed to be in range
        _RWSTD_ASSERT (first.cur_ <= res.cur_ && res.cur_ <= last.cur_);

        n_expect_pred = std::size_t (res.cur_ - first.cur_) + 1;
        const std::size_t tmp = std::size_t (last.cur_ - first.cur_) - 1;
        if (tmp < n_expect_pred)
            n_expect_pred = tmp;
    }

    success = std::size_t (n_expect_pred) == n_total_pred;
    rw_assert (success, 0, line, 
               "line %d: adjacent_find<%s>(\"%s\", ...) "
               "invoked %s %zu times, expected %td",
               __LINE__, itname, src,
               predicate ? predicate : "operator==()", 
               n_total_pred, n_expect_pred);
}

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

template <class ForwardIterator, class T>
void run_tests (ForwardIterator dummy_iter, const T*, const char* predicate)
{
    static const char* const itname = type_name (dummy_iter, (T*)0);

    rw_info (0, 0, 0, "std::adjacent_find (%s, %1$s%{?}, %s%{;})", 
             itname, 0 != predicate, predicate);
    
#define TEST(src, off) \
    do_test (__LINE__, src, std::size_t (off), dummy_iter, (X*)0, predicate)

    //    +------------------ subject sequence
    //    |               +-- offset of returned iterator,
    //    |               |   -1 denotes the end of sequence
    //    v               v
    TEST ("",            -1);
    TEST ("a",           -1);
    TEST ("ab",          -1);
    TEST ("abc",         -1);
    TEST ("abcd",        -1);
    TEST ("abcde",       -1);
    TEST ("abcdef",      -1);
    TEST ("abcdefg",     -1);
    TEST ("abcdefgh",    -1);
    TEST ("abcdefghi",   -1);
    TEST ("abcdefghij",  -1);
    TEST ("abcdefghijk", -1);

    TEST ("aabcdefghij",  0);
    TEST ("abbcdefghij",  1);
    TEST ("abccdefghij",  2);
    TEST ("abcddefghij",  3);
    TEST ("abcdeefghij",  4);
    TEST ("abcdeffghij",  5);
    TEST ("abcdefgghij",  6);
    TEST ("abcdefghhij",  7);
    TEST ("abcdefghiij",  8);
    TEST ("abcdefghijj",  9);

    TEST ("aaabcdefghi",  0);
    TEST ("abbbcdefghi",  1);
    TEST ("abcccdefghi",  2);
    TEST ("abcdddefghi",  3);
    TEST ("abcdeeefghi",  4);
    TEST ("abcdefffghi",  5);
    TEST ("abcdefggghi",  6);
    TEST ("abcdefghhhi",  7);
    TEST ("abcdefghiii",  8);
    TEST ("abcdefghijjj", 9);

}

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

/* 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
/* extern */ int rw_opt_no_predicate;    // --no-Predicate

static 
void test_adjacent_find (const char* predicate)
{
    rw_info (0, 0, 0, 
             "template <class %s> "
             "%1$s std::adjacent_find (%1$s, %1$s%{?}, %s%{;})",
             "ForwardIterator", 0 != predicate, predicate);

    if (rw_opt_no_fwd_iter) {
        rw_note (0, __FILE__, __LINE__, "ForwardIterator test disabled");
    }
    else {
        run_tests (FwdIter<X>(), (X*)0, predicate);
    }

    if (rw_opt_no_bidir_iter) {
        rw_note (0, __FILE__, __LINE__, "BidirectionalIterator test disabled");
    }
    else {
        run_tests (BidirIter<X>(), (X*)0, predicate);
    }

    if (rw_opt_no_rnd_iter) {
        rw_note (0, __FILE__, __LINE__, "RandomAccessIterator test disabled");
    }
    else {
        run_tests (RandomAccessIter<X>(), (X*)0, predicate);
    }
}

static int
run_test (int, char*[])
{
    test_adjacent_find(0);

    if (rw_opt_no_predicate) {
        rw_note (0, __FILE__, __LINE__, "Predicate test disabled");
    }
    else {
        test_adjacent_find ("std::equal_to<X>");
    }
                
    return 0;
}

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

int main (int argc, char *argv[])
{
    return rw_test (argc, argv, __FILE__,
                    "lib.alg.adjacent.find",
                    0 /* no comment */, run_test,
                    "|-no-ForwardIterator#"
                    "|-no-BidirectionalIterator#"
                    "|-no-RandomAccessIterator#"
                    "|-no-Predicate",
                    &rw_opt_no_fwd_iter,
                    &rw_opt_no_bidir_iter,
                    &rw_opt_no_rnd_iter,
                    &rw_opt_no_predicate);
}

--------------010706020209090505050208--