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