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 skip_iterator()59 skip_iterator() : m_last() {} 60 skip_iterator(iter_t it,iter_t last,const Pred & pred)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> skip_iterator(const skip_iterator<OtherIter,pred_t,default_pass> & other)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 increment()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: adjacent_filtered_rangeboost::range_detail::adjacent_filtered_range132 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 { adjacent_holderboost::range_detail::adjacent_holder142 adjacent_holder( T r ) : holder<T>(r) 143 { } 144 }; 145 146 template< class T > 147 struct adjacent_excl_holder : holder<T> 148 { adjacent_excl_holderboost::range_detail::adjacent_excl_holder149 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> operator |(ForwardRng & r,const adjacent_holder<BinPredicate> & f)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> operator |(const ForwardRng & r,const adjacent_holder<BinPredicate> & f)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> operator |(ForwardRng & r,const adjacent_excl_holder<BinPredicate> & f)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, const ForwardRng, false> operator |(const ForwardRng & r,const adjacent_excl_holder<BinPredicate> & f)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> adjacent_filter(ForwardRng & rng,BinPredicate filter_pred)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> adjacent_filter(const ForwardRng & rng,BinPredicate filter_pred)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 238