25.find.cpp

Go to the documentation of this file.

 
#include <algorithm>    // for find()
#include <cstring>      // for size_t, strlen()
 
#include <rw_alg_test.h>   
#include <rw_value.h>      // for UserClass
#include <rw_driver.h>     // for rw_test()
 
 
_RWSTD_NAMESPACE (std) { 
 
#ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION
 
template
InputIter<eq_comp<base<> > > 
find (InputIter<eq_comp<base<> > >, InputIter<eq_comp<base<> > >, 
      const eq_comp<base<> >&);
 
template
InputIter<eq_comp<base<> > > 
find_if (InputIter<eq_comp<base<> > >, InputIter<eq_comp<base<> > >, 
         predicate<eq_comp<base<> > >);
 
#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION
 
}   // namespace std
 
 
 
template <class T>
struct Predicate
{
    static std::size_t funcalls_;
 
    Predicate (const T &val, int /* dummy */)
        : val_ (val) {
        funcalls_ = 0;
    }
 
    class ConvertibleToBool {
        bool result_;
    public:
        ConvertibleToBool (bool res): result_ (res) { /* empty */ }
        operator bool() const { return result_; }
    };
 
    // return a type other than bool but one that is implicitly
    // convertible to bool to detect incorrect assumptions
    ConvertibleToBool operator() (T obj) /* not const */ {
        ++funcalls_;
        return ConvertibleToBool (obj == val_);
    }
 
private:
    void operator= (Predicate&);
    const T &val_;
};
 
template <class T>
std::size_t Predicate<T>::funcalls_;
 
 
template <class InputIterator>
void test_find (int           line,     // line number of test case
                const char   *src,      // source sequence
                std::size_t   findoff,  // offset of the element to find
                InputIterator dummy_iter,
                bool          test_pred)
{
    static const char* const itname = type_name (dummy_iter, (UserClass*)0);
    static const char* const pname  = test_pred ? "Predicate" : "operator==";
 
    const std::size_t nsrc = std::strlen (src);
 
    // normalize offset
    if (nsrc < findoff)
        findoff = nsrc;
 
    // create always at least 1 element (used to test failed searches)
    UserClass* const tsrc      = UserClass::from_char (src, nsrc + 1);
    UserClass* const src_begin = tsrc;
    UserClass* const src_end   = tsrc + nsrc;
 
    //                         current    [first,    last)
    const InputIterator first (src_begin, src_begin, src_end);
    const InputIterator last  (src_end,   src_begin, src_end);
 
    // get a reference to the object to find (when findoff == nsrc
    // the sought for element is outside the source range and won't
    // be found)
    const UserClass &to_find = tsrc [findoff];
 
    // construct a predicate object to use with find_if
    const Predicate<UserClass> pred (to_find, 0 /* dummy */);
 
    // reset the operator==() counter
    UserClass::n_total_op_eq_ = 0;
 
    // invoke find() or find_if(), depending on the predicate flag
    const InputIterator res = test_pred ?
        std::find_if (first, last, pred) : std::find (first, last, to_find);
 
    // silence a bogus EDG eccp remark #550-D:
    // variable "res" was set but never used
    _RWSTD_UNUSED (res);
 
    // verify 25.1.5 p2
    if (!rw_assert (res.cur_ == first.cur_ + findoff, 0, line,
                    "line %d: find%{?}_if%{;} (%s = \"%s\", ..., '%c')"
                    " == (it + %zu), got (it + %td)",
                    __LINE__, test_pred, itname, src, to_find.data_.val_,
                    findoff, res.cur_ - first.cur_)) {
        delete[] tsrc;
        return;
    }
 
    // verify 25.1.5 p3
    // Complexity: At most last - first applications
    //             of the corresponding predicate.
    // The complexity when find is successful is actually
    // (res - first) applications of the corresponding predicate.
 
    const std::size_t npreds =
        test_pred ? pred.funcalls_ : UserClass::n_total_op_eq_;
 
    rw_assert (npreds <= findoff + 1, 0, line,
               "line %d: find%{?}_if%{;} (%s = \"%s\", ..., '%c') "
               "invoked %s %zu times, expected no more than %zu",
               __LINE__, test_pred, itname, src, to_find.data_.val_,
               pname, npreds, findoff + 1);
 
    delete[] tsrc;
}
 
 
template <class InputIterator>
void test_find (InputIterator dummy_iter, bool test_pred)
{   
    static const char* const itname = type_name (dummy_iter, (UserClass*)0);
 
    rw_info (0, 0, 0, "std::find%{?}_if%{;} (%s, %2$s, "
             "%{?}Predicate%{:}const UserClass&%{;})",
             test_pred, itname, test_pred);
 
#define TEST(src, off_find)                             \
    test_find (__LINE__, src, std::size_t (off_find),   \
               dummy_iter, test_pred)
 
    //    +------------------ subject sequence
    //    |               +--- offset of the value to find (-1 for none)
    //    |               |    also the offset of the returned iterator
    //    |               |
    //    |               |
    //    v               v
    TEST ("",            -1);
    TEST ("a",            0);
    TEST ("aa",           0);
    TEST ("ab",           1);
    TEST ("aaa",          0);
    TEST ("abb",          1);
    TEST ("abc",          2);
    TEST ("abcc",         2);
    TEST ("abcd",         3);
    TEST ("abcde",        4);
    TEST ("abcdef",       5);
    TEST ("abcdefg",      6);
    TEST ("abcdefgh",     7);
    TEST ("abcdefghi",    8);
    TEST ("abcdefghij",   9);
    TEST ("abcdefghijk", 10);
    TEST ("abcdefghijk", -1);
}
 
 
/* 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
/* extern */ int rw_opt_no_predicate;    // --no-Predicate
 
static void
test_find (bool test_pred)
{
    rw_info (0, 0, 0, 
             "template <class %s, class %s> "
             "%1$s std::find%{?}_if%{;} (%1$s, %1$s, "
             "%{?}%2$s%{:}const %2$s&%{;})",
             "InputIterator", test_pred ? "Predicate" : "T",
             test_pred);
 
    if (rw_opt_no_input_iter) {
        rw_note (0, __FILE__, __LINE__, "InputIterator test disabled");
    }
    else {
        test_find (InputIter<UserClass>(0, 0, 0), test_pred);
    }
 
    if (rw_opt_no_fwd_iter) {
        rw_note (0, __FILE__, __LINE__, "ForwardIterator test disabled");
    }
    else {
        test_find (ConstFwdIter<UserClass>(), test_pred);
        test_find (FwdIter<UserClass>(), test_pred);
    }
 
    if (rw_opt_no_bidir_iter) {
        rw_note (0, __FILE__, __LINE__, "BidirectionalIterator test disabled");
    }
    else {
        test_find (ConstBidirIter<UserClass>(), test_pred);
        test_find (BidirIter<UserClass>(), test_pred);
    }
 
    if (rw_opt_no_rnd_iter) {
        rw_note (0, __FILE__, __LINE__, "RandomAccessIterator test disabled");
    }
    else {
        test_find (ConstRandomAccessIter<UserClass>(), test_pred);
        test_find (RandomAccessIter<UserClass>(), test_pred);
    }
}
 
 
static int
run_test (int, char*[])
{
    test_find (false);
 
    if (rw_opt_no_predicate) {
        rw_note (0, __FILE__, __LINE__, "Predicate test disabled");
    }
    else {
        test_find (true);
    }
                
    return 0;
}
 
 
int main (int argc, char *argv[])
{
    return rw_test (argc, argv, __FILE__,
                    "lib.alg.find",
                    0 /* no comment */, run_test,
                    "|-no-InputIterator#"
                    "|-no-ForwardIterator#"
                    "|-no-BidirectionalIterator#"
                    "|-no-RandomAccessIterator#"
                    "|-no-Predicate#",
                    &rw_opt_no_input_iter,
                    &rw_opt_no_fwd_iter,
                    &rw_opt_no_bidir_iter,
                    &rw_opt_no_rnd_iter,
                    &rw_opt_no_predicate);
}