boost/range/adaptor/strided.hpp
// 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