]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |