/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *

 	Modified file Copyright (c) 1996
 	Evelio Perez-Albuerne  <thoth256@hway.net>
   http://www.hway.net/thoth256

 	Permission to use, copy, modify, distribute and sell this software
	and its documentation for any purpose is hereby granted without fee,
	provided that the above copyright notice appear in all copies and
	that both that copyright notice and this permission notice appear
	in supporting documentation.  I make no representations about the
   suitability of this software for any purpose.  It is provided
   "as is" without express or implied warranty.

   	ring<T> container
   	Version 1.01
      4/16/96

   Changes in this version: Fixed comparison operator so that both
   	size and capacity must match to proceed to the item-by-item
      comparison. Added E-mail and WWW site addresses to comments
      section.
*/

#ifndef RING_H
#define RING_H

#include <stdcomp.h>

#include <function>
#include <iterator>
#include <algorith>

#ifndef Allocator
#define Allocator allocator
#include <memory>
#endif

#ifndef ring
#define ring ring
#endif

#ifndef RWSTD_NO_NAMESPACE
namespace std {
#endif


template <class T>
class ring
{
 public:
	class iterator;
	class const_iterator;
	friend class iterator;
	friend class const_iterator;
 public:
	typedef Allocator<T> ring_allocator;
	typedef T value_type;
	typedef ring_allocator::pointer pointer;
	typedef ring_allocator::reference reference;
	typedef ring_allocator::const_reference const_reference;
	typedef ring_allocator::size_type size_type;
	typedef ring_allocator::difference_type difference_type;
	// The iterator classes need the ring_pointer type.
	typedef ring<T>* ring_pointer;
 public:
	// Iterator and const_iterator are modified from their
	// counterparts in deque<T>.
	// The implementation of iterator has changed.
	class iterator : public random_access_iterator<T, difference_type>
	{
		friend class ring<T>;
		friend class const_iterator;
	 protected:
		pointer current;
		ring_pointer parent_ring;
		iterator(pointer x, ring_pointer y)
			: current(x), parent_ring(y) {}
	 public:
		iterator() : current(0), parent_ring(0) {}
		iterator(const iterator& x)
			: current(x.current), parent_ring(x.parent_ring) {}
		reference operator*() const { return *current; }
		// Note that  no checking is done
		// to make sure the two iterators have the same parent ring.
		difference_type operator-(const iterator& x) const
		{
			return current < x.current
				? current - x.current + parent_ring->ring_size()
				: current - x.current;
		}
		iterator& operator++()		// Prefix
		{
			if (++current == parent_ring->end_of_storage)
				current = parent_ring->start_of_storage;
			return *this;
		}
		iterator operator++(int)	// Postfix
		{
			iterator tmp = *this;
			++*this;
			return tmp;
		}
		iterator& operator--()		// Prefix
		{
			if (current == parent_ring->start_of_storage)
				current = parent_ring->end_of_storage;
			--current;
			return *this;
		}
		iterator operator--(int)	// Postfix
		{
			iterator tmp = *this;
			--*this;
			return tmp;
		}
		iterator& operator+=(difference_type n)
		{
			current += n;
			if (current >= parent_ring->end_of_storage)
				current -= parent_ring->ring_size();
			else
				if (current < parent_ring->start_of_storage)
					current += parent_ring->ring_size();
			return *this;
		}
		iterator& operator-=(difference_type n) { return *this += -n; }
		iterator operator+(difference_type rhs) const
		{
			return iterator(*this) += rhs;
		}
		iterator operator-(difference_type rhs) const
		{
			return iterator(*this) -= rhs;
		}
		reference operator[](difference_type n) { return *(*this + n); }
		// Note that no checking is done to make sure the iterators
		// have the same parent_ring.
		bool operator==(const iterator& x) const
		{
			return current == x.current;
		}
		// This is the only member function that needs to know
		// the value of parent_ring->start.current. The logical
		// identity A || B = !(!A && !B) is used in the else clause
		// to avoid having to evaluate the pointer expression when
		// possible.
		bool operator<(const iterator& x) const
		{
			if (current < parent_ring->start.current)
				return current < x.current
					&& x.current < parent_ring->start.current;
			else
				return !(!(current < x.current)
					&& !(x.current < parent_ring->start.current));
		}
	};
	// The implementation of const_iterator has changed.
	class const_iterator : public random_access_iterator<T, difference_type>
	{
		friend class ring<T>;
		friend class iterator;
	 protected:
		pointer current;
		ring_pointer parent_ring;
		const_iterator(pointer x, ring_pointer y)
			: current(x), parent_ring(y) {}
	 public:
		const_iterator() : current(0), parent_ring(0) {}
		const_iterator(const iterator& x)
			: current(x.current), parent_ring(x.parent_ring) {}
		const_reference operator*() const { return *current; }
		difference_type operator-(const const_iterator& x) const
		{
			return current < x.current
				? current - x.current + parent_ring->ring_size()
				: current - x.current;
		}
		const_iterator& operator++()		// Prefix
		{
			if (++current == parent_ring->end_of_storage)
				current = parent_ring->start_of_storage;
			return *this;
		}
		const_iterator operator++(int)	// Postfix
		{
			const_iterator tmp = *this;
			++*this;
			return tmp;
		}
		const_iterator& operator--()		// Prefix
		{
			if (current == parent_ring->start_of_storage)
				current = parent_ring->end_of_storage;
			--current;
			return *this;
		}
		const_iterator operator--(int)	// Postfix
		{
			const_iterator tmp = *this;
			--*this;
			return tmp;
		}
		const_iterator& operator+=(difference_type n)
		{
			current += n;
			if (current >= parent_ring->end_of_storage)
				current -= parent_ring->ring_size();
			else
				if (current < parent_ring->start_of_storage)
					current += parent_ring->ring_size();
			return *this;
		}
		const_iterator& operator-=(difference_type n) { return *this += -n; }
		const_iterator operator+(difference_type rhs) const
		{
			return const_iterator(*this) += rhs;
		}
		const_iterator operator-(difference_type rhs) const
		{
			return const_iterator(*this) -= rhs;
		}
		const_reference operator[](difference_type n)
		{
			return *(*this + n);
		}
		// Note that no checking is done to make sure the iterators
		// have the same parent_ring.
		bool operator==(const const_iterator& x) const
		{
			return current == x.current;
		}
		// This is the only member function that needs to know
		// the value of parent_ring->start.current. The logical
		// identity A || B = !(!A && !B) is used in the else clause
		// to avoid having to evaluate the pointer expression when
		// possible.
		bool operator<(const const_iterator& x) const
		{
			if (current < parent_ring->start.current)
				return current < x.current
					&& x.current < parent_ring->start.current;
			else
				return !(!(current < x.current)
					&& !(x.current < parent_ring->start.current));
		}
	};
	typedef reverse_iterator<const_iterator, value_type, const_reference,
		difference_type>  const_reverse_iterator;
	typedef reverse_iterator<iterator, value_type, reference, difference_type>
		reverse_iterator;
 protected:
	static Allocator<T> static_allocator;
	pointer start_of_storage;	// New data member in ring.
	pointer end_of_storage;
	iterator start;
	iterator finish;
	// The ring_size() function has been added to
	// simplify some of the iterator programing.
	size_type ring_size() const
		{ return size_type(end_of_storage - start_of_storage); }
 public:
	iterator begin() { return start; }
	const_iterator begin() const { return start; }
	iterator end() { return finish; }
	const_iterator end() const { return finish; }
	reverse_iterator rbegin() { return reverse_iterator(end()); }
	const_reverse_iterator rbegin() const
	{
		return const_reverse_iterator(end());
	}
	reverse_iterator rend() { return reverse_iterator(begin()); }
	const_reverse_iterator rend() const
	{
		return const_reverse_iterator(begin());
	}
	size_type size() const { return size_type(end() - begin()); }
	// Implementation of max_size has changed.
	size_type max_size() const { return static_allocator.max_size() - 1; }
	// Implementation of capacity has changed.
	size_type capacity() const
   	{ return start_of_storage != 0 ? ring_size() - 1 : size_type(0); }
	bool empty() const { return begin() == end(); }
	// The full() function has been added.
	bool full() const
   	{ return start_of_storage != 0 ? finish + 1 == start : true; }
	reference operator[](size_type n) { return *(begin() + n); }
	const_reference operator[](size_type n) const { return *(begin() + n); }
	// Implementation of all constructors have changed.
	ring() : start_of_storage(0), end_of_storage(0),
		 start(0, this), finish(0, this) {}
	// The interface for this constructor has changed. The vector version
	// fills n elements of the vector with copies of a second argument
	// (of type const T&) to the constructor. The constructor in ring
	// sets the size of the ring but does *not* initialize any elements.
	ring(size_type n)
		: start_of_storage(static_allocator.allocate(n + 1)),
		end_of_storage(start_of_storage + n + 1),
		start(start_of_storage, this), finish(start) {}
	ring(const ring<T>& x)
		: start_of_storage(static_allocator.allocate(x.ring_size())),
		end_of_storage(start_of_storage + x.ring_size()),
		start(start_of_storage, this), finish(start)
	{
		copy(x.begin(), x.end(), back_inserter(*this));
	}
	ring(const_iterator first, const_iterator last)
	{
		size_type n = 0;
		distance(first, last, n);
		start_of_storage = static_allocator.allocate(n + 1);
		end_of_storage = start_of_storage + n + 1;
		start = iterator(start_of_storage, this);
		finish = start;
		copy(first, last, back_inserter(*this));
	}
	~ring()
	{
		while (!empty()) pop_front();
		static_allocator.deallocate(start_of_storage);
	}
	ring<T>& operator=(const ring<T>& x);
	// Interface and implementation of reserve function has changed.
	// This function now sets the ring size to the new value (n),
	// regardless of whether this makes the ring larger or smaller.
	void resize(size_type n)
	{
		if (capacity() != n)
		{
			iterator tmp(static_allocator.allocate(n + 1), this);
			size_type new_size = n < size() ? n : size();

			uninitialized_copy(start, start + new_size, tmp.current);
			while (!empty()) pop_front();
			static_allocator.deallocate(start_of_storage);
			start_of_storage = tmp.current;
			end_of_storage = start_of_storage + (n + 1);
			start = tmp;
			finish = start + new_size;
		}
	}
	reference front() { return *begin(); }
	const_reference front() const { return *begin(); }
	reference back() { return *(end() - 1); }
	const_reference back() const { return *(end() - 1); }
	// Interface for push_back has changed as an call to this function
	// when the container is full will lead to deletion of the first element
	// in the ring. The implementation of push_back has also changed.
	void push_back(const T& x)
	{
		if (full())
		{
			destroy(start.current);
			++start;
		}
		construct(finish.current, x);
		++finish;
	}
	// A push_front function has been added.
	void push_front(const T& x)
	{
		if (full())
		{
			--finish;
			destroy(finish.current);
		}
		--start;
		construct(start.current, x);
	}
	// Implementation of swap has changed.
	void swap(ring<T>& x)
	{
#ifndef RWSTD_NO_NAMESPACE
		std::swap(start, x.start);
		std::swap(finish, x.finish);
		std::swap(start_of_storage, x.start_of_storage);
		std::swap(end_of_storage, x.end_of_storage);
#else
		::swap(start, x.start);
		::swap(finish, x.finish);
		::swap(start_of_storage, x.start_of_storage);
		::swap(end_of_storage, x.end_of_storage);
#endif
	}
	// Each of the insert function has been replaced by
	// two new functions: insert_forward and insert_backward.
	// They take the same arguments but differ in their behavior
	// if the container is full. insert_forward moves the elements
	// after the insert position down by one and deletes the
	// last element in the container. insert_backward moves the
	// elements before the insertion position up by one and deletes the
	// first element in the container. Neither function, however, will
	// ever delete the newly inserted item. When the container is *not* full,
	// the functions leave the container in a logically identical state.
	iterator insert_forward(iterator position, const T& x)
	{
		if (position == finish)
		{
			// Will not delete itself, so in a full container,
			// the first element must go.
			push_back(x);
			return (finish - 1);
		}
		if (position == start)
		{
			push_front(x);
			return start;
		}
		if (full())
			copy_backward(position, finish - 1, finish);
		else
		{
			construct(finish.current, *(finish - 1));
			copy_backward(position, finish - 1, finish);
			++finish;
		}
		*position = x;
		return position;
	}
	iterator insert_backward(iterator position, const T& x)
	{
		if (position == start)
		{
			// Will not delete itself, so in a full container,
			// the last element must go.
			push_front(x);
			return start;
		}
		if (position == finish)
		{
			push_back(x);
			return (finish - 1);
		}
		construct(finish.current, *(finish - 1));
		copy_backward(position, finish - 1, finish);
		if (full())
		{
			destroy(start.current);
			++start;
		}
		++finish;
		*position = x;
		return position;
	}
	void insert_forward(iterator position, const_iterator first,
		const_iterator last);
	void insert_backward(iterator position, const_iterator first,
		const_iterator last);
	void insert_forward(iterator position, size_type n, const T& x);
	void insert_backward(iterator position, size_type n, const T& x);
	void pop_back()
	{
		/* Borland bug */
		--finish;
		destroy(finish.current);
	}
	// A pop_front function has been added.
	void pop_front()
	{
		destroy(start.current);
		++start;
	}
	void erase(iterator position)
	{
		if (position + 1 != end())
			copy(position + 1, end(), position);
		/* Borland bug */
		--finish;
		destroy(finish.current);
	}
	void erase(iterator first, iterator last)
	{
		ring<T>::iterator i = copy(last, end(), first);
		while (i != finish)
			destroy((i++).current);
		// work around for destroy(copy(last, end(), first), finish);
		finish = finish - (last - first);
	}
};

template <class T>
inline bool operator==(const ring<T>& x, const ring<T>& y)
{
	return x.capacity() == y.capacity() && x.size() == y.size()
   	&& equal(x.begin(), x.end(), y.begin());
}

template <class T>
inline bool operator<(const ring<T>& x, const ring<T>& y)
{
	return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}


template <class T>
ring<T>::ring_allocator ring<T>::static_allocator;

template <class T>
ring<T>& ring<T>::operator=(const ring<T>& x)
{
	if (&x == this) return *this;
	if (x.ring_size() != ring_size())
	{
		while (!empty()) pop_front();
		static_allocator.deallocate(start_of_storage);
		start_of_storage = static_allocator.allocate(x.ring_size());
		end_of_storage = start_of_storage + x.ring_size();
		start = iterator(start_of_storage, this);
		finish = start;
		copy(x.begin(), x.end(), back_inserter(*this));
	}
	else
		if (size() >= x.size())
		{
			ring<T>::iterator i = copy(x.begin(), x.end(), begin());
			while (i != finish)
				destroy((i++).current);
			// work around for destroy(copy(x.begin(), x.end(), begin()), finish);
			finish = begin() + x.size();
		}
		else
		{
			copy(x.begin(), x.begin() + size(), begin());
			copy(x.begin() + size(), x.end(), back_inserter(*this));
		}
	return *this;
}

template <class T>
void ring<T>::insert_forward(iterator position, const_iterator first,
	const_iterator last)
{
	size_type n;
	__initialize(n, size_type(0));
	distance(first, last, n);

   if (n < capacity())
   {
   	// Some of the old ring contents will be retained.
		difference_type pre_count  = position - begin();
      if (n + pre_count < capacity())
      {
      	// Some post-insert items will be be retained.
         bool postToCopy = true;	// If true, some of the post-insert
         								// items need to be copied after
                                 // construction is complete.
         iterator t = end() + min(n, capacity() - size());
         iterator new_finish = t;
         const_iterator s = t - n;
         while (t != end())
         {
         	if (s == position)
            {
            	s = last;
               postToCopy = false;
            }
            construct((--t).current, *--s);
         }
        	finish = new_finish;
         if (postToCopy)
         {
         	// Cast to const_iterator is a workaround for an
            // unexplained failure of the compiler to perform this
            // cast automatically.
         	copy_backward(static_cast<const_iterator>(position), s, t);
            copy(first, last, position);
         }
         else
         	copy(first, s, position);
      }
      else
      {
      	// All post items will be deleted.
         const_iterator s = first;
         for (iterator t = position; t != end(); ++t, ++s)
         	*t = *s;
      	for (; s != last; ++s)
      		push_back(*s);
      }
   }
   else
   {
   	// Entire contents of ring will be replaced by new values.
   	const_iterator s = first + (n - capacity());
      for (iterator t = begin(); t != end(); ++t, ++s)
      	*t = *s;
      for (; s != last; ++s)
      	push_back(*s);
   }
}

template <class T>
void ring<T>::insert_backward(iterator position, const_iterator first,
	const_iterator last)
{
	size_type n;
	__initialize(n, size_type(0));
	distance(first, last, n);

   if (n < capacity())
   {
   	// Some of the old ring contents will be retained.
		difference_type post_count  = end() - position;
      if (n + post_count < capacity())
      {
      	// Some post-insert items will be be retained.
         bool preToCopy = true;	// If true, some of the pre-insert
         								// items need to be copied after
                                 // construction is complete.
         iterator t = begin() - min(n, capacity() - size());
         iterator new_start = t;
         const_iterator s = t + n;
         for (; t != begin(); ++t, ++s)
         {
         	if (s == position)
            {
            	s = first;
               preToCopy = false;
            }
            construct(t.current, *s);
         }
        	start = new_start;
         if (preToCopy)
         {
         	// Cast to const_iterator is a workaround for an
            // unexplained failure of the compiler to perform this
            // cast automatically.
         	copy(s, static_cast<const_iterator>(position), t);
            copy(first, last, position - n);
         }
         else
         	copy(s, last, t);
      }
      else
      {
      	// All pre items will be deleted.
         const_iterator s = last;
         for (iterator t = position; t != begin();)
         	*--t = *--s;
      	while (s != first)
      		push_front(*--s);
      }
   }
   else
   {
   	// Entire contents of ring will be replaced by new values.
   	const_iterator s = first + (n - capacity());
      for (iterator t = begin(); t != end(); ++t, ++s)
      	*t = *s;
      for (; s != last; ++s)
      	push_back(*s);
   }
}

template <class T>
void ring<T>::insert_forward(iterator position, size_type n,
	const T& x)
{
   if (n < capacity())
   {
   	// Some of the old ring contents will be retained.
		difference_type pre_count  = position - begin();
      if (n + pre_count < capacity())
      {
      	// Some post-insert items will be be retained.
         bool postToCopy = true;	// If true, some of the post-insert
         								// items need to be copied after
                                 // construction is complete.
         iterator t = end() + min(n, capacity() - size());
         iterator new_finish = t;
         const_iterator s = t - n;
         while (t != end())
         {
         	if (s == position)
            {
            	while (t != end())
						construct((--t).current, x);
               postToCopy = false;
            }
            else
            	construct((--t).current, *--s);
         }
         if (postToCopy)
         {
         	// Cast to const_iterator is a workaround for an
            // unexplained failure of the compiler to perform this
            // cast automatically.
         	copy_backward(static_cast<const_iterator>(position), s, t);
            fill(position, position + n, x);
         }
         else
         	fill(position, end(), x);

        	finish = new_finish;
      }
      else
      {
      	// All post items will be deleted.
         fill(position, end(), x);
         size_type m = n - (end() - position);
      	for (size_type i = size_type(0); i < m; ++i)
      		push_back(x);
      }
   }
   else
   {
   	// Entire contents of ring will be replaced by new values.
      fill(begin(), end(), x);
      size_type m = capacity() - size();
      for (size_type i = size_type(0); i < m; ++i)
      	push_back(x);
   }
}

template <class T>
void ring<T>::insert_backward(iterator position, size_type n,
	const T& x)
{
   if (n < capacity())
   {
   	// Some of the old ring contents will be retained.
		difference_type post_count  = end() - position;
      if (n + post_count < capacity())
      {
      	// Some pre-insert items will be be retained.
         bool preToCopy = true;	// If true, some of the pre-insert
         								// items need to be copied after
                                 // construction is complete.
         iterator t = begin() - min(n, capacity() - size());
         iterator new_start = t;
         const_iterator s = t + n;
         while (t != begin())
         {
         	if (s == position)
            {
            	while (t != begin())
               {
						construct(t.current, x);
                  ++t;
               }
               preToCopy = false;
            }
            else
            {
            	construct(t.current, *s);
               ++t; ++s;
            }
         }

         if (preToCopy)
         {
         	// Cast to const_iterator is a workaround for an
            // unexplained failure of the compiler to perform this
            // cast automatically.
         	copy(s, static_cast<const_iterator>(position), t);
            fill(position - n, position, x);
         }
         else
         	fill(begin(), position, x);

			start = new_start;
      }
      else
      {
      	// All pre items will be deleted.
         fill(begin(), position, x);
         size_type m = n - (position - begin());
      	for (size_type i = size_type(0); i < m; ++i)
      		push_front(x);
      }
   }
   else
   {
   	// Entire contents of ring will be replaced by new values.
      fill(begin(), end(), x);
      size_type m = capacity() - size();
      for (size_type i = size_type(0); i < m; ++i)
      	push_back(x);
   }
}

#ifndef RWSTD_NO_NAMESPACE
}
#endif

#undef Allocator
#undef ring

#endif