1 | // Boost.Range library |
2 | // |
3 | // Copyright Neil Groves 2009. Use, modification and |
4 | // distribution is subject to the Boost Software License, Version |
5 | // 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
6 | // http://www.boost.org/LICENSE_1_0.txt) |
7 | // |
8 | // |
9 | // For more information, see http://www.boost.org/libs/range/ |
10 | // |
11 | #include <boost/range/algorithm/search_n.hpp> |
12 | |
13 | #include <boost/test/test_tools.hpp> |
14 | #include <boost/test/unit_test.hpp> |
15 | |
16 | #include <boost/assign.hpp> |
17 | #include <algorithm> |
18 | #include <list> |
19 | #include <set> |
20 | #include <vector> |
21 | |
22 | namespace |
23 | { |
24 | template<typename ForwardIterator, typename Integer, typename Value> |
25 | inline ForwardIterator |
26 | reference_search_n(ForwardIterator first, ForwardIterator last, |
27 | Integer count, const Value& value) |
28 | { |
29 | if (count <= 0) |
30 | return first; |
31 | else if (count == 1) |
32 | return std::find(first, last, value); |
33 | else |
34 | { |
35 | first = std::find(first, last, value); |
36 | while (first != last) |
37 | { |
38 | typename std::iterator_traits<ForwardIterator>::difference_type n = count; |
39 | ForwardIterator i = first; |
40 | ++i; |
41 | while (i != last && n != 1 && *i==value) |
42 | { |
43 | ++i; |
44 | --n; |
45 | } |
46 | if (n == 1) |
47 | return first; |
48 | if (i == last) |
49 | return last; |
50 | first = std::find(++i, last, value); |
51 | } |
52 | } |
53 | return last; |
54 | } |
55 | |
56 | template<typename ForwardIterator, typename Integer, typename Value, |
57 | typename BinaryPredicate> |
58 | inline ForwardIterator |
59 | reference_search_n(ForwardIterator first, ForwardIterator last, |
60 | Integer count, const Value& value, |
61 | BinaryPredicate pred) |
62 | { |
63 | typedef typename std::iterator_traits< |
64 | ForwardIterator |
65 | >::iterator_category cat_t BOOST_RANGE_UNUSED; |
66 | |
67 | if (count <= 0) |
68 | return first; |
69 | if (count == 1) |
70 | { |
71 | while (first != last && !static_cast<bool>(pred(*first, value))) |
72 | ++first; |
73 | return first; |
74 | } |
75 | else |
76 | { |
77 | typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_t; |
78 | |
79 | while (first != last && !static_cast<bool>(pred(*first, value))) |
80 | ++first; |
81 | |
82 | while (first != last) |
83 | { |
84 | difference_t n = count; |
85 | ForwardIterator i = first; |
86 | ++i; |
87 | while (i != last && n != 1 && static_cast<bool>(pred(*i, value))) |
88 | { |
89 | ++i; |
90 | --n; |
91 | } |
92 | if (n == 1) |
93 | return first; |
94 | if (i == last) |
95 | return last; |
96 | first = ++i; |
97 | while (first != last && !static_cast<bool>(pred(*first, value))) |
98 | ++first; |
99 | } |
100 | } |
101 | return last; |
102 | } |
103 | |
104 | template< class Container1, class Value, class Pred > |
105 | void test_search_n_pred_impl(Container1& cont1, Value value, Pred pred) |
106 | { |
107 | typedef BOOST_DEDUCED_TYPENAME Container1::const_iterator const_iterator1_t; |
108 | typedef BOOST_DEDUCED_TYPENAME Container1::iterator iterator1_t; |
109 | |
110 | const Container1& ccont1 = cont1; |
111 | |
112 | for (std::size_t n = 0; n < cont1.size(); ++n) |
113 | { |
114 | iterator1_t it = boost::search_n(cont1, n, value, pred); |
115 | BOOST_CHECK( it == boost::search_n(boost::make_iterator_range(cont1), n, value, pred) ); |
116 | BOOST_CHECK( it == reference_search_n(cont1.begin(), cont1.end(), n, value, pred) ); |
117 | |
118 | const_iterator1_t cit = boost::search_n(ccont1, n, value, pred); |
119 | BOOST_CHECK( cit == boost::search_n(boost::make_iterator_range(ccont1), n, value, pred) ); |
120 | BOOST_CHECK( cit == reference_search_n(ccont1.begin(), ccont1.end(), n, value, pred) ); |
121 | } |
122 | } |
123 | |
124 | template< class Container1, class Value > |
125 | void test_search_n_impl(Container1& cont1, Value value) |
126 | { |
127 | typedef BOOST_DEDUCED_TYPENAME Container1::const_iterator const_iterator1_t; |
128 | typedef BOOST_DEDUCED_TYPENAME Container1::iterator iterator1_t; |
129 | |
130 | const Container1& ccont1 = cont1; |
131 | |
132 | for (std::size_t n = 0; n < cont1.size(); ++n) |
133 | { |
134 | iterator1_t it = boost::search_n(cont1, n, value); |
135 | BOOST_CHECK( it == boost::search_n(boost::make_iterator_range(cont1), n, value) ); |
136 | BOOST_CHECK( it == reference_search_n(cont1.begin(), cont1.end(), n, value) ); |
137 | |
138 | const_iterator1_t cit = boost::search_n(ccont1, n, value); |
139 | BOOST_CHECK( cit == boost::search_n(boost::make_iterator_range(ccont1), n, value) ); |
140 | BOOST_CHECK( cit == reference_search_n(ccont1.begin(), ccont1.end(), n, value) ); |
141 | } |
142 | |
143 | test_search_n_pred_impl(cont1, value, std::less<int>()); |
144 | test_search_n_pred_impl(cont1, value, std::greater<int>()); |
145 | test_search_n_pred_impl(cont1, value, std::equal_to<int>()); |
146 | test_search_n_pred_impl(cont1, value, std::not_equal_to<int>()); |
147 | } |
148 | |
149 | template< class Container1, class Container2 > |
150 | void test_search_n_impl() |
151 | { |
152 | using namespace boost::assign; |
153 | |
154 | Container1 cont1; |
155 | |
156 | test_search_n_impl(cont1, 1); |
157 | |
158 | cont1 += 1; |
159 | test_search_n_impl(cont1, 1); |
160 | test_search_n_impl(cont1, 0); |
161 | |
162 | cont1.clear(); |
163 | cont1 += 1,1; |
164 | test_search_n_impl(cont1, 1); |
165 | test_search_n_impl(cont1, 0); |
166 | |
167 | cont1 += 1,1,1; |
168 | test_search_n_impl(cont1, 1); |
169 | test_search_n_impl(cont1, 0); |
170 | |
171 | cont1.clear(); |
172 | cont1 += 1,2,3,4,5,6,7,8,9; |
173 | test_search_n_impl(cont1, 1); |
174 | test_search_n_impl(cont1, 2); |
175 | test_search_n_impl(cont1, 5); |
176 | test_search_n_impl(cont1, 9); |
177 | } |
178 | |
179 | void test_search_n() |
180 | { |
181 | test_search_n_impl< std::list<int>, std::list<int> >(); |
182 | test_search_n_impl< std::vector<int>, std::vector<int> >(); |
183 | test_search_n_impl< std::set<int>, std::set<int> >(); |
184 | test_search_n_impl< std::list<int>, std::vector<int> >(); |
185 | test_search_n_impl< std::vector<int>, std::list<int> >(); |
186 | } |
187 | } |
188 | |
189 | boost::unit_test::test_suite* |
190 | init_unit_test_suite(int argc, char* argv[]) |
191 | { |
192 | boost::unit_test::test_suite* test |
193 | = BOOST_TEST_SUITE( "RangeTestSuite.algorithm.search_n" ); |
194 | |
195 | test->add( BOOST_TEST_CASE( &test_search_n ) ); |
196 | |
197 | return test; |
198 | } |
199 | |