1//===----------------------------------------------------------------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is dual licensed under the MIT and the University of Illinois Open
6// Source Licenses. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10// UNSUPPORTED: c++98, c++03, c++11, c++14
11// XFAIL: c++17, c++2a
12
13// <functional>
14
15// boyer_moore_horspool searcher
16// template<class RandomAccessIterator1,
17//          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
18//          class BinaryPredicate = equal_to<>>
19// class boyer_moore_horspool_searcher {
20// public:
21//   boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
22//                                 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
23//
24//   template<class RandomAccessIterator2>
25//   pair<RandomAccessIterator2, RandomAccessIterator2>
26//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
27//
28// private:
29//   RandomAccessIterator1 pat_first_; // exposition only
30//   RandomAccessIterator1 pat_last_;  // exposition only
31//   Hash                  hash_;      // exposition only
32//   BinaryPredicate       pred_;      // exposition only
33// };
34
35#include <algorithm>
36#include <functional>
37#include <cassert>
38
39#include "test_iterators.h"
40
41template <typename T> struct MyHash {
42    size_t operator () (T t) const { return static_cast<size_t>(t); }
43};
44
45template <typename Iter1, typename Iter2>
46void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned /*max_count*/) {
47    std::boyer_moore_horspool_searcher<Iter2,
48                 MyHash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>>
49          s{b2, e2};
50    assert(result == std::search(b1, e1, s));
51}
52
53template <class Iter1, class Iter2>
54void
55test()
56{
57    int ia[] = {0, 1, 2, 3, 4, 5};
58    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
59    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
60    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
61    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
62    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
63    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
64    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
65    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
66    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
67    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
68    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
69    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
70    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
71    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
72    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
73    int ic[] = {1};
74    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
75    int id[] = {1, 2};
76    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
77    int ie[] = {1, 2, 3};
78    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
79    int ig[] = {1, 2, 3, 4};
80    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
81    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
82    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
83    int ii[] = {1, 1, 2};
84    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
85}
86
87template <class Iter1, class Iter2>
88void
89test2()
90{
91    char ia[] = {0, 1, 2, 3, 4, 5};
92    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
93    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
94    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
95    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
96    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
97    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
98    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
99    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
100    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
101    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
102    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
103    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
104    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
105    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
106    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
107    char ic[] = {1};
108    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
109    char id[] = {1, 2};
110    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
111    char ie[] = {1, 2, 3};
112    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
113    char ig[] = {1, 2, 3, 4};
114    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
115    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
116    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
117    char ii[] = {1, 1, 2};
118    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
119}
120
121int main() {
122    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
123    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
124}
125