//  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