Re: [boost] cyclic buffer

From: Neal D. Becker (nbecker_at_[hidden])
Date: 2002-10-01 09:23:08

This is from Gennadiy Rozental.  I believe this is the latest
version. Please correct me if not.  Since it is small, I'll just post it here:

//  (C) Copyright Gennadiy Rozental 2002.
//  Permission to copy, use, modify, sell and distribute this software
//  is granted provided this copyright notice appears in all copies.
//  This software is provided "as is" without express or implied warranty,
//  and with no claim as to its suitability for any purpose.
//
//  See http://www.boost.org for most recent version including documentation.

#ifndef CYCLE_ITERATOR_HPP
#define CYCLE_ITERATOR_HPP

#include<boost/iterator_adaptors.hpp>

#include<utility>

namespace boost {

namespace detail{

template<typename BaseIterator>
class cycle_iterator_policy : public default_iterator_policies {
    typedef boost::detail::iterator_traits<BaseIterator>::difference_type difference_type;
public:
    // Constructors
    cycle_iterator_policy( BaseIterator const& b, BaseIterator const& e )
    : m_bounds( b, e )                                                  {}

    // policy implementation
    template<typename CycleIterator>
    void    increment( CycleIterator& x ) const
    {
        if( m_bounds.first == m_bounds.second )
            return;

        if( ++x.base() == m_bounds.second )
            x.base() = m_bounds.first;
    }

    template<typename CycleIterator>
    void    decrement( CycleIterator& x ) const
    {
        if( m_bounds.first == m_bounds.second )
            return;

        if( x.base() == m_bounds.first )
            x.base() = m_bounds.second;

        --x.base();
    }

    template <typename CycleIterator>
    void    advance( CycleIterator& x, difference_type n ) const
    {
        const difference_type cycle_size = m_bounds.second - m_bounds.first;
        
        if( cycle_size == 0 )
            return;

        n %= cycle_size;

        x.base() = m_bounds.first + ( x.base() - m_bounds.first + n + cycle_size ) % cycle_size;
    }

    template <class CycleIterator1, class CycleIterator2>
    difference_type
    distance(const CycleIterator1& x, const CycleIterator2& y) const
    {
        const difference_type cycle_size = m_bounds.second - m_bounds.first;
        
        if( cycle_size == 0 )
            return 0;

        return (y.base() - x.base() + cycle_size) % cycle_size;
    }

private:
    // Data members
    const std::pair<BaseIterator,BaseIterator>    m_bounds;
};

} // namespace detail

template<typename BaseIterator,
         typename Value = boost::detail::iterator_traits<BaseIterator>::value_type
>
struct cycle_iterator_generator {
    typedef detail::cycle_iterator_policy<BaseIterator>                         policies_type;
    typedef boost::iterator_adaptor<BaseIterator,policies_type,Value>           type;
};

template<typename BaseIterator, typename ConstBaseIterator,
         typename Value      = boost::detail::iterator_traits<BaseIterator>::value_type,
         typename ConstValue = boost::detail::iterator_traits<ConstBaseIterator>::value_type
>
struct cycle_iterator_pair_generator
{
    typedef detail::cycle_iterator_policy<BaseIterator>                         policies_type;
    typedef boost::iterator_adaptor<BaseIterator,policies_type,Value>           iterator;
    typedef boost::iterator_adaptor<ConstBaseIterator,policies_type,ConstValue> const_iterator;

};

#ifndef __SUNPRO_CC
template<typename BaseIterator>
typename cycle_iterator_generator<BaseIterator>::type
make_cycle_iterator( BaseIterator const& base, std::pair<BaseIterator, BaseIterator> const& range) {
    typedef typename cycle_iterator_generator<BaseIterator>::type ret_type;

    return ret_type( base, 
                     detail::cycle_iterator_policy<BaseIterator>( range.first, range.second ) );
}

template<typename BaseIterator>
typename cycle_iterator_generator<BaseIterator>::type
make_cycle_iterator( BaseIterator const& begin, BaseIterator const& end ) {
    typedef typename cycle_iterator_generator<BaseIterator>::type ret_type;

    return ret_type( begin, 
                     detail::cycle_iterator_policy<BaseIterator>( begin, end ) );
}

// template<class Container>
// typename cycle_iterator_generator<typename Container::iterator>::type
// make_cycle_iterator( Container& c ) {
//     typedef typename Container::iterator BaseIterator;
//     typedef typename cycle_iterator_generator<BaseIterator>::type ret_type;

//     return ret_type( c.begin(), 
//                      detail::cycle_iterator_policy<BaseIterator>( c.begin(), c.end() ) );
// }
#endif

} // namespace boost

#endif

//  Revision History
//   29 Jan 02  Initial version (Gennadiy Rozental)
//    3 Feb 02  Eliminate raising of iterator category (Gennadiy Rozental;Thanks to Thomas Witt)
//    3 Feb 02  Added cycle_iterator_pair_generator (Gennadiy Rozental;Thanks to Thomas Witt for poining out interoperability issue)
//    4 Feb 02  Added distance implementation (Gennadiy Rozental;Thanks to Neal Becker for pointing out need for it)
//   17 Feb 02  Removed <algorithm> include (Thomas Witt)
//   17 Feb 02  Added const qualifiers (Thomas Witt)
//   17 Feb 02  Made iterator parameters const& (Thomas Witt)
//   17 Feb 02  Added make_cycle_iterator with base parameter (Thomas Witt)