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/strided.hpp b/include/boost/range/adaptor/strided.hpp
new file mode 100644
index 0000000..560b820
--- /dev/null
+++ b/include/boost/range/adaptor/strided.hpp
@@ -0,0 +1,697 @@
+// Boost.Range library
+//
+// Copyright Neil Groves 2007. 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)
+//
+//
+// For more information, see http://www.boost.org/libs/range/
+//
+#ifndef BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
+#define BOOST_RANGE_ADAPTOR_STRIDED_HPP_INCLUDED
+
+#include <boost/range/adaptor/argument_fwd.hpp>
+#include <boost/range/iterator_range.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+#include <iterator>
+
+namespace boost
+{
+ namespace range_detail
+ {
+ // strided_iterator for wrapping a forward traversal iterator
+ template<class BaseIterator, class Category>
+ class strided_iterator
+ : public iterator_facade<
+ strided_iterator<BaseIterator, Category>
+ , typename iterator_value<BaseIterator>::type
+ , forward_traversal_tag
+ , typename iterator_reference<BaseIterator>::type
+ , typename iterator_difference<BaseIterator>::type
+ >
+ {
+ friend class ::boost::iterator_core_access;
+
+ typedef iterator_facade<
+ strided_iterator<BaseIterator, Category>
+ , typename iterator_value<BaseIterator>::type
+ , forward_traversal_tag
+ , typename iterator_reference<BaseIterator>::type
+ , typename iterator_difference<BaseIterator>::type
+ > super_t;
+
+ public:
+ typedef typename super_t::difference_type difference_type;
+ typedef typename super_t::reference reference;
+ typedef BaseIterator base_iterator;
+ typedef std::forward_iterator_tag iterator_category;
+
+ strided_iterator()
+ : m_it()
+ , m_last()
+ , m_stride()
+ {
+ }
+
+ strided_iterator(base_iterator it,
+ base_iterator last,
+ difference_type stride)
+ : m_it(it)
+ , m_last(last)
+ , m_stride(stride)
+ {
+ }
+
+ template<class OtherIterator>
+ strided_iterator(
+ const strided_iterator<OtherIterator, Category>& other,
+ typename enable_if_convertible<
+ OtherIterator,
+ base_iterator
+ >::type* = 0
+ )
+ : m_it(other.base())
+ , m_last(other.base_end())
+ , m_stride(other.get_stride())
+ {
+ }
+
+ base_iterator base() const
+ {
+ return m_it;
+ }
+
+ base_iterator base_end() const
+ {
+ return m_last;
+ }
+
+ difference_type get_stride() const
+ {
+ return m_stride;
+ }
+
+ private:
+ void increment()
+ {
+ for (difference_type i = 0;
+ (m_it != m_last) && (i < m_stride); ++i)
+ {
+ ++m_it;
+ }
+ }
+
+ reference dereference() const
+ {
+ return *m_it;
+ }
+
+ template<class OtherIterator>
+ bool equal(
+ const strided_iterator<OtherIterator, Category>& other,
+ typename enable_if_convertible<
+ OtherIterator,
+ base_iterator
+ >::type* = 0) const
+ {
+ return m_it == other.m_it;
+ }
+
+ base_iterator m_it;
+ base_iterator m_last;
+ difference_type m_stride;
+ };
+
+ // strided_iterator for wrapping a bidirectional iterator
+ template<class BaseIterator>
+ class strided_iterator<BaseIterator, bidirectional_traversal_tag>
+ : public iterator_facade<
+ strided_iterator<BaseIterator, bidirectional_traversal_tag>
+ , typename iterator_value<BaseIterator>::type
+ , bidirectional_traversal_tag
+ , typename iterator_reference<BaseIterator>::type
+ , typename iterator_difference<BaseIterator>::type
+ >
+ {
+ friend class ::boost::iterator_core_access;
+
+ typedef iterator_facade<
+ strided_iterator<BaseIterator, bidirectional_traversal_tag>
+ , typename iterator_value<BaseIterator>::type
+ , bidirectional_traversal_tag
+ , typename iterator_reference<BaseIterator>::type
+ , typename iterator_difference<BaseIterator>::type
+ > super_t;
+ public:
+ typedef typename super_t::difference_type difference_type;
+ typedef typename super_t::reference reference;
+ typedef BaseIterator base_iterator;
+ typedef typename boost::make_unsigned<difference_type>::type
+ size_type;
+ typedef std::bidirectional_iterator_tag iterator_category;
+
+ strided_iterator()
+ : m_it()
+ , m_offset()
+ , m_index()
+ , m_stride()
+ {
+ }
+
+ strided_iterator(base_iterator it,
+ size_type index,
+ difference_type stride)
+ : m_it(it)
+ , m_offset()
+ , m_index(index)
+ , m_stride(stride)
+ {
+ if (stride && ((m_index % stride) != 0))
+ m_index += (stride - (m_index % stride));
+ }
+
+ template<class OtherIterator>
+ strided_iterator(
+ const strided_iterator<
+ OtherIterator,
+ bidirectional_traversal_tag
+ >& other,
+ typename enable_if_convertible<
+ OtherIterator,
+ base_iterator
+ >::type* = 0
+ )
+ : m_it(other.base())
+ , m_offset(other.get_offset())
+ , m_index(other.get_index())
+ , m_stride(other.get_stride())
+ {
+ }
+
+ base_iterator base() const
+ {
+ return m_it;
+ }
+
+ difference_type get_offset() const
+ {
+ return m_offset;
+ }
+
+ size_type get_index() const
+ {
+ return m_index;
+ }
+
+ difference_type get_stride() const
+ {
+ return m_stride;
+ }
+
+ private:
+ void increment()
+ {
+ m_offset += m_stride;
+ }
+
+ void decrement()
+ {
+ m_offset -= m_stride;
+ }
+
+ reference dereference() const
+ {
+ update();
+ return *m_it;
+ }
+
+ void update() const
+ {
+ std::advance(m_it, m_offset);
+ m_index += m_offset;
+ m_offset = 0;
+ }
+
+ template<class OtherIterator>
+ bool equal(
+ const strided_iterator<
+ OtherIterator,
+ bidirectional_traversal_tag
+ >& other,
+ typename enable_if_convertible<
+ OtherIterator,
+ base_iterator
+ >::type* = 0) const
+ {
+ return (m_index + m_offset) ==
+ (other.get_index() + other.get_offset());
+ }
+
+ mutable base_iterator m_it;
+ mutable difference_type m_offset;
+ mutable size_type m_index;
+ difference_type m_stride;
+ };
+
+ // strided_iterator implementation for wrapping a random access iterator
+ template<class BaseIterator>
+ class strided_iterator<BaseIterator, random_access_traversal_tag>
+ : public iterator_facade<
+ strided_iterator<BaseIterator, random_access_traversal_tag>
+ , typename iterator_value<BaseIterator>::type
+ , random_access_traversal_tag
+ , typename iterator_reference<BaseIterator>::type
+ , typename iterator_difference<BaseIterator>::type
+ >
+ {
+ friend class ::boost::iterator_core_access;
+
+ typedef iterator_facade<
+ strided_iterator<BaseIterator, random_access_traversal_tag>
+ , typename iterator_value<BaseIterator>::type
+ , random_access_traversal_tag
+ , typename iterator_reference<BaseIterator>::type
+ , typename iterator_difference<BaseIterator>::type
+ > super_t;
+ public:
+ typedef typename super_t::difference_type difference_type;
+ typedef typename super_t::reference reference;
+ typedef BaseIterator base_iterator;
+ typedef std::random_access_iterator_tag iterator_category;
+
+ strided_iterator()
+ : m_it()
+ , m_first()
+ , m_index(0)
+ , m_stride()
+ {
+ }
+
+ strided_iterator(
+ base_iterator first,
+ base_iterator it,
+ difference_type stride
+ )
+ : m_it(it)
+ , m_first(first)
+ , m_index(stride ? (it - first) : difference_type())
+ , m_stride(stride)
+ {
+ if (stride && ((m_index % stride) != 0))
+ m_index += (stride - (m_index % stride));
+ }
+
+ template<class OtherIterator>
+ strided_iterator(
+ const strided_iterator<
+ OtherIterator,
+ random_access_traversal_tag
+ >& other,
+ typename enable_if_convertible<
+ OtherIterator,
+ base_iterator
+ >::type* = 0
+ )
+ : m_it(other.base())
+ , m_first(other.base_begin())
+ , m_index(other.get_index())
+ , m_stride(other.get_stride())
+ {
+ }
+
+ base_iterator base_begin() const
+ {
+ return m_first;
+ }
+
+ base_iterator base() const
+ {
+ return m_it;
+ }
+
+ difference_type get_stride() const
+ {
+ return m_stride;
+ }
+
+ difference_type get_index() const
+ {
+ return m_index;
+ }
+
+ private:
+ void increment()
+ {
+ m_index += m_stride;
+ }
+
+ void decrement()
+ {
+ m_index -= m_stride;
+ }
+
+ void advance(difference_type offset)
+ {
+ m_index += (m_stride * offset);
+ }
+
+ // Implementation detail: only update the actual underlying iterator
+ // at the point of dereference. This is done so that the increment
+ // and decrement can overshoot the valid sequence as is required
+ // by striding. Since we can do all comparisons just with the index
+ // simply, and all dereferences must be within the valid range.
+ void update() const
+ {
+ m_it = m_first + m_index;
+ }
+
+ template<class OtherIterator>
+ difference_type distance_to(
+ const strided_iterator<
+ OtherIterator,
+ random_access_traversal_tag
+ >& other,
+ typename enable_if_convertible<
+ OtherIterator, base_iterator>::type* = 0) const
+ {
+ BOOST_ASSERT((other.m_index - m_index) % m_stride == difference_type());
+ return (other.m_index - m_index) / m_stride;
+ }
+
+ template<class OtherIterator>
+ bool equal(
+ const strided_iterator<
+ OtherIterator,
+ random_access_traversal_tag
+ >& other,
+ typename enable_if_convertible<
+ OtherIterator, base_iterator>::type* = 0) const
+ {
+ return m_index == other.m_index;
+ }
+
+ reference dereference() const
+ {
+ update();
+ return *m_it;
+ }
+
+ private:
+ mutable base_iterator m_it;
+ base_iterator m_first;
+ difference_type m_index;
+ difference_type m_stride;
+ };
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<Rng>::type,
+ forward_traversal_tag
+ >
+ make_begin_strided_iterator(
+ Rng& rng,
+ Difference stride,
+ forward_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<Rng>::type,
+ forward_traversal_tag
+ >(boost::begin(rng), boost::end(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<const Rng>::type,
+ forward_traversal_tag
+ >
+ make_begin_strided_iterator(
+ const Rng& rng,
+ Difference stride,
+ forward_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<const Rng>::type,
+ forward_traversal_tag
+ >(boost::begin(rng), boost::end(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<Rng>::type,
+ forward_traversal_tag
+ >
+ make_end_strided_iterator(
+ Rng& rng,
+ Difference stride,
+ forward_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<Rng>::type,
+ forward_traversal_tag
+ >(boost::end(rng), boost::end(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<const Rng>::type,
+ forward_traversal_tag
+ >
+ make_end_strided_iterator(
+ const Rng& rng,
+ Difference stride,
+ forward_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<const Rng>::type,
+ forward_traversal_tag
+ >(boost::end(rng), boost::end(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<Rng>::type,
+ bidirectional_traversal_tag
+ >
+ make_begin_strided_iterator(
+ Rng& rng,
+ Difference stride,
+ bidirectional_traversal_tag)
+ {
+ typedef typename range_difference<Rng>::type difference_type;
+
+ return strided_iterator<
+ typename range_iterator<Rng>::type,
+ bidirectional_traversal_tag
+ >(boost::begin(rng), difference_type(), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<const Rng>::type,
+ bidirectional_traversal_tag
+ >
+ make_begin_strided_iterator(
+ const Rng& rng,
+ Difference stride,
+ bidirectional_traversal_tag)
+ {
+ typedef typename range_difference<const Rng>::type difference_type;
+
+ return strided_iterator<
+ typename range_iterator<const Rng>::type,
+ bidirectional_traversal_tag
+ >(boost::begin(rng), difference_type(), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<Rng>::type,
+ bidirectional_traversal_tag
+ >
+ make_end_strided_iterator(
+ Rng& rng,
+ Difference stride,
+ bidirectional_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<Rng>::type,
+ bidirectional_traversal_tag
+ >(boost::end(rng), boost::size(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<const Rng>::type,
+ bidirectional_traversal_tag
+ >
+ make_end_strided_iterator(
+ const Rng& rng,
+ Difference stride,
+ bidirectional_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<const Rng>::type,
+ bidirectional_traversal_tag
+ >(boost::end(rng), boost::size(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<Rng>::type,
+ random_access_traversal_tag
+ >
+ make_begin_strided_iterator(
+ Rng& rng,
+ Difference stride,
+ random_access_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<Rng>::type,
+ random_access_traversal_tag
+ >(boost::begin(rng), boost::begin(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<const Rng>::type,
+ random_access_traversal_tag
+ >
+ make_begin_strided_iterator(
+ const Rng& rng,
+ Difference stride,
+ random_access_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<const Rng>::type,
+ random_access_traversal_tag
+ >(boost::begin(rng), boost::begin(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<Rng>::type,
+ random_access_traversal_tag
+ >
+ make_end_strided_iterator(
+ Rng& rng,
+ Difference stride,
+ random_access_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<Rng>::type,
+ random_access_traversal_tag
+ >(boost::begin(rng), boost::end(rng), stride);
+ }
+
+ template<class Rng, class Difference> inline
+ strided_iterator<
+ typename range_iterator<const Rng>::type,
+ random_access_traversal_tag
+ >
+ make_end_strided_iterator(
+ const Rng& rng,
+ Difference stride,
+ random_access_traversal_tag)
+ {
+ return strided_iterator<
+ typename range_iterator<const Rng>::type,
+ random_access_traversal_tag
+ >(boost::begin(rng), boost::end(rng), stride);
+ }
+
+ template<
+ class Rng,
+ class Category =
+ typename iterators::pure_iterator_traversal<
+ typename range_iterator<Rng>::type
+ >::type
+ >
+ class strided_range
+ : public iterator_range<
+ range_detail::strided_iterator<
+ typename range_iterator<Rng>::type,
+ Category
+ >
+ >
+ {
+ typedef range_detail::strided_iterator<
+ typename range_iterator<Rng>::type,
+ Category
+ > iter_type;
+ typedef iterator_range<iter_type> super_t;
+ public:
+ template<class Difference>
+ strided_range(Difference stride, Rng& rng)
+ : super_t(
+ range_detail::make_begin_strided_iterator(
+ rng, stride,
+ typename iterator_traversal<
+ typename range_iterator<Rng>::type
+ >::type()),
+ range_detail::make_end_strided_iterator(
+ rng, stride,
+ typename iterator_traversal<
+ typename range_iterator<Rng>::type
+ >::type()))
+ {
+ BOOST_ASSERT( stride >= 0 );
+ }
+ };
+
+ template<class Difference>
+ class strided_holder : public holder<Difference>
+ {
+ public:
+ explicit strided_holder(Difference value)
+ : holder<Difference>(value)
+ {
+ }
+ };
+
+ template<class Rng, class Difference>
+ inline strided_range<Rng>
+ operator|(Rng& rng, const strided_holder<Difference>& stride)
+ {
+ return strided_range<Rng>(stride.val, rng);
+ }
+
+ template<class Rng, class Difference>
+ inline strided_range<const Rng>
+ operator|(const Rng& rng, const strided_holder<Difference>& stride)
+ {
+ return strided_range<const Rng>(stride.val, rng);
+ }
+
+ } // namespace range_detail
+
+ using range_detail::strided_range;
+
+ namespace adaptors
+ {
+
+ namespace
+ {
+ const range_detail::forwarder<range_detail::strided_holder>
+ strided = range_detail::forwarder<
+ range_detail::strided_holder>();
+ }
+
+ template<class Range, class Difference>
+ inline strided_range<Range>
+ stride(Range& rng, Difference step)
+ {
+ return strided_range<Range>(step, rng);
+ }
+
+ template<class Range, class Difference>
+ inline strided_range<const Range>
+ stride(const Range& rng, Difference step)
+ {
+ return strided_range<const Range>(step, rng);
+ }
+
+ } // namespace 'adaptors'
+} // namespace 'boost'
+
+#endif