Index: include/bits/predefined_ops.h =================================================================== RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/Attic/predefined_ops.h,v retrieving revision 1.1.2.2 diff -u -b -r1.1.2.2 predefined_ops.h --- include/bits/predefined_ops.h 14 Mar 2005 10:38:03 -0000 1.1.2.2 +++ include/bits/predefined_ops.h 21 Jun 2005 13:23:54 -0000 @@ -54,6 +54,58 @@ operator()(const _Lhs& __lhs, const _Rhs& __rhs) const { return __lhs == __rhs; } }; + + /** + * @if maint + * A class inspired by bind2nd and company, which wraps a function or + * class and a reference, and produces a unary function object. It has less + * requirements than the standard version and is designed to be use to wrap + * binary predicates given to algorithms in the standard library. + * @endif + */ + template + class __bind2nd + { + _Comp _M_comp; + const _Value& _M_value; + + public: + explicit + __bind2nd(_Comp __comp, const _Value& __inval) + : _M_comp(__comp), _M_value(__inval) {} + + template + bool + operator()(const _Lhs& __lhs) + { return _M_comp(__lhs, _M_value); } + }; + + /** + * @if maint + * Specialisation of __bind2nd for equality. + * @endif + */ + template + class __bind2nd<__gnu_cxx::__ops::equal_to, _Value> + { + const _Value& _M_value; + + public: + explicit + __bind2nd(__gnu_cxx::__ops::equal_to, const _Value& __inval) + : _M_value(__inval) {} + + template + bool + operator()(const _Lhs& __lhs) + { return __lhs == _M_value; } + }; + + template + inline __bind2nd<_Comp, _Value> + bind2nd(_Comp __comp, const _Value& __value) + { return __bind2nd<_Comp, _Value>(__comp, __value); } + } // namespace __ops } // namespace __gnu_cxx Index: include/bits/stl_algo.h =================================================================== RCS file: /cvsroot/gcc/gcc/libstdc++-v3/include/bits/stl_algo.h,v retrieving revision 1.47.6.13 diff -u -b -r1.47.6.13 stl_algo.h --- include/bits/stl_algo.h 13 Jun 2005 19:12:02 -0000 1.47.6.13 +++ include/bits/stl_algo.h 21 Jun 2005 13:23:54 -0000 @@ -430,6 +430,90 @@ } /** + * @if maint + * This is an uglified + * search(_ForwardIterator1, _FowrardIterator1, _ForwardIterator2, + * _ForwardIterator2, _BinaryPredicate) + * overloaded for when one of the two iterator types is not random access. + * @endif + */ + template + _ForwardIterator1 + __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __predicate, forward_iterator_tag, + forward_iterator_tag) + { + // General case. + _ForwardIterator2 __p1, __p; + __p1 = __first2; ++__p1; + _ForwardIterator1 __current = __first1; + + while (__first1 != __last1) + { + __first1 = std::find_if(__first1, __last1, + __gnu_cxx::__ops::bind2nd(__predicate, + *__first2)); + if (__first1 == __last1) + return __last1; + + __p = __p1; + __current = __first1; + if (++__current == __last1) + return __last1; + + while (__predicate(*__current, *__p)) + { + if (++__p == __last2) + return __first1; + if (++__current == __last1) + return __last1; + } + ++__first1; + } + return __first1; + } + + /** + * @if maint + * This is an uglified + * search(_ForwardIterator1, _FowrardIterator1, _ForwardIterator2, + * _ForwardIterator2, _BinaryPredicate) + * overloaded for when both iterator types are random acccess. + * @endif + */ + template + _ForwardIterator1 + __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __predicate, random_access_iterator_tag, + random_access_iterator_tag) + { + typedef typename iterator_traits<_ForwardIterator2>::difference_type + _Distance; + _Distance __length(__last2 - __first2); + + if (__length > (__last1 - __first1)) + return __last1; + + _ForwardIterator1 __lastpossible(__last1 - __length + 1); + __first1 = std::find_if(__first1, __lastpossible, + __gnu_cxx::__ops::bind2nd(__predicate, + *__first2)); + while(__first1 != __lastpossible) + { + if (std::equal(__first1, __first1 + __length, __first2, __predicate)) + return __first1; + __first1 = std::find_if(__first1 + 1, __lastpossible, + __gnu_cxx::__ops::bind2nd(__predicate, + *__first2)); + } + return __last1; + } + + /** * @brief Search a sequence for a matching sub-sequence using a predicate. * @param first1 A forward iterator. * @param last1 A forward iterator. @@ -451,7 +535,7 @@ */ template - _ForwardIterator1 + inline _ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate) @@ -473,45 +557,12 @@ _ForwardIterator2 __tmp(__first2); ++__tmp; if (__tmp == __last2) - { - while (__first1 != __last1 && !__predicate(*__first1, *__first2)) - ++__first1; - return __first1; - } - - // General case. - _ForwardIterator2 __p1, __p; - __p1 = __first2; ++__p1; - _ForwardIterator1 __current = __first1; - - while (__first1 != __last1) - { - while (__first1 != __last1) - { - if (__predicate(*__first1, *__first2)) - break; - ++__first1; - } - while (__first1 != __last1 && !__predicate(*__first1, *__first2)) - ++__first1; - if (__first1 == __last1) - return __last1; - - __p = __p1; - __current = __first1; - if (++__current == __last1) - return __last1; + return std::find_if(__first1, __last1, + __gnu_cxx::__ops::bind2nd(__predicate, *__first2)); - while (__predicate(*__current, *__p)) - { - if (++__p == __last2) - return __first1; - if (++__current == __last1) - return __last1; - } - ++__first1; - } - return __first1; + return std::__search(__first1, __last1, __first2, __last2, __predicate, + std::__iterator_category(__first1), + std::__iterator_category(__first2)); } /** Index: testsuite/25_algorithms/search/1.cc =================================================================== RCS file: /cvsroot/gcc/gcc/libstdc++-v3/testsuite/25_algorithms/search/1.cc,v retrieving revision 1.1.2.2 diff -u -b -r1.1.2.2 1.cc --- testsuite/25_algorithms/search/1.cc 29 Mar 2005 16:32:32 -0000 1.1.2.2 +++ testsuite/25_algorithms/search/1.cc 21 Jun 2005 13:23:57 -0000 @@ -24,9 +24,11 @@ using __gnu_test::test_container; using __gnu_test::forward_iterator_wrapper; +using __gnu_test::random_access_iterator_wrapper; using std::search; typedef test_container Container; +typedef test_container RAcontainer; int array1[] = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1}; int array2[] = {0, 0, 0}; @@ -101,6 +103,53 @@ == array3 + 6); } +bool +lexstep(int* start, int length) +{ + int i = 0; + int carry = 1; + while(i < length && carry) + { + if(start[i] == 1) + start[i] = 0; + else + { + start[i] = 1; + carry = 0; + } + i++; + } + return !carry; +} + +void test7() +{ + int array1[6]; + int array2[6]; + for(int length1 = 0; length1 < 6; length1++) + { + for(int length2 = 0; length2 < 6; length2++) + { + std::fill_n(array1, length1, 0); + while(lexstep(array1, length1)) + { + std::fill_n(array2, length2, 0); + while(lexstep(array2, length2)) + { + Container con1(array1, array1 + length1); + Container con2(array2, array2 + length2); + RAcontainer rcon1(array1, array1 + length1); + RAcontainer rcon2(array2, array2 + length2); + VERIFY(search(con1.begin(), con1.end(), con2.begin(), + con2.end()).ptr == + search(rcon1.begin(), rcon1.end(), rcon2.begin(), + rcon2.end()).ptr); + } + } + } + } +} + int main() { @@ -110,4 +159,5 @@ test4(); test5(); test6(); + test7(); } Index: testsuite/25_algorithms/search/check_type.cc =================================================================== RCS file: /cvsroot/gcc/gcc/libstdc++-v3/testsuite/25_algorithms/search/check_type.cc,v retrieving revision 1.1.2.1 diff -u -b -r1.1.2.1 check_type.cc --- testsuite/25_algorithms/search/check_type.cc 1 Feb 2005 11:10:27 -0000 1.1.2.1 +++ testsuite/25_algorithms/search/check_type.cc 21 Jun 2005 13:23:57 -0000 @@ -25,14 +25,33 @@ using __gnu_test::forward_iterator_wrapper; -struct S1 { }; -struct S2 { }; +struct T1 { }; +struct T2 { }; + +struct S1 +{ + S1(T1) { } +}; + +struct S2 { + S2(T2) { } +}; bool operator==(const S1&, const S2&) {return true;} -struct X1 { }; -struct X2 { }; +struct V1 { }; +struct V2 { }; + +struct X1 +{ + X1(V1) { }; +}; + +struct X2 +{ + X2(V2) { }; +}; bool predicate(const X1&, const X2&) {return true;} @@ -41,6 +60,14 @@ test1(forward_iterator_wrapper& s1, forward_iterator_wrapper& s2) { return std::search(s1, s1, s2, s2); } +forward_iterator_wrapper +test2(forward_iterator_wrapper& s1, forward_iterator_wrapper& s2) +{ return std::search(s1, s1, s2, s2); } + forward_iterator_wrapper -test2(forward_iterator_wrapper& x1, forward_iterator_wrapper& x2) +test3(forward_iterator_wrapper& x1, forward_iterator_wrapper& x2) +{ return std::search(x1, x1, x2, x2, predicate); } + +forward_iterator_wrapper +test4(forward_iterator_wrapper& x1, forward_iterator_wrapper& x2) { return std::search(x1, x1, x2, x2, predicate); }