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