boost/range/adaptor/adjacent_filtered.hpp

   1 // Boost.Range library
   2 //
   3 //  Copyright Thorsten Ottosen, Neil Groves 2006 - 2008. Use, modification and
   4 //  distribution is subject to the Boost Software License, Version
   5 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6 //  http://www.boost.org/LICENSE_1_0.txt)
   7 //
   8 // For more information, see http://www.boost.org/libs/range/
   9 //
  10
  11 #ifndef BOOST_RANGE_ADAPTOR_ADJACENT_FILTER_IMPL_HPP
  12 #define BOOST_RANGE_ADAPTOR_ADJACENT_FILTER_IMPL_HPP
  13
  14 #include <boost/config.hpp>
  15 #ifdef BOOST_MSVC
  16 #pragma warning( push )
  17 #pragma warning( disable : 4355 )
  18 #endif
  19
  20 #include <boost/range/adaptor/argument_fwd.hpp>
  21 #include <boost/range/iterator_range.hpp>
  22 #include <boost/range/begin.hpp>
  23 #include <boost/range/end.hpp>
  24 #include <boost/range/concepts.hpp>
  25 #include <boost/iterator/iterator_adaptor.hpp>
  26 #include <boost/next_prior.hpp>
  27
  28
  29 namespace boost
  30 {
  31     namespace range_detail
  32     {
  33         template< class Iter, class Pred, bool default_pass >
  34         class skip_iterator
  35           : public boost::iterator_adaptor<
  36                     skip_iterator<Iter,Pred,default_pass>,
  37                     Iter,
  38                     BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::value_type,
  39                     boost::forward_traversal_tag,
  40                     BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::reference,
  41                     BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::difference_type
  42                 >
  43           , private Pred
  44         {
  45         private:
  46             typedef boost::iterator_adaptor<
  47                         skip_iterator<Iter,Pred,default_pass>,
  48                         Iter,
  49                         BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::value_type,
  50                         boost::forward_traversal_tag,
  51                         BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::reference,
  52                         BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::difference_type
  53                     > base_t;
  54
  55         public:
  56             typedef Pred pred_t;
  57             typedef Iter iter_t;
  58
  59             skip_iterator() : m_last() {}
  60
  61             skip_iterator(iter_t it, iter_t last, const Pred& pred)
  62                 : base_t(it)
  63                 , pred_t(pred)
  64                 , m_last(last)
  65             {
  66             }
  67
  68             template<class OtherIter>
  69             skip_iterator( const skip_iterator<OtherIter, pred_t, default_pass>& other )
  70             : base_t(other.base())
  71             , pred_t(other)
  72             , m_last(other.m_last)
  73             {
  74             }
  75
  76             void increment()
  77             {
  78                 iter_t& it = this->base_reference();
  79                 BOOST_ASSERT( it != m_last );
  80                 pred_t& bi_pred = *this;
  81                 iter_t prev = it;
  82                 ++it;
  83                 if (it != m_last)
  84                 {
  85                     if (default_pass)
  86                     {
  87                         while (it != m_last && !bi_pred(*prev, *it))
  88                         {
  89                             ++it;
  90                             ++prev;
  91                         }
  92                     }
  93                     else
  94                     {
  95                         for (; it != m_last; ++it, ++prev)
  96                         {
  97                             if (bi_pred(*prev, *it))
  98                             {
  99                                 break;
 100                             }
 101                         }
 102                     }
 103                 }
 104             }
 105
 106             iter_t m_last;
 107         };
 108
 109         template< class P, class R, bool default_pass >
 110         struct adjacent_filtered_range
 111             : iterator_range< skip_iterator<
 112                                 BOOST_DEDUCED_TYPENAME range_iterator<R>::type,
 113                                 P,
 114                                 default_pass
 115                             >
 116                         >
 117         {
 118         private:
 119             typedef skip_iterator<
 120                         BOOST_DEDUCED_TYPENAME range_iterator<R>::type,
 121                         P,
 122                         default_pass
 123                      >
 124                 skip_iter;
 125
 126             typedef iterator_range<skip_iter>
 127                 base_range;
 128
 129             typedef BOOST_DEDUCED_TYPENAME range_iterator<R>::type raw_iterator;
 130
 131         public:
 132             adjacent_filtered_range( const P& p, R& r )
 133             : base_range(skip_iter(boost::begin(r), boost::end(r), p),
 134                          skip_iter(boost::end(r), boost::end(r), p))
 135             {
 136             }
 137         };
 138
 139         template< class T >
 140         struct adjacent_holder : holder<T>
 141         {
 142             adjacent_holder( T r ) : holder<T>(r)
 143             { }
 144         };
 145
 146         template< class T >
 147         struct adjacent_excl_holder : holder<T>
 148         {
 149             adjacent_excl_holder( T r ) : holder<T>(r)
 150             { }
 151         };
 152
 153         template< class ForwardRng, class BinPredicate >
 154         inline adjacent_filtered_range<BinPredicate, ForwardRng, true>
 155         operator|( ForwardRng& r,
 156                    const adjacent_holder<BinPredicate>& f )
 157         {
 158             BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRng>));
 159
 160             return adjacent_filtered_range<BinPredicate, ForwardRng, true>( f.val, r );
 161         }
 162
 163         template< class ForwardRng, class BinPredicate >
 164         inline adjacent_filtered_range<BinPredicate, const ForwardRng, true>
 165         operator|( const ForwardRng& r,
 166                    const adjacent_holder<BinPredicate>& f )
 167         {
 168             BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRng>));
 169
 170             return adjacent_filtered_range<BinPredicate,
 171                                            const ForwardRng, true>( f.val, r );
 172         }
 173
 174         template< class ForwardRng, class BinPredicate >
 175         inline adjacent_filtered_range<BinPredicate, ForwardRng, false>
 176         operator|( ForwardRng& r,
 177                    const adjacent_excl_holder<BinPredicate>& f )
 178         {
 179             BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRng>));
 180             return adjacent_filtered_range<BinPredicate, ForwardRng, false>( f.val, r );
 181         }
 182
 183         template< class ForwardRng, class BinPredicate >
 184         inline adjacent_filtered_range<BinPredicate, ForwardRng, false>
 185         operator|( const ForwardRng& r,
 186                    const adjacent_excl_holder<BinPredicate>& f )
 187         {
 188             BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRng>));
 189             return adjacent_filtered_range<BinPredicate,
 190                                            const ForwardRng, false>( f.val, r );
 191         }
 192
 193     } // 'range_detail'
 194
 195     // Bring adjacent_filter_range into the boost namespace so that users of
 196     // this library may specify the return type of the '|' operator and
 197     // adjacent_filter()
 198     using range_detail::adjacent_filtered_range;
 199
 200     namespace adaptors
 201     {
 202         namespace
 203         {
 204             const range_detail::forwarder<range_detail::adjacent_holder>
 205                 adjacent_filtered =
 206                    range_detail::forwarder<range_detail::adjacent_holder>();
 207
 208             const range_detail::forwarder<range_detail::adjacent_excl_holder>
 209                 adjacent_filtered_excl =
 210                     range_detail::forwarder<range_detail::adjacent_excl_holder>();
 211         }
 212
 213         template<class ForwardRng, class BinPredicate>
 214         inline adjacent_filtered_range<BinPredicate, ForwardRng, true>
 215         adjacent_filter(ForwardRng& rng, BinPredicate filter_pred)
 216         {
 217             BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<ForwardRng>));
 218             return adjacent_filtered_range<BinPredicate, ForwardRng, true>(filter_pred, rng);
 219         }
 220
 221         template<class ForwardRng, class BinPredicate>
 222         inline adjacent_filtered_range<BinPredicate, const ForwardRng, true>
 223         adjacent_filter(const ForwardRng& rng, BinPredicate filter_pred)
 224         {
 225             BOOST_RANGE_CONCEPT_ASSERT((ForwardRangeConcept<const ForwardRng>));
 226             return adjacent_filtered_range<BinPredicate, const ForwardRng, true>(filter_pred, rng);
 227         }
 228
 229     } // 'adaptors'
 230
 231 }
 232
 233 #ifdef BOOST_MSVC
 234 #pragma warning( pop )
 235 #endif
 236
 237 #endif