/*************************************************************************
	
	file created on:	2002/08/23   12:47
	filename: 			LinkedList.h
	author:				Andreas Hartl<andy@runicsoft.com>

		visit http://www.runicsoft.com for updates and more information

	purpose:	a template double linked list class
**************************************************************************/

/*
EXAMPLE of how to use the list traversal facilities:
	
	DList<int> list;
	
	list.Start ();
	while ( list.IsValid () )
	{
		printf ( "%i\n", list.GetCurrent()->data );
		list.GoForward ();		
	}

The same with a for loop:

  	for ( list.Start (); list.IsValid (); list.GoForward () )
		printf ( "%i\n", list.GetCurrent()->data );

Traversing the list backwards:

  	for ( list.End (); list.IsValid (); list.GoBackward () )
		printf ( "%i\n", list.GetCurrent()->data );


*/

#ifndef TEMPLATE_DOUBLE_LINKED_LIST
	#define TEMPLATE_DOUBLE_LINKED_LIST

 

template <class T> class DLNode {       // the DLNode; the elements the list will consist off
public:
	T data;                             // data in node
	DLNode<T>* next;                    // pointer to next node
	DLNode<T>* prev;                    // pointer to previous node
};


template <class T> class DList {
private:


	DLNode<T>* First;              // pointer first element of list 
	DLNode<T>* Last;               // pointer last element of list
	DLNode<T>* TempDLNode;		   // temporary node	
	DLNode<T>* Walker;             // node pointer used for list traversal
	int		 numElements;          // number of nodes in list

	public:
	DList ();					   // constructor
	~DList ();					   // destructor

	void AddAsFirst    ( T thedata );       
	void AddAsLast     ( T thedata );
	
	void RemoveFirst   ( void );
	void RemoveLast    ( void );

	DLNode<T>* GetFirst  ( void );
	DLNode<T>* GetLast   ( void );

	int GetNumElements ( void );

	void InsertAfter   ( DLNode<T>* node, T thedata );    // inserts a new DLNode after DLNode and fills it with thedata
	void Remove        ( DLNode<T>* node );    // removes DLNode 

	DLNode<T>* GetNode   ( int x );    // gets the x'th DLNode in the list
												
	void NewListLeft   ( DList<T>* newlist, DLNode<T>* node );  // returns all nodes left of <node> in a new list
	void NewListRight  ( DList<T>* newlist, DLNode<T>* node ); 

	// functions for list traversal:
	void Start      ();   // sets listwalker to first element
	void End        ();   // sets listwalker to last element
	bool IsAtEnd    ();   // return true if listwalker has arrived at the last node
	bool IsAtStart  ();   // returns true if listwalker is at first node
	bool GoForward  ();   // moves listwalker one forward, returns false if at end
	bool GoBackward ();   // moves listwalker one back, returns false if at first node
	DLNode<T>* GetCurrent ();  // returns pointer to the node the listwalker currently points to
	bool IsValid    ();   // returns true if listwalker points to a valid node
};



// constructor: list is empty when created, so there are no elements in it
// and Head and Tail must be NULL-pointers

template<class T>DList<T>::DList ()       
{
	First = NULL;
	Last  = NULL;
	numElements = 0;
	TempDLNode = NULL;
	Walker = NULL;
}

// destructor: releases all nodes
template<class T>DList<T>::~DList ()
{
	DLNode<T>* temp1 = First;
	DLNode<T>* temp2 = NULL;
	while ( temp1 != NULL )
	{
		temp2 = temp1;
		temp1  = temp1->next;
		if ( temp2 )
		{
			delete temp2;
			temp2 = NULL;
		}
	}
	if ( temp2 )
	{
		delete ( temp2 );
		temp2 = NULL;
	}
	if ( temp1 )
	{	
		delete ( temp1 );
		temp1 = NULL;
	}
	numElements = 0;
	TempDLNode  = NULL;
	Walker      = NULL;
}

// AddAsFirst ( int thedata )
// adds a new DLNode as the first element in the list and sets its
// data to thedata
template<class T> void DList<T>:: AddAsFirst ( T thedata )
{

	DLNode<T>* newDLNode = new DLNode<T>;
	newDLNode->data = thedata;
	newDLNode->prev = NULL;
	if ( Last == NULL )
	{
		Last = newDLNode;
		Last->next = NULL;
	}
	if ( First != NULL )
	{
		newDLNode->next = First;
		First->prev = newDLNode;
	}
	    
	First = newDLNode;

	numElements++;
}

// AddAsLast ( int thedata )
// adds new DLNode as the last element in the list and sets its 
// data to thedata 
template<class T> void DList<T>::AddAsLast ( T thedata )
{
	DLNode<T>* newDLNode = new DLNode<T>;
	newDLNode->data = thedata;
	newDLNode->next = NULL;
	if ( First == NULL )
	{
		First = newDLNode;
		First->prev = NULL;
	}
	if ( Last == NULL )
		Last = newDLNode;
	else 
	{
		Last->next = newDLNode;
		newDLNode->prev = Last;
		Last = newDLNode;
		Last->next = NULL;
	}
	numElements++;
}

// RemoveFirst: removes the first item of the list
template<class T> void DList<T>::RemoveFirst ( void )
{
	if ( First != NULL )
	{
		if ( First->next != NULL )
		{
			TempDLNode = First->next;
			delete ( First );
			First = TempDLNode;
			First->prev = NULL;
		}
		else delete ( First );
	}
	numElements--;
}
	
// RemoveLast: removes the last item of the list
template<class T> void DList<T>::RemoveLast ( void )
{
	if ( Last != NULL )
	{
		TempDLNode = Last->prev;
		if ( Last->prev != NULL )
		{
			delete ( Last );
			Last = TempDLNode;
			Last->next = NULL;
		}
		else
		{
			Last->prev->next = NULL;
			delete ( Last );
		}


	}
	numElements--;
}

// GetFirst(): retrieving the pointer to the first element in the list
template<class T>DLNode<T>* DList<T>::GetFirst ( void )     
{
	return ( First );
}

// GetLast(): retrieving the pointer to the last element in the list
template<class T>DLNode<T>* DList<T>::GetLast ( void )
{
	return ( Last );
}


template<class T>int DList<T>::GetNumElements ()
{
	return ( numElements );
}

template<class T> void DList<T>::InsertAfter ( DLNode<T>* node, T thedata )
{
	DLNode<T>* newDLNode = new DLNode<T>;
	newDLNode->data = thedata;
	newDLNode->next = DLNode->next;
	newDLNode->prev = node;
	DLNode->next->prev = newDLNode;
	DLNode->next = newDLNode;

}

template<class T> void DList<T>::Remove ( DLNode<T>* node )
{
	DLNode->next->prev = DLNode->prev;
	DLNode->prev->next = DLNode->next;
	delete ( node );
}


template<class T>DLNode<T>* DList<T>::GetNode ( int x )
{

	if ( x <= numElements )
	{
		TempDLNode = First;
		for ( int c = 0; c < x; c++ )
			TempDLNode = TempDLNode->next;

		return TempDLNode;
	}
	else return NULL;

}

// this function makes a new list from all DLNodes of the current list that come
// before DLNode
template<class T>void DList<T>::NewListLeft ( DList<T>* newlist, DLNode<T>* node )
{
	TempDLNode = node;
	while ( TempDLNode != NULL )
	{
		newlist->AddAsFirst ( TempDLNode->data );
		TempDLNode = TempDLNode->prev;
	}
}

template<class T>void DList<T>::NewListRight ( DList<T>* newlist, DLNode<T>* node )
{
	TempDLNode = node;
	while ( TempDLNode != NULL )
	{
		newlist->AddAsLast ( TempDLNode->data );
		TempDLNode = TempDLNode->next;
	}
}


template<class T>void DList<T>::Start ()
{
	Walker = First;
}

template<class T>void DList<T>::End ()
{
	Walker = Last;
}

template<class T>bool DList<T>::IsAtEnd ()
{
	return ( Walker == Last );
}

template<class T>bool DList<T>::IsAtStart ()
{
	return ( Walker == First );
}

template<class T>bool DList<T>::GoForward ()
{
	if ( Walker == Last )
	{	
		Walker = NULL;
		return false;
	}
	Walker = Walker->next;
	return true;
}

template<class T>bool DList<T>::GoBackward ()
{
	if ( Walker == First )
	{
		Walker = NULL;
		return false;
	}
	Walker = Walker->prev;
	return true;
}

template<class T>DLNode<T>* DList<T>::GetCurrent ()
{
	return Walker;
}

template<class T>bool DList<T>::IsValid ()
{
	return ( NULL != Walker );
}

#endif