Home | History | Annotate | Download | only in func.search.bmh
      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 
     41 template <typename T> struct MyHash {
     42     size_t operator () (T t) const { return static_cast<size_t>(t); }
     43 };
     44 
     45 template <typename Iter1, typename Iter2>
     46 void 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 
     53 template <class Iter1, class Iter2>
     54 void
     55 test()
     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 
     87 template <class Iter1, class Iter2>
     88 void
     89 test2()
     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 
    121 int 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