Index: include/experimental/functional =================================================================== --- include/experimental/functional +++ include/experimental/functional @@ -20,7 +20,7 @@ namespace experimental { inline namespace fundamentals_v1 { - // See C++14 ยง20.9.9, Function object binders + // See C++14 20.9.9, Function object binders template constexpr bool is_bind_expression_v = is_bind_expression::value; template constexpr int is_placeholder_v @@ -89,7 +89,13 @@ #include #include + +#include // for CHAR_BIT #include +#include +#include +#include +#include #include <__undef_min_max> @@ -103,16 +109,20 @@ // default searcher template> +_LIBCPP_TYPE_VIS class default_searcher { public: + _LIBCPP_INLINE_VISIBILITY default_searcher(_ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate()) : __first_(__f), __last_(__l), __pred_(__p) {} template - _ForwardIterator2 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const { + _LIBCPP_INLINE_VISIBILITY + _ForwardIterator2 operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const + { return _VSTD::search(__f, __l, __first_, __last_, __pred_); - } + } private: _ForwardIterator __first_; @@ -121,13 +131,321 @@ }; template> +_LIBCPP_INLINE_VISIBILITY default_searcher<_ForwardIterator, _BinaryPredicate> make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ()) { return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p); } +template class _BMSkipTable; +// General case for BM data searching; use a map +template +class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> { +public: // TODO private: + typedef _Value value_type; + typedef _Key key_type; + + const _Value __default_value_; + std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table; + +public: + _LIBCPP_INLINE_VISIBILITY + _BMSkipTable(std::size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred) + : __default_value_(__default), __table(__sz, __hf, __pred) {} + + _LIBCPP_INLINE_VISIBILITY + void insert(const key_type &__key, value_type __val) + { + __table [__key] = __val; // Would skip_.insert (val) be better here? + } + + _LIBCPP_INLINE_VISIBILITY + value_type operator [](const key_type & __key) const + { + auto __it = __table.find (__key); + return __it == __table.end() ? __default_value_ : __it->second; + } +}; + + +// Special case small numeric values; use an array +template +class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> { +public: // TODO private: + typedef _Value value_type; + typedef _Key key_type; + + typedef typename std::make_unsigned::type unsigned_key_type; + typedef std::array<_Value, 1U << (CHAR_BIT * sizeof(key_type))> skip_map; + skip_map __table; + +public: + _LIBCPP_INLINE_VISIBILITY + _BMSkipTable(std::size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/) + { + std::fill_n(__table.begin(), __table.size(), __default); + } + + _LIBCPP_INLINE_VISIBILITY + void insert(key_type __key, value_type __val) + { + __table[static_cast(__key)] = __val; + } + + _LIBCPP_INLINE_VISIBILITY + value_type operator [](key_type __key) const + { + return __table[static_cast(__key)]; + } +}; + + +template ::value_type>, + class _BinaryPredicate = equal_to<>> +_LIBCPP_TYPE_VIS +class boyer_moore_searcher { +public: // TODO private: + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; + typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; + typedef _BMSkipTable::value && // what about enums? + sizeof(value_type) == 1 && + is_same<_Hash, hash>::value && + is_same<_BinaryPredicate, equal_to<>>::value + > skip_table_type; + +public: + boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, + _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) + : __first_(__f), __last_(__l), __pred_(__pred), + __pattern_length_(_VSTD::distance(__first_, __last_)), + __skip_(__pattern_length_, -1, __hf, __pred_), + __suffix_(__pattern_length_ + 1) + { + // build the skip table + for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) + __skip_.insert(*__f, __i); + + this->build_suffix_table ( __first_, __last_, __pred_ ); + } + + template + _RandomAccessIterator2 + operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const + { + static_assert ( std::is_same< + typename std::decay::value_type>::type, + typename std::decay::value_type>::type + >::value, + "Corpus and Pattern iterators must point to the same type" ); + + if (__f == __l ) return __f; // empty corpus + if (__first_ == __last_) return __f; // empty pattern + + // If the pattern is larger than the corpus, we can't find it! + if ( __pattern_length_ > _VSTD::distance (__f, __l)) + return __l; + + // Do the search + return this->__search(__f, __l); + } + +public: // TODO private: + _RandomAccessIterator1 __first_; + _RandomAccessIterator1 __last_; + _BinaryPredicate __pred_; + const difference_type __pattern_length_; + skip_table_type __skip_; + std::vector __suffix_; + + template + _RandomAccessIterator2 __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const + { + _RandomAccessIterator2 __cur = __f; + const _RandomAccessIterator2 __last = __l - __pattern_length_; + + while (__cur <= __last) + { + + // Do we match right where we are? + difference_type __j = __pattern_length_; + while (__pred_(__first_ [__j-1], __cur [__j-1])) { + __j--; + // We matched - we're done! + if ( __j == 0 ) + return __cur; + } + + // Since we didn't match, figure out how far to skip forward + difference_type __k = __skip_[__cur [ __j - 1 ]]; + difference_type __m = __j - __k - 1; + if (__k < __j && __m > __suffix_[ __j ]) + __cur += __m; + else + __cur += __suffix_[ __j ]; + } + + return __l; // We didn't find anything + } + + + template + void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix ) + { + const std::size_t __count = _VSTD::distance(__f, __l); + + __prefix[0] = 0; + std::size_t __k = 0; + for ( std::size_t __i = 1; __i < __count; ++__i ) + { + while ( __k > 0 && !__pred ( __f[__k], __f[__i] )) + __k = __prefix [ __k - 1 ]; + + if ( __pred ( __f[__k], __f[__i] )) + __k++; + __prefix [ __i ] = __k; + } + } + + void build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, + _BinaryPredicate __pred) + { + const std::size_t __count = _VSTD::distance(__f, __l); + if (__count > 0) + { + _VSTD::vector reversed(__count); + (void) _VSTD::reverse_copy(__f, __l, reversed.begin ()); + + _VSTD::vector __prefix(__count); + __compute_bm_prefix(__f, __l, __pred, __prefix); + + _VSTD::vector __prefix_reversed(__count); + __compute_bm_prefix(reversed.begin (), reversed.end (), __pred, __prefix_reversed); + + for ( std::size_t __i = 0; __i <= __count; __i++ ) + __suffix_[__i] = __count - __prefix [__count-1]; + + for ( std::size_t __i = 0; __i < __count; __i++ ) + { + const std::size_t __j = __count - __prefix_reversed[__i]; + const difference_type __k = __i - __prefix_reversed[__i] + 1; + + if (__suffix_[__j] > __k) + __suffix_[__j] = __k; + } + } + } + +}; + +template::value_type>, + class _BinaryPredicate = equal_to<>> +_LIBCPP_INLINE_VISIBILITY +boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> +make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, + _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) +{ + return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); +} + +// boyer-moore-horspool +template ::value_type>, + class _BinaryPredicate = equal_to<>> +_LIBCPP_TYPE_VIS +class boyer_moore_horspool_searcher { +public: // TODO private: + typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type; + typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type value_type; + typedef _BMSkipTable::value && // what about enums? + sizeof(value_type) == 1 && + is_same<_Hash, hash>::value && + is_same<_BinaryPredicate, equal_to<>>::value + > skip_table_type; + +public: + boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l, + _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate()) + : __first_(__f), __last_(__l), __pred_(__pred), + __pattern_length_(_VSTD::distance(__first_, __last_)), + __skip_(__pattern_length_, __pattern_length_, __hf, __pred_) + { + // build the skip table + if ( __f != __l ) + { + __l = __l - 1; + for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i ) + __skip_.insert(*__f, __pattern_length_ - 1 - __i); + } + } + + template + _RandomAccessIterator2 + operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const + { + static_assert ( std::is_same< + typename std::decay::value_type>::type, + typename std::decay::value_type>::type + >::value, + "Corpus and Pattern iterators must point to the same type" ); + + if (__f == __l ) return __f; // empty corpus + if (__first_ == __last_) return __f; // empty pattern + + // If the pattern is larger than the corpus, we can't find it! + if ( __pattern_length_ > _VSTD::distance (__f, __l)) + return __l; + + // Do the search + return this->__search(__f, __l); + } + +public: // TODO private: + _RandomAccessIterator1 __first_; + _RandomAccessIterator1 __last_; + _BinaryPredicate __pred_; + const difference_type __pattern_length_; + skip_table_type __skip_; + + template + _RandomAccessIterator2 __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const { + _RandomAccessIterator2 __cur = __f; + const _RandomAccessIterator2 __last = __l - __pattern_length_; + + while (__cur <= __last) + { + // Do we match right where we are? + difference_type __j = __pattern_length_; + while (__pred_(__first_[__j-1], __cur[__j-1])) + { + __j--; + // We matched - we're done! + if ( __j == 0 ) + return __cur; + } + __cur += __skip_[__cur[__pattern_length_-1]]; + } + + return __l; + } +}; + +template::value_type>, + class _BinaryPredicate = equal_to<>> +_LIBCPP_INLINE_VISIBILITY +boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate> +make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l, + _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ()) +{ + return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p); +} + _LIBCPP_END_NAMESPACE_LFTS #endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */ Index: test/std/experimental/algorithms/alg.search/search.pass.cpp =================================================================== --- test/std/experimental/algorithms/alg.search/search.pass.cpp +++ test/std/experimental/algorithms/alg.search/search.pass.cpp @@ -7,6 +7,8 @@ // //===----------------------------------------------------------------------===// +// UNSUPPORTED: c++98, c++03, c++11 + // // template @@ -35,7 +37,7 @@ int main() { typedef int * RI; - static_assert(std::is_same::value, "" ); + static_assert((std::is_same::value), "" ); RI it{nullptr}; assert(it == std::experimental::search(it, it, MySearcher())); Index: test/std/experimental/func/func.searchers/func.searchers.boyer_moore/default.pass.cpp =================================================================== --- test/std/experimental/func/func.searchers/func.searchers.boyer_moore/default.pass.cpp +++ test/std/experimental/func/func.searchers/func.searchers.boyer_moore/default.pass.cpp @@ -0,0 +1,128 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11 + +// + +// boyer_moore searcher +// template::value_type>, +// class BinaryPredicate = equal_to<>> +// class boyer_moore_searcher { +// public: +// boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, +// Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); +// +// template +// RandomAccessIterator2 +// operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; +// +// private: +// RandomAccessIterator1 pat_first_; // exposition only +// RandomAccessIterator1 pat_last_; // exposition only +// Hash hash_; // exposition only +// BinaryPredicate pred_; // exposition only +// }; + + +#include +#include +#include + +#include "test_iterators.h" + +template +void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result) { + std::experimental::boyer_moore_searcher s{b2, e2}; + assert(result == std::experimental::search(b1, e1, s)); +} + +template +void +test() +{ + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2)); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1)); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1)); + int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + int ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1)); + int id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1)); + int ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4)); + int ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8)); + int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + int ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3)); + int ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0}; + const unsigned sj = sizeof(ij)/sizeof(ij[0]); + int ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0}; + const unsigned sk = sizeof(ik)/sizeof(ik[0]); + do_search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk), Iter1(ij+6)); +} + +template +void +test2() +{ + char ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2)); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1)); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1)); + char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + char ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1)); + char id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1)); + char ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4)); + char ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8)); + char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + char ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3)); + char ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0}; + const unsigned sj = sizeof(ij)/sizeof(ij[0]); + char ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0}; + const unsigned sk = sizeof(ik)/sizeof(ik[0]); + do_search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk), Iter1(ij+6)); +} + +int main() { + test, random_access_iterator >(); + test2, random_access_iterator >(); +} Index: test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pass.cpp =================================================================== --- test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pass.cpp +++ test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pass.cpp @@ -0,0 +1,124 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11 + +// + +// boyer_moore searcher +// template::value_type>, +// class BinaryPredicate = equal_to<>> +// class boyer_moore_searcher { +// public: +// boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, +// Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); +// +// template +// RandomAccessIterator2 +// operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; +// +// private: +// RandomAccessIterator1 pat_first_; // exposition only +// RandomAccessIterator1 pat_last_; // exposition only +// Hash hash_; // exposition only +// BinaryPredicate pred_; // exposition only +// }; + + +#include +#include +#include + +#include "test_iterators.h" + +template struct MyHash { + size_t operator () (T t) const { return static_cast(t); } +}; + +template +void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) { + std::experimental::boyer_moore_searcher::value_type>::type>> + s{b2, e2}; + assert(result == std::experimental::search(b1, e1, s)); +} + +template +void +test() +{ + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + int ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + int id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + int ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + int ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + int ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +template +void +test2() +{ + char ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + char ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + char id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + char ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + char ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + char ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +int main() { + test, random_access_iterator >(); + test2, random_access_iterator >(); +} Index: test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pred.pass.cpp =================================================================== --- test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pred.pass.cpp +++ test/std/experimental/func/func.searchers/func.searchers.boyer_moore/hash.pred.pass.cpp @@ -0,0 +1,135 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11 + +// + +// boyer_moore searcher +// template::value_type>, +// class BinaryPredicate = equal_to<>> +// class boyer_moore_searcher { +// public: +// boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, +// Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); +// +// template +// RandomAccessIterator2 +// operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; +// +// private: +// RandomAccessIterator1 pat_first_; // exposition only +// RandomAccessIterator1 pat_last_; // exposition only +// Hash hash_; // exposition only +// BinaryPredicate pred_; // exposition only +// }; + + +#include +#include +#include + +#include "test_iterators.h" + +template struct MyHash { + size_t operator () (T t) const { return static_cast(t); } +}; + +struct count_equal +{ + static unsigned count; + template + bool operator()(const T& x, const T& y) const + {++count; return x == y;} +}; + +unsigned count_equal::count = 0; + +template +void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) { + std::experimental::boyer_moore_searcher::value_type>::type>, + count_equal> + s{b2, e2}; + assert(result == std::experimental::search(b1, e1, s)); +} + +template +void +test() +{ + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + int ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + int id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + int ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + int ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + int ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +template +void +test2() +{ + char ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + char ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + char id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + char ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + char ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + char ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +int main() { + test, random_access_iterator >(); + test2, random_access_iterator >(); +} Index: test/std/experimental/func/func.searchers/func.searchers.boyer_moore/pred.pass.cpp =================================================================== --- test/std/experimental/func/func.searchers/func.searchers.boyer_moore/pred.pass.cpp +++ test/std/experimental/func/func.searchers/func.searchers.boyer_moore/pred.pass.cpp @@ -0,0 +1,131 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11 + +// + +// boyer_moore searcher +// template::value_type>, +// class BinaryPredicate = equal_to<>> +// class boyer_moore_searcher { +// public: +// boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, +// Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); +// +// template +// RandomAccessIterator2 +// operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; +// +// private: +// RandomAccessIterator1 pat_first_; // exposition only +// RandomAccessIterator1 pat_last_; // exposition only +// Hash hash_; // exposition only +// BinaryPredicate pred_; // exposition only +// }; + + +#include +#include +#include + +#include "test_iterators.h" + +struct count_equal +{ + static unsigned count; + template + bool operator()(const T& x, const T& y) const + {++count; return x == y;} +}; + +unsigned count_equal::count = 0; + +template +void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) { + std::experimental::boyer_moore_searcher::value_type>::type>, count_equal> s{b2, e2}; + count_equal::count = 0; + assert(result == std::experimental::search(b1, e1, s)); +// assert(count_equal::count <= max_count); +} + +template +void +test() +{ + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + int ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + int id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + int ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + int ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + int ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +template +void +test2() +{ + char ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + char ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + char id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + char ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + char ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + char ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +int main() { + test, random_access_iterator >(); + test2, random_access_iterator >(); +} Index: test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/default.pass.cpp =================================================================== --- test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/default.pass.cpp +++ test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/default.pass.cpp @@ -0,0 +1,128 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11 + +// + +// boyer_moore_horspool searcher +// template::value_type>, +// class BinaryPredicate = equal_to<>> +// class boyer_moore_horspool_searcher { +// public: +// boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, +// Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); +// +// template +// RandomAccessIterator2 +// operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; +// +// private: +// RandomAccessIterator1 pat_first_; // exposition only +// RandomAccessIterator1 pat_last_; // exposition only +// Hash hash_; // exposition only +// BinaryPredicate pred_; // exposition only +// }; + + +#include +#include +#include + +#include "test_iterators.h" + +template +void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result) { + std::experimental::boyer_moore_horspool_searcher s{b2, e2}; + assert(result == std::experimental::search(b1, e1, s)); +} + +template +void +test() +{ + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1)); +// do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia)); +// do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2)); +// do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2)); +// do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia)); +// do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1)); +// do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3)); +// do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia)); +// do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1)); +// do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1)); +// int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; +// const unsigned sb = sizeof(ib)/sizeof(ib[0]); +// int ic[] = {1}; +// do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1)); +// int id[] = {1, 2}; +// do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1)); +// int ie[] = {1, 2, 3}; +// do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4)); +// int ig[] = {1, 2, 3, 4}; +// do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8)); +// int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; +// const unsigned sh = sizeof(ih)/sizeof(ih[0]); +// int ii[] = {1, 1, 2}; +// do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3)); +// int ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0}; +// const unsigned sj = sizeof(ij)/sizeof(ij[0]); +// int ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0}; +// const unsigned sk = sizeof(ik)/sizeof(ik[0]); +// do_search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk), Iter1(ij+6)); +} + +template +void +test2() +{ + char ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2)); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3)); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia)); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1)); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1)); + char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + char ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1)); + char id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1)); + char ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4)); + char ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8)); + char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + char ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3)); + char ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0}; + const unsigned sj = sizeof(ij)/sizeof(ij[0]); + char ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0}; + const unsigned sk = sizeof(ik)/sizeof(ik[0]); + do_search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk), Iter1(ij+6)); +} + +int main() { + test, random_access_iterator >(); +// test2, random_access_iterator >(); +} Index: test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pass.cpp =================================================================== --- test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pass.cpp +++ test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pass.cpp @@ -0,0 +1,123 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11 + +// + +// boyer_moore_horspool searcher +// template::value_type>, +// class BinaryPredicate = equal_to<>> +// class boyer_moore_horspool_searcher { +// public: +// boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, +// Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); +// +// template +// RandomAccessIterator2 +// operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; +// +// private: +// RandomAccessIterator1 pat_first_; // exposition only +// RandomAccessIterator1 pat_last_; // exposition only +// Hash hash_; // exposition only +// BinaryPredicate pred_; // exposition only +// }; + +#include +#include +#include + +#include "test_iterators.h" + +template struct MyHash { + size_t operator () (T t) const { return static_cast(t); } +}; + +template +void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) { + std::experimental::boyer_moore_horspool_searcher::value_type>::type>> + s{b2, e2}; + assert(result == std::experimental::search(b1, e1, s)); +} + +template +void +test() +{ + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + int ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + int id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + int ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + int ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + int ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +template +void +test2() +{ + char ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + char ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + char id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + char ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + char ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + char ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +int main() { + test, random_access_iterator >(); + test2, random_access_iterator >(); +} Index: test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp =================================================================== --- test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp +++ test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp @@ -0,0 +1,134 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11 + +// + +// boyer_moore_horspool searcher +// template::value_type>, +// class BinaryPredicate = equal_to<>> +// class boyer_moore_horspool_searcher { +// public: +// boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, +// Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); +// +// template +// RandomAccessIterator2 +// operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; +// +// private: +// RandomAccessIterator1 pat_first_; // exposition only +// RandomAccessIterator1 pat_last_; // exposition only +// Hash hash_; // exposition only +// BinaryPredicate pred_; // exposition only +// }; + +#include +#include +#include + +#include "test_iterators.h" + +template struct MyHash { + size_t operator () (T t) const { return static_cast(t); } +}; + +struct count_equal +{ + static unsigned count; + template + bool operator()(const T& x, const T& y) const + {++count; return x == y;} +}; + +unsigned count_equal::count = 0; + +template +void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) { + std::experimental::boyer_moore_horspool_searcher::value_type>::type>, + count_equal> + s{b2, e2}; + assert(result == std::experimental::search(b1, e1, s)); +} + +template +void +test() +{ + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + int ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + int id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + int ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + int ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + int ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +template +void +test2() +{ + char ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + char ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + char id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + char ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + char ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + char ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +int main() { + test, random_access_iterator >(); + test2, random_access_iterator >(); +} Index: test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/pred.pass.cpp =================================================================== --- test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/pred.pass.cpp +++ test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/pred.pass.cpp @@ -0,0 +1,130 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03, c++11 + +// + +// boyer_moore_horspool searcher +// template::value_type>, +// class BinaryPredicate = equal_to<>> +// class boyer_moore_horspool_searcher { +// public: +// boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last, +// Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate()); +// +// template +// RandomAccessIterator2 +// operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const; +// +// private: +// RandomAccessIterator1 pat_first_; // exposition only +// RandomAccessIterator1 pat_last_; // exposition only +// Hash hash_; // exposition only +// BinaryPredicate pred_; // exposition only +// }; + +#include +#include +#include + +#include "test_iterators.h" + +struct count_equal +{ + static unsigned count; + template + bool operator()(const T& x, const T& y) const + {++count; return x == y;} +}; + +unsigned count_equal::count = 0; + +template +void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) { + std::experimental::boyer_moore_horspool_searcher::value_type>::type>, count_equal> s{b2, e2}; + count_equal::count = 0; + assert(result == std::experimental::search(b1, e1, s)); +// assert(count_equal::count <= max_count); +} + +template +void +test() +{ + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + int ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + int id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + int ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + int ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + int ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +template +void +test2() +{ + char ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned sa = sizeof(ia)/sizeof(ia[0]); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+1), Iter1(ia), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+1), Iter2(ia+2), Iter1(ia+1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+2), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+2), Iter2(ia+3), Iter1(ia+2), sa); + do_search(Iter1(ia), Iter1(ia), Iter2(ia+2), Iter2(ia+3), Iter1(ia), 0); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa); + do_search(Iter1(ia), Iter1(ia+sa), Iter2(ia), Iter2(ia+sa), Iter1(ia), sa*sa); + do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia), Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa); + do_search(Iter1(ia), Iter1(ia+1), Iter2(ia), Iter2(ia+sa), Iter1(ia+1), sa); + char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sb = sizeof(ib)/sizeof(ib[0]); + char ic[] = {1}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb); + char id[] = {1, 2}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2); + char ie[] = {1, 2, 3}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3); + char ig[] = {1, 2, 3, 4}; + do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4); + char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4}; + const unsigned sh = sizeof(ih)/sizeof(ih[0]); + char ii[] = {1, 1, 2}; + do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3), sh*3); +} + +int main() { + test, random_access_iterator >(); + test2, random_access_iterator >(); +}