diff options
Diffstat (limited to 'src/third_party/boost-1.60.0/boost/range/adaptor/strided.hpp')
| -rw-r--r-- | src/third_party/boost-1.60.0/boost/range/adaptor/strided.hpp | 697 |
1 files changed, 697 insertions, 0 deletions
diff --git a/src/third_party/boost-1.60.0/boost/range/adaptor/strided.hpp b/src/third_party/boost-1.60.0/boost/range/adaptor/strided.hpp new file mode 100644 index 00000000000..560b8200c76 --- /dev/null +++ b/src/third_party/boost-1.60.0/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 |