//  (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/iterator_adaptor.hpp>
#include<utility>

namespace boost {

  template<typename BaseIterator>
  class cycle_iterator : public boost::iterator_adaptor<
    cycle_iterator<BaseIterator>,
    BaseIterator> {

    friend class iterator_core_access;

  public:

    typedef typename boost::iterator_adaptor<cycle_iterator<BaseIterator>,BaseIterator> super_t;
    typedef typename std::iterator_traits<BaseIterator>::difference_type difference_type;

    cycle_iterator() {}

    static BaseIterator reduce (BaseIterator c, BaseIterator b, BaseIterator e) {
      difference_type size = e - b;
      difference_type offset = (c - b) % size;
      if (offset < 0)
	offset += size;
      return b + offset;
    }

    explicit cycle_iterator (BaseIterator _base, BaseIterator const& b, BaseIterator const& e) :
      super_t (reduce(_base, b, e)), m_bounds (b, e) {}

    void increment () {
      if (m_bounds.first == m_bounds.second)
	return;

      if (++base_reference() == m_bounds.second )
	base_reference() = m_bounds.first;
    }

    void decrement () {
      if(m_bounds.first == m_bounds.second)
	return;

      if (base_reference() == m_bounds.first)
	base_reference() = m_bounds.second;

      --base_reference();
    }

    void advance (difference_type n) {
      const difference_type cycle_size = m_bounds.second - m_bounds.first;
      if (cycle_size == 0)
            return;

      else
	base_reference() = reduce (base_reference() + n, m_bounds.first, m_bounds.second);
    }

    difference_type
    distance_to (cycle_iterator<BaseIterator> const& y) const {
      const difference_type cycle_size = m_bounds.second - m_bounds.first;
      if (cycle_size == 0)
	return 0;

      else
	return -((base_reference() - y.base_reference() + cycle_size) % cycle_size);
    }

private:

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

  template<typename BaseIterator>
  cycle_iterator<BaseIterator> make_cycle_iterator(BaseIterator current, BaseIterator b, BaseIterator e) {
    return cycle_iterator<BaseIterator> (current, b, e);
  }

} // 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)
//   13 Apr 04  Convert to new iterator_adaptor (Neal Becker)