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// <functional>
11
12// UNSUPPORTED: c++98, c++03, c++11, c++14
13
14// default searcher
15// template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
16// class default_searcher {
17// public:
18//     default_searcher(_ForwardIterator __f, _ForwardIterator __l,
19//                             _BinaryPredicate __p = _BinaryPredicate())
20//         : __first_(__f), __last_(__l), __pred_(__p) {}
21//
22//     template <typename _ForwardIterator2>
23//     pair<_ForwardIterator2, _ForwardIterator2>
24//     operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const {
25//         return std::search(__f, __l, __first_, __last_, __pred_);
26//         }
27//
28// private:
29//     _ForwardIterator __first_;
30//     _ForwardIterator __last_;
31//     _BinaryPredicate __pred_;
32//     };
33
34
35#include <algorithm>
36#include <functional>
37#include <cassert>
38
39#include "test_iterators.h"
40
41struct count_equal
42{
43    static unsigned count;
44    template <class T>
45    bool operator()(const T& x, const T& y) const
46        {++count; return x == y;}
47};
48
49unsigned count_equal::count = 0;
50
51template <typename Iter1, typename Iter2>
52void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned max_count) {
53    std::default_searcher<Iter2, count_equal> s{b2, e2};
54    count_equal::count = 0;
55    assert(result == std::search(b1, e1, s));
56    assert(count_equal::count <= max_count);
57}
58
59template <class Iter1, class Iter2>
60void
61test()
62{
63    int ia[] = {0, 1, 2, 3, 4, 5};
64    const unsigned sa = sizeof(ia)/sizeof(ia[0]);
65    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
66    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
67    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
68    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
69    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
70    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
71    do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
72    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
73    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
74    do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
75    do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
76    do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
77    int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
78    const unsigned sb = sizeof(ib)/sizeof(ib[0]);
79    int ic[] = {1};
80    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
81    int id[] = {1, 2};
82    do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
83    int ie[] = {1, 2, 3};
84    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
85    int ig[] = {1, 2, 3, 4};
86    do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
87    int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
88    const unsigned sh = sizeof(ih)/sizeof(ih[0]);
89    int ii[] = {1, 1, 2};
90    do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
91}
92
93int main() {
94    test<forward_iterator<const int*>, forward_iterator<const int*> >();
95    test<forward_iterator<const int*>, bidirectional_iterator<const int*> >();
96    test<forward_iterator<const int*>, random_access_iterator<const int*> >();
97    test<bidirectional_iterator<const int*>, forward_iterator<const int*> >();
98    test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*> >();
99    test<bidirectional_iterator<const int*>, random_access_iterator<const int*> >();
100    test<random_access_iterator<const int*>, forward_iterator<const int*> >();
101    test<random_access_iterator<const int*>, bidirectional_iterator<const int*> >();
102    test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
103}
104