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
37namespace boost
38{
39 namespace adaptors
40 {
41
42struct 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()
62template<class T, class Indexable = std::ptrdiff_t>
63class 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
77public:
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
117namespace range_detail
118{
119
120template<typename Iter>
121struct 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.
142template<typename Iter>
143struct indexed_traversal
144{
145private:
146 typedef typename iterator_traversal<Iter>::type wrapped_traversal;
147
148public:
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
161template<typename Iter>
162class 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{
171public:
172 typedef Iter wrapped;
173
174private:
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
183public:
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
262template<typename SinglePassRange>
263struct 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>));
278public:
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
315template<class SinglePassRange>
316inline indexed_range<SinglePassRange>
317operator|(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
327template<class SinglePassRange>
328inline indexed_range<const SinglePassRange>
329operator|(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
339template<class SinglePassRange>
340inline indexed_range<SinglePassRange>
341index(
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
353template<class SinglePassRange>
354inline indexed_range<const SinglePassRange>
355index(
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