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)
7 // For more information, see http://www.boost.org/libs/range/
9 #ifndef BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED
10 #define BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED
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>
24 namespace range_detail
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.
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)
36 first = std::find(first, last, value);
39 typename std::iterator_traits<ForwardIterator>::difference_type n = count;
40 ForwardIterator i = first;
42 while (i != last && n != 1 && *i==value)
51 first = std::find(++i, last, value);
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)
63 typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t;
65 difference_t tail_size = last - first;
66 const difference_t pattern_size = count;
68 if (tail_size < pattern_size)
71 const difference_t skip_offset = pattern_size - 1;
72 RandomAccessIterator look_ahead = first + skip_offset;
73 tail_size -= pattern_size;
77 // look_ahead here is pointing to the last element of the
78 // next possible match
79 while (!(*look_ahead == value)) // skip loop...
81 if (tail_size < pattern_size)
82 return last; // no match
83 look_ahead += pattern_size;
84 tail_size -= pattern_size;
86 difference_t remainder = skip_offset;
87 for (RandomAccessIterator back_track = look_ahead - 1;
88 *back_track == value; --back_track)
92 return look_ahead - skip_offset; // matched
95 if (remainder > tail_size)
96 return last; // no match
97 look_ahead += remainder;
98 tail_size -= remainder;
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)
113 typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_t;
115 while (first != last && !static_cast<bool>(pred(*first, value)))
118 while (first != last)
120 difference_t n = count;
121 ForwardIterator i = first;
123 while (i != last && n != 1 && static_cast<bool>(pred(*i, value)))
133 while (first != last && !static_cast<bool>(pred(*first, value)))
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)
148 typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t;
150 difference_t tail_size = last - first;
151 const difference_t pattern_size = count;
153 if (tail_size < pattern_size)
156 const difference_t skip_offset = pattern_size - 1;
157 RandomAccessIterator look_ahead = first + skip_offset;
158 tail_size -= pattern_size;
162 // look_ahead points to the last element of the next
164 while (!static_cast<bool>(pred(*look_ahead, value))) // skip loop
166 if (tail_size < pattern_size)
167 return last; // no match
168 look_ahead += pattern_size;
169 tail_size -= pattern_size;
171 difference_t remainder = skip_offset;
172 for (RandomAccessIterator back_track = look_ahead - 1;
173 pred(*back_track, value); --back_track)
175 if (--remainder == 0)
176 return look_ahead -= skip_offset; // success
178 if (remainder > tail_size)
180 return last; // no match
182 look_ahead += remainder;
183 tail_size -= remainder;
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)
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>));
197 typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t;
202 return std::find(first, last, value);
203 return range_detail::search_n_impl(first, last, count, value, cat_t());
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)
213 BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>));
214 BOOST_RANGE_CONCEPT_ASSERT((
215 BinaryPredicateConcept<
217 typename std::iterator_traits<ForwardIterator>::value_type,
221 typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t;
227 while (first != last && !static_cast<bool>(pred(*first, value)))
231 return range_detail::search_n_pred_impl(first, last, count,
232 value, pred, cat_t());
234 } // namespace range_detail
238 /// \brief template function search
240 /// range-based version of the search std algorithm
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)
251 BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
252 return range_detail::search_n_impl(boost::begin(rng),boost::end(rng), count, value);
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)
260 BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
261 return range_detail::search_n_impl(boost::begin(rng), boost::end(rng), count, value);
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)
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);
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)
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);
292 // range_return overloads
295 template< range_return_value re, class ForwardRange, class Integer,
297 inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type
298 search_n(ForwardRange& rng, Integer count, const Value& value)
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),
308 template< range_return_value re, class ForwardRange, class Integer,
310 inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type
311 search_n(const ForwardRange& rng, Integer count, const Value& value)
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),
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)
327 BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
328 BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
329 BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type,
331 return range_return<ForwardRange,re>::
332 pack(range_detail::search_n_pred_impl(boost::begin(rng),
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)
345 BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
346 BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
347 BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type,
349 return range_return<const ForwardRange,re>::
350 pack(range_detail::search_n_pred_impl(boost::begin(rng),
357 using range::search_n;
360 #endif // include guard