boost/range/irange.hpp
// Boost.Range library
//
// Copyright Neil Groves 2010. 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_IRANGE_HPP_INCLUDED
#define BOOST_RANGE_IRANGE_HPP_INCLUDED
#include <boost/assert.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/range/iterator_range.hpp>
namespace boost
{
namespace range_detail
{
// integer_iterator is an iterator over an integer sequence that
// is bounded only by the limits of the underlying integer
// representation.
//
// This is useful for implementing the irange(first, last)
// function.
//
// Note:
// This use of this iterator and irange is appreciably less
// performant than the corresponding hand-written integer
// loop on many compilers.
template<typename Integer>
class integer_iterator
: public boost::iterator_facade<
integer_iterator<Integer>,
Integer,
boost::random_access_traversal_tag,
Integer,
std::ptrdiff_t
>
{
typedef boost::iterator_facade<
integer_iterator<Integer>,
Integer,
boost::random_access_traversal_tag,
Integer,
std::ptrdiff_t
> base_t;
public:
typedef typename base_t::value_type value_type;
typedef typename base_t::difference_type difference_type;
typedef typename base_t::reference reference;
integer_iterator() : m_value() {}
explicit integer_iterator(value_type x) : m_value(x) {}
private:
void increment()
{
++m_value;
}
void decrement()
{
--m_value;
}
void advance(difference_type offset)
{
m_value += offset;
}
difference_type distance_to(const integer_iterator& other) const
{
return other.m_value - m_value;
}
bool equal(const integer_iterator& other) const
{
return m_value == other.m_value;
}
reference dereference() const
{
return m_value;
}
friend class ::boost::iterator_core_access;
value_type m_value;
};
// integer_iterator_with_step is similar in nature to the
// integer_iterator but provides the ability to 'move' in
// a number of steps specified at construction time.
//
// The three variable implementation provides the best guarantees
// of loop termination upon various combinations of input.
//
// While this design is less performant than some less
// safe alternatives, the use of ranges and iterators to
// perform counting will never be optimal anyhow, hence
// if optimal performance is desired a hand-coded loop
// is the solution.
template<typename Integer>
class integer_iterator_with_step
: public boost::iterator_facade<
integer_iterator_with_step<Integer>,
Integer,
boost::random_access_traversal_tag,
Integer,
std::ptrdiff_t
>
{
typedef boost::iterator_facade<
integer_iterator_with_step<Integer>,
Integer,
boost::random_access_traversal_tag,
Integer,
std::ptrdiff_t
> base_t;
public:
typedef typename base_t::value_type value_type;
typedef typename base_t::difference_type difference_type;
typedef typename base_t::reference reference;
integer_iterator_with_step(value_type first, difference_type step, value_type step_size)
: m_first(first)
, m_step(step)
, m_step_size(step_size)
{
}
private:
void increment()
{
++m_step;
}
void decrement()
{
--m_step;
}
void advance(difference_type offset)
{
m_step += offset;
}
difference_type distance_to(const integer_iterator_with_step& other) const
{
return other.m_step - m_step;
}
bool equal(const integer_iterator_with_step& other) const
{
return m_step == other.m_step;
}
reference dereference() const
{
return m_first + (m_step * m_step_size);
}
friend class ::boost::iterator_core_access;
value_type m_first;
value_type m_step;
difference_type m_step_size;
};
} // namespace range_detail
template<typename Integer>
class integer_range
: public iterator_range< range_detail::integer_iterator<Integer> >
{
typedef range_detail::integer_iterator<Integer> iterator_t;
typedef iterator_range<iterator_t> base_t;
public:
integer_range(Integer first, Integer last)
: base_t(iterator_t(first), iterator_t(last))
{
}
};
template<typename Integer>
class strided_integer_range
: public iterator_range< range_detail::integer_iterator_with_step<Integer> >
{
typedef range_detail::integer_iterator_with_step<Integer> iterator_t;
typedef iterator_range<iterator_t> base_t;
public:
template<typename Iterator>
strided_integer_range(Iterator first, Iterator last)
: base_t(first, last)
{
}
};
template<typename Integer>
integer_range<Integer>
irange(Integer first, Integer last)
{
BOOST_ASSERT( first <= last );
return integer_range<Integer>(first, last);
}
template<typename Integer, typename StepSize>
strided_integer_range<Integer>
irange(Integer first, Integer last, StepSize step_size)
{
BOOST_ASSERT( step_size != 0 );
BOOST_ASSERT( (step_size > 0) ? (last >= first) : (last <= first) );
typedef typename range_detail::integer_iterator_with_step<Integer> iterator_t;
const std::ptrdiff_t sz = static_cast<std::ptrdiff_t>(step_size >= 0 ? step_size : -step_size);
const Integer l = step_size >= 0 ? last : first;
const Integer f = step_size >= 0 ? first : last;
const std::ptrdiff_t num_steps = (l + ((l-f) % sz) - f) / sz;
BOOST_ASSERT(num_steps >= 0);
return strided_integer_range<Integer>(
iterator_t(first, 0, step_size),
iterator_t(first, num_steps, step_size));
}
} // namespace boost
#endif // include guard