#ifndef __LinkLIST__
#define __LinkLIST__
#include <iostream.h>
#include "Boolean.h"
#include "Error.h"

//#define debugLists

#ifdef debugLists
long gc;
#endif

enum direction{backward=0, forward=1,
	  rightLeft = 0, leftRight = 1};

// REQUIREMENTS on type <data>:
// Must implement the operator ==, the output operator<<,
// and default and copy constructors.

template <class data> class LinkList;
template <class data> class Context;
template <class data> class LinkListNode;

// auxiliary function  -- Machine dependent code.
template <class data>
inline 
LinkListNode<data>* ExclOr(const LinkListNode<data> *a,const LinkListNode<data> *b)
{
	return (LinkListNode<data>*)((long)a^(long)b);
}

//**************************  LIST  **************************
template <class data>
class LinkList 
{	public:
		LinkList(const data& dummy)
		:	_length(0) // empty list
		{ 	_head[0] = newNode(dummy, NULL, NULL);
			_head[1] = newNode(dummy, NULL, NULL);
		}
	
		LinkList(LinkList<data>& L) // copy constructor
		:	_length(0)
		{ 	_head[0] = newNode(L._head[0]->_value, NULL, NULL);
			_head[1] = newNode(L._head[0]->_value, NULL, NULL);
			Context<data> C(L);
			data v;
			while(C.iterate(v))
				insertFirst(v,backward);
		}
	
		virtual ~LinkList() // This class will have derived classes.
		{	clear();
		}
	
		LinkList & operator= (LinkList& L)  // assignment operator
		{	if ( this == &L) return *this;
			clear();
			Context<data> C(L);
			data v;
			while(C.iterate(v))
				insertFirst(v,backward);
			return *this;
		}
	
		virtual	void insertFirst(const data& val, direction d = forward)
		{	LinkListNode<data> *second = ExclOr(_head[1-d], _head[d]->_access);
			LinkListNode<data> *n = newNode(val, _head[d], second);
			_length++;
			_head[d]->_access = ExclOr(_head[1-d],n);
			second->_access = ExclOr(n, ExclOr(_head[d],second->_access));
		}
	
		data first(direction d = forward)const
			// Returns data in first location, dummy for empty list.
		{	LinkListNode<data> *firstNode = ExclOr((LinkListNode<data>*)_head[1-d],(LinkListNode<data>*)_head[d]->_access);
			return firstNode->at();
		}
	
		virtual data removeFirst(direction d = forward)
			// Removes and returns data at _head of list.
			// Returns dummy and is otherwise
			// a no-op for an empty list.
		{	Context<data> firstLoc(*this,d);
			data result = firstLoc._nbr[d]->at();
			firstLoc.removeNext(d);
			return result;
		}
	
		void reverse(void)
		{	LinkListNode<data> *n = _head[0];
			_head[0] = _head[1];
	      _head[1] = n;
		}
	
		Boolean empty()const{return Boolean(_head[0]->_access == NULL);};
			// TRUE for an empty list.
	
		void clear()
			// Removes all data from the list, leaving it empty.
		{	while(!empty()) removeFirst();
		}
	
	//	void append(LinkList)
			// Appends the data to the end of this list.
	//	{
	    	// not yet implemented
	//	}
	
		virtual	void removeAll(const data& val)
			// Removes all copies of the data from this list.
		{	Context<data> here(*this);
			while(!here.atEnd())
			{	if(here.findNext(val))
					here.removeNext();
				else
					here.toFirst(backward);
			}
		}
	
		long length()const {return _length;}
	
		long testLevels(ostream &os, long start = 0)
		{	os << ' '<<_length<<' ';
			return start;
		}
	
	protected:
		LinkListNode<data>* _head[2];
		long _length;
	
		LinkListNode<data>* newNode(data val, LinkListNode<data> *left, LinkListNode<data> *right)
		{	LinkListNode<data> *result = new LinkListNode<data>(val,left,right);
			if(!result)userERROR("Heap exhausted.");
			return result;
		}
	
	friend class Context<data>;
};

//**************************** CONTEXT************************
template <class data>
class Context 
{	public:
		Context(LinkList<data>& L, direction d = forward)
		:	_owner(L)
		{	_nbr[1-d] = L._head[d];
			_nbr[d] = ExclOr(L._head[1-d],L._head[d]->_access);
	#ifdef debugLists
	gc++;
	#endif
		}
	
		Context(const Context<data>& C, direction d = forward)
		:	_owner(C._owner)
		{	_nbr[1-d] = C._nbr[1-d];
			_nbr[d] = C._nbr[d];
	#ifdef debugLists
			gc++;
	#endif
		}
	
		~Context()
		{	// Nothing
	//	#ifdef debugLists
	// gc--;
	// #endif
		}
	
		const  Context<data>& operator= (const  Context<data>& C)
		{	if ( this == &C) return *this;
			if (&_owner != &(C._owner))userERROR("Illegal assignment.");
			_nbr[0] = C._nbr[0];
			_nbr[1] = C._nbr[1];
			return *this;
		}
	
		void insert(const data& val, direction d = forward)
			// Creates a new location at this position.
			// The new node is left behind the position so a sequence of inserts
			// is like enqueue rather than push.  
		{	LinkListNode<data> *aNode = _owner.newNode(val,_nbr[0],_nbr[1]);
			_nbr[0]->_access = ExclOr(_nbr[0]->_access, ExclOr(_nbr[1],aNode));
			_nbr[1]->_access = ExclOr(_nbr[1]->_access, ExclOr(_nbr[0], aNode));
//			LinkListNode<data>* oldNode = _nbr[1-d];
			_nbr[1-d] = aNode;
			_owner._length++;
		}
	
		void toFirst(direction d = forward)
			// move to the position before the first value.
		{	_nbr[1-d] = _owner._head[d];
			_nbr[d] = ExclOr(_owner._head[1-d], _owner._head[d]->_access);
		}
	
		data next(direction d = forward)const
			// Returns data in next position(or dummy).
		{	return _nbr[d]->_value;
		};
	
		void setNext(const data& val, direction d = forward) const
			// Set the data in the following position if any.
		{	if(!atEnd(d)) _nbr[d]->atPut(val);
		}
	
		data removeNext(direction d = forward)
			// Returns the data removed from the list.
			// Returns dummy if nothing can be removed.
		{	data result = _nbr[d]->at();
			if(! atEnd(d))
			{	LinkListNode<data> *nbr = ExclOr(_nbr[1-d], _nbr[d]->_access);
				_nbr[1-d]->_access = ExclOr(_nbr[1-d]->_access, ExclOr(_nbr[d], nbr));
				nbr->_access = ExclOr(nbr->_access, ExclOr(_nbr[d],_nbr[1-d]));
				LinkListNode<data> *temp = _nbr[d];
				_nbr[d] = nbr;
				delete temp;
				_owner._length--;
			}
			  return result;
		}
	
		Boolean atEnd(direction d = forward)const
			// TRUE if before the first element.
		{	return Boolean(_nbr[d] == _owner._head[1-d]);
		};
	
		void advance(direction d = forward)
			// Will not move from last to first.
		{	if(! atEnd(d))
			{	LinkListNode<data> *temp = _nbr[1-d];
				_nbr[1-d] = _nbr[d];
				_nbr[d] = ExclOr(temp, _nbr[d]->_access);
			}
		}
	
		Boolean findNext(const data& val, direction d = forward)
			// Moves forward until the data can be found in the next location.
			// Does not wrap around the end. 
			// Does not move if data cannot be found.
			// Does not move if data is found just to the right.
		{	LinkListNode<data> *L = _nbr[0];
			LinkListNode<data> *R = _nbr[1];
			while(!atEnd(d) && !(next(d) == val))advance(d);
			if(!(next(d) == val))
			{	_nbr[0] = L;
				_nbr[1] = R;
					return FALSE;
			}
			return TRUE;
		}
	
		Boolean iterate(data &v, direction d = forward)
		// If not afterLast then set v to the next item, advance,
		// and return true. Otherwise do not set v, leave position
		// unchanged and return false.
		{	Boolean result = Boolean(! atEnd(d));
			if(result)
			{	v = next(d);
				advance(d);
			}
			return result;
		}
	
	//	LinkList<data> split()
			// Splits the owner of this context into two at the point of the context.
			// The owner list will contain the values before the context,
			// the returned list will contain those after.
	//	{
	//		LinkList<data> result;
	     // not yet implemented
	//		return result;	
	//	}
	
	protected:
	
		LinkList<data> & _owner;
		LinkListNode<data> *_nbr[2];
	
	
		Context(LinkList<data>& L, direction d, Boolean ) 
		:	_owner(L)
		{	_nbr[1-d] = L._head[d];
			_nbr[d] = ExclOr(L._head[1-d],L._head[d]->_access);
	#ifdef debugLists
			gc++;
	#endif
		}
	
	friend class LinkList<data>;
	friend
	  ostream&  operator<< (ostream& outp , LinkList<data>& val);
};

//********************************* NODE ************************
template <class data> 
class LinkListNode 
{	public:
		data at()const{return _value;};
		void atPut(const data& val){_value = val;};
	protected:
		LinkListNode(data val, LinkListNode<data> *left, LinkListNode<data> *right)
		:	_value(val),
			_access(ExclOr(left,right))
		{
		}
	
	 //	LinkListNode():_value(NULL),_access(NULL){}
		LinkListNode(const LinkListNode<data> & N): _value(N._value), _access(N._access){}
	
		~LinkListNode(){}
	
		const LinkListNode<data>& operator= (const LinkListNode<data>& N)
		{	if ( this == &N) return *this;
			_value = N._value;
			_access = N._access;
			return *this;
		}
	
		data _value;
		LinkListNode<data> *_access;
			// This will not be a valid address but the XOR of the two addresses
			// of the left and right neighbors.
			// DO NOT DEREFERENCE the access value
	
	friend class LinkList<data>;
	friend class Context<data>;
};


//***************** OPERATORS *******************

template <class data>
ostream&  operator << (ostream& outp , const LinkList<data>& val)
{	Context<data>  it ((LinkList<data>&)val); // Casting Away Const
	data v;
	while(it.iterate(v))
	{	outp << v << ' ';
	}
	return outp;	
}

#endif