// © Copyright 1997. Joseph Bergin. All rights reserved.

#ifndef CIRCLELIST_H
#define CIRCLELIST_H

#include "algo_jb.h"

static void fail(char * s){
cout << s << endl;
cout << "Fatal error.  Sorry."<<endl;
abort();
}

template <class E>
class CircleList // singly linked circular list.  
{	class Iterator;
	public:
	typedef Iterator iterator;
	typedef E value_type;
	typedef E& reference;
	typedef E* pointer;
	
 protected:	
	class Node  // Nested class. The nodes of the list.
	{	public:
		E value;
		bool header;
		Node *next;
		Node(E val, Node * n):value(val),next(n), header(false){}
	};
	
	class Iterator // Nested class. Iterators over the list. 
	// This is only a forward iterator.  
	// An iterator points to the node before the one it logically references. 
	{	Iterator(const CircleList<E> *const L)
		:	here(L->head),
			isEnd(L->empty())  
		{
		}

		Iterator() 
		:	here(NULL)
		{fail("Illegal iterator");
		}
	public:
		reference operator*()const
		{	return here->next->value;
		}

		iterator& operator++()
		{	here = here->next;
			if(here->next->header)here = here->next;
			if( here->header) isEnd = true;
			return *this;
		}
		
		iterator operator++(int)
		{	iterator result = *this;
			++*this;
			return result;
		}
		
		iterator& operator=(const iterator& it)
		{	if(this != &it)
			{	here = it.here;
				isEnd = it.isEnd;
			}
			return *this;
		}
		
		bool operator==(const iterator& it)const
		{	return here == it.here && isEnd == it.isEnd;
		}
		
	private:	
		CircleList<E>::Node *here;
		bool isEnd;
		
	friend class CircleList;
	};
	
public:
	
	CircleList():head(new Node(E(), NULL)){ head->next = head; head->header = true;}
	
	CircleList(const CircleList& L) // copy constructor
	{	copy(L);
	}

	~CircleList(){	free();}

	CircleList& operator= (const CircleList& L)  // assignment operator
	{	if ( this == &L) return *this;
		free();
		copy(L);
		return *this;
	}
	
	int size()const  // Linear time. Should be constant time. 
	{	iterator i = begin();
		int result = 0;
		while(i != end())
		{	++i;
			++result;
		}
		return result;
	}

	void push_front(const E& val)
	{	head->next = newNode(val, head->next);
	}
				
	void pop_front(){ erase(begin());}

	E& front()const
		// Returns E in first location, NULL for empty list.
	{	return head->next->value;
	}
	
	void insert(iterator& i, const E& val)
	// Insert before i. 
	{	i.here->next = newNode(val, i.here->next);
	}
	
	void erase(iterator& i)
		// Removes element at location of i and moves to following location. 
	{	if(i.here->next == head)return;
		CircleList<E>::Node *temp = i.here->next->next;
		delete i.here->next;
		i.here->next = temp;
	}
	
	void remove(const E& d) // remove all elements that are == to d
	{	for(iterator i = begin(); i != end(); )
			if(*i == d) erase(i); else ++i;
	}

	bool empty()const{return head->next == head;};
		// TRUE for an empty list.

	void clear_aux(Node * n)
	{	if( n == head) return;
		head->next = n->next;
		delete n;
		clear_aux(head->next);
	}
	
	void clear_rec()
	{	clear_aux(head->next);
	}
	
	void clear()
		// Removes all elements from the list, leaving it empty.
	{	iterator i = begin();
		while(!empty()) erase(i);
	}

	iterator begin()const { return iterator(this); }

	iterator end()const
	{	iterator result(this);
		result.isEnd = true;
		return result;
	}

	void sort(iterator& start, iterator& done)
	// PRE: done does not preceed start.  
	// requires a forward_iterator version of partition_aux.  
	{	if(start != done)
		{	iterator mid(done);
			partition_aux(start, mid, done);
			sort(start, mid);
			sort(++mid, done);
		}
	}

	void sort() // NOT stable, Therefore does not meet STL requirements.
	// requires a forward_iterator version of partition_aux.  
	{	if(size() > 1) sort(begin(), end()); 
	}

protected:
	Node* newNode(E val, Node *left)
	{	Node *result = new Node(val,left);
		return result;
	}

	Node *copy_aux(Node *here, Node *OriginalHead)
	{	if(here->header) return OriginalHead;
		Node *n = new Node(here->value, copy_aux(here->next,OriginalHead));
		return n;
	}
	
	void copy(const CircleList& L)
	{	head = new Node(E(),NULL);
	 	head->next = head; 
	 	head->header = true;
	 	Node *here = L.head->next;
	 	head->next = copy_aux(here, head);
	}
	
	void free()
	{	clear();
		delete head;
	}

friend class Iterator;

	Node* head;
};

template <class data>
ostream&  operator << (ostream& outp , CircleList<data>& val){
	
	for(CircleList<data>::iterator  i = val.begin(); i != val.end(); ++i)
	{	outp << *i << ' ';
	}
	return outp;
}

// Advantages of doubly linking the list: 
// (1) An iterator can point to the node in question, not the node before.
// (2) An iterator can easily be bidirectional.
// (3) The end() iterator can be more easily arranged. 
// (4) push_back() and back() can be implemented easily.  
//		Actually, this can be maintained if we keep two pointers in a list, one to the header
//		and another to the last data node.  
#endif