range/adaptor/indexed.hpp

0001 //  Copyright 2014 Neil Groves
0002 //
0003 //  Copyright (c) 2010 Ilya Murav'jov
0004 //
0005 //  Use, modification and distribution is subject to the Boost Software License,
0006 //  Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 //  http://www.boost.org/LICENSE_1_0.txt)
0008 //
0009 // Credits:
0010 //  My (Neil's) first indexed adaptor was hindered by having the underlying
0011 //  iterator return the same reference as the wrapped iterator. This meant that
0012 //  to obtain the index one had to get to the index_iterator and call the
0013 //  index() function on it. Ilya politely pointed out that this was useless in
0014 //  a number of scenarios since one naturally hides the use of iterators in
0015 //  good range-based code. Ilya provided a new interface (which has remained)
0016 //  and a first implementation. Much of this original implementation has
0017 //  been simplified and now supports more compilers and platforms.
0018 //
0019 #ifndef BOOST_RANGE_ADAPTOR_INDEXED_HPP_INCLUDED
0020 #define BOOST_RANGE_ADAPTOR_INDEXED_HPP_INCLUDED
0021
0022 #include <boost/range/config.hpp>
0023 #include <boost/range/adaptor/argument_fwd.hpp>
0024 #include <boost/range/iterator_range.hpp>
0025 #include <boost/range/traversal.hpp>
0026 #include <boost/range/size.hpp>
0027 #include <boost/range/begin.hpp>
0028 #include <boost/range/end.hpp>
0029 #include <boost/mpl/if.hpp>
0030 #include <boost/type_traits/is_convertible.hpp>
0031
0032 #include <boost/iterator/iterator_traits.hpp>
0033 #include <boost/iterator/iterator_facade.hpp>
0034
0035 #include <boost/tuple/tuple.hpp>
0036
0037 namespace boost
0038 {
0039     namespace adaptors
0040     {
0041
0042 struct indexed
0043 {
0044     explicit indexed(std::ptrdiff_t x = 0)
0045         : val(x)
0046     {
0047     }
0048     std::ptrdiff_t val;
0049 };
0050
0051     } // namespace adaptors
0052
0053     namespace range
0054     {
0055
0056 // Why yet another "pair" class:
0057 // - std::pair can't store references
0058 // - no need for typing for index type (default to "std::ptrdiff_t"); this is
0059 // useful in BOOST_FOREACH() expressions that have pitfalls with commas
0060 //   ( see http://www.boost.org/doc/libs/1_44_0/doc/html/foreach/pitfalls.html )
0061 // - meaningful access functions index(), value()
0062 template<class T, class Indexable = std::ptrdiff_t>
0063 class index_value
0064     : public tuple<Indexable, T>
0065 {
0066     typedef tuple<Indexable, T> base_t;
0067
0068     template<int N>
0069     struct iv_types
0070     {
0071         typedef typename tuples::element<N, base_t>::type n_type;
0072
0073         typedef typename tuples::access_traits<n_type>::non_const_type non_const_type;
0074         typedef typename tuples::access_traits<n_type>::const_type const_type;
0075     };
0076
0077 public:
0078     typedef typename iv_types<0>::non_const_type index_type;
0079     typedef typename iv_types<0>::const_type const_index_type;
0080     typedef typename iv_types<1>::non_const_type value_type;
0081     typedef typename iv_types<1>::const_type const_value_type;
0082
0083     index_value()
0084     {
0085     }
0086
0087     index_value(typename tuples::access_traits<Indexable>::parameter_type t0,
0088                 typename tuples::access_traits<T>::parameter_type t1)
0089         : base_t(t0, t1)
0090     {
0091     }
0092
0093     // member functions index(), value() (non-const and const)
0094     index_type index()
0095     {
0096         return boost::tuples::get<0>(*this);
0097     }
0098
0099     const_index_type index() const
0100     {
0101         return boost::tuples::get<0>(*this);
0102     }
0103
0104     value_type value()
0105     {
0106         return boost::tuples::get<1>(*this);
0107     }
0108
0109     const_value_type value() const
0110     {
0111         return boost::tuples::get<1>(*this);
0112     }
0113 };
0114
0115     } // namespace range
0116
0117 namespace range_detail
0118 {
0119
0120 template<typename Iter>
0121 struct indexed_iterator_value_type
0122 {
0123     typedef ::boost::range::index_value<
0124         typename iterator_reference<Iter>::type,
0125         typename iterator_difference<Iter>::type
0126     > type;
0127 };
0128
0129 // Meta-function to get the traversal for the range and therefore iterator
0130 // returned by the indexed adaptor for a specified iterator type.
0131 //
0132 // Random access -> Random access
0133 // Bidirectional -> Forward
0134 // Forward -> Forward
0135 // SinglePass -> SinglePass
0136 //
0137 // The rationale for demoting a Bidirectional input to Forward is that the end
0138 // iterator cannot cheaply have an index computed for it. Therefore I chose to
0139 // demote to forward traversal. I can maintain the ability to traverse randomly
0140 // when the input is Random Access since the index for the end iterator is cheap
0141 // to compute.
0142 template<typename Iter>
0143 struct indexed_traversal
0144 {
0145 private:
0146     typedef typename iterator_traversal<Iter>::type wrapped_traversal;
0147
0148 public:
0149
0150     typedef typename mpl::if_<
0151         is_convertible<wrapped_traversal, random_access_traversal_tag>,
0152         random_access_traversal_tag,
0153         typename mpl::if_<
0154             is_convertible<wrapped_traversal, bidirectional_traversal_tag>,
0155             forward_traversal_tag,
0156             wrapped_traversal
0157         >::type
0158     >::type type;
0159 };
0160
0161 template<typename Iter>
0162 class indexed_iterator
0163     : public iterator_facade<
0164             indexed_iterator<Iter>,
0165             typename indexed_iterator_value_type<Iter>::type,
0166             typename indexed_traversal<Iter>::type,
0167             typename indexed_iterator_value_type<Iter>::type,
0168             typename iterator_difference<Iter>::type
0169         >
0170 {
0171 public:
0172     typedef Iter wrapped;
0173
0174 private:
0175     typedef iterator_facade<
0176         indexed_iterator<wrapped>,
0177         typename indexed_iterator_value_type<wrapped>::type,
0178         typename indexed_traversal<wrapped>::type,
0179         typename indexed_iterator_value_type<wrapped>::type,
0180         typename iterator_difference<wrapped>::type
0181     > base_t;
0182
0183 public:
0184     typedef typename base_t::difference_type difference_type;
0185     typedef typename base_t::reference reference;
0186     typedef typename base_t::difference_type index_type;
0187
0188     indexed_iterator()
0189         : m_it()
0190         , m_index()
0191     {
0192     }
0193
0194     template<typename OtherWrapped>
0195     indexed_iterator(
0196         const indexed_iterator<OtherWrapped>& other,
0197         typename enable_if<is_convertible<OtherWrapped, wrapped> >::type* = 0
0198     )
0199         : m_it(other.get())
0200         , m_index(other.get_index())
0201     {
0202     }
0203
0204     explicit indexed_iterator(wrapped it, index_type index)
0205         : m_it(it)
0206         , m_index(index)
0207     {
0208     }
0209
0210     wrapped get() const
0211     {
0212         return m_it;
0213     }
0214
0215     index_type get_index() const
0216     {
0217         return m_index;
0218     }
0219
0220  private:
0221     friend class boost::iterator_core_access;
0222
0223     reference dereference() const
0224     {
0225         return reference(m_index, *m_it);
0226     }
0227
0228     bool equal(const indexed_iterator& other) const
0229     {
0230         return m_it == other.m_it;
0231     }
0232
0233     void increment()
0234     {
0235         ++m_index;
0236         ++m_it;
0237     }
0238
0239     void decrement()
0240     {
0241         BOOST_ASSERT_MSG(m_index > 0, "indexed Iterator out of bounds");
0242         --m_index;
0243         --m_it;
0244     }
0245
0246     void advance(index_type n)
0247     {
0248         m_index += n;
0249         BOOST_ASSERT_MSG(m_index >= 0, "indexed Iterator out of bounds");
0250         m_it += n;
0251     }
0252
0253     difference_type distance_to(const indexed_iterator& other) const
0254     {
0255         return other.m_it - m_it;
0256     }
0257
0258     wrapped m_it;
0259     index_type m_index;
0260 };
0261
0262 template<typename SinglePassRange>
0263 struct indexed_range
0264     : iterator_range<
0265         indexed_iterator<
0266             typename range_iterator<SinglePassRange>::type
0267         >
0268     >
0269 {
0270     typedef iterator_range<
0271         indexed_iterator<
0272             typename range_iterator<SinglePassRange>::type
0273         >
0274     > base_t;
0275
0276     BOOST_RANGE_CONCEPT_ASSERT((
0277         boost::SinglePassRangeConcept<SinglePassRange>));
0278 public:
0279     typedef indexed_iterator<
0280         typename range_iterator<SinglePassRange>::type
0281     > iterator;
0282
0283     // Constructor for non-random access iterators.
0284     // This sets the end iterator index to i despite this being incorrect it
0285     // is never observable since bidirectional iterators are demoted to
0286     // forward iterators.
0287     indexed_range(
0288         typename base_t::difference_type i,
0289         SinglePassRange& r,
0290         single_pass_traversal_tag
0291         )
0292         : base_t(iterator(boost::begin(r), i),
0293                  iterator(boost::end(r), i))
0294     {
0295     }
0296
0297     indexed_range(
0298         typename base_t::difference_type i,
0299         SinglePassRange& r,
0300         random_access_traversal_tag
0301         )
0302         : base_t(iterator(boost::begin(r), i),
0303                  iterator(boost::end(r), i + boost::size(r)))
0304     {
0305     }
0306 };
0307
0308     } // namespace range_detail
0309
0310     using range_detail::indexed_range;
0311
0312     namespace adaptors
0313     {
0314
0315 template<class SinglePassRange>
0316 inline indexed_range<SinglePassRange>
0317 operator|(SinglePassRange& r, indexed e)
0318 {
0319     BOOST_RANGE_CONCEPT_ASSERT((
0320         boost::SinglePassRangeConcept<SinglePassRange>
0321     ));
0322     return indexed_range<SinglePassRange>(
0323                 e.val, r,
0324                 typename range_traversal<SinglePassRange>::type());
0325 }
0326
0327 template<class SinglePassRange>
0328 inline indexed_range<const SinglePassRange>
0329 operator|(const SinglePassRange& r, indexed e)
0330 {
0331     BOOST_RANGE_CONCEPT_ASSERT((
0332         boost::SinglePassRangeConcept<const SinglePassRange>
0333     ));
0334     return indexed_range<const SinglePassRange>(
0335                 e.val, r,
0336                 typename range_traversal<const SinglePassRange>::type());
0337 }
0338
0339 template<class SinglePassRange>
0340 inline indexed_range<SinglePassRange>
0341 index(
0342     SinglePassRange& rng,
0343     typename range_difference<SinglePassRange>::type index_value = 0)
0344 {
0345     BOOST_RANGE_CONCEPT_ASSERT((
0346         boost::SinglePassRangeConcept<SinglePassRange>
0347     ));
0348     return indexed_range<SinglePassRange>(
0349                 index_value, rng,
0350                 typename range_traversal<SinglePassRange>::type());
0351 }
0352
0353 template<class SinglePassRange>
0354 inline indexed_range<const SinglePassRange>
0355 index(
0356     const SinglePassRange& rng,
0357     typename range_difference<const SinglePassRange>::type index_value = 0)
0358 {
0359     BOOST_RANGE_CONCEPT_ASSERT((
0360         boost::SinglePassRangeConcept<SinglePassRange>
0361     ));
0362     return indexed_range<const SinglePassRange>(
0363                 index_value, rng,
0364                 typename range_traversal<const SinglePassRange>::type());
0365 }
0366
0367     } // namespace adaptors
0368 } // namespace boost
0369
0370 #if !defined(BOOST_NO_CXX11_HDR_TUPLE)
0371
0372 namespace std {
0373
0374 #if defined(BOOST_CLANG)
0375 #pragma clang diagnostic push
0376 #pragma clang diagnostic ignored "-Wmismatched-tags"
0377 #endif
0378
0379 template<size_t N, class T, class Indexable>
0380 struct tuple_element<N, boost::range::index_value<T, Indexable>>:
0381     boost::tuples::element<N, boost::range::index_value<T, Indexable>> {};
0382
0383 template<class T, class Indexable>
0384 struct tuple_size<boost::range::index_value<T, Indexable>>:
0385     std::integral_constant<std::size_t, 2> {};
0386
0387 #if defined(BOOST_CLANG)
0388 #pragma clang diagnostic pop
0389 #endif
0390
0391 } // namespace std
0392
0393 #endif // !defined(BOOST_NO_CXX11_HDR_TUPLE)
0394
0395 #endif // include guard