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/iterator/iterator_adaptor.hpp> |
---|
25 | #include <boost/next_prior.hpp> |
---|
26 | |
---|
27 | |
---|
28 | namespace boost |
---|
29 | { |
---|
30 | namespace range_detail |
---|
31 | { |
---|
32 | template< class Iter, class Pred, bool default_pass > |
---|
33 | class skip_iterator |
---|
34 | : public boost::iterator_adaptor< |
---|
35 | skip_iterator<Iter,Pred,default_pass>, |
---|
36 | Iter, |
---|
37 | BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::value_type, |
---|
38 | boost::forward_traversal_tag, |
---|
39 | BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::reference, |
---|
40 | BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::difference_type |
---|
41 | > |
---|
42 | , private Pred |
---|
43 | { |
---|
44 | private: |
---|
45 | typedef boost::iterator_adaptor< |
---|
46 | skip_iterator<Iter,Pred,default_pass>, |
---|
47 | Iter, |
---|
48 | BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::value_type, |
---|
49 | boost::forward_traversal_tag, |
---|
50 | BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::reference, |
---|
51 | BOOST_DEDUCED_TYPENAME std::iterator_traits<Iter>::difference_type |
---|
52 | > base_t; |
---|
53 | |
---|
54 | public: |
---|
55 | typedef Pred pred_t; |
---|
56 | typedef Iter iter_t; |
---|
57 | |
---|
58 | skip_iterator() : m_last() {} |
---|
59 | |
---|
60 | skip_iterator(iter_t it, iter_t last, const Pred& pred) |
---|
61 | : base_t(it) |
---|
62 | , pred_t(pred) |
---|
63 | , m_last(last) |
---|
64 | { |
---|
65 | move_to_next_valid(); |
---|
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 | void move_to_next_valid() |
---|
75 | { |
---|
76 | iter_t& it = this->base_reference(); |
---|
77 | pred_t& bi_pred = *this; |
---|
78 | if (it != m_last) |
---|
79 | { |
---|
80 | if (default_pass) |
---|
81 | { |
---|
82 | iter_t nxt = ::boost::next(it); |
---|
83 | while (nxt != m_last && !bi_pred(*it, *nxt)) |
---|
84 | { |
---|
85 | ++it; |
---|
86 | ++nxt; |
---|
87 | } |
---|
88 | } |
---|
89 | else |
---|
90 | { |
---|
91 | iter_t nxt = ::boost::next(it); |
---|
92 | for(; nxt != m_last; ++it, ++nxt) |
---|
93 | { |
---|
94 | if (bi_pred(*it, *nxt)) |
---|
95 | { |
---|
96 | break; |
---|
97 | } |
---|
98 | } |
---|
99 | if (nxt == m_last) |
---|
100 | { |
---|
101 | it = m_last; |
---|
102 | } |
---|
103 | } |
---|
104 | } |
---|
105 | } |
---|
106 | |
---|
107 | void increment() |
---|
108 | { |
---|
109 | iter_t& it = this->base_reference(); |
---|
110 | BOOST_ASSERT( it != m_last ); |
---|
111 | ++it; |
---|
112 | move_to_next_valid(); |
---|
113 | } |
---|
114 | |
---|
115 | iter_t m_last; |
---|
116 | }; |
---|
117 | |
---|
118 | template< class P, class R, bool default_pass > |
---|
119 | struct adjacent_filter_range |
---|
120 | : iterator_range< skip_iterator< |
---|
121 | BOOST_DEDUCED_TYPENAME range_iterator<R>::type, |
---|
122 | P, |
---|
123 | default_pass |
---|
124 | > |
---|
125 | > |
---|
126 | { |
---|
127 | private: |
---|
128 | typedef skip_iterator< |
---|
129 | BOOST_DEDUCED_TYPENAME range_iterator<R>::type, |
---|
130 | P, |
---|
131 | default_pass |
---|
132 | > |
---|
133 | skip_iter; |
---|
134 | |
---|
135 | typedef iterator_range<skip_iter> |
---|
136 | base_range; |
---|
137 | |
---|
138 | typedef BOOST_DEDUCED_TYPENAME range_iterator<R>::type raw_iterator; |
---|
139 | |
---|
140 | public: |
---|
141 | adjacent_filter_range( const P& p, R& r ) |
---|
142 | : base_range(skip_iter(boost::begin(r), boost::end(r), p), |
---|
143 | skip_iter(boost::end(r), boost::end(r), p)) |
---|
144 | { |
---|
145 | } |
---|
146 | |
---|
147 | private: |
---|
148 | P m_pred; |
---|
149 | R* m_range; |
---|
150 | }; |
---|
151 | |
---|
152 | template< class T > |
---|
153 | struct adjacent_holder : holder<T> |
---|
154 | { |
---|
155 | adjacent_holder( T r ) : holder<T>(r) |
---|
156 | { } |
---|
157 | }; |
---|
158 | |
---|
159 | template< class T > |
---|
160 | struct adjacent_excl_holder : holder<T> |
---|
161 | { |
---|
162 | adjacent_excl_holder( T r ) : holder<T>(r) |
---|
163 | { } |
---|
164 | }; |
---|
165 | |
---|
166 | template< class ForwardRng, class BinPredicate > |
---|
167 | inline adjacent_filter_range<BinPredicate, ForwardRng, true> |
---|
168 | operator|( ForwardRng& r, |
---|
169 | const adjacent_holder<BinPredicate>& f ) |
---|
170 | { |
---|
171 | return adjacent_filter_range<BinPredicate, ForwardRng, true>( f.val, r ); |
---|
172 | } |
---|
173 | |
---|
174 | template< class ForwardRng, class BinPredicate > |
---|
175 | inline adjacent_filter_range<BinPredicate, const ForwardRng, true> |
---|
176 | operator|( const ForwardRng& r, |
---|
177 | const adjacent_holder<BinPredicate>& f ) |
---|
178 | { |
---|
179 | return adjacent_filter_range<BinPredicate, |
---|
180 | const ForwardRng, true>( f.val, r ); |
---|
181 | } |
---|
182 | |
---|
183 | template< class ForwardRng, class BinPredicate > |
---|
184 | inline adjacent_filter_range<BinPredicate, ForwardRng, false> |
---|
185 | operator|( ForwardRng& r, |
---|
186 | const adjacent_excl_holder<BinPredicate>& f ) |
---|
187 | { |
---|
188 | return adjacent_filter_range<BinPredicate, ForwardRng, false>( f.val, r ); |
---|
189 | } |
---|
190 | |
---|
191 | template< class ForwardRng, class BinPredicate > |
---|
192 | inline adjacent_filter_range<BinPredicate, ForwardRng, false> |
---|
193 | operator|( const ForwardRng& r, |
---|
194 | const adjacent_excl_holder<BinPredicate>& f ) |
---|
195 | { |
---|
196 | return adjacent_filter_range<BinPredicate, |
---|
197 | const ForwardRng, false>( f.val, r ); |
---|
198 | } |
---|
199 | |
---|
200 | } // 'range_detail' |
---|
201 | |
---|
202 | // Bring adjacent_filter_range into the boost namespace so that users of |
---|
203 | // this library may specify the return type of the '|' operator and |
---|
204 | // adjacent_filter() |
---|
205 | using range_detail::adjacent_filter_range; |
---|
206 | |
---|
207 | namespace adaptors |
---|
208 | { |
---|
209 | namespace |
---|
210 | { |
---|
211 | const range_detail::forwarder<range_detail::adjacent_holder> |
---|
212 | adjacent_filtered = |
---|
213 | range_detail::forwarder<range_detail::adjacent_holder>(); |
---|
214 | |
---|
215 | const range_detail::forwarder<range_detail::adjacent_excl_holder> |
---|
216 | adjacent_filtered_excl = |
---|
217 | range_detail::forwarder<range_detail::adjacent_excl_holder>(); |
---|
218 | } |
---|
219 | |
---|
220 | template<class ForwardRng, class BinPredicate> |
---|
221 | inline adjacent_filter_range<BinPredicate, ForwardRng, true> |
---|
222 | adjacent_filter(ForwardRng& rng, BinPredicate filter_pred) |
---|
223 | { |
---|
224 | return adjacent_filter_range<BinPredicate, ForwardRng, true>(filter_pred, rng); |
---|
225 | } |
---|
226 | |
---|
227 | template<class ForwardRng, class BinPredicate> |
---|
228 | inline adjacent_filter_range<BinPredicate, const ForwardRng, true> |
---|
229 | adjacent_filter(const ForwardRng& rng, BinPredicate filter_pred) |
---|
230 | { |
---|
231 | return adjacent_filter_range<BinPredicate, const ForwardRng, true>(filter_pred, rng); |
---|
232 | } |
---|
233 | |
---|
234 | } // 'adaptors' |
---|
235 | |
---|
236 | } |
---|
237 | |
---|
238 | #ifdef BOOST_MSVC |
---|
239 | #pragma warning( pop ) |
---|
240 | #endif |
---|
241 | |
---|
242 | #endif |
---|