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
11
12// <functional>
13
14// boyer_moore searcher
15// template<class RandomAccessIterator1,
16//          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
17//          class BinaryPredicate = equal_to<>>
18// class boyer_moore_searcher {
19// public:
20//   boyer_moore_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
21//                        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
22//
23//   template<class RandomAccessIterator2>
24//   pair<RandomAccessIterator2, RandomAccessIterator2>
25//   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
26//
27// private:
28//   RandomAccessIterator1 pat_first_; // exposition only
29//   RandomAccessIterator1 pat_last_;  // exposition only
30//   Hash                  hash_;      // exposition only
31//   BinaryPredicate       pred_;      // exposition only
32// };
33
34
35#include <experimental/algorithm>
36#include <experimental/functional>
37#include <cassert>
38
39#include "test_iterators.h"
40
41template <typename Iter1, typename Iter2>
42void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result) {
43    std::experimental::boyer_moore_searcher<Iter2> s{b2, e2};
44    assert(result == std::experimental::search(b1, e1, s));
45}
46
47template <class Iter1, class Iter2>
48void
49test()
50{
51    int ia[] = {0, 1, 2, 3, 4, 5};
52    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
53    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia));
54    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia));
55    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1));
56    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia));
57    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
58    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
59    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia));
60    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1));
61    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3));
62    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia));
63    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1));
64    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1));
65    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
66    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
67    int ic[] = {1};
68    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1));
69    int id[] = {1, 2};
70    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1));
71    int ie[] = {1, 2, 3};
72    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4));
73    int ig[] = {1, 2, 3, 4};
74    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8));
75    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
76    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
77    int ii[] = {1, 1, 2};
78    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3));
79    int ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
80    const unsigned sj = sizeof(ij)/sizeof(ij[0]);
81    int ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
82    const unsigned sk = sizeof(ik)/sizeof(ik[0]);
83    do_search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk), Iter1(ij+6));
84}
85
86template <class Iter1, class Iter2>
87void
88test2()
89{
90    char ia[] = {0, 1, 2, 3, 4, 5};
91    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
92    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia));
93    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia));
94    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1));
95    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia));
96    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
97    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2));
98    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia));
99    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1));
100    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3));
101    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia));
102    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1));
103    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1));
104    char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
105    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
106    char ic[] = {1};
107    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1));
108    char id[] = {1, 2};
109    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1));
110    char ie[] = {1, 2, 3};
111    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4));
112    char ig[] = {1, 2, 3, 4};
113    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8));
114    char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
115    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
116    char ii[] = {1, 1, 2};
117    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3));
118    char ij[] = {0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
119    const unsigned sj = sizeof(ij)/sizeof(ij[0]);
120    char ik[] = {0, 0, 0, 0, 1, 1, 1, 1, 0, 0};
121    const unsigned sk = sizeof(ik)/sizeof(ik[0]);
122    do_search(Iter1(ij), Iter1(ij+sj), Iter2(ik), Iter2(ik+sk), Iter1(ij+6));
123}
124
125int main() {
126    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
127    test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
128}
129