range/algorithm/search_n.hpp

0001 //  Copyright Neil Groves 2009. Use, modification and
0002 //  distribution is subject to the Boost Software License, Version
0003 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
0004 //  http://www.boost.org/LICENSE_1_0.txt)
0005 //
0006 //
0007 // For more information, see http://www.boost.org/libs/range/
0008 //
0009 #ifndef BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED
0010 #define BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED
0011
0012 #include <boost/concept_check.hpp>
0013 #include <boost/range/begin.hpp>
0014 #include <boost/range/end.hpp>
0015 #include <boost/range/concepts.hpp>
0016 #include <boost/range/detail/range_return.hpp>
0017 #include <boost/range/value_type.hpp>
0018 #include <iterator>
0019 #include <algorithm>
0020
0021 namespace boost
0022 {
0023
0024 namespace range_detail
0025 {
0026     // Rationale: search_n is implemented rather than delegate to
0027     // the standard library implementation because some standard
0028     // library implementations are broken eg. MSVC.
0029
0030     // search_n forward iterator version
0031     template<typename ForwardIterator, typename Integer, typename Value>
0032     inline ForwardIterator
0033     search_n_impl(ForwardIterator first, ForwardIterator last, Integer count,
0034                   const Value& value, std::forward_iterator_tag)
0035     {
0036         first = std::find(first, last, value);
0037         while (first != last)
0038         {
0039             typename std::iterator_traits<ForwardIterator>::difference_type n = count;
0040             ForwardIterator i = first;
0041             ++i;
0042             while (i != last && n != 1 && *i==value)
0043             {
0044                 ++i;
0045                 --n;
0046             }
0047             if (n == 1)
0048                 return first;
0049             if (i == last)
0050                 return last;
0051             first = std::find(++i, last, value);
0052         }
0053         return last;
0054     }
0055
0056     // search_n random-access iterator version
0057     template<typename RandomAccessIterator, typename Integer, typename Value>
0058     inline RandomAccessIterator
0059     search_n_impl(RandomAccessIterator first, RandomAccessIterator last,
0060                   Integer count, const Value& value,
0061                   std::random_access_iterator_tag)
0062     {
0063         typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t;
0064
0065         difference_t tail_size = last - first;
0066         const difference_t pattern_size = count;
0067
0068         if (tail_size < pattern_size)
0069             return last;
0070
0071         const difference_t skip_offset = pattern_size - 1;
0072         RandomAccessIterator look_ahead = first + skip_offset;
0073         tail_size -= pattern_size;
0074
0075         while (1)
0076         {
0077             // look_ahead here is pointing to the last element of the
0078             // next possible match
0079             while (!(*look_ahead == value)) // skip loop...
0080             {
0081                 if (tail_size < pattern_size)
0082                     return last; // no match
0083                 look_ahead += pattern_size;
0084                 tail_size -= pattern_size;
0085             }
0086             difference_t remainder = skip_offset;
0087             for (RandomAccessIterator back_track = look_ahead - 1;
0088                     *back_track == value; --back_track)
0089             {
0090                 if (--remainder == 0)
0091                 {
0092                     return look_ahead - skip_offset; // matched
0093                 }
0094             }
0095             if (remainder > tail_size)
0096                 return last; // no match
0097             look_ahead += remainder;
0098             tail_size -= remainder;
0099         }
0100
0101         return last;
0102     }
0103
0104     // search_n for forward iterators using a binary predicate
0105     // to determine a match
0106     template<typename ForwardIterator, typename Integer, typename Value,
0107              typename BinaryPredicate>
0108     inline ForwardIterator
0109     search_n_pred_impl(ForwardIterator first, ForwardIterator last,
0110                        Integer count, const Value& value,
0111                        BinaryPredicate pred, std::forward_iterator_tag)
0112     {
0113         typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_t;
0114
0115         while (first != last && !static_cast<bool>(pred(*first, value)))
0116             ++first;
0117
0118         while (first != last)
0119         {
0120             difference_t n = count;
0121             ForwardIterator i = first;
0122             ++i;
0123             while (i != last && n != 1 && static_cast<bool>(pred(*i, value)))
0124             {
0125                 ++i;
0126                 --n;
0127             }
0128             if (n == 1)
0129                 return first;
0130             if (i == last)
0131                 return last;
0132             first = ++i;
0133             while (first != last && !static_cast<bool>(pred(*first, value)))
0134                 ++first;
0135         }
0136         return last;
0137     }
0138
0139     // search_n for random-access iterators using a binary predicate
0140     // to determine a match
0141     template<typename RandomAccessIterator, typename Integer,
0142              typename Value, typename BinaryPredicate>
0143     inline RandomAccessIterator
0144     search_n_pred_impl(RandomAccessIterator first, RandomAccessIterator last,
0145                        Integer count, const Value& value,
0146                        BinaryPredicate pred, std::random_access_iterator_tag)
0147     {
0148         typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t;
0149
0150         difference_t tail_size = last - first;
0151         const difference_t pattern_size = count;
0152
0153         if (tail_size < pattern_size)
0154             return last;
0155
0156         const difference_t skip_offset = pattern_size - 1;
0157         RandomAccessIterator look_ahead = first + skip_offset;
0158         tail_size -= pattern_size;
0159
0160         while (1)
0161         {
0162             // look_ahead points to the last element of the next
0163             // possible match
0164             while (!static_cast<bool>(pred(*look_ahead, value))) // skip loop
0165             {
0166                 if (tail_size < pattern_size)
0167                     return last; // no match
0168                 look_ahead += pattern_size;
0169                 tail_size -= pattern_size;
0170             }
0171             difference_t remainder = skip_offset;
0172             for (RandomAccessIterator back_track = look_ahead - 1;
0173                     pred(*back_track, value); --back_track)
0174             {
0175                 if (--remainder == 0)
0176                     return look_ahead -= skip_offset; // success
0177             }
0178             if (remainder > tail_size)
0179             {
0180                 return last; // no match
0181             }
0182             look_ahead += remainder;
0183             tail_size -= remainder;
0184         }
0185     }
0186
0187     template<typename ForwardIterator, typename Integer, typename Value>
0188     inline ForwardIterator
0189     search_n_impl(ForwardIterator first, ForwardIterator last,
0190                   Integer count, const Value& value)
0191     {
0192         BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>));
0193         BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept<Value>));
0194         BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept<typename std::iterator_traits<ForwardIterator>::value_type>));
0195         //BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept2<typename std::iterator_traits<ForwardIterator>::value_type, Value>));
0196
0197         typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t;
0198
0199         if (count <= 0)
0200             return first;
0201         if (count == 1)
0202             return std::find(first, last, value);
0203         return range_detail::search_n_impl(first, last, count, value, cat_t());
0204     }
0205
0206     template<typename ForwardIterator, typename Integer, typename Value,
0207              typename BinaryPredicate>
0208     inline ForwardIterator
0209     search_n_pred_impl(ForwardIterator first, ForwardIterator last,
0210                        Integer count, const Value& value,
0211                        BinaryPredicate pred)
0212     {
0213         BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>));
0214         BOOST_RANGE_CONCEPT_ASSERT((
0215             BinaryPredicateConcept<
0216                 BinaryPredicate,
0217                 typename std::iterator_traits<ForwardIterator>::value_type,
0218                 Value>
0219             ));
0220
0221         typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t;
0222
0223         if (count <= 0)
0224             return first;
0225         if (count == 1)
0226         {
0227             while (first != last && !static_cast<bool>(pred(*first, value)))
0228                 ++first;
0229             return first;
0230         }
0231         return range_detail::search_n_pred_impl(first, last, count,
0232                                                 value, pred, cat_t());
0233     }
0234 } // namespace range_detail
0235
0236 namespace range {
0237
0238 /// \brief template function search
0239 ///
0240 /// range-based version of the search std algorithm
0241 ///
0242 /// \pre ForwardRange is a model of the ForwardRangeConcept
0243 /// \pre Integer is an integral type
0244 /// \pre Value is a model of the EqualityComparableConcept
0245 /// \pre ForwardRange's value type is a model of the EqualityComparableConcept
0246 /// \pre Object's of ForwardRange's value type can be compared for equality with Objects of type Value
0247 template< class ForwardRange, class Integer, class Value >
0248 inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type
0249 search_n(ForwardRange& rng, Integer count, const Value& value)
0250 {
0251     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
0252     return range_detail::search_n_impl(boost::begin(rng),boost::end(rng), count, value);
0253 }
0254
0255 /// \overload
0256 template< class ForwardRange, class Integer, class Value >
0257 inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type
0258 search_n(const ForwardRange& rng, Integer count, const Value& value)
0259 {
0260     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
0261     return range_detail::search_n_impl(boost::begin(rng), boost::end(rng), count, value);
0262 }
0263
0264 /// \overload
0265 template< class ForwardRange, class Integer, class Value,
0266           class BinaryPredicate >
0267 inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type
0268 search_n(ForwardRange& rng, Integer count, const Value& value,
0269          BinaryPredicate binary_pred)
0270 {
0271     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
0272     BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
0273         BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type, const Value&>));
0274     return range_detail::search_n_pred_impl(boost::begin(rng), boost::end(rng),
0275         count, value, binary_pred);
0276 }
0277
0278 /// \overload
0279 template< class ForwardRange, class Integer, class Value,
0280           class BinaryPredicate >
0281 inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type
0282 search_n(const ForwardRange& rng, Integer count, const Value& value,
0283          BinaryPredicate binary_pred)
0284 {
0285     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
0286     BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
0287         BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type, const Value&>));
0288     return range_detail::search_n_pred_impl(boost::begin(rng), boost::end(rng),
0289         count, value, binary_pred);
0290 }
0291
0292 // range_return overloads
0293
0294 /// \overload
0295 template< range_return_value re, class ForwardRange, class Integer,
0296           class Value >
0297 inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type
0298 search_n(ForwardRange& rng, Integer count, const Value& value)
0299 {
0300     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
0301     return range_return<ForwardRange,re>::
0302         pack(range_detail::search_n_impl(boost::begin(rng),boost::end(rng),
0303                            count, value),
0304              rng);
0305 }
0306
0307 /// \overload
0308 template< range_return_value re, class ForwardRange, class Integer,
0309           class Value >
0310 inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type
0311 search_n(const ForwardRange& rng, Integer count, const Value& value)
0312 {
0313     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
0314     return range_return<const ForwardRange,re>::
0315         pack(range_detail::search_n_impl(boost::begin(rng), boost::end(rng),
0316                            count, value),
0317              rng);
0318 }
0319
0320 /// \overload
0321 template< range_return_value re, class ForwardRange, class Integer,
0322           class Value, class BinaryPredicate >
0323 inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type
0324 search_n(ForwardRange& rng, Integer count, const Value& value,
0325          BinaryPredicate pred)
0326 {
0327     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
0328     BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
0329         BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type,
0330         const Value&>));
0331     return range_return<ForwardRange,re>::
0332         pack(range_detail::search_n_pred_impl(boost::begin(rng),
0333                                               boost::end(rng),
0334                            count, value, pred),
0335              rng);
0336 }
0337
0338 /// \overload
0339 template< range_return_value re, class ForwardRange, class Integer,
0340           class Value, class BinaryPredicate >
0341 inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type
0342 search_n(const ForwardRange& rng, Integer count, const Value& value,
0343          BinaryPredicate pred)
0344 {
0345     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
0346     BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
0347         BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type,
0348         const Value&>));
0349     return range_return<const ForwardRange,re>::
0350         pack(range_detail::search_n_pred_impl(boost::begin(rng),
0351                                               boost::end(rng),
0352                            count, value, pred),
0353              rng);
0354 }
0355
0356     } // namespace range
0357     using range::search_n;
0358 } // namespace boost
0359
0360 #endif // include guard