test/std/experimental/func/func.searchers/func.searchers.boyer_moore_horspool/hash.pred.pass.cpp

   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_horspool searcher
  15 // template<class RandomAccessIterator1,
  16 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
  17 //          class BinaryPredicate = equal_to<>>
  18 // class boyer_moore_horspool_searcher {
  19 // public:
  20 //   boyer_moore_horspool_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 #include <experimental/algorithm>
  35 #include <experimental/functional>
  36 #include <cassert>
  37
  38 #include "test_iterators.h"
  39
  40 template <typename T> struct MyHash {
  41         size_t operator () (T t) const { return static_cast<size_t>(t); }
  42 };
  43
  44 struct count_equal
  45 {
  46     static unsigned count;
  47     template <class T>
  48     bool operator()(const T& x, const T& y) const
  49         {++count; return x == y;}
  50 };
  51
  52 unsigned count_equal::count = 0;
  53
  54 template <typename Iter1, typename Iter2>
  55 void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) {
  56     std::experimental::boyer_moore_horspool_searcher<Iter2,
  57                  MyHash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>,
  58                  count_equal>
  59           s{b2, e2};
  60     count_equal::count = 0;
  61     assert(result == std::experimental::search(b1, e1, s));
  62     assert(count_equal::count <= max_count);
  63 }
  64
  65 template <class Iter1, class Iter2>
  66 void
  67 test()
  68 {
  69     int ia[] = {0, 1, 2, 3, 4, 5};
  70     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
  71     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
  72     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
  73     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
  74     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
  75     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
  76     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
  77     do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
  78     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
  79     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
  80     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
  81     do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
  82     do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
  83     int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
  84     const unsigned sb = sizeof(ib)/sizeof(ib[0]);
  85     int ic[] = {1};
  86     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
  87     int id[] = {1, 2};
  88     do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
  89     int ie[] = {1, 2, 3};
  90     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
  91     int ig[] = {1, 2, 3, 4};
  92     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
  93     int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
  94     const unsigned sh = sizeof(ih)/sizeof(ih[0]);
  95     int ii[] = {1, 1, 2};
  96     do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
  97 }
  98
  99 template <class Iter1, class Iter2>
 100 void
 101 test2()
 102 {
 103     char ia[] = {0, 1, 2, 3, 4, 5};
 104     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
 105     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
 106     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
 107     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
 108     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
 109     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
 110     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
 111     do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
 112     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
 113     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
 114     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
 115     do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
 116     do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
 117     char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
 118     const unsigned sb = sizeof(ib)/sizeof(ib[0]);
 119     char ic[] = {1};
 120     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
 121     char id[] = {1, 2};
 122     do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
 123     char ie[] = {1, 2, 3};
 124     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
 125     char ig[] = {1, 2, 3, 4};
 126     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
 127     char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
 128     const unsigned sh = sizeof(ih)/sizeof(ih[0]);
 129     char ii[] = {1, 1, 2};
 130     do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
 131 }
 132
 133 int main() {
 134     test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
 135     test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
 136 }