1 | // Copyright Neil Groves 2009. Use, modification and |
2 | // distribution is subject to the Boost Software License, Version |
3 | // 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
4 | // http://www.boost.org/LICENSE_1_0.txt) |
5 | // |
6 | // |
7 | // For more information, see http://www.boost.org/libs/range/ |
8 | // |
9 | #ifndef BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED |
10 | #define BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED |
11 | |
12 | #include <boost/concept_check.hpp> |
13 | #include <boost/range/begin.hpp> |
14 | #include <boost/range/end.hpp> |
15 | #include <boost/range/concepts.hpp> |
16 | #include <boost/range/detail/range_return.hpp> |
17 | #include <boost/range/value_type.hpp> |
18 | #include <iterator> |
19 | #include <algorithm> |
20 | |
21 | namespace boost |
22 | { |
23 | |
24 | namespace range_detail |
25 | { |
26 | // Rationale: search_n is implemented rather than delegate to |
27 | // the standard library implementation because some standard |
28 | // library implementations are broken eg. MSVC. |
29 | |
30 | // search_n forward iterator version |
31 | template<typename ForwardIterator, typename Integer, typename Value> |
32 | inline ForwardIterator |
33 | search_n_impl(ForwardIterator first, ForwardIterator last, Integer count, |
34 | const Value& value, std::forward_iterator_tag) |
35 | { |
36 | first = std::find(first, last, value); |
37 | while (first != last) |
38 | { |
39 | typename std::iterator_traits<ForwardIterator>::difference_type n = count; |
40 | ForwardIterator i = first; |
41 | ++i; |
42 | while (i != last && n != 1 && *i==value) |
43 | { |
44 | ++i; |
45 | --n; |
46 | } |
47 | if (n == 1) |
48 | return first; |
49 | if (i == last) |
50 | return last; |
51 | first = std::find(++i, last, value); |
52 | } |
53 | return last; |
54 | } |
55 | |
56 | // search_n random-access iterator version |
57 | template<typename RandomAccessIterator, typename Integer, typename Value> |
58 | inline RandomAccessIterator |
59 | search_n_impl(RandomAccessIterator first, RandomAccessIterator last, |
60 | Integer count, const Value& value, |
61 | std::random_access_iterator_tag) |
62 | { |
63 | typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t; |
64 | |
65 | difference_t tail_size = last - first; |
66 | const difference_t pattern_size = count; |
67 | |
68 | if (tail_size < pattern_size) |
69 | return last; |
70 | |
71 | const difference_t skip_offset = pattern_size - 1; |
72 | RandomAccessIterator look_ahead = first + skip_offset; |
73 | tail_size -= pattern_size; |
74 | |
75 | while (1) |
76 | { |
77 | // look_ahead here is pointing to the last element of the |
78 | // next possible match |
79 | while (!(*look_ahead == value)) // skip loop... |
80 | { |
81 | if (tail_size < pattern_size) |
82 | return last; // no match |
83 | look_ahead += pattern_size; |
84 | tail_size -= pattern_size; |
85 | } |
86 | difference_t remainder = skip_offset; |
87 | for (RandomAccessIterator back_track = look_ahead - 1; |
88 | *back_track == value; --back_track) |
89 | { |
90 | if (--remainder == 0) |
91 | { |
92 | return look_ahead - skip_offset; // matched |
93 | } |
94 | } |
95 | if (remainder > tail_size) |
96 | return last; // no match |
97 | look_ahead += remainder; |
98 | tail_size -= remainder; |
99 | } |
100 | |
101 | return last; |
102 | } |
103 | |
104 | // search_n for forward iterators using a binary predicate |
105 | // to determine a match |
106 | template<typename ForwardIterator, typename Integer, typename Value, |
107 | typename BinaryPredicate> |
108 | inline ForwardIterator |
109 | search_n_pred_impl(ForwardIterator first, ForwardIterator last, |
110 | Integer count, const Value& value, |
111 | BinaryPredicate pred, std::forward_iterator_tag) |
112 | { |
113 | typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_t; |
114 | |
115 | while (first != last && !static_cast<bool>(pred(*first, value))) |
116 | ++first; |
117 | |
118 | while (first != last) |
119 | { |
120 | difference_t n = count; |
121 | ForwardIterator i = first; |
122 | ++i; |
123 | while (i != last && n != 1 && static_cast<bool>(pred(*i, value))) |
124 | { |
125 | ++i; |
126 | --n; |
127 | } |
128 | if (n == 1) |
129 | return first; |
130 | if (i == last) |
131 | return last; |
132 | first = ++i; |
133 | while (first != last && !static_cast<bool>(pred(*first, value))) |
134 | ++first; |
135 | } |
136 | return last; |
137 | } |
138 | |
139 | // search_n for random-access iterators using a binary predicate |
140 | // to determine a match |
141 | template<typename RandomAccessIterator, typename Integer, |
142 | typename Value, typename BinaryPredicate> |
143 | inline RandomAccessIterator |
144 | search_n_pred_impl(RandomAccessIterator first, RandomAccessIterator last, |
145 | Integer count, const Value& value, |
146 | BinaryPredicate pred, std::random_access_iterator_tag) |
147 | { |
148 | typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t; |
149 | |
150 | difference_t tail_size = last - first; |
151 | const difference_t pattern_size = count; |
152 | |
153 | if (tail_size < pattern_size) |
154 | return last; |
155 | |
156 | const difference_t skip_offset = pattern_size - 1; |
157 | RandomAccessIterator look_ahead = first + skip_offset; |
158 | tail_size -= pattern_size; |
159 | |
160 | while (1) |
161 | { |
162 | // look_ahead points to the last element of the next |
163 | // possible match |
164 | while (!static_cast<bool>(pred(*look_ahead, value))) // skip loop |
165 | { |
166 | if (tail_size < pattern_size) |
167 | return last; // no match |
168 | look_ahead += pattern_size; |
169 | tail_size -= pattern_size; |
170 | } |
171 | difference_t remainder = skip_offset; |
172 | for (RandomAccessIterator back_track = look_ahead - 1; |
173 | pred(*back_track, value); --back_track) |
174 | { |
175 | if (--remainder == 0) |
176 | return look_ahead -= skip_offset; // success |
177 | } |
178 | if (remainder > tail_size) |
179 | { |
180 | return last; // no match |
181 | } |
182 | look_ahead += remainder; |
183 | tail_size -= remainder; |
184 | } |
185 | } |
186 | |
187 | template<typename ForwardIterator, typename Integer, typename Value> |
188 | inline ForwardIterator |
189 | search_n_impl(ForwardIterator first, ForwardIterator last, |
190 | Integer count, const Value& value) |
191 | { |
192 | BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>)); |
193 | BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept<Value>)); |
194 | BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept<typename std::iterator_traits<ForwardIterator>::value_type>)); |
195 | //BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept2<typename std::iterator_traits<ForwardIterator>::value_type, Value>)); |
196 | |
197 | typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t; |
198 | |
199 | if (count <= 0) |
200 | return first; |
201 | if (count == 1) |
202 | return std::find(first, last, value); |
203 | return range_detail::search_n_impl(first, last, count, value, cat_t()); |
204 | } |
205 | |
206 | template<typename ForwardIterator, typename Integer, typename Value, |
207 | typename BinaryPredicate> |
208 | inline ForwardIterator |
209 | search_n_pred_impl(ForwardIterator first, ForwardIterator last, |
210 | Integer count, const Value& value, |
211 | BinaryPredicate pred) |
212 | { |
213 | BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>)); |
214 | BOOST_RANGE_CONCEPT_ASSERT(( |
215 | BinaryPredicateConcept< |
216 | BinaryPredicate, |
217 | typename std::iterator_traits<ForwardIterator>::value_type, |
218 | Value> |
219 | )); |
220 | |
221 | typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t; |
222 | |
223 | if (count <= 0) |
224 | return first; |
225 | if (count == 1) |
226 | { |
227 | while (first != last && !static_cast<bool>(pred(*first, value))) |
228 | ++first; |
229 | return first; |
230 | } |
231 | return range_detail::search_n_pred_impl(first, last, count, |
232 | value, pred, cat_t()); |
233 | } |
234 | } // namespace range_detail |
235 | |
236 | namespace range { |
237 | |
238 | /// \brief template function search |
239 | /// |
240 | /// range-based version of the search std algorithm |
241 | /// |
242 | /// \pre ForwardRange is a model of the ForwardRangeConcept |
243 | /// \pre Integer is an integral type |
244 | /// \pre Value is a model of the EqualityComparableConcept |
245 | /// \pre ForwardRange's value type is a model of the EqualityComparableConcept |
246 | /// \pre Object's of ForwardRange's value type can be compared for equality with Objects of type Value |
247 | template< class ForwardRange, class Integer, class Value > |
248 | inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type |
249 | search_n(ForwardRange& rng, Integer count, const Value& value) |
250 | { |
251 | BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>)); |
252 | return range_detail::search_n_impl(boost::begin(rng),boost::end(rng), count, value); |
253 | } |
254 | |
255 | /// \overload |
256 | template< class ForwardRange, class Integer, class Value > |
257 | inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type |
258 | search_n(const ForwardRange& rng, Integer count, const Value& value) |
259 | { |
260 | BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>)); |
261 | return range_detail::search_n_impl(boost::begin(rng), boost::end(rng), count, value); |
262 | } |
263 | |
264 | /// \overload |
265 | template< class ForwardRange, class Integer, class Value, |
266 | class BinaryPredicate > |
267 | inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type |
268 | search_n(ForwardRange& rng, Integer count, const Value& value, |
269 | BinaryPredicate binary_pred) |
270 | { |
271 | BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>)); |
272 | BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, |
273 | BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type, const Value&>)); |
274 | return range_detail::search_n_pred_impl(boost::begin(rng), boost::end(rng), |
275 | count, value, binary_pred); |
276 | } |
277 | |
278 | /// \overload |
279 | template< class ForwardRange, class Integer, class Value, |
280 | class BinaryPredicate > |
281 | inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type |
282 | search_n(const ForwardRange& rng, Integer count, const Value& value, |
283 | BinaryPredicate binary_pred) |
284 | { |
285 | BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>)); |
286 | BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, |
287 | BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type, const Value&>)); |
288 | return range_detail::search_n_pred_impl(boost::begin(rng), boost::end(rng), |
289 | count, value, binary_pred); |
290 | } |
291 | |
292 | // range_return overloads |
293 | |
294 | /// \overload |
295 | template< range_return_value re, class ForwardRange, class Integer, |
296 | class Value > |
297 | inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type |
298 | search_n(ForwardRange& rng, Integer count, const Value& value) |
299 | { |
300 | BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>)); |
301 | return range_return<ForwardRange,re>:: |
302 | pack(range_detail::search_n_impl(boost::begin(rng),boost::end(rng), |
303 | count, value), |
304 | rng); |
305 | } |
306 | |
307 | /// \overload |
308 | template< range_return_value re, class ForwardRange, class Integer, |
309 | class Value > |
310 | inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type |
311 | search_n(const ForwardRange& rng, Integer count, const Value& value) |
312 | { |
313 | BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>)); |
314 | return range_return<const ForwardRange,re>:: |
315 | pack(range_detail::search_n_impl(boost::begin(rng), boost::end(rng), |
316 | count, value), |
317 | rng); |
318 | } |
319 | |
320 | /// \overload |
321 | template< range_return_value re, class ForwardRange, class Integer, |
322 | class Value, class BinaryPredicate > |
323 | inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type |
324 | search_n(ForwardRange& rng, Integer count, const Value& value, |
325 | BinaryPredicate pred) |
326 | { |
327 | BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>)); |
328 | BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, |
329 | BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type, |
330 | const Value&>)); |
331 | return range_return<ForwardRange,re>:: |
332 | pack(range_detail::search_n_pred_impl(boost::begin(rng), |
333 | boost::end(rng), |
334 | count, value, pred), |
335 | rng); |
336 | } |
337 | |
338 | /// \overload |
339 | template< range_return_value re, class ForwardRange, class Integer, |
340 | class Value, class BinaryPredicate > |
341 | inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type |
342 | search_n(const ForwardRange& rng, Integer count, const Value& value, |
343 | BinaryPredicate pred) |
344 | { |
345 | BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>)); |
346 | BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, |
347 | BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type, |
348 | const Value&>)); |
349 | return range_return<const ForwardRange,re>:: |
350 | pack(range_detail::search_n_pred_impl(boost::begin(rng), |
351 | boost::end(rng), |
352 | count, value, pred), |
353 | rng); |
354 | } |
355 | |
356 | } // namespace range |
357 | using range::search_n; |
358 | } // namespace boost |
359 | |
360 | #endif // include guard |
361 | |