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
29namespace 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
238