Chris@101: //  Copyright 2014 Neil Groves
Chris@16: //
Chris@101: //  Copyright (c) 2010 Ilya Murav'jov
Chris@101: // 
Chris@101: //  Use, modification and distribution is subject to the Boost Software License,
Chris@101: //  Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //  http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@101: // Credits:
Chris@101: //  My (Neil's) first indexed adaptor was hindered by having the underlying
Chris@101: //  iterator return the same reference as the wrapped iterator. This meant that
Chris@101: //  to obtain the index one had to get to the index_iterator and call the
Chris@101: //  index() function on it. Ilya politely pointed out that this was useless in
Chris@101: //  a number of scenarios since one naturally hides the use of iterators in
Chris@101: //  good range-based code. Ilya provided a new interface (which has remained)
Chris@101: //  and a first implementation. Much of this original implementation has
Chris@101: //  been simplified and now supports more compilers and platforms.
Chris@16: //
Chris@101: #ifndef BOOST_RANGE_ADAPTOR_INDEXED_HPP_INCLUDED
Chris@101: #define BOOST_RANGE_ADAPTOR_INDEXED_HPP_INCLUDED
Chris@16: 
Chris@101: #include <boost/range/config.hpp>
Chris@16: #include <boost/range/adaptor/argument_fwd.hpp>
Chris@16: #include <boost/range/iterator_range.hpp>
Chris@101: #include <boost/range/traversal.hpp>
Chris@101: #include <boost/range/size.hpp>
Chris@16: #include <boost/range/begin.hpp>
Chris@16: #include <boost/range/end.hpp>
Chris@101: #include <boost/mpl/if.hpp>
Chris@101: #include <boost/type_traits/is_convertible.hpp>
Chris@16: 
Chris@101: #include <boost/iterator/iterator_traits.hpp>
Chris@101: #include <boost/iterator/iterator_facade.hpp>
Chris@16: 
Chris@101: #include <boost/tuple/tuple.hpp>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16:     namespace adaptors
Chris@16:     {
Chris@101: 
Chris@101: struct indexed
Chris@101: {
Chris@101:     explicit indexed(std::ptrdiff_t x = 0)
Chris@101:         : val(x)
Chris@101:     {
Chris@101:     }
Chris@101:     std::ptrdiff_t val;
Chris@101: };
Chris@101: 
Chris@101:     } // namespace adaptors
Chris@101: 
Chris@101:     namespace range
Chris@101:     {
Chris@101: 
Chris@101: // Why yet another "pair" class:
Chris@101: // - std::pair can't store references
Chris@101: // - no need for typing for index type (default to "std::ptrdiff_t"); this is
Chris@101: // useful in BOOST_FOREACH() expressions that have pitfalls with commas
Chris@101: //   ( see http://www.boost.org/doc/libs/1_44_0/doc/html/foreach/pitfalls.html )
Chris@101: // - meaningful access functions index(), value()
Chris@101: template<class T, class Indexable = std::ptrdiff_t>
Chris@101: class index_value
Chris@101:     : public tuple<Indexable, T>
Chris@101: {
Chris@101:     typedef tuple<Indexable, T> base_t;
Chris@101: 
Chris@101:     template<int N>
Chris@101:     struct iv_types
Chris@101:     {
Chris@101:         typedef typename tuples::element<N, base_t>::type n_type;
Chris@101: 
Chris@101:         typedef typename tuples::access_traits<n_type>::non_const_type non_const_type;
Chris@101:         typedef typename tuples::access_traits<n_type>::const_type const_type;
Chris@101:     };
Chris@101: 
Chris@101: public:
Chris@101:     typedef typename iv_types<0>::non_const_type index_type;
Chris@101:     typedef typename iv_types<0>::const_type const_index_type;
Chris@101:     typedef typename iv_types<1>::non_const_type value_type;
Chris@101:     typedef typename iv_types<1>::const_type const_value_type;
Chris@101: 
Chris@101:     index_value()
Chris@101:     {
Chris@16:     }
Chris@16: 
Chris@101:     index_value(typename tuples::access_traits<Indexable>::parameter_type t0,
Chris@101:                 typename tuples::access_traits<T>::parameter_type t1)
Chris@101:         : base_t(t0, t1)
Chris@16:     {
Chris@101:     }
Chris@16: 
Chris@101:     // member functions index(), value() (non-const and const)
Chris@101:     index_type index()
Chris@101:     {
Chris@101:         return boost::tuples::get<0>(*this);
Chris@101:     }
Chris@16: 
Chris@101:     const_index_type index() const
Chris@101:     {
Chris@101:         return boost::tuples::get<0>(*this);
Chris@101:     }
Chris@16: 
Chris@101:     value_type value()
Chris@101:     {
Chris@101:         return boost::tuples::get<1>(*this);
Chris@101:     }
Chris@16: 
Chris@101:     const_value_type value() const
Chris@101:     {
Chris@101:         return boost::tuples::get<1>(*this);
Chris@101:     }
Chris@101: };
Chris@16: 
Chris@101:     } // namespace range
Chris@16: 
Chris@101: namespace range_detail
Chris@101: {
Chris@16: 
Chris@101: template<typename Iter>
Chris@101: struct indexed_iterator_value_type
Chris@101: {
Chris@101:     typedef ::boost::range::index_value<
Chris@101:         typename iterator_reference<Iter>::type,
Chris@101:         typename iterator_difference<Iter>::type
Chris@101:     > type;
Chris@101: };
Chris@16: 
Chris@101: // Meta-function to get the traversal for the range and therefore iterator
Chris@101: // returned by the indexed adaptor for a specified iterator type.
Chris@101: //
Chris@101: // Random access -> Random access
Chris@101: // Bidirectional -> Forward
Chris@101: // Forward -> Forward
Chris@101: // SinglePass -> SinglePass
Chris@101: //
Chris@101: // The rationale for demoting a Bidirectional input to Forward is that the end
Chris@101: // iterator cannot cheaply have an index computed for it. Therefore I chose to
Chris@101: // demote to forward traversal. I can maintain the ability to traverse randomly
Chris@101: // when the input is Random Access since the index for the end iterator is cheap
Chris@101: // to compute.
Chris@101: template<typename Iter>
Chris@101: struct indexed_traversal
Chris@101: {
Chris@101: private:
Chris@101:     typedef typename iterator_traversal<Iter>::type wrapped_traversal;
Chris@16: 
Chris@101: public:
Chris@16: 
Chris@101:     typedef typename mpl::if_<
Chris@101:         is_convertible<wrapped_traversal, random_access_traversal_tag>,
Chris@101:         random_access_traversal_tag,
Chris@101:         typename mpl::if_<
Chris@101:             is_convertible<wrapped_traversal, bidirectional_traversal_tag>,
Chris@101:             forward_traversal_tag,
Chris@101:             wrapped_traversal
Chris@101:         >::type
Chris@101:     >::type type;
Chris@101: };
Chris@16: 
Chris@101: template<typename Iter>
Chris@101: class indexed_iterator
Chris@101:     : public iterator_facade<
Chris@101:             indexed_iterator<Iter>,
Chris@101:             typename indexed_iterator_value_type<Iter>::type,
Chris@101:             typename indexed_traversal<Iter>::type,
Chris@101:             typename indexed_iterator_value_type<Iter>::type,
Chris@101:             typename iterator_difference<Iter>::type
Chris@101:         >
Chris@101: {
Chris@101: public:
Chris@101:     typedef Iter wrapped;
Chris@16: 
Chris@101: private:
Chris@101:     typedef iterator_facade<
Chris@101:         indexed_iterator<wrapped>,
Chris@101:         typename indexed_iterator_value_type<wrapped>::type,
Chris@101:         typename indexed_traversal<wrapped>::type,
Chris@101:         typename indexed_iterator_value_type<wrapped>::type,
Chris@101:         typename iterator_difference<wrapped>::type
Chris@101:     > base_t;
Chris@101: 
Chris@101: public:
Chris@101:     typedef typename base_t::difference_type difference_type;
Chris@101:     typedef typename base_t::reference reference;
Chris@101:     typedef typename base_t::difference_type index_type;
Chris@101: 
Chris@101:     indexed_iterator()
Chris@101:         : m_it()
Chris@101:         , m_index()
Chris@101:     {
Chris@101:     }
Chris@101: 
Chris@101:     template<typename OtherWrapped>
Chris@101:     indexed_iterator(
Chris@101:         const indexed_iterator<OtherWrapped>& other,
Chris@101:         typename enable_if<is_convertible<OtherWrapped, wrapped> >::type* = 0
Chris@101:     )
Chris@101:         : m_it(other.get())
Chris@101:         , m_index(other.get_index())
Chris@101:     {
Chris@101:     }
Chris@101: 
Chris@101:     explicit indexed_iterator(wrapped it, index_type index)
Chris@101:         : m_it(it)
Chris@101:         , m_index(index)
Chris@101:     {
Chris@101:     }
Chris@101: 
Chris@101:     wrapped get() const
Chris@101:     {
Chris@101:         return m_it;
Chris@101:     }
Chris@101: 
Chris@101:     index_type get_index() const
Chris@101:     {
Chris@101:         return m_index;
Chris@101:     }
Chris@101: 
Chris@101:  private:
Chris@101:     friend class boost::iterator_core_access;
Chris@101: 
Chris@101:     reference dereference() const
Chris@101:     {
Chris@101:         return reference(m_index, *m_it);
Chris@101:     }
Chris@101: 
Chris@101:     bool equal(const indexed_iterator& other) const
Chris@101:     {
Chris@101:         return m_it == other.m_it;
Chris@101:     }
Chris@101: 
Chris@101:     void increment()
Chris@101:     {
Chris@101:         ++m_index;
Chris@101:         ++m_it;
Chris@101:     }
Chris@101: 
Chris@101:     void decrement()
Chris@101:     {
Chris@101:         BOOST_ASSERT_MSG(m_index > 0, "indexed Iterator out of bounds");
Chris@101:         --m_index;
Chris@101:         --m_it;
Chris@101:     }
Chris@101: 
Chris@101:     void advance(index_type n)
Chris@101:     {
Chris@101:         m_index += n;
Chris@101:         BOOST_ASSERT_MSG(m_index >= 0, "indexed Iterator out of bounds");
Chris@101:         m_it += n;
Chris@101:     }
Chris@101: 
Chris@101:     difference_type distance_to(const indexed_iterator& other) const
Chris@101:     {
Chris@101:         return other.m_it - m_it;
Chris@101:     }
Chris@101: 
Chris@101:     wrapped m_it;
Chris@101:     index_type m_index;
Chris@101: };
Chris@101: 
Chris@101: template<typename SinglePassRange>
Chris@101: struct indexed_range
Chris@101:     : iterator_range<
Chris@101:         indexed_iterator<
Chris@101:             typename range_iterator<SinglePassRange>::type
Chris@101:         >
Chris@101:     >
Chris@101: {
Chris@101:     typedef iterator_range<
Chris@101:         indexed_iterator<
Chris@101:             typename range_iterator<SinglePassRange>::type
Chris@101:         >
Chris@101:     > base_t;
Chris@101: 
Chris@101:     BOOST_RANGE_CONCEPT_ASSERT((
Chris@101:         boost::SinglePassRangeConcept<SinglePassRange>));
Chris@101: public:
Chris@101:     typedef indexed_iterator<
Chris@101:         typename range_iterator<SinglePassRange>::type
Chris@101:     > iterator;
Chris@101: 
Chris@101:     // Constructor for non-random access iterators.
Chris@101:     // This sets the end iterator index to i despite this being incorrect it
Chris@101:     // is never observable since bidirectional iterators are demoted to
Chris@101:     // forward iterators.
Chris@101:     indexed_range(
Chris@101:         typename base_t::difference_type i,
Chris@101:         SinglePassRange& r,
Chris@101:         single_pass_traversal_tag
Chris@101:         )
Chris@101:         : base_t(iterator(boost::begin(r), i),
Chris@101:                  iterator(boost::end(r), i))
Chris@101:     {
Chris@101:     }
Chris@101: 
Chris@101:     indexed_range(
Chris@101:         typename base_t::difference_type i,
Chris@101:         SinglePassRange& r,
Chris@101:         random_access_traversal_tag
Chris@101:         )
Chris@101:         : base_t(iterator(boost::begin(r), i),
Chris@101:                  iterator(boost::end(r), i + boost::size(r)))
Chris@101:     {
Chris@101:     }
Chris@101: };
Chris@101: 
Chris@101:     } // namespace range_detail 
Chris@101: 
Chris@16:     using range_detail::indexed_range;
Chris@16: 
Chris@16:     namespace adaptors
Chris@16:     {
Chris@16: 
Chris@101: template<class SinglePassRange>
Chris@101: inline indexed_range<SinglePassRange>
Chris@101: operator|(SinglePassRange& r, indexed e)
Chris@101: {
Chris@101:     BOOST_RANGE_CONCEPT_ASSERT((
Chris@101:         boost::SinglePassRangeConcept<SinglePassRange>
Chris@101:     ));
Chris@101:     return indexed_range<SinglePassRange>(
Chris@101:                 e.val, r,
Chris@101:                 typename range_traversal<SinglePassRange>::type());
Chris@16: }
Chris@16: 
Chris@101: template<class SinglePassRange>
Chris@101: inline indexed_range<const SinglePassRange>
Chris@101: operator|(const SinglePassRange& r, indexed e)
Chris@101: {
Chris@101:     BOOST_RANGE_CONCEPT_ASSERT((
Chris@101:         boost::SinglePassRangeConcept<const SinglePassRange>
Chris@101:     ));
Chris@101:     return indexed_range<const SinglePassRange>(
Chris@101:                 e.val, r,
Chris@101:                 typename range_traversal<const SinglePassRange>::type());
Chris@101: }
Chris@16: 
Chris@101: template<class SinglePassRange>
Chris@101: inline indexed_range<SinglePassRange>
Chris@101: index(
Chris@101:     SinglePassRange& rng,
Chris@101:     typename range_difference<SinglePassRange>::type index_value = 0)
Chris@101: {
Chris@101:     BOOST_RANGE_CONCEPT_ASSERT((
Chris@101:         boost::SinglePassRangeConcept<SinglePassRange>
Chris@101:     ));
Chris@101:     return indexed_range<SinglePassRange>(
Chris@101:                 index_value, rng,
Chris@101:                 typename range_traversal<SinglePassRange>::type());
Chris@101: }
Chris@101: 
Chris@101: template<class SinglePassRange>
Chris@101: inline indexed_range<const SinglePassRange>
Chris@101: index(
Chris@101:     const SinglePassRange& rng,
Chris@101:     typename range_difference<const SinglePassRange>::type index_value = 0)
Chris@101: {
Chris@101:     BOOST_RANGE_CONCEPT_ASSERT((
Chris@101:         boost::SinglePassRangeConcept<SinglePassRange>
Chris@101:     ));
Chris@101:     return indexed_range<const SinglePassRange>(
Chris@101:                 index_value, rng,
Chris@101:                 typename range_traversal<const SinglePassRange>::type());
Chris@101: }
Chris@101: 
Chris@101:     } // namespace adaptors
Chris@101: } // namespace boost
Chris@101: 
Chris@101: #endif // include guard