/usr/include/boost/range/algorithm
Edit: /usr/include/boost/range/algorithm/search_n.hpp (13554B)
// 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
#include
#include
#include
#include
#include
#include
#include
namespace boost
{
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
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::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
inline RandomAccessIterator
search_n_impl(RandomAccessIterator first, RandomAccessIterator last,
Integer count, const Value& value,
std::random_access_iterator_tag)
{
typedef typename std::iterator_traits::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
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::difference_type difference_t;
while (first != last && !static_cast(pred(*first, value)))
++first;
while (first != last)
{
difference_t n = count;
ForwardIterator i = first;
++i;
while (i != last && n != 1 && static_cast(pred(*i, value)))
{
++i;
--n;
}
if (n == 1)
return first;
if (i == last)
return last;
first = ++i;
while (first != last && !static_cast(pred(*first, value)))
++first;
}
return last;
}
// search_n for random-access iterators using a binary predicate
// to determine a match
template
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::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(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
inline ForwardIterator
search_n_impl(ForwardIterator first, ForwardIterator last,
Integer count, const Value& value)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept));
BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept));
BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept::value_type>));
//BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept2::value_type, Value>));
typedef typename std::iterator_traits::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
inline ForwardIterator
search_n_pred_impl(ForwardIterator first, ForwardIterator last,
Integer count, const Value& value,
BinaryPredicate pred)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept));
BOOST_RANGE_CONCEPT_ASSERT((
BinaryPredicateConcept<
BinaryPredicate,
typename std::iterator_traits::value_type,
Value>
));
typedef typename std::iterator_traits::iterator_category cat_t;
if (count <= 0)
return first;
if (count == 1)
{
while (first != last && !static_cast(pred(*first, value)))
++first;
return first;
}
return range_detail::search_n_pred_impl(first, last, count,
value, pred, cat_t());
}
} // namespace range_detail
namespace range {
/// \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::type
search_n(ForwardRange& rng, Integer count, const Value& value)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept));
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::type
search_n(const ForwardRange& rng, Integer count, const Value& value)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept));
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::type
search_n(ForwardRange& rng, Integer count, const Value& value,
BinaryPredicate binary_pred)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept));
BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept::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::type
search_n(const ForwardRange& rng, Integer count, const Value& value,
BinaryPredicate binary_pred)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept));
BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept::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::type
search_n(ForwardRange& rng, Integer count, const Value& value)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept));
return range_return::
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::type
search_n(const ForwardRange& rng, Integer count, const Value& value)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept));
return range_return::
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::type
search_n(ForwardRange& rng, Integer count, const Value& value,
BinaryPredicate pred)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept));
BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept::type,
const Value&>));
return range_return::
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::type
search_n(const ForwardRange& rng, Integer count, const Value& value,
BinaryPredicate pred)
{
BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept));
BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept::type,
const Value&>));
return range_return::
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