| // Copyright Neil Groves 2009. Use, modification and |
| // distribution is subject to the Boost Software License, Version |
| // 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // |
| // For more information, see http://www.boost.org/libs/range/ |
| // |
| #ifndef BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED |
| #define BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED |
| |
| #include <boost/concept_check.hpp> |
| #include <boost/range/begin.hpp> |
| #include <boost/range/end.hpp> |
| #include <boost/range/concepts.hpp> |
| #include <boost/range/detail/range_return.hpp> |
| #include <boost/range/value_type.hpp> |
| #include <iterator> |
| #include <algorithm> |
| |
| namespace boost |
| { |
| namespace range |
| { |
| |
| namespace range_detail |
| { |
| // Rationale: search_n is implemented rather than delegate to |
| // the standard library implementation because some standard |
| // library implementations are broken eg. MSVC. |
| |
| // search_n forward iterator version |
| template<typename ForwardIterator, typename Integer, typename Value> |
| inline ForwardIterator |
| search_n_impl(ForwardIterator first, ForwardIterator last, Integer count, |
| const Value& value, std::forward_iterator_tag) |
| { |
| first = std::find(first, last, value); |
| while (first != last) |
| { |
| typename std::iterator_traits<ForwardIterator>::difference_type n = count; |
| ForwardIterator i = first; |
| ++i; |
| while (i != last && n != 1 && *i==value) |
| { |
| ++i; |
| --n; |
| } |
| if (n == 1) |
| return first; |
| if (i == last) |
| return last; |
| first = std::find(++i, last, value); |
| } |
| return last; |
| } |
| |
| // search_n random-access iterator version |
| template<typename RandomAccessIterator, typename Integer, typename Value> |
| inline RandomAccessIterator |
| search_n_impl(RandomAccessIterator first, RandomAccessIterator last, |
| Integer count, const Value& value, |
| std::random_access_iterator_tag) |
| { |
| typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t; |
| |
| difference_t tail_size = last - first; |
| const difference_t pattern_size = count; |
| |
| if (tail_size < pattern_size) |
| return last; |
| |
| const difference_t skip_offset = pattern_size - 1; |
| RandomAccessIterator look_ahead = first + skip_offset; |
| tail_size -= pattern_size; |
| |
| while (1) |
| { |
| // look_ahead here is pointing to the last element of the |
| // next possible match |
| while (!(*look_ahead == value)) // skip loop... |
| { |
| if (tail_size < pattern_size) |
| return last; // no match |
| look_ahead += pattern_size; |
| tail_size -= pattern_size; |
| } |
| difference_t remainder = skip_offset; |
| for (RandomAccessIterator back_track = look_ahead - 1; |
| *back_track == value; --back_track) |
| { |
| if (--remainder == 0) |
| { |
| return look_ahead - skip_offset; // matched |
| } |
| } |
| if (remainder > tail_size) |
| return last; // no match |
| look_ahead += remainder; |
| tail_size -= remainder; |
| } |
| |
| return last; |
| } |
| |
| // search_n for forward iterators using a binary predicate |
| // to determine a match |
| template<typename ForwardIterator, typename Integer, typename Value, |
| typename BinaryPredicate> |
| inline ForwardIterator |
| search_n_pred_impl(ForwardIterator first, ForwardIterator last, |
| Integer count, const Value& value, |
| BinaryPredicate pred, std::forward_iterator_tag) |
| { |
| typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_t; |
| |
| while (first != last && !static_cast<bool>(pred(*first, value))) |
| ++first; |
| |
| while (first != last) |
| { |
| difference_t n = count; |
| ForwardIterator i = first; |
| ++i; |
| while (i != last && n != 1 && static_cast<bool>(pred(*i, value))) |
| { |
| ++i; |
| --n; |
| } |
| if (n == 1) |
| return first; |
| if (i == last) |
| return last; |
| first = ++i; |
| while (first != last && !static_cast<bool>(pred(*first, value))) |
| ++first; |
| } |
| return last; |
| } |
| |
| // search_n for random-access iterators using a binary predicate |
| // to determine a match |
| template<typename RandomAccessIterator, typename Integer, |
| typename Value, typename BinaryPredicate> |
| inline RandomAccessIterator |
| search_n_pred_impl(RandomAccessIterator first, RandomAccessIterator last, |
| Integer count, const Value& value, |
| BinaryPredicate pred, std::random_access_iterator_tag) |
| { |
| typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t; |
| |
| difference_t tail_size = last - first; |
| const difference_t pattern_size = count; |
| |
| if (tail_size < pattern_size) |
| return last; |
| |
| const difference_t skip_offset = pattern_size - 1; |
| RandomAccessIterator look_ahead = first + skip_offset; |
| tail_size -= pattern_size; |
| |
| while (1) |
| { |
| // look_ahead points to the last element of the next |
| // possible match |
| while (!static_cast<bool>(pred(*look_ahead, value))) // skip loop |
| { |
| if (tail_size < pattern_size) |
| return last; // no match |
| look_ahead += pattern_size; |
| tail_size -= pattern_size; |
| } |
| difference_t remainder = skip_offset; |
| for (RandomAccessIterator back_track = look_ahead - 1; |
| pred(*back_track, value); --back_track) |
| { |
| if (--remainder == 0) |
| return look_ahead -= skip_offset; // success |
| } |
| if (remainder > tail_size) |
| { |
| return last; // no match |
| } |
| look_ahead += remainder; |
| tail_size -= remainder; |
| } |
| } |
| |
| template<typename ForwardIterator, typename Integer, typename Value> |
| inline ForwardIterator |
| search_n_impl(ForwardIterator first, ForwardIterator last, |
| Integer count, const Value& value) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>)); |
| BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept<Value>)); |
| BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept<typename std::iterator_traits<ForwardIterator>::value_type>)); |
| //BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept2<typename std::iterator_traits<ForwardIterator>::value_type, Value>)); |
| |
| typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t; |
| |
| if (count <= 0) |
| return first; |
| if (count == 1) |
| return std::find(first, last, value); |
| return range_detail::search_n_impl(first, last, count, value, cat_t()); |
| } |
| |
| template<typename ForwardIterator, typename Integer, typename Value, |
| typename BinaryPredicate> |
| inline ForwardIterator |
| search_n_pred_impl(ForwardIterator first, ForwardIterator last, |
| Integer count, const Value& value, |
| BinaryPredicate pred) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>)); |
| BOOST_RANGE_CONCEPT_ASSERT(( |
| BinaryPredicateConcept< |
| BinaryPredicate, |
| typename std::iterator_traits<ForwardIterator>::value_type, |
| Value> |
| )); |
| |
| typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t; |
| |
| if (count <= 0) |
| return first; |
| if (count == 1) |
| { |
| while (first != last && !static_cast<bool>(pred(*first, value))) |
| ++first; |
| return first; |
| } |
| return range_detail::search_n_pred_impl(first, last, count, |
| value, pred, cat_t()); |
| } |
| } // namespace range_detail |
| |
| /// \brief template function search |
| /// |
| /// range-based version of the search std algorithm |
| /// |
| /// \pre ForwardRange is a model of the ForwardRangeConcept |
| /// \pre Integer is an integral type |
| /// \pre Value is a model of the EqualityComparableConcept |
| /// \pre ForwardRange's value type is a model of the EqualityComparableConcept |
| /// \pre Object's of ForwardRange's value type can be compared for equality with Objects of type Value |
| template< class ForwardRange, class Integer, class Value > |
| inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type |
| search_n(ForwardRange& rng, Integer count, const Value& value) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>)); |
| return range_detail::search_n_impl(boost::begin(rng),boost::end(rng), count, value); |
| } |
| |
| /// \overload |
| template< class ForwardRange, class Integer, class Value > |
| inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type |
| search_n(const ForwardRange& rng, Integer count, const Value& value) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>)); |
| return range_detail::search_n_impl(boost::begin(rng), boost::end(rng), count, value); |
| } |
| |
| /// \overload |
| template< class ForwardRange, class Integer, class Value, |
| class BinaryPredicate > |
| inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type |
| search_n(ForwardRange& rng, Integer count, const Value& value, |
| BinaryPredicate binary_pred) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>)); |
| BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, |
| BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type, const Value&>)); |
| return range_detail::search_n_pred_impl(boost::begin(rng), boost::end(rng), |
| count, value, binary_pred); |
| } |
| |
| /// \overload |
| template< class ForwardRange, class Integer, class Value, |
| class BinaryPredicate > |
| inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type |
| search_n(const ForwardRange& rng, Integer count, const Value& value, |
| BinaryPredicate binary_pred) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>)); |
| BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, |
| BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type, const Value&>)); |
| return range_detail::search_n_pred_impl(boost::begin(rng), boost::end(rng), |
| count, value, binary_pred); |
| } |
| |
| // range_return overloads |
| |
| /// \overload |
| template< range_return_value re, class ForwardRange, class Integer, |
| class Value > |
| inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type |
| search_n(ForwardRange& rng, Integer count, const Value& value) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>)); |
| return range_return<ForwardRange,re>:: |
| pack(range_detail::search_n_impl(boost::begin(rng),boost::end(rng), |
| count, value), |
| rng); |
| } |
| |
| /// \overload |
| template< range_return_value re, class ForwardRange, class Integer, |
| class Value > |
| inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type |
| search_n(const ForwardRange& rng, Integer count, const Value& value) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>)); |
| return range_return<const ForwardRange,re>:: |
| pack(range_detail::search_n_impl(boost::begin(rng), boost::end(rng), |
| count, value), |
| rng); |
| } |
| |
| /// \overload |
| template< range_return_value re, class ForwardRange, class Integer, |
| class Value, class BinaryPredicate > |
| inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type |
| search_n(ForwardRange& rng, Integer count, const Value& value, |
| BinaryPredicate pred) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>)); |
| BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, |
| BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type, |
| const Value&>)); |
| return range_return<ForwardRange,re>:: |
| pack(range_detail::search_n_pred_impl(boost::begin(rng), |
| boost::end(rng), |
| count, value, pred), |
| rng); |
| } |
| |
| /// \overload |
| template< range_return_value re, class ForwardRange, class Integer, |
| class Value, class BinaryPredicate > |
| inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type |
| search_n(const ForwardRange& rng, Integer count, const Value& value, |
| BinaryPredicate pred) |
| { |
| BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>)); |
| BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate, |
| BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type, |
| const Value&>)); |
| return range_return<const ForwardRange,re>:: |
| pack(range_detail::search_n_pred_impl(boost::begin(rng), |
| boost::end(rng), |
| count, value, pred), |
| rng); |
| } |
| |
| } // namespace range |
| using range::search_n; |
| } // namespace boost |
| |
| #endif // include guard |