#ifndef cycle_iterator_H
#define cycle_iterator_H

#include <boost/iterator/iterator_adaptor.hpp>
#include <iterator>

namespace boost {

  //! This is a cycle iterator that does keep track of wraparound.
  template<typename BaseIterator, typename offset_t>
  class cycle_iterator : public boost::iterator_adaptor<cycle_iterator<BaseIterator, offset_t>,
							BaseIterator
						       >
  {
  public:
    typedef typename boost::iterator_adaptor<cycle_iterator<BaseIterator, offset_t>,
					     BaseIterator
					    > super_t;

    typedef typename super_t::difference_type difference_type;
    typedef typename super_t::value_type value_type;
    typedef typename super_t::reference reference;

    explicit cycle_iterator() {}

    explicit cycle_iterator (BaseIterator const& _b, BaseIterator const& _e, offset_t offset=0) :
      base(_b), size (_e-_b) {
      SetPos (offset);
    }

    template <typename OtherBase>
    cycle_iterator (cycle_iterator<OtherBase,offset_t> const& other) :
      base (other.base),
      size (other.size),
      position (other.position),
      wrap (other.wrap)
    {}

  private:
    friend class boost::iterator_core_access;
  

    void increment () {
      ++position;
      if (position >= size) {
	++wrap;
	position -= size;
      }
    }

    void decrement () {
      --position;
      if (position < 0) {
	--wrap;
	position += size;
      }
    }

    void SetPos (offset_t newpos) {
      position = newpos % size;
      wrap = newpos / size;
      if (position < 0) {
	--wrap;
	position += size;
      }
    }

    void advance (difference_type n) {
      offset_t newpos = realposition() + n;
      SetPos (newpos);
    }

    difference_type
    distance_to (cycle_iterator<BaseIterator, offset_t> const& y) const {
      if (size == 0)
	return 0;

      else {
	offset_t pos1 = realposition();
	offset_t pos2 = y.realposition();
	return -(pos1 - pos2);
      }
    }

    bool equal (cycle_iterator<BaseIterator, offset_t> const& y) const {
      return distance_to (y) == 0;
    }

    reference dereference() { return *(base + position); }

    const reference dereference() const { return *(base + position); }

   offset_t PositiveMod (offset_t x) const {
      offset_t y = x % size;
      if (y < 0)
	y += size;
      return y;
    }

  public:

    reference operator[] (difference_type n) { return *(base + PositiveMod (position + n)); }
    
    const reference operator[] (difference_type n) const { return *(base +PositiveMod (position + n)); }
  
    offset_t offset() const { return position; }

    offset_t realposition () const {
      return position + wrap * size;
    }


    //  private:

    BaseIterator base;
    offset_t size;
    offset_t position;
    offset_t wrap;
  };

  template<typename offset_t, typename BaseIterator>
  cycle_iterator<BaseIterator, offset_t> make_cycle_iterator(BaseIterator b, BaseIterator e, offset_t offset=0) {
    return cycle_iterator<BaseIterator, offset_t> (b, e, offset);
  }

  template<typename BaseIterator>
  cycle_iterator<BaseIterator, int> make_cycle_iterator(BaseIterator b, BaseIterator e, int offset=0) {
    return cycle_iterator<BaseIterator, int> (b, e, offset);
  }

} //namespace boost

#endif