Squashed 'third_party/boostorg/range/' content from commit 4cfd4d8
Change-Id: I641c49f21039952b16f888223a952503e43a28a9
git-subtree-dir: third_party/boostorg/range
git-subtree-split: 4cfd4d8287ca949d7f29256adf3e796a0d1775ec
diff --git a/include/boost/range/adaptor/indexed.hpp b/include/boost/range/adaptor/indexed.hpp
new file mode 100644
index 0000000..a426bd6
--- /dev/null
+++ b/include/boost/range/adaptor/indexed.hpp
@@ -0,0 +1,370 @@
+// 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