/*************************************************************************** * * find.cpp - test exercising 25.1.2-5 [lib.alg.find] * * $Id: //stdlib/dev/tests/stdlib/algorithm/find.cpp#18 $ * *************************************************************************** * * Copyright (c) 1994-2005 Quovadx, Inc. All Rights Reserved. * * This computer software is owned by Quovadx, Inc. and is protected by * U.S. copyright laws and other laws and by international treaties. * This computer software is furnished by Quovadx, Inc., pursuant to a * written license agreement and may be used, copied, transmitted, and * stored only in accordance with the terms of such license agreement and * with the inclusion of the above copyright notice. This computer * software or any other copies thereof may not be provided or otherwise * made available to any other person. * * * U.S. Government Restricted Rights. * * This computer software: (a) was developed at private expense and is in * all respects the proprietary information of Quovadx, Inc.; (b) was not * developed with government funds; (c) is a trade secret of Quovadx, * Inc. for all purposes of the Freedom of Information Act; and (d) is a * commercial item and thus, pursuant to Section 12.212 of the Federal * Acquisition Regulations (FAR) and DFAR Supplement Section 227.7202, * Government's use, duplication or disclosure of the computer software * is subject to the restrictions set forth by Quovadx, Inc. * **************************************************************************/ #include // for find() #include // for size_t #include #include // for rw_test() /**************************************************************************/ _RWSTD_NAMESPACE (std) { #ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION template InputIter > > find (InputIter > >, InputIter > >, const eq_comp >&); template InputIter > > find_if (InputIter > >, InputIter > >, predicate > >); #endif // _RWSTD_NO_EXPLICIT_INSTANTIATION } // namespace std /**************************************************************************/ // used to exercise find_if with all types of iterators struct FindIfPredicateBase { static std::size_t funcalls_; bool is_const_; FindIfPredicateBase (bool is_const) : is_const_ (is_const) { funcalls_ = 0; } private: void operator= (FindIfPredicateBase& ); }; std::size_t FindIfPredicateBase::funcalls_; template struct ConstFindIfPredicate : FindIfPredicateBase { ConstFindIfPredicate(T& tofind) : FindIfPredicateBase(true), tofind_(tofind) {} int operator() (T obj) { ++funcalls_; return obj == tofind_; } static const char* name () { return "ConstFunction"; } private: T& tofind_; }; template struct MutableFindIfPredicate : FindIfPredicateBase { MutableFindIfPredicate(T& tofind) : FindIfPredicateBase(true), tofind_(tofind) {} int operator() (T& obj) { ++funcalls_; return obj == tofind_; } static const char* name () { return "MutableFunction"; } private: T& tofind_; }; /**************************************************************************/ // used to initialize an array of objects of type T static const char *tinit_begin; int tinit () { typedef unsigned char UChar; return UChar (*tinit_begin++); } /**************************************************************************/ // exercises std::find() template void do_test_find (int line, // line number of test case const char *src, // source sequence std::size_t startoff, // offset of the start element std::size_t findoff, // offset of the element to find std::size_t resoff, // offset of result InputIterator dummy_iter, const T* ) { 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 T default ctor initialize objects from `src' tinit_begin = src; T::gen_ = tinit; T* const tsrc = new T [nsrc]; T* const src_begin = tsrc + startoff; T* const src_end = tsrc + nsrc; const InputIterator first = make_iter (src_begin, src_begin, src_end, dummy_iter); const InputIterator last = make_iter (src_end, src_begin, src_end, dummy_iter); // construct T to be found T* temp_t = 0; if (nsrc) temp_t = new T (tsrc[findoff]); else // the sequence is empty, search any dummy value temp_t = new T(); // compute the number of invocations of the predicate std::size_t last_n_op_assign = T::n_total_op_assign_; InputIterator res = std::find (first, last, *temp_t); // verify 25.1.5 p1 bool success = res.cur_ == first.cur_ + resoff - startoff; rw_assert (success, 0, line, "line %d: find<%s>(it = \"%s\", ...)" " == (it + %zu), got (it + %td)", __LINE__, itname, src, resoff, res.cur_ - first.cur_); if (!success) { delete[] tsrc; delete temp_t; return; } if (res.cur_ != last.cur_) { success = res->val_ == temp_t->val_; rw_assert (success, 0, line, "line %d: find<%s>(it = \"%s\", ...)" " expected value %d got %d", __LINE__, itname, src, temp_t->val_, res->val_); if (!success) { delete[] tsrc; delete temp_t; return; } } // verify 25.1.5 p2 success = T::n_total_op_assign_ - last_n_op_assign <= nsrc - startoff; rw_assert (success, 0, line, "line %d: find<%s>(\"%s\", ...) " "invoked operator==() %zu times, expected %td", __LINE__, itname, src, T::n_total_op_eq_, nsrc - startoff); delete[] tsrc; delete temp_t; } // exercises std::find_if() template void do_test_find_if (int line, // line number of test case const char *src, // source sequence std::size_t startoff, // offset of the start element std::size_t findoff, // offset of the element to find std::size_t resoff, // offset of result InputIterator dummy_iter, Function* , T* ) { static const char* const itname = type_name (dummy_iter, (T*)0); static const char* const fname = Function::name (); const std::size_t nsrc = std::strlen (src); if (std::size_t (-1) == resoff) resoff = nsrc; // have the T default ctor initialize objects from `src' tinit_begin = src; T::gen_ = tinit; T* const tsrc = new T [nsrc]; T* const src_begin = tsrc + startoff; T* const src_end = tsrc + nsrc; const InputIterator first = make_iter (src_begin, src_begin, src_end, dummy_iter); const InputIterator last = make_iter (src_end, src_begin, src_end, dummy_iter); // construct T to be found T* temp_t = 0; if (nsrc) temp_t = new T (tsrc[findoff]); else // the sequence is empty, search any dummy value temp_t = new T(); const Function fun (*temp_t); InputIterator res((T*)0, (T*)0, (T*)0); res = std::find_if (first, last, fun); // verify 25.1.5 p1 bool success = res.cur_ == first.cur_ + resoff - startoff; rw_assert (success, 0, line, "line %d: find_if<%s>(it = \"%s\", ...)" " == (it + %zu), got (it + %td)", __LINE__, itname, src, resoff, res.cur_ - first.cur_); if (!success) { delete[] tsrc; delete temp_t; return; } if (res.cur_ != last.cur_) { success = res->val_ == temp_t->val_; rw_assert (success, 0, line, "line %d: find_if<%s>(it = \"%s\", ...)" " expected value %c got %c", __LINE__, itname, src, temp_t->val_, res->val_); if (!success) { delete[] tsrc; delete temp_t; return; } } // verify 25.1.5 p2 success = fun.funcalls_ <= nsrc - startoff; rw_assert (success, 0, line, "line %d: find<%s>(\"%s\", ...) " "invoked %s %zu times, expected no more than %td", __LINE__, itname, src, fname, T::n_total_op_eq_, nsrc - startoff); delete[] tsrc; delete temp_t; } /**************************************************************************/ template void run_find_tests (InputIterator dummy_iter, const T*) { static const char* const itname = type_name (dummy_iter, (T*)0); static const char* const tname = "X"; rw_info (0, 0, 0, "std::find (%s, %1$s, %s)", itname, tname); #define TEST(src, off_start, off_find, off_res) \ do_test_find (__LINE__, src, std::size_t (off_start), \ std::size_t (off_find), std::size_t (off_res), \ dummy_iter, (X*)0) // +------------------ subject sequence // | +--- offset of the start iterator // | | +--- offset of the element to find // | | | +-- offset of returned iterator, // | | | | -1 denotes the end of sequence // v v v v TEST ("a", 0, 0, 0); TEST ("ab", 0, 1, 1); TEST ("abc", 0, 2, 2); TEST ("abcd", 0, 3, 3); TEST ("abcde", 0, 4, 4); TEST ("abcdef", 0, 5, 5); TEST ("abcdefg", 0, 6, 6); TEST ("abcdefgh", 0, 7, 7); TEST ("abcdefghi", 0, 8, 8); TEST ("abcdefghij", 0, 9, 9); TEST ("abcdefghijk", 0, 10, 10); TEST ("aabcdefghij", 0, 0, 0); TEST ("abbcdefghij", 0, 1, 1); TEST ("abccdefghij", 0, 2, 2); TEST ("abcddefghij", 0, 3, 3); TEST ("abcdeefghij", 0, 4, 4); TEST ("abcdeffghij", 0, 5, 5); TEST ("abcdefgghij", 0, 6, 6); TEST ("abcdefghhij", 0, 7, 7); TEST ("abcdefghiij", 0, 8, 8); TEST ("abcdefghijj", 0, 9, 9); TEST ("", 0, 0, -1); TEST ("abcdefghijk", 1, 0, -1); TEST ("abcdefghijk", 2, 1, -1); TEST ("abcdefghijk", 3, 2, -1); TEST ("abcdefghijk", 4, 3, -1); TEST ("abcdefghijk", 5, 4, -1); TEST ("abcdefghijk", 6, 5, -1); TEST ("abcdefghijk", 7, 6, -1); TEST ("abcdefghijk", 8, 7, -1); TEST ("abcdefghijk", 9, 8, -1); } template void run_find_if_tests (InputIterator dummy_iter, Function* dummy_f, const T*) { static const char* const itname = type_name (dummy_iter, (T*)0); static const char* const fname = Function::name (); rw_info (0, 0, 0, "std::find_if (%s, %1$s, %s)", itname, fname); #define TEST_IF(src, off_start, off_find, off_res) \ do_test_find_if (__LINE__, src, std::size_t (off_start), \ std::size_t (off_find), \ std::size_t (off_res), dummy_iter, dummy_f, (X*)0) // +------------------ subject sequence // | +--- offset of the start iterator // | | +--- offset of the element to find // | | | +-- offset of returned iterator, // | | | | -1 denotes the end of sequence // v v v v TEST_IF ("a", 0, 0, 0); TEST_IF ("ab", 0, 1, 1); TEST_IF ("abc", 0, 2, 2); TEST_IF ("abcd", 0, 3, 3); TEST_IF ("abcde", 0, 4, 4); TEST_IF ("abcdef", 0, 5, 5); TEST_IF ("abcdefg", 0, 6, 6); TEST_IF ("abcdefgh", 0, 7, 7); TEST_IF ("abcdefghi", 0, 8, 8); TEST_IF ("abcdefghij", 0, 9, 9); TEST_IF ("abcdefghijk", 0, 10, 10); TEST_IF ("aabcdefghij", 0, 0, 0); TEST_IF ("abbcdefghij", 0, 1, 1); TEST_IF ("abccdefghij", 0, 2, 2); TEST_IF ("abcddefghij", 0, 3, 3); TEST_IF ("abcdeefghij", 0, 4, 4); TEST_IF ("abcdeffghij", 0, 5, 5); TEST_IF ("abcdefgghij", 0, 6, 6); TEST_IF ("abcdefghhij", 0, 7, 7); TEST_IF ("abcdefghiij", 0, 8, 8); TEST_IF ("abcdefghijj", 0, 9, 9); TEST_IF ("", 0, 0, -1); TEST_IF ("abcdefghijk", 1, 0, -1); TEST_IF ("abcdefghijk", 2, 1, -1); TEST_IF ("abcdefghijk", 3, 2, -1); TEST_IF ("abcdefghijk", 4, 3, -1); TEST_IF ("abcdefghijk", 5, 4, -1); TEST_IF ("abcdefghijk", 6, 5, -1); TEST_IF ("abcdefghijk", 7, 6, -1); TEST_IF ("abcdefghijk", 8, 7, -1); TEST_IF ("abcdefghijk", 9, 8, -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 () { rw_info (0, 0, 0, "template " "%1$s std::find (%1$s, %1$s, const T& )", "InputIterator"); if (rw_opt_no_input_iter) { rw_note (0, __FILE__, __LINE__, "InputIterator test disabled"); } else { run_find_tests (InputIter((X*)0, (X*)0, (X*)0), (X*)0); } if (rw_opt_no_fwd_iter) { rw_note (0, __FILE__, __LINE__, "ForwardIterator test disabled"); } else { run_find_tests (FwdIter(), (X*)0); } if (rw_opt_no_bidir_iter) { rw_note (0, __FILE__, __LINE__, "BidirectionalIterator test disabled"); } else { run_find_tests (BidirIter(), (X*)0); } if (rw_opt_no_rnd_iter) { rw_note (0, __FILE__, __LINE__, "RandomAccessIterator test disabled"); } else { run_find_tests (RandomAccessIter(), (X*)0); } } static void test_find_if () { rw_info (0, 0, 0, "template " "%1$s std::find_if (%1$s, %1$s, %s )", "InputIterator", "Function"); if (rw_opt_no_input_iter) { rw_note (0, __FILE__, __LINE__, "InputIterator test disabled"); } else { run_find_if_tests (InputIter((X*)0, (X*)0, (X*)0), (ConstFindIfPredicate *) 0, (X*)0); } if (rw_opt_no_fwd_iter) { rw_note (0, __FILE__, __LINE__, "ForwardIterator test disabled"); } else { run_find_if_tests (ConstFwdIter(), (ConstFindIfPredicate *) 0, (X*)0); run_find_if_tests (FwdIter(), (ConstFindIfPredicate *) 0, (X*)0); run_find_if_tests (FwdIter(), (MutableFindIfPredicate *) 0, (X*)0); } if (rw_opt_no_bidir_iter) { rw_note (0, __FILE__, __LINE__, "BidirectionalIterator test disabled"); } else { run_find_if_tests (ConstBidirIter(), (ConstFindIfPredicate *) 0, (X*)0); run_find_if_tests (BidirIter(), (ConstFindIfPredicate *) 0, (X*)0); run_find_if_tests (BidirIter(), (MutableFindIfPredicate *) 0, (X*)0); } if (rw_opt_no_rnd_iter) { rw_note (0, __FILE__, __LINE__, "RandomAccessIterator test disabled"); } else { run_find_if_tests (ConstRandomAccessIter(), (ConstFindIfPredicate *) 0, (X*)0); run_find_if_tests (RandomAccessIter(), (ConstFindIfPredicate *) 0, (X*)0); run_find_if_tests (RandomAccessIter(), (MutableFindIfPredicate *) 0, (X*)0); } } static int run_test (int, char*[]) { test_find(); if (rw_opt_no_predicate) { rw_note (0, __FILE__, __LINE__, "Predicate test disabled"); } else { test_find_if (); } 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); }