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