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

#ifndef __FastList__
#define __FastList__

#include <iostream.h>
#include "Error.h"
#include "Boolean.h"

#define _DebugFLists_

// This class represents lists that share representations with each other
// This is safe since lists are not mutable.  We only delete nodes when no
// list refers to them.  Note that circular references are not possible here,
// so reference counting works.  

// The const flags on some of the methods are lies
// We change the refcounts of some of the nodes.

//*********************  FLNODE   **************************
template <class E>
class FLNode 
{ // no public:
		FLNode(const E& e):_next(NULL), _value(e), _refCount(1){};
		FLNode(const FLNode<E> &n): _next(n._next), _value(n._value),_refCount(1)
		{	userERROR("Illegal copy constructor in FastList Node.");
		}
		FLNode & operator = (const FLNode &)
		{	userERROR("Illegal operator= in FastList Node");
			return *this; // unreachable.
		}
		
	private:
		FLNode<E> *_next;
		E _value;
		unsigned int _refCount; // Delete the node if this drops to zero.
		

#ifdef _DebugFLists_		
	void dump()
	{	cout << _value << ' '<<'<'<<_refCount<<"> .";
		if(_next != NULL) _next->dump();
	}
#endif

	friend class FastList<E>;
};

// ****************** LIST   ******************************
template<class E>
class FastList
{	public:
		FastList():	_first(NULL){}
		
		FastList(const FastList& t)
		{	copy(t);
		}
		
		FastList<E> & operator =(const FastList& t)
		{
			if(this != &t)
			{	free();
				copy(t);
			}
			return *this;		
		}

		~FastList()
		{	free();
		}
		
		Boolean empty() const
		{	return Boolean(_first == NULL);
		}
		
		E head() const
		{	if(_first == NULL) userERROR("Empty list has no head.");
			return _first->_value;
		}
		
		FastList<E> tail() const
		{	if(_first == NULL) userERROR("Empty list has no tail.");
			FastList<E> result;
			if(_first->_next != NULL)
			{	result._first = _first->_next;
				result._first->_refCount++;
			}
			return result;
		}
		
		FastList<E> consElement(const E& e) const
		{	FLNode<E> *first = new FLNode<E>(e);
			if(first==NULL)userERROR("Memory failure in FastList.");
			first->_next = _first;
			if(_first != NULL)_first->_refCount++;
			FastList<E> result;
			result._first = first;
			return result;
		}

#ifdef _DebugFLists_				
		void dump(){_first->dump();cout<<endl;}
#endif
		
	private:
		FLNode<E> * _first;
		
		void copy(const FastList &t)
		{	_first = t._first;	// Copy t's representation.
			if(_first != NULL) _first->_refCount++;
		}

		void free()
		{	FLNode<E> *temp;
			while(_first != NULL && _first->_refCount==1)
			{	temp = _first->_next;
				delete _first;
				_first = temp;
			}
			if(_first != NULL)_first->_refCount--;
		}
};

template <class E> 
FastList<E> operator +(const E& e, const FastList<E>& t)
{	return t.consElement(e);
}

template <class E> 
FastList<E> cons(const E& e, const FastList<E>& t)
{	return t.consElement(e);
}

#endif