boost/range/algorithm/search_n.hpp

   1 //  Copyright Neil Groves 2009. Use, modification and
   2 //  distribution is subject to the Boost Software License, Version
   3 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
   4 //  http://www.boost.org/LICENSE_1_0.txt)
   5 //
   6 //
   7 // For more information, see http://www.boost.org/libs/range/
   8 //
   9 #ifndef BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED
  10 #define BOOST_RANGE_ALGORITHM_SEARCH_N_HPP_INCLUDED
  11
  12 #include <boost/concept_check.hpp>
  13 #include <boost/range/begin.hpp>
  14 #include <boost/range/end.hpp>
  15 #include <boost/range/concepts.hpp>
  16 #include <boost/range/detail/range_return.hpp>
  17 #include <boost/range/value_type.hpp>
  18 #include <iterator>
  19 #include <algorithm>
  20
  21 namespace boost
  22 {
  23
  24 namespace range_detail
  25 {
  26     // Rationale: search_n is implemented rather than delegate to
  27     // the standard library implementation because some standard
  28     // library implementations are broken eg. MSVC.
  29
  30     // search_n forward iterator version
  31     template<typename ForwardIterator, typename Integer, typename Value>
  32     inline ForwardIterator
  33     search_n_impl(ForwardIterator first, ForwardIterator last, Integer count,
  34                   const Value& value, std::forward_iterator_tag)
  35     {
  36         first = std::find(first, last, value);
  37         while (first != last)
  38         {
  39             typename std::iterator_traits<ForwardIterator>::difference_type n = count;
  40             ForwardIterator i = first;
  41             ++i;
  42             while (i != last && n != 1 && *i==value)
  43             {
  44                 ++i;
  45                 --n;
  46             }
  47             if (n == 1)
  48                 return first;
  49             if (i == last)
  50                 return last;
  51             first = std::find(++i, last, value);
  52         }
  53         return last;
  54     }
  55
  56     // search_n random-access iterator version
  57     template<typename RandomAccessIterator, typename Integer, typename Value>
  58     inline RandomAccessIterator
  59     search_n_impl(RandomAccessIterator first, RandomAccessIterator last,
  60                   Integer count, const Value& value,
  61                   std::random_access_iterator_tag)
  62     {
  63         typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t;
  64
  65         difference_t tail_size = last - first;
  66         const difference_t pattern_size = count;
  67
  68         if (tail_size < pattern_size)
  69             return last;
  70
  71         const difference_t skip_offset = pattern_size - 1;
  72         RandomAccessIterator look_ahead = first + skip_offset;
  73         tail_size -= pattern_size;
  74
  75         while (1)
  76         {
  77             // look_ahead here is pointing to the last element of the
  78             // next possible match
  79             while (!(*look_ahead == value)) // skip loop...
  80             {
  81                 if (tail_size < pattern_size)
  82                     return last; // no match
  83                 look_ahead += pattern_size;
  84                 tail_size -= pattern_size;
  85             }
  86             difference_t remainder = skip_offset;
  87             for (RandomAccessIterator back_track = look_ahead - 1;
  88                     *back_track == value; --back_track)
  89             {
  90                 if (--remainder == 0)
  91                 {
  92                     return look_ahead - skip_offset; // matched
  93                 }
  94             }
  95             if (remainder > tail_size)
  96                 return last; // no match
  97             look_ahead += remainder;
  98             tail_size -= remainder;
  99         }
 100
 101         return last;
 102     }
 103
 104     // search_n for forward iterators using a binary predicate
 105     // to determine a match
 106     template<typename ForwardIterator, typename Integer, typename Value,
 107              typename BinaryPredicate>
 108     inline ForwardIterator
 109     search_n_pred_impl(ForwardIterator first, ForwardIterator last,
 110                        Integer count, const Value& value,
 111                        BinaryPredicate pred, std::forward_iterator_tag)
 112     {
 113         typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_t;
 114
 115         while (first != last && !static_cast<bool>(pred(*first, value)))
 116             ++first;
 117
 118         while (first != last)
 119         {
 120             difference_t n = count;
 121             ForwardIterator i = first;
 122             ++i;
 123             while (i != last && n != 1 && static_cast<bool>(pred(*i, value)))
 124             {
 125                 ++i;
 126                 --n;
 127             }
 128             if (n == 1)
 129                 return first;
 130             if (i == last)
 131                 return last;
 132             first = ++i;
 133             while (first != last && !static_cast<bool>(pred(*first, value)))
 134                 ++first;
 135         }
 136         return last;
 137     }
 138
 139     // search_n for random-access iterators using a binary predicate
 140     // to determine a match
 141     template<typename RandomAccessIterator, typename Integer,
 142              typename Value, typename BinaryPredicate>
 143     inline RandomAccessIterator
 144     search_n_pred_impl(RandomAccessIterator first, RandomAccessIterator last,
 145                        Integer count, const Value& value,
 146                        BinaryPredicate pred, std::random_access_iterator_tag)
 147     {
 148         typedef typename std::iterator_traits<RandomAccessIterator>::difference_type difference_t;
 149
 150         difference_t tail_size = last - first;
 151         const difference_t pattern_size = count;
 152
 153         if (tail_size < pattern_size)
 154             return last;
 155
 156         const difference_t skip_offset = pattern_size - 1;
 157         RandomAccessIterator look_ahead = first + skip_offset;
 158         tail_size -= pattern_size;
 159
 160         while (1)
 161         {
 162             // look_ahead points to the last element of the next
 163             // possible match
 164             while (!static_cast<bool>(pred(*look_ahead, value))) // skip loop
 165             {
 166                 if (tail_size < pattern_size)
 167                     return last; // no match
 168                 look_ahead += pattern_size;
 169                 tail_size -= pattern_size;
 170             }
 171             difference_t remainder = skip_offset;
 172             for (RandomAccessIterator back_track = look_ahead - 1;
 173                     pred(*back_track, value); --back_track)
 174             {
 175                 if (--remainder == 0)
 176                     return look_ahead -= skip_offset; // success
 177             }
 178             if (remainder > tail_size)
 179             {
 180                 return last; // no match
 181             }
 182             look_ahead += remainder;
 183             tail_size -= remainder;
 184         }
 185     }
 186
 187     template<typename ForwardIterator, typename Integer, typename Value>
 188     inline ForwardIterator
 189     search_n_impl(ForwardIterator first, ForwardIterator last,
 190                   Integer count, const Value& value)
 191     {
 192         BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>));
 193         BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept<Value>));
 194         BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept<typename std::iterator_traits<ForwardIterator>::value_type>));
 195         //BOOST_RANGE_CONCEPT_ASSERT((EqualityComparableConcept2<typename std::iterator_traits<ForwardIterator>::value_type, Value>));
 196
 197         typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t;
 198
 199         if (count <= 0)
 200             return first;
 201         if (count == 1)
 202             return std::find(first, last, value);
 203         return range_detail::search_n_impl(first, last, count, value, cat_t());
 204     }
 205
 206     template<typename ForwardIterator, typename Integer, typename Value,
 207              typename BinaryPredicate>
 208     inline ForwardIterator
 209     search_n_pred_impl(ForwardIterator first, ForwardIterator last,
 210                        Integer count, const Value& value,
 211                        BinaryPredicate pred)
 212     {
 213         BOOST_RANGE_CONCEPT_ASSERT((ForwardIteratorConcept<ForwardIterator>));
 214         BOOST_RANGE_CONCEPT_ASSERT((
 215             BinaryPredicateConcept<
 216                 BinaryPredicate,
 217                 typename std::iterator_traits<ForwardIterator>::value_type,
 218                 Value>
 219             ));
 220
 221         typedef typename std::iterator_traits<ForwardIterator>::iterator_category cat_t;
 222
 223         if (count <= 0)
 224             return first;
 225         if (count == 1)
 226         {
 227             while (first != last && !static_cast<bool>(pred(*first, value)))
 228                 ++first;
 229             return first;
 230         }
 231         return range_detail::search_n_pred_impl(first, last, count,
 232                                                 value, pred, cat_t());
 233     }
 234 } // namespace range_detail
 235
 236 namespace range {
 237
 238 /// \brief template function search
 239 ///
 240 /// range-based version of the search std algorithm
 241 ///
 242 /// \pre ForwardRange is a model of the ForwardRangeConcept
 243 /// \pre Integer is an integral type
 244 /// \pre Value is a model of the EqualityComparableConcept
 245 /// \pre ForwardRange's value type is a model of the EqualityComparableConcept
 246 /// \pre Object's of ForwardRange's value type can be compared for equality with Objects of type Value
 247 template< class ForwardRange, class Integer, class Value >
 248 inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type
 249 search_n(ForwardRange& rng, Integer count, const Value& value)
 250 {
 251     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
 252     return range_detail::search_n_impl(boost::begin(rng),boost::end(rng), count, value);
 253 }
 254
 255 /// \overload
 256 template< class ForwardRange, class Integer, class Value >
 257 inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type
 258 search_n(const ForwardRange& rng, Integer count, const Value& value)
 259 {
 260     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
 261     return range_detail::search_n_impl(boost::begin(rng), boost::end(rng), count, value);
 262 }
 263
 264 /// \overload
 265 template< class ForwardRange, class Integer, class Value,
 266           class BinaryPredicate >
 267 inline BOOST_DEDUCED_TYPENAME range_iterator<ForwardRange>::type
 268 search_n(ForwardRange& rng, Integer count, const Value& value,
 269          BinaryPredicate binary_pred)
 270 {
 271     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
 272     BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
 273         BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type, const Value&>));
 274     return range_detail::search_n_pred_impl(boost::begin(rng), boost::end(rng),
 275         count, value, binary_pred);
 276 }
 277
 278 /// \overload
 279 template< class ForwardRange, class Integer, class Value,
 280           class BinaryPredicate >
 281 inline BOOST_DEDUCED_TYPENAME range_iterator<const ForwardRange>::type
 282 search_n(const ForwardRange& rng, Integer count, const Value& value,
 283          BinaryPredicate binary_pred)
 284 {
 285     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
 286     BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
 287         BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type, const Value&>));
 288     return range_detail::search_n_pred_impl(boost::begin(rng), boost::end(rng),
 289         count, value, binary_pred);
 290 }
 291
 292 // range_return overloads
 293
 294 /// \overload
 295 template< range_return_value re, class ForwardRange, class Integer,
 296           class Value >
 297 inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type
 298 search_n(ForwardRange& rng, Integer count, const Value& value)
 299 {
 300     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
 301     return range_return<ForwardRange,re>::
 302         pack(range_detail::search_n_impl(boost::begin(rng),boost::end(rng),
 303                            count, value),
 304              rng);
 305 }
 306
 307 /// \overload
 308 template< range_return_value re, class ForwardRange, class Integer,
 309           class Value >
 310 inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type
 311 search_n(const ForwardRange& rng, Integer count, const Value& value)
 312 {
 313     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
 314     return range_return<const ForwardRange,re>::
 315         pack(range_detail::search_n_impl(boost::begin(rng), boost::end(rng),
 316                            count, value),
 317              rng);
 318 }
 319
 320 /// \overload
 321 template< range_return_value re, class ForwardRange, class Integer,
 322           class Value, class BinaryPredicate >
 323 inline BOOST_DEDUCED_TYPENAME range_return<ForwardRange,re>::type
 324 search_n(ForwardRange& rng, Integer count, const Value& value,
 325          BinaryPredicate pred)
 326 {
 327     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRange>));
 328     BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
 329         BOOST_DEDUCED_TYPENAME range_value<ForwardRange>::type,
 330         const Value&>));
 331     return range_return<ForwardRange,re>::
 332         pack(range_detail::search_n_pred_impl(boost::begin(rng),
 333                                               boost::end(rng),
 334                            count, value, pred),
 335              rng);
 336 }
 337
 338 /// \overload
 339 template< range_return_value re, class ForwardRange, class Integer,
 340           class Value, class BinaryPredicate >
 341 inline BOOST_DEDUCED_TYPENAME range_return<const ForwardRange,re>::type
 342 search_n(const ForwardRange& rng, Integer count, const Value& value,
 343          BinaryPredicate pred)
 344 {
 345     BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRange>));
 346     BOOST_RANGE_CONCEPT_ASSERT((BinaryPredicateConcept<BinaryPredicate,
 347         BOOST_DEDUCED_TYPENAME range_value<const ForwardRange>::type,
 348         const Value&>));
 349     return range_return<const ForwardRange,re>::
 350         pack(range_detail::search_n_pred_impl(boost::begin(rng),
 351                                               boost::end(rng),
 352                            count, value, pred),
 353              rng);
 354 }
 355
 356     } // namespace range
 357     using range::search_n;
 358 } // namespace boost
 359
 360 #endif // include guard