/*
	Twilight Prophecy 3D/Multimedia SDK
	A multi-platform development system for virtual reality and multimedia.

	Copyright (C) 1997-2001 by Twilight 3D Finland Oy Ltd.
*/
#ifndef PRCORE_LINKEDLIST_HPP
#define PRCORE_LINKEDLIST_HPP



namespace prcore
{

	template <class T>
	class LinkedList
	{
		public:

		struct Iterator
		{
			Iterator*	prev;
			Iterator*	next;
			T			data;

			const T&	operator * () const { return data; }
			T&			operator * () { return data; }
		};

		LinkedList();
		LinkedList(const LinkedList&);
		~LinkedList();

		void			operator = (const LinkedList&);
		const T&		operator [] (int index) const;
		T&				operator [] (int index);

		bool			IsEmpty() const;
		int				GetSize() const;
		Iterator*		Begin() const;
		Iterator*		End() const;

		T&				PushBack(const T&);
		T&				PushFront(const T&);
		T&				PushBack();
		T&				PushFront();
		void			InsertBefore(Iterator*, const T&);
		void			InsertAfter(Iterator*, const T&);
		void			PopBack();
		void			PopFront();
		void			Remove(Iterator* node);
		void			Remove(const T&);
		void			Erase(Iterator* first, Iterator* last);
		void			Clear();

		private:

		int				mSize;
		Iterator*		mpHead;
		Iterator*		mpTail;
		
		// iterator cache
		Iterator*		mpCache;
		
		Iterator*		GetIterator();
		void			ReleaseIterator(Iterator*);
		void			ClearIteratorCache();
		void			ClearIteratorList();
		Iterator*		PushNodeBack();
		Iterator*		PushNodeFront();
	};


template <class T> 
LinkedList<T>::Iterator* LinkedList<T>::GetIterator()
{
	if ( !mpCache )
		return new Iterator();

	Iterator* node = mpCache;		
	mpCache = mpCache->next;

	return node;	
}


template <class T> 
void LinkedList<T>::ReleaseIterator(Iterator* node)
{
	assert( node != NULL );
	
	node->next = mpCache;
	mpCache = node;
}


template <class T> 
void LinkedList<T>::ClearIteratorCache()
{
	Iterator* node = mpCache;
	while ( node )
	{
		Iterator* next = node->next;
		delete node;
		node = next;
	}

	mpCache = NULL;
}


template <class T> 
void LinkedList<T>::ClearIteratorList()
{
	Iterator* node = mpHead;
	while ( node )
	{
		Iterator* next = node->next;
		delete node;
		node = next;
	}

	mSize = 0;
	mpHead = NULL;
	mpTail = NULL;
}


template <class T>
LinkedList<T>::Iterator* LinkedList<T>::PushNodeBack()
{
	Iterator* node = GetIterator();
	++mSize;

	node->prev = mpTail;
	node->next = NULL;

	if ( mpTail )
		mpTail->next = node;
	else
		mpHead = node;

	mpTail = node;

	return node;
}


template <class T>
LinkedList<T>::Iterator* LinkedList<T>::PushNodeFront()
{
	Iterator* node = GetIterator();
	++mSize;

	node->prev = NULL;
	node->next = mpHead;

	if ( mpHead )
		mpHead->prev = node;
	else
		mpTail = node;

	mpHead = node;

	return node;
}

	
template <class T> 
LinkedList<T>::LinkedList()
{
	mSize = 0;
	mpHead = NULL;
	mpTail = NULL;
	mpCache = NULL;
}


template <class T>
LinkedList<T>::LinkedList(const LinkedList& other)
{
	mSize = 0;
	mpHead = NULL;
	mpTail = NULL;
	mpCache = NULL;
	*this = other;
}


template <class T>
LinkedList<T>::~LinkedList()
{
	ClearIteratorList();
	ClearIteratorCache();
}


template <class T>
void LinkedList<T>::operator = (const LinkedList& other)
{
	// clear
	ClearIteratorList();

	// copy data
	Iterator* node = other.Begin();
	while ( node )
	{
		PushBack( **node );
		node = node->next;
	}
}


template <class T>
const T& LinkedList<T>::operator [] (int index) const
{
	assert ( index>=0 && index < GetSize() );

	Iterator* node = Begin();
	for ( int i=0; i<index; i++ )
		node = node->next;

	return **node;
}


template <class T>
T& LinkedList<T>::operator [] (int index)
{
	assert ( index>=0 && index < GetSize() );

	Iterator* node = Begin();
	for ( int i=0; i<index; i++ )
		node = node->next;

	return **node;
}


template <class T>
bool LinkedList<T>::IsEmpty() const
{
	return GetSize() ? false : true;
}


template <class T>
int LinkedList<T>::GetSize() const
{
	return mSize;
}


template <class T>
LinkedList<T>::Iterator* LinkedList<T>::Begin() const
{
	return mpHead;
}


template <class T>
LinkedList<T>::Iterator* LinkedList<T>::End() const
{
	return mpTail;
}


template <class T>
T& LinkedList<T>::PushBack(const T& type)
{
	Iterator* node = PushNodeBack();
	node->data = type;
	return node->data;
}


template <class T>
T& LinkedList<T>::PushFront(const T& type)
{
	Iterator* node = PushNodeFront();
	node->data = type;
	return node->data;
}


template <class T>
T& LinkedList<T>::PushBack()
{
	Iterator* node = PushNodeBack();
	return node->data;
}


template <class T>
T& LinkedList<T>::PushFront()
{
	Iterator* node = PushNodeFront();
	return node->data;
}


template <class T>
void LinkedList<T>::InsertBefore(Iterator* it, const T& type)
{
	assert( it );
	Iterator* node = GetIterator();
	++mSize;

	Iterator* prev = it->prev;
	it->prev = node;

	if ( prev )
		prev->next = node;
	else
		mpHead = node;

	node->next = it;
	node->prev = prev;
	node->data = type;
}


template <class T>
void LinkedList<T>::InsertAfter(Iterator* it, const T& type)
{
	assert( it );
	Iterator* node = GetIterator();
	++mSize;

	Iterator* next = it->next;
	it->next = node;

	if ( next )
		next->prev = node;
	else
		mpTail = node;

	node->prev = it;
	node->next = next;
	node->data = type;
}


template <class T>
void LinkedList<T>::PopBack()
{
	Iterator* node = mpTail;

	if ( node )
	{
		Iterator* prev = node->prev;

		if ( prev )
			prev->next = NULL;
		else
			mpHead = NULL;

		mpTail = prev;
		ReleaseIterator( node );
		--mSize;
	}
}


template <class T>
void LinkedList<T>::PopFront()
{
	Iterator* node = mpHead;
	if ( node )
	{
		Iterator* next = node->next;

		if ( next )
			next->prev = NULL;
		else
			mpTail = NULL;

		mpHead = next;
		ReleaseIterator( node );
		--mSize;
	}
}


template <class T>
void LinkedList<T>::Remove(Iterator* node)
{
	assert(node != NULL);
	
	Iterator* next = node->next;
	Iterator* prev = node->prev;

	if ( node == mpHead )
		mpHead = next;

	if ( node == mpTail )
		mpTail = node->prev;

	if ( prev )
		prev->next = next;

	if ( next )
		next->prev = prev;

	ReleaseIterator( node );
	--mSize;
}


template <class T>
void LinkedList<T>::Remove(const T& item)
{
	Iterator* node = mpHead;
	while ( node )
	{
		Iterator* next = node->next;

		if ( **node == item )
			Remove(node);

		node = next;
	}
}


template <class T>
void LinkedList<T>::Erase(Iterator* first, Iterator* last)
{
	if ( IsEmpty() || !first || !last )
		return;

	if ( first == mpHead )
		mpHead = last->next;

	if ( last == mpTail )
		mpTail = first->prev;


	Iterator* node = first;

	while ( node )
	{
		Iterator* next = node->next;
		Iterator* prev = node->prev;

		if ( prev )
			prev->next = next;

		if ( next )
			next->prev = prev;

		ReleaseIterator( node );
		--mSize;
		
		if ( node==last )
			break;
			
		node = next;
	}
}


template <class T>
void LinkedList<T>::Clear()
{
	ClearIteratorList();
	ClearIteratorCache();
}

} // namespace prcore



#endif