// llist2.hpp
// ctrudeau@etude
//
// This file contains the declaration and class code for the link list class.
//
// ----------------------------------------------------------------------------

#include <stdio.h>

// Node - container where objects in the linked list are stored
template <class T>
class Node  
{
public:
	Node( T *_pData )
	{
		pData = _pData;
		pNext = NULL;
	} // end constructor

	Node *Next() { return( pNext ); }
	void SetNext( Node *pNode ) { pNext = pNode; }
	T *Data() { return( pData ); }

private:
	T *pData;
	Node *pNext;
}; // end Node

// ----------------------------------------------------------------------------

template <class T>
class LList
{
public:
	LList()
	{
		pHead = NULL;
		pTail = NULL;
		pCurrent = NULL;
	} // end constructor
	
	~LList() { this->destroy(); }

	// member functions for manipulating the list
	void push( T *pData );
	void queue( T *pData );
	T *pop();
	void destroy();

	// member functions for traversing the list
	void top() { pCurrent = NULL; }
	T *first()
	{
		if( pHead == NULL )
			return( NULL );

		return( pHead->Data() );
	} // end first

	T *last()
	{
		if( pTail == NULL )
			return( NULL );

		return( pTail->Data() ); 
	} // end last

	T *next();

private:
	Node<T> *pHead;
	Node<T> *pTail;
	Node<T> *pCurrent;
}; // end LList

// ============================================================================
// Implementation Code
// ============================================================================

// queue -- this function puts an item on the tail of the list
template <class T>
void LList<T>::queue( T *pData )
{
	Node<T> *pNewNode;

	// create the new node
	pNewNode = new Node<T>( pData );

	// place the node in the list
	if( pHead == NULL )
	{
		// list is empty
		pHead = pNewNode;
		pTail = pNewNode;
	} // end if -- empty list
	else
	{
		// list has at least one item in it
		pTail->SetNext(pNewNode );
		pTail = pNewNode;
	} // end else
} // end queue

// ----------------------------------------------------------------------------

// push - this function pushes an item on the front of the list
//
template <class T>
void LList<T>::push( T *pData )
{
	Node<T> *pNewNode;
	
	// create the new node
	pNewNode = new Node<T>( pData );

	// place the node on the list
	pNewNode->SetNext( pHead );
	pHead = pNewNode;

	// if the list was empty then this is both the head and tail 
	if( pTail == NULL )
		pTail = pNewNode;

} // end push

// ----------------------------------------------------------------------------

// pop - this function removes an item from the front of the list
template <class T>
T *LList<T>::pop()
{
	T *pData;

	// if the list is empty return NULL
	if( pHead == NULL )
		return( NULL );

	// get the head node's data
	pData = pHead->Data();

	// if there is only one item in the list 
	if( pHead == pTail )
	{
		// remove old node
		delete pHead;

		// set head and tail pointers
		pHead = NULL;
		pTail = NULL;
	} // end if -- one item in list
	else
	{
		// remove old node
		delete pHead;
	
		// set head pointer
		pHead = pHead->Next();
	} // end else -- were at least two items in list
	
	return( pData );
} // end pop

// ----------------------------------------------------------------------------

// destroy - deletes entire list
template <class T>
void LList<T>::destroy()
{
	T *pData;
	Node<T> *pNode, *pTempNode;

	pNode = pHead;
	while( pNode != NULL )
	{
		pTempNode = pNode->Next();
		pData = pNode->Data();
		delete pData;
		delete pNode;
		
		pNode = pTempNode;
	} // end while

	pHead = NULL;
	pTail = NULL;
	pCurrent = NULL;
} // end destroy

// ----------------------------------------------------------------------------

// next - sets the current pointer to the next item and returns a pointer to
//        its data object; if current pointer is NULL then returns the first
//        item in the list returns NULL if no next item
//
template <class T>
T *LList<T>::next()
{
	// if the list is empty return NULL
	if( pHead == NULL )
		return( NULL );

	// change the current pointer
	if( pCurrent == NULL )
		pCurrent = pHead;
	else
		pCurrent = pCurrent->Next();

	if( pCurrent == NULL )
		return( NULL );

	return( pCurrent->Data() );
} // end next

// ----------------------------------------------------------------------------