1 | // Copyright 2014 Neil Groves |
2 | // |
3 | // Copyright (c) 2010 Ilya Murav'jov |
4 | // |
5 | // Use, modification and distribution is subject to the Boost Software License, |
6 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | // |
9 | // Credits: |
10 | // My (Neil's) first indexed adaptor was hindered by having the underlying |
11 | // iterator return the same reference as the wrapped iterator. This meant that |
12 | // to obtain the index one had to get to the index_iterator and call the |
13 | // index() function on it. Ilya politely pointed out that this was useless in |
14 | // a number of scenarios since one naturally hides the use of iterators in |
15 | // good range-based code. Ilya provided a new interface (which has remained) |
16 | // and a first implementation. Much of this original implementation has |
17 | // been simplified and now supports more compilers and platforms. |
18 | // |
19 | #ifndef BOOST_RANGE_ADAPTOR_INDEXED_HPP_INCLUDED |
20 | #define BOOST_RANGE_ADAPTOR_INDEXED_HPP_INCLUDED |
21 | |
22 | #include <boost/range/config.hpp> |
23 | #include <boost/range/adaptor/argument_fwd.hpp> |
24 | #include <boost/range/iterator_range.hpp> |
25 | #include <boost/range/traversal.hpp> |
26 | #include <boost/range/size.hpp> |
27 | #include <boost/range/begin.hpp> |
28 | #include <boost/range/end.hpp> |
29 | #include <boost/mpl/if.hpp> |
30 | #include <boost/type_traits/is_convertible.hpp> |
31 | |
32 | #include <boost/iterator/iterator_traits.hpp> |
33 | #include <boost/iterator/iterator_facade.hpp> |
34 | |
35 | #include <boost/tuple/tuple.hpp> |
36 | |
37 | namespace boost |
38 | { |
39 | namespace adaptors |
40 | { |
41 | |
42 | struct indexed |
43 | { |
44 | explicit indexed(std::ptrdiff_t x = 0) |
45 | : val(x) |
46 | { |
47 | } |
48 | std::ptrdiff_t val; |
49 | }; |
50 | |
51 | } // namespace adaptors |
52 | |
53 | namespace range |
54 | { |
55 | |
56 | // Why yet another "pair" class: |
57 | // - std::pair can't store references |
58 | // - no need for typing for index type (default to "std::ptrdiff_t"); this is |
59 | // useful in BOOST_FOREACH() expressions that have pitfalls with commas |
60 | // ( see http://www.boost.org/doc/libs/1_44_0/doc/html/foreach/pitfalls.html ) |
61 | // - meaningful access functions index(), value() |
62 | template<class T, class Indexable = std::ptrdiff_t> |
63 | class index_value |
64 | : public tuple<Indexable, T> |
65 | { |
66 | typedef tuple<Indexable, T> base_t; |
67 | |
68 | template<int N> |
69 | struct iv_types |
70 | { |
71 | typedef typename tuples::element<N, base_t>::type n_type; |
72 | |
73 | typedef typename tuples::access_traits<n_type>::non_const_type non_const_type; |
74 | typedef typename tuples::access_traits<n_type>::const_type const_type; |
75 | }; |
76 | |
77 | public: |
78 | typedef typename iv_types<0>::non_const_type index_type; |
79 | typedef typename iv_types<0>::const_type const_index_type; |
80 | typedef typename iv_types<1>::non_const_type value_type; |
81 | typedef typename iv_types<1>::const_type const_value_type; |
82 | |
83 | index_value() |
84 | { |
85 | } |
86 | |
87 | index_value(typename tuples::access_traits<Indexable>::parameter_type t0, |
88 | typename tuples::access_traits<T>::parameter_type t1) |
89 | : base_t(t0, t1) |
90 | { |
91 | } |
92 | |
93 | // member functions index(), value() (non-const and const) |
94 | index_type index() |
95 | { |
96 | return boost::tuples::get<0>(*this); |
97 | } |
98 | |
99 | const_index_type index() const |
100 | { |
101 | return boost::tuples::get<0>(*this); |
102 | } |
103 | |
104 | value_type value() |
105 | { |
106 | return boost::tuples::get<1>(*this); |
107 | } |
108 | |
109 | const_value_type value() const |
110 | { |
111 | return boost::tuples::get<1>(*this); |
112 | } |
113 | }; |
114 | |
115 | } // namespace range |
116 | |
117 | namespace range_detail |
118 | { |
119 | |
120 | template<typename Iter> |
121 | struct indexed_iterator_value_type |
122 | { |
123 | typedef ::boost::range::index_value< |
124 | typename iterator_reference<Iter>::type, |
125 | typename iterator_difference<Iter>::type |
126 | > type; |
127 | }; |
128 | |
129 | // Meta-function to get the traversal for the range and therefore iterator |
130 | // returned by the indexed adaptor for a specified iterator type. |
131 | // |
132 | // Random access -> Random access |
133 | // Bidirectional -> Forward |
134 | // Forward -> Forward |
135 | // SinglePass -> SinglePass |
136 | // |
137 | // The rationale for demoting a Bidirectional input to Forward is that the end |
138 | // iterator cannot cheaply have an index computed for it. Therefore I chose to |
139 | // demote to forward traversal. I can maintain the ability to traverse randomly |
140 | // when the input is Random Access since the index for the end iterator is cheap |
141 | // to compute. |
142 | template<typename Iter> |
143 | struct indexed_traversal |
144 | { |
145 | private: |
146 | typedef typename iterator_traversal<Iter>::type wrapped_traversal; |
147 | |
148 | public: |
149 | |
150 | typedef typename mpl::if_< |
151 | is_convertible<wrapped_traversal, random_access_traversal_tag>, |
152 | random_access_traversal_tag, |
153 | typename mpl::if_< |
154 | is_convertible<wrapped_traversal, bidirectional_traversal_tag>, |
155 | forward_traversal_tag, |
156 | wrapped_traversal |
157 | >::type |
158 | >::type type; |
159 | }; |
160 | |
161 | template<typename Iter> |
162 | class indexed_iterator |
163 | : public iterator_facade< |
164 | indexed_iterator<Iter>, |
165 | typename indexed_iterator_value_type<Iter>::type, |
166 | typename indexed_traversal<Iter>::type, |
167 | typename indexed_iterator_value_type<Iter>::type, |
168 | typename iterator_difference<Iter>::type |
169 | > |
170 | { |
171 | public: |
172 | typedef Iter wrapped; |
173 | |
174 | private: |
175 | typedef iterator_facade< |
176 | indexed_iterator<wrapped>, |
177 | typename indexed_iterator_value_type<wrapped>::type, |
178 | typename indexed_traversal<wrapped>::type, |
179 | typename indexed_iterator_value_type<wrapped>::type, |
180 | typename iterator_difference<wrapped>::type |
181 | > base_t; |
182 | |
183 | public: |
184 | typedef typename base_t::difference_type difference_type; |
185 | typedef typename base_t::reference reference; |
186 | typedef typename base_t::difference_type index_type; |
187 | |
188 | indexed_iterator() |
189 | : m_it() |
190 | , m_index() |
191 | { |
192 | } |
193 | |
194 | template<typename OtherWrapped> |
195 | indexed_iterator( |
196 | const indexed_iterator<OtherWrapped>& other, |
197 | typename enable_if<is_convertible<OtherWrapped, wrapped> >::type* = 0 |
198 | ) |
199 | : m_it(other.get()) |
200 | , m_index(other.get_index()) |
201 | { |
202 | } |
203 | |
204 | explicit indexed_iterator(wrapped it, index_type index) |
205 | : m_it(it) |
206 | , m_index(index) |
207 | { |
208 | } |
209 | |
210 | wrapped get() const |
211 | { |
212 | return m_it; |
213 | } |
214 | |
215 | index_type get_index() const |
216 | { |
217 | return m_index; |
218 | } |
219 | |
220 | private: |
221 | friend class boost::iterator_core_access; |
222 | |
223 | reference dereference() const |
224 | { |
225 | return reference(m_index, *m_it); |
226 | } |
227 | |
228 | bool equal(const indexed_iterator& other) const |
229 | { |
230 | return m_it == other.m_it; |
231 | } |
232 | |
233 | void increment() |
234 | { |
235 | ++m_index; |
236 | ++m_it; |
237 | } |
238 | |
239 | void decrement() |
240 | { |
241 | BOOST_ASSERT_MSG(m_index > 0, "indexed Iterator out of bounds" ); |
242 | --m_index; |
243 | --m_it; |
244 | } |
245 | |
246 | void advance(index_type n) |
247 | { |
248 | m_index += n; |
249 | BOOST_ASSERT_MSG(m_index >= 0, "indexed Iterator out of bounds" ); |
250 | m_it += n; |
251 | } |
252 | |
253 | difference_type distance_to(const indexed_iterator& other) const |
254 | { |
255 | return other.m_it - m_it; |
256 | } |
257 | |
258 | wrapped m_it; |
259 | index_type m_index; |
260 | }; |
261 | |
262 | template<typename SinglePassRange> |
263 | struct indexed_range |
264 | : iterator_range< |
265 | indexed_iterator< |
266 | typename range_iterator<SinglePassRange>::type |
267 | > |
268 | > |
269 | { |
270 | typedef iterator_range< |
271 | indexed_iterator< |
272 | typename range_iterator<SinglePassRange>::type |
273 | > |
274 | > base_t; |
275 | |
276 | BOOST_RANGE_CONCEPT_ASSERT(( |
277 | boost::SinglePassRangeConcept<SinglePassRange>)); |
278 | public: |
279 | typedef indexed_iterator< |
280 | typename range_iterator<SinglePassRange>::type |
281 | > iterator; |
282 | |
283 | // Constructor for non-random access iterators. |
284 | // This sets the end iterator index to i despite this being incorrect it |
285 | // is never observable since bidirectional iterators are demoted to |
286 | // forward iterators. |
287 | indexed_range( |
288 | typename base_t::difference_type i, |
289 | SinglePassRange& r, |
290 | single_pass_traversal_tag |
291 | ) |
292 | : base_t(iterator(boost::begin(r), i), |
293 | iterator(boost::end(r), i)) |
294 | { |
295 | } |
296 | |
297 | indexed_range( |
298 | typename base_t::difference_type i, |
299 | SinglePassRange& r, |
300 | random_access_traversal_tag |
301 | ) |
302 | : base_t(iterator(boost::begin(r), i), |
303 | iterator(boost::end(r), i + boost::size(r))) |
304 | { |
305 | } |
306 | }; |
307 | |
308 | } // namespace range_detail |
309 | |
310 | using range_detail::indexed_range; |
311 | |
312 | namespace adaptors |
313 | { |
314 | |
315 | template<class SinglePassRange> |
316 | inline indexed_range<SinglePassRange> |
317 | operator|(SinglePassRange& r, indexed e) |
318 | { |
319 | BOOST_RANGE_CONCEPT_ASSERT(( |
320 | boost::SinglePassRangeConcept<SinglePassRange> |
321 | )); |
322 | return indexed_range<SinglePassRange>( |
323 | e.val, r, |
324 | typename range_traversal<SinglePassRange>::type()); |
325 | } |
326 | |
327 | template<class SinglePassRange> |
328 | inline indexed_range<const SinglePassRange> |
329 | operator|(const SinglePassRange& r, indexed e) |
330 | { |
331 | BOOST_RANGE_CONCEPT_ASSERT(( |
332 | boost::SinglePassRangeConcept<const SinglePassRange> |
333 | )); |
334 | return indexed_range<const SinglePassRange>( |
335 | e.val, r, |
336 | typename range_traversal<const SinglePassRange>::type()); |
337 | } |
338 | |
339 | template<class SinglePassRange> |
340 | inline indexed_range<SinglePassRange> |
341 | index( |
342 | SinglePassRange& rng, |
343 | typename range_difference<SinglePassRange>::type index_value = 0) |
344 | { |
345 | BOOST_RANGE_CONCEPT_ASSERT(( |
346 | boost::SinglePassRangeConcept<SinglePassRange> |
347 | )); |
348 | return indexed_range<SinglePassRange>( |
349 | index_value, rng, |
350 | typename range_traversal<SinglePassRange>::type()); |
351 | } |
352 | |
353 | template<class SinglePassRange> |
354 | inline indexed_range<const SinglePassRange> |
355 | index( |
356 | const SinglePassRange& rng, |
357 | typename range_difference<const SinglePassRange>::type index_value = 0) |
358 | { |
359 | BOOST_RANGE_CONCEPT_ASSERT(( |
360 | boost::SinglePassRangeConcept<SinglePassRange> |
361 | )); |
362 | return indexed_range<const SinglePassRange>( |
363 | index_value, rng, |
364 | typename range_traversal<const SinglePassRange>::type()); |
365 | } |
366 | |
367 | } // namespace adaptors |
368 | } // namespace boost |
369 | |
370 | #endif // include guard |
371 | |