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
21namespace boost
22{
23
24namespace 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
236namespace 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
247template< class ForwardRange, class Integer, class Value >
248inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type
249search_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
256template< class ForwardRange, class Integer, class Value >
257inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type
258search_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
265template< class ForwardRange, class Integer, class Value,
266 class BinaryPredicate >
267inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type
268search_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
279template< class ForwardRange, class Integer, class Value,
280 class BinaryPredicate >
281inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type
282search_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
295template< range_return_value re, class ForwardRange, class Integer,
296 class Value >
297inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type
298search_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
308template< range_return_value re, class ForwardRange, class Integer,
309 class Value >
310inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type
311search_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
321template< range_return_value re, class ForwardRange, class Integer,
322 class Value, class BinaryPredicate >
323inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type
324search_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
339template< range_return_value re, class ForwardRange, class Integer,
340 class Value, class BinaryPredicate >
341inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type
342search_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

source code of boost/libs/range/include/boost/range/algorithm/search_n.hpp