Return-Path: 
 <stdcxx-dev-return-825-apmail-incubator-stdcxx-dev-archive=incubator.apache.org@incubator.apache.org>
Delivered-To: apmail-incubator-stdcxx-dev-archive@www.apache.org
Received: (qmail 77605 invoked from network); 3 Feb 2006 16:11:49 -0000
Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199)
  by minotaur.apache.org with SMTP; 3 Feb 2006 16:11:49 -0000
Received: (qmail 83765 invoked by uid 500); 3 Feb 2006 16:11:49 -0000
Delivered-To: apmail-incubator-stdcxx-dev-archive@incubator.apache.org
Received: (qmail 83740 invoked by uid 500); 3 Feb 2006 16:11:48 -0000
Mailing-List: contact stdcxx-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
List-Help: <mailto:stdcxx-dev-help@incubator.apache.org>
List-Unsubscribe: <mailto:stdcxx-dev-unsubscribe@incubator.apache.org>
List-Post: <mailto:stdcxx-dev@incubator.apache.org>
List-Id: <stdcxx-dev.incubator.apache.org>
Reply-To: stdcxx-dev@incubator.apache.org
Delivered-To: mailing list stdcxx-dev@incubator.apache.org
Received: (qmail 83721 invoked by uid 99); 3 Feb 2006 16:11:48 -0000
Received: from asf.osuosl.org (HELO asf.osuosl.org) (140.211.166.49)
    by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 03 Feb 2006 08:11:48 -0800
X-ASF-Spam-Status: No, hits=-0.0 required=10.0
	tests=SPF_PASS
X-Spam-Check-By: apache.org
Received-SPF: pass (asf.osuosl.org: domain of AntonP@moscow.vdiweb.com
 designates 195.210.189.132 as permitted sender)
Received: from [195.210.189.132] (HELO exmsk.moscow.vdiweb.com)
 (195.210.189.132)
    by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 03 Feb 2006 08:11:46 -0800
Received: from [10.11.0.166] ([10.11.0.166]) by exmsk.moscow.vdiweb.com with
 Microsoft SMTPSVC(6.0.3790.1830);
	 Fri, 3 Feb 2006 19:11:22 +0300
Message-ID: <43E380A2.6090201@moscow.vdiweb.com>
Date: Fri, 03 Feb 2006 19:11:14 +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
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: stdcxx-dev@incubator.apache.org
Subject: test for lib.binary.search
Content-Type: multipart/mixed;
 boundary="------------090607040504050504020001"
X-OriginalArrivalTime: 03 Feb 2006 16:11:22.0712 (UTC)
 FILETIME=[79BF1580:01C628DC]
X-Virus-Checked: Checked by ClamAV on apache.org
X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N

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

The attached file contains the test for the lib.binary.search algorithm.

Here I use new compare functor instead of binary_predicate because
the following code fails to compile:

template
bool
std::binary_search (int*, int*,
                    const int&,
                    binary_predicate<int >);

with error:
stdlib\\include\algorithm(1036): error C2248:
'conv_to_bool::operator`!'' : cannot access private member declared in
class 'conv_to_bool'

The binary_search accepts Compare (not BinaryPredicate) functor. The
standard (25.3, p2) says that Compare should return true or false. At
the same time, it says (25, p8) that BinaryPredicate should return value
testable as true. The difference results in the error above.
It looks like we shouldn't use binary_predicate to test this algorithm
(as well as lower.bound, upper.bound, equal.range there the difference
between compare and binary_predicate is not significant). So it would be
useful to add compare functor to the alg_test.h header. Or it is
possible to modify the binary_search algorithm to not use the
"! operator()".
What do you think about it?

And here is another small question:
may be it would be useful to merge tests for lower.bound, upper.bound,
equal.range and binary.search into one .cpp file (tests for these
algorithms are very similar)?


Thanks,
Anton Pevtsov

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

/***************************************************************************
 *
 * 25.upper.bound.cpp - test exercising 25.3.3.2 [lib.upper.bound]
 *
 * $Id: 25.upper.bound.cpp 360601 2006-01-02 00:19:08Z 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 <rw/_config.h>

#if defined (__IBMCPP__) && !defined (_RWSTD_NO_IMPLICIT_INCLUSION)
  // disable implicit inclusion to work around a limitation
  // of IBM VisualAge 5.0 (see PR #26959)
#  define _RWSTD_NO_IMPLICIT_INCLUSION 
#endif

#include <algorithm>    // for binary_search()
#include <cstring>      // for strlen()

#include <alg_test.h>   // for iterators
#include <driver.h>     // for rw_test(), ...

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

// meets requirements listed at 25.3, p2
template <class T>
struct compare {
    bool operator() (const T &a, const T &b) const {
        _RWSTD_UNUSED(a);
        _RWSTD_UNUSED(b);
        return true;
    }
};

_RWSTD_NAMESPACE (std) { 

#ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION

template
bool
binary_search (FwdIter<lt_comp<assign<base<cpy_ctor> > > >, 
               FwdIter<lt_comp<assign<base<cpy_ctor> > > >,
               const lt_comp<assign<base<cpy_ctor> > >&);

template
bool
binary_search (FwdIter<lt_comp<assign<base<cpy_ctor> > > >, 
               FwdIter<lt_comp<assign<base<cpy_ctor> > > >,
               const lt_comp<assign<base<cpy_ctor> > >&,
               compare<lt_comp<assign<base<cpy_ctor> > > >);

#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION

}   // namespace std

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

// distinct and not Less-Than-Comparable with class T (except as
// defined below) to detect unwarranted assumptions made by the
// implementation of the algorithms
struct Y
{
    X xval_;

    // not Default-Constructible
    Y (int /* dummy */, int /*dummy */): xval_ () { }

    // CopyConstructible
    Y (const Y &rhs): xval_ (rhs.xval_) { }

private:

    void operator=(Y&);   // not Assignable
};


inline bool
operator< (const X &lhs, const Y &rhs)
{
    return lhs < rhs.xval_;
}

inline bool
operator< (const Y &lhs, const X &rhs)
{
    return lhs.xval_ < rhs;
}

// predicate used as the Compare argument to upper_bound()
struct LessThan
{
    static std::size_t funcalls_;

    LessThan (int /* dummy */, int /* dummy */) {
        funcalls_ = 0;
    }

    // return a type other than bool but one that is implicitly
    // convertible to bool to detect incorrect assumptions
    bool operator() (const X &lhs, const Y &rhs) {
        ++funcalls_;
        return lhs < rhs.xval_;
    }

    bool operator() (const Y &lhs, const X &rhs) {
        ++funcalls_;
        return lhs.xval_ < rhs;
    }

private:
    void operator= (LessThan&);   // not assignable
};

std::size_t LessThan::funcalls_;

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

template <class T, class ForwardIterator>
void test_binary_search (int                    line,
                         const char            *src_str,
                         char                   val_char,
                         bool                   exp_res,
                         std::size_t            ncomp,
                         const ForwardIterator &it,
                         const T*,
                         bool                   predicate)
{
    RW_ASSERT (0 != src_str);

    const char* const tname   = "X";
    const char* const itname  = type_name (it, (T*)0);
    const char* const funname = predicate ? "LessThan" : "operator<()";

    const std::size_t nsrc = std::strlen (src_str);
    T* const xsrc = T::from_char (src_str, nsrc);
    T* const xsrc_end = xsrc + nsrc;

    // construct the source range to pass to the algorithm
    const ForwardIterator first = make_iter (xsrc, xsrc, xsrc_end, it);
    const ForwardIterator last  = make_iter (xsrc_end, xsrc, xsrc_end, it);

    // construct the object to pass to the algorithm
    // the type of the object is distinct from the iterator's value_type
    // to detect unwarranted assumptions made by the implementation
    Y value (0, 0 /* dummy arguments */);
    value.xval_.val_ = val_char;

    // construct the Compare function object to pass to the algorithm
    // when `predicate' is true
    const LessThan comp (0, 0 /* dummy arguments */);

    // reset the counter of invocations of T::operator<()
    T::n_total_op_lt_ = 0;

    // invoke the appropriate form of the algorithm, storing
    // the resturned value
    const bool result = predicate
        ? std::binary_search (first, last, value, comp)
        : std::binary_search (first, last, value);

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

    rw_assert (result == exp_res, 0, line,
               "binary_search <%s, const %s&%{?}, %s%{;}> (\"%s\", %#c, ...) "
               "expected %s, got %s",
               itname, tname, predicate, funname, src_str, val_char,
               exp_res ? "true" : "false", result ? "true" : "false");

    // verify complexity
    const std::size_t n_ops = predicate
        ? LessThan::funcalls_ : T::n_total_op_lt_;

    rw_assert (n_ops <= ncomp, 0, line,
               "binary_search <%s, const %s&%{?}, %s%{;}> (\"%s\", %#c, ...) "
               "complexity: invoked %4$s at most %zu times, got %zu",
               itname, tname, predicate, funname, src_str, val_char,
               ncomp, n_ops);

    delete[] xsrc;
}

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

template <class T, class ForwardIterator>
void test_binary_search (const ForwardIterator &it,
                         const T*,
                         bool                   predicate)
{
    const char* const itname = type_name (it, (T*)0);
    const char* const funname = predicate ? "LessThan" : "operator<()";

    rw_info (0, 0, 0, "std::binary_search (%s, %1$s, const X&%{?}, %s%{;})",
             itname, predicate, funname);

#define TEST(str, val, res, comp) \
    test_binary_search (__LINE__, str, val, res, std::size_t (comp),       \
                        it, (T*)0, predicate)

    //    +--------------- source sequence
    //    |     +--------- value argument
    //    |     |   +----- expected result: true/false
    //    |     |   |      +-- complexity: at most (log(last - first) + 2)
    //    |     |   |      |   comparisons (or applications of the predicate)
    //    |     |   |      |
    //    V     V   V      V
    TEST ("",  'a', false, 0);
    TEST ("a", 'a', true,  2);
    TEST ("a", 'b', false, 2);
    TEST ("b", 'a', false, 2);

    TEST ("aa", 'a', true,  3);
    TEST ("ab", 'a', true,  3);
    TEST ("ab", 'b', true,  3);
    TEST ("bb", 'a', false, 3);

    TEST ("abcdefghij", 'a', true,  6);
    TEST ("abcdefghij", 'c', true,  6);
    TEST ("abcdefghij", 'f', true,  6);
    TEST ("abcdefghij", 'h', true,  6);
    TEST ("abcdefghij", 'j', true,  6);
    TEST ("aacceeggii", 'c', true,  6);
    TEST ("aacceeggii", 'g', true,  6);
    TEST ("aacceeggii", 'b', false, 6);
    TEST ("aacceeggii", 'f', false, 6);
    TEST ("aacceeggii", 'j', false, 6);
    TEST ("cccceeggii", 'a', false, 6);
}

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

/* extern */ int rw_opt_no_predicate;            // --no-predicate
/* 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>
void test_binary_search (const T*,
                         bool predicate)
{
    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);

    rw_info (0, 0, 0, "template <class %s, class %s%{?}, class %s%{;}> "
             "bool std::binary_search (%1$s, %1$s, const %2$s&%{?}, %s%{;})",
             "ForwardIterator", "X", predicate, "Compare", predicate,
             "Compare");

    if (rw_opt_no_fwd_iter) {
        rw_note (0, 0, 0, "ForwardIterator test disabled");
    }
    else {
        test_binary_search (fwd_iter, (T*)0, predicate);
    }

    if (rw_opt_no_bidir_iter) {
        rw_note (0, 0, 0, "BidirectionalIterator test disabled");
    }
    else {
        test_binary_search (bidir_iter, (T*)0, predicate);
    }

    if (rw_opt_no_fwd_iter) {
        rw_note (0, 0, 0, "RandomAccessIterator test disabled");
    }
    else {
        test_binary_search (rand_iter, (T*)0, predicate);
    }
}

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

static int
run_test (int, char*[])
{
    test_binary_search ((X*)0, false);

    if (rw_opt_no_predicate) {
        rw_note (0, __FILE__, __LINE__,
                 "test of the Predicate form of std::binary_search disabled");
    }
    else {
        test_binary_search ((X*)0, true);
    }

    return 0;
}

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

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

--------------090607040504050504020001--