/*
 * (C) Copyright Gennadiy Rozental 2002.
 * (C) Copyright Neal D. Becker (2004)
 * 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.
*/

#ifndef cycle_facade_H
#define cycle_facade_H

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

namespace boost {

template<typename BaseIterator>
class cycle_facade : public boost::iterator_facade<cycle_facade<BaseIterator>,
						   typename std::iterator_traits<BaseIterator>::value_type,
						   boost::random_access_traversal_tag
						   >
{
public:
  typedef typename boost::iterator_facade<cycle_facade<BaseIterator>,
					  typename std::iterator_traits<BaseIterator>::value_type,
					  boost::random_access_traversal_tag
					  > 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_facade (BaseIterator _base, BaseIterator const& _b, BaseIterator const& _e) :
    b(_b), e(_e), base (reduce (_base, _b, _e)) {}


private:
  friend class boost::iterator_core_access;

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

  void increment () {
    if (b == e)
      return;

    if (++base == e)
      base = b;
  }

  void decrement () {
    if (b == e)
      return;

    if (base == b)
      base = e;

    --base;
  }

  void advance (difference_type n) {
    const difference_type size = e - b;
    if (size == 0)
      return;

    else
      base = reduce (base + n, b, e);
  }

  difference_type
  distance_to (cycle_facade<BaseIterator> const& y) const {
    const difference_type size = e - b;
    if (size == 0)
      return 0;

    else
      return -((base - y.base + size) % size);
  }

  bool equal (cycle_facade<BaseIterator> const& y) const {
    return base == y.base;
  }

  reference dereference() const { return *base; }

public:

  reference operator[] (int n) { return *reduce (base+n, b, e); }

  const reference operator[] (int n) const { return *reduce (base+n, b, e); }

private:

  /*const*/ BaseIterator b; //not const for default assign
  /*const*/ BaseIterator e;
  BaseIterator base;
};

template<typename BaseIterator>
cycle_facade<BaseIterator> make_cycle_facade(BaseIterator current, BaseIterator b, BaseIterator e) {
  return cycle_facade<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)
//   14 Apr 04  Convert to facade (Neal Becker)