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, const 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 | |