boost/range/adaptor/indexed.hpp

   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