//-----------------------------------------------------------------------------
// Copyright (c) 1991,1992 Southeastern Universities Research Association,
//                         Continuous Electron Beam Accelerator Facility
//
// This software was developed under a United States Government license
// described in the NOTICE file included as part of this distribution.
//
//-----------------------------------------------------------------------------
//
// Description:  General purpose linked list class with smart iterator.
//
// Author:  Walt Akers
//
//-----------------------------------------------------------------------------

#if !defined (_LINKED_LIST_H_)
#define _LINKED_LIST_H_

#include <limits.h>

// *****************************************************************************
// * class LinkedListDataDestructor :
// *	This is a pure virtual base class that can be used to create a
// *	destructor class for the data that is stored in the LinkedList class.
// *	If a destructor class is specified, it can be called by the LinkedList
// *	to delete the user defined data whenever it is removed from the list.
// *****************************************************************************
class LinkedListDataDestructor 
{
public:	
	virtual void destroy ( void * data ) = 0;
};


// *****************************************************************************
// * class LinkedListDataConstructor :
// *	This is a pure virtual class that can be used to create a constructor
// *	class for data that is being stored in the LinkedList class.  If this
// *	constructor class is specified, then it will be called each time data
// *	is added to the list in order to perform any user defined pre-processing
// *	that is necessary.
// *****************************************************************************
class LinkedListDataConstructor
{
public:
	virtual void * construct ( void * data ) = 0;
};
	

// *****************************************************************************
// * class LinkedList :
// *	This is the storage class for the linked list, it will maintain a list
// *	of data nodes and provide iterator objects to the developer upon
// *	request.
// *****************************************************************************
class LinkedList
{
friend class LinkedListIterator;

private:
	// *********************************************************************
	// * class LinkedList::Node :
	// *	An embedded class that defines the storage structure for each
	// *	entity in the doubly-linked list.
	// *********************************************************************
	class Node
		{
		public:
			Node * prev;
			Node * next;
			void * data;
		
			Node ( void * Data = NULL ) 
				: prev(NULL), 
				  next(NULL),
				  data(Data)
				{
				}
		};
	
	// *********************************************************************
	// * LinkedListDataDestructor * destructor:
	// *	This is a class that may be specified by the linked list user.
	// *	If specified, this method will be called by the linked list
	// *	any remove is called in order to delete the user data.  If the
	// *	destructor is not specified, then the user provided data will
	// *	not be deleted.
	// *********************************************************************
	LinkedListDataDestructor * destructor;
	
	// *********************************************************************
	// * LinkedListDataConstructor * constructor :
	// * 	This is a class that contains a virtual construct method that
	// *	is called whenever new data is added to the linked list. This
	// *	construct method can do any preprocessing that of the data that
	// *	is desired by the user.
	// *********************************************************************
	LinkedListDataConstructor * constructor;

	// *********************************************************************
	// * Node * head:
	// *	This item points to the first node in the list.  It is NULL when
	// *	the class is created and is initialized when the first data item
	// *	is added to the list.
	// *********************************************************************
	Node * head;
	
	// *********************************************************************
	// * Node * tail:
	// *	This item points to the last node in the list.  It is NULL when
	// *	the class is created and is initailized and updated each time a
	// *	data item is added to the list.
	// *********************************************************************
	Node * tail;
	
	// *********************************************************************
	// * LinkedListIterator * iterList;
	// *	This is a list of iterators that have been created to access 
	// *	this list.
	// *********************************************************************
	LinkedListIterator * iterList;

	// *********************************************************************
	// * size_t count
	// *	This is the total number of entries that are currently stored 
	// *	in the linked list.
	// *********************************************************************
	size_t count;

	// *********************************************************************
	// * LinkedList::remove :
	// *	This method is called by the LinkedListIterator in order to
	// *	remove an entry from the linked list.  It will locate all 
	// *	iterators that might be impacted by this change and will update
	// *	them appropriately.
	// *********************************************************************
	inline int remove  ( LinkedListIterator & iter );
	
	// *********************************************************************
	// * LinkedList::append :
	// *	This method is called by the LinkedListIterator in order to
	// *	append a new entry to the linked list.
	// *
	// *	Note that the newly appended entry will become the current entry
	// *	for this iterator.
	// *********************************************************************
	inline int append  ( LinkedListIterator & iter, LinkedList::Node & node );

	// *********************************************************************
	// * LinkedList::insert :
	// *	This method is called by the LinkedListIterator to insert a
	// *	new entry above or below the current entry.  It will locate all 
	// *	iterators that might be impacted by this change and will update
	// *	them appropriately.
	// *
	// *	Note that the iterator must be pointing to a valid entry or the
	// *	list must be empty in order for this to work.  The newly 
	// *	inserted entry will become the current entry for this iterator.
	// *********************************************************************
	inline int insert ( LinkedListIterator & iter, LinkedList::Node & node, int above=1 );

	// *********************************************************************
	// * LinkedList::reindex :
	// *	This is an emergency fall-back that should never be called.  
	// *	This method will be executed if the indexing/count in the list
	// *	or any of its iterators becomes invalid...  It will recount all
	// *	of the items in the list and then walk through each of the 
	// *	iterators and update their internal indices.
	// *********************************************************************
	inline void reindex ( void );

public:
	// *********************************************************************
	// * LinkedList::LinkedList :
	// *	This is the constructor for the class, it initializes all 
	// *	internal variables to there default values.
	// *********************************************************************
	inline LinkedList ( void );

	// *********************************************************************
	// * LinkedList::~LinkedList :
	// *	This is the destructor for the class, it deletes all nodes that
	// *	may have been created to store data.  It will also invalidate
	// *	the listPtr for any existing iterators. This destructor will NOT 
	// *	delete the data that is stored in the Nodes.
	// *********************************************************************
	inline ~LinkedList ( void );

	// *********************************************************************
	// * LinkedList::iterator :
	// *	This method will return a new linked list iterator that can 
	// *	be used to traverse this list.
	// *********************************************************************
	inline LinkedListIterator * iterator ( void );

	// *********************************************************************
	// * LinkedList::setDestructor :
	// *	This inline method allows the caller to set the destructor that
	// *	will be used by the class to delete data.
	// *********************************************************************
	inline void setDestructor ( LinkedListDataDestructor * Destructor = NULL );
	
	// *********************************************************************
	// * LinkedList::setConstructor :
	// *	This method allows the caller to set the constructor that will
	// *	be used by the class to initialize inbound data.
	// *********************************************************************
	inline void setConstructor ( LinkedListDataConstructor * Constructor = NULL );
};


// *****************************************************************************
// * class LinkedListIterator :
// *	This class is used to allow the caller to traverse the data in the 
// *	 linked list class.
// *****************************************************************************
class LinkedListIterator 
{
friend class LinkedList;

private:
	// *********************************************************************
	// * LinkedListIterator * next :
	// *	This entry allows the linked list to maintain a list of all 
	// *	iterators that are in use.  This list is used to update indices
	// *	when entries are deleted.
	// *********************************************************************
	LinkedListIterator * nextIter;
	
	// *********************************************************************
	// * LinkedList * list :
	// * 	This is the linked list that owns the iterator.
	// *********************************************************************
	LinkedList * list;

	// *********************************************************************
	// * LinkedList::Node * node :
	// *	This is the current entry in the linked list.
	// *********************************************************************
	LinkedList::Node * node;
	
	// *********************************************************************
	// * int index :
	// *	This is the index of the current entry in the list.  Indexes
	// *	start at 0.
	// *********************************************************************
	int index;

	// *********************************************************************
	// * LinkedListIterator::LinkedListIterator :
	// *	This is the constructor for the iterator.  It is private to 
	// *	prevent it from being instanciated directly.  In order to obtain
	// *	a LinkedListIterator the developer must call the iterator method
	// *	of the LinkedList.
	// *
	// *	This method will automatically position the developer at the 
	// *	top of the linked list.
	// *********************************************************************
	inline LinkedListIterator ( LinkedList * listPtr );

public:
	// *********************************************************************
	// * LinkedListIterator::~LinkedListIterator :
	// *	This is the destructor for the iterator. The user must call
	// *	this method when the iterator is no longer needed.  It will 
	// *	remove itself from teh table of iterators registered with the
	// *	LinkedList prior to being deleted.
	// *********************************************************************
	inline ~LinkedListIterator ( void );

	// *********************************************************************
	// * LinkedListIterator::first :
	// *	This method will position the iterator to the top of the list
	// *	of entries in the linked list and set the index to 0.  If the
	// *	linked list is empty, then the index will be set to -1 and the
	// *	node willbe set to NULL.
	// *********************************************************************
	inline void first ( void );

	// *********************************************************************
	// * LinkedListIterator::last :
	// *	This method will position the iterator to the bottom of the 
	// *	list of entries and set the index to the appropriate 
	// *	value (count-1).  If the list is empty the index will be set to 
	// *	-1 and the node will be set to NULL.
	// *********************************************************************
	inline void last ( void );
	
	// *********************************************************************
	// * LinkedListIterator::prev :
	// *	This method will position the iterator to the previous entry 
	// *	in the list.  
	// * 
	// *	If the iterator is already at the top of the list or the list is 
	// *	empty, then a -1 will be returned and the current entry will be 
	// *	marked as invalid.  
	// * 
	// *	If the iterator is passed the bottom of the list, this method 
	// *	will reposition to the tail.
	// * 
	// *	On success a value of 0 is returned.
	// *********************************************************************
	inline int prev ( void );

	// *********************************************************************
	// * LinkedListIterator::next :
	// *	This method will position the iterator to the next entry in the 
	// *	list. 
	// * 
	// *	If the iterator is already at the bottom of the list or the list 
	// *	is  empty, then a -1 will be returned and the current entry will 
	// *	be marked as invalid.  
	// * 
	// *	If the iterator is above the top of the list, this method 
	// *	will reposition to the head.
	// * 
	// *	On success a value of 0 is returned.
	// *********************************************************************
	inline int next ( void );

	// *********************************************************************
	// * LinkedListIterator::remove :
	// *	This method is called to remove the current entry from the
	// *	linked list.  It will return 0 if the entry is successful 
	// *	removed, or -1 if an error occurs.
	// *********************************************************************
	inline int remove ( void );

	// *********************************************************************
	// * LinkedListIterator::append :
	// *	This method is called to append an entry to the bottom of the
	// *	list.  It will return 0 if the entry is successfully added, or
	// *	-1 if an error occurs.
	// *********************************************************************
	inline int append ( void * data );

	// *********************************************************************
	// * LinkedListIterator::insert :
	// *	This method is called to insert a new entry at the current 
	// *	position in the linked list.  It will return 0 on success, or
	// *	-1 if an error occurs.
	// *
	// *	The above flag (TRUE by default) indicates that the new entry
	// *	should be inserted above or below the current entry.
	// *********************************************************************
	inline int insert ( void * data, int above = 1 );
		
	// *********************************************************************
	// * LinkedListIterator::replace :
	// *	This method will replace the data in the current node with the
	// *	user provided data.  It is the responsibility of the user to 
	// *	delete the old data if necessary.  this method will return 0
	// *	on success, or -1 if there is no current entry.
	// *********************************************************************
	inline int replace ( void * data );
	
	// *********************************************************************
	// * LinkedListIterator::isvalid :
	// *	This method allows the developer to determine if the iterator
	// *	is currently pointing at a valid entry.  This method returns
	// *	1 if the entry is valid or 0 if the entry is bogus.
	// *********************************************************************
	inline int isvalid ( void );

	// *********************************************************************
	// * LinkedListIterator::get_index :
	// *	This method returns the index of the current data item.  If the
	// *	data item is invalid, then an index of -1 is returned.
	// *********************************************************************
	inline int get_index ( void );

	// *********************************************************************
	// * LinkedListIterator::get_count :
	// *	This method will return the total number of entries in the list.
	// *********************************************************************
	inline int get_count ( void );
	
	// *********************************************************************
	// * LinkedListIterator::get_value :
	// *	This method returns the value of the current entry in the list.
	// *	If the current entry is invalid, a value of NULL is returned.
	// *********************************************************************
	inline void * get_value ( void );

	// *********************************************************************
	// * LinkedListIterator::operator [];
	// *	This method returns the value of the entry in the list at the 
	// *	specified index.  If the index is out of range, then a value
	// *	of NULL will be returned.
	// *
	// *	Note that the index operator cannot be used to replace the 
	// *	pointer used by the list.  Use the replace method to install
	// *	a new pointer.
	// *********************************************************************
	inline void * operator [] ( size_t idx );
};


// *****************************************************************************
// * LinkedList::remove :
// *	This method is called by the LinkedListIterator in order to
// *	remove an entry from the linked list.  It will locate all 
// *	iterators that might be impacted by this change and will update
// *	them appropriately.
// *****************************************************************************
inline int LinkedList::remove  ( LinkedListIterator & iter )
	{
	int result;

	// *********************************************************************
	// * Check to make sure that the node contained in the iterator 
	// * is valid, that the iterator points to this list, and that 
	// * the iterator's index is in a valid range.
	// *********************************************************************
	if(iter.node!=NULL && iter.list==this && 
	   iter.index<count && iter.index>=0)
		{
		LinkedListIterator * iters;
		Node               * deadNode = iter.node;
		Node               * node     = NULL;
		int                  index    = iter.index;
		
		// *************************************************************
		// * Identify the node that will take the place of the
		// * deleted node and determine what its index will be.
		// * By default, the replacement node will be the 
		// * previous node when possible or the next node if
		// * the head node is deleted.
		// *************************************************************
		if(deadNode->prev!=NULL)
			{
			node = deadNode->prev;
			index--;
			}
		else	node = deadNode->next;
		
		// *************************************************************
		// * Ensure that the head and tail are correct.
		// *************************************************************
		if(deadNode->prev==NULL) head = deadNode->next;
		if(deadNode->next==NULL) tail = deadNode->prev;

		// *************************************************************
		// * Update the pointers on the nodes surrounding the node to
		// * be removed...
		// *************************************************************
		if(deadNode->next) deadNode->next->prev = deadNode->prev;
		if(deadNode->prev) deadNode->prev->next = deadNode->next;

		// *************************************************************
		// * Walk through the list of all iterators and update
		// * them.  If an iterator points to the deleted node,
		// * then it will be updated with the replacement node
		// * and index as determined above.  If a iterator has
		// * a node that occurs later in the list, then its
		// * index will be decremented to indicate its new 
		// * position.
		// *************************************************************
		for(iters=iterList; iters!=NULL; iters=iters->nextIter)
			{
			if(iters->node==NULL) 
				{
				continue;
				}
			else if (head==NULL)
				{
				iters->node  = NULL;
				iters->index = -1;
				}
			else if(iters->node==deadNode)
				{
				iters->node  = node;
				iters->index = index;
				}
			else if(iters->index > index)
				{
				iters->index--;
				}
			}

		// *************************************************************
		// * Delete the old node and decrement the count.  Note,
		// * this approach WILL NOT delete the data that is 
		// * associated with the entry... the developer is 
		// * responsible for deleting the data.
		// *************************************************************
		if(destructor) destructor->destroy(deadNode->data);
		delete deadNode;
		count--;
		result = 0;
		}
	else result = -1;

	return result;
	}

// *****************************************************************************
// * LinkedList::append :
// *	This method is called by the LinkedListIterator in order to
// *	append a new entry to the linked list.
// *
// *	Note that the newly appended entry will become the current entry
// *	for this iterator.
// *****************************************************************************
inline int LinkedList::append  ( LinkedListIterator & iter, LinkedList::Node & node )
	{
	int result;

	// *********************************************************************
	// * If a constructor class has been specified, use the construct method
	// * to pre-process the data.
	// *********************************************************************
	if(constructor!=NULL) node.data = constructor->construct(node.data);

	// *********************************************************************
	// * Ensure that the iterator points to the current list and 
	// * then append the entry to the end of the list and increment
	// * the count.
	// *********************************************************************
	if(iter.list == this)
		{
		int index = count++;
		
		node.prev  = tail;
		node.next  = NULL;
		if(tail!=NULL) tail->next = &node;
		if(head==NULL) head       = &node;
		tail                      = &node;

		iter.node  = &node;
		iter.index = index;
		
		result = 0;
		}
	else result = -1;
	
	return result;
	}

// *****************************************************************************
// * LinkedList::insert :
// *	This method is called by the LinkedListIterator to insert a
// *	new entry above or below the current entry.  It will locate all 
// *	iterators that might be impacted by this change and will update
// *	them appropriately.
// *
// *	Note that the iterator must be pointing to a valid entry or the
// *	list must be empty in order for this to work.  The newly 
// *	inserted entry will become the current entry for this iterator.
// *****************************************************************************
inline int LinkedList::insert ( LinkedListIterator & iter, LinkedList::Node & node, int above )
	{
	int result;

	// *********************************************************************
	// * If a constructor class has been specified, use the construct method
	// * to pre-process the data.
	// *********************************************************************
	if(constructor!=NULL) node.data = constructor->construct(node.data);

	// *********************************************************************
	// * If there are no entries in the list, then use the append
	// * method to add the new entry to the head of the list.
	// *********************************************************************
	if(iter.list == this && count==0) 
		{
		result = append(iter, node);
		}
	// *********************************************************************
	// * If the iterator points to this list and the insertion point
	// * is not NULL, then attempt to insert the entry.
	// *********************************************************************
	else if(iter.list == this && iter.node!=NULL)
		{
		LinkedListIterator * iters;
		int                  index = iter.index;
		
		// *************************************************************
		// * Insert the entry above or below the current entry.
		// * If the new node is inserted below the current 
		// * entry, then the index must be incremented to 
		// * reflect its new position.
		// *************************************************************
		if(above)
			{
			if((node.prev = iter.node->prev)!=NULL) 
				node.prev->next = &node;
			if((node.next = iter.node)!=NULL) 
				node.next->prev = &node;
			}
		else	{
			if((node.next = iter.node->next)!=NULL)
				node.next->prev = &node;
			if((node.prev = iter.node)!=NULL)
				node.prev->next = &node;
			index++;
			}

		// *************************************************************
		// * If the new entry occupies the head or tail position
		// * in the list, then update these variables to reflect
		// * its position.
		// *************************************************************
		if(node.prev==NULL) head = &node;
		if(node.next==NULL) tail = &node;
		
		// *************************************************************
		// * Walk through the list and increment the indexes of
		// * any iterator that contains a node that occurs later
		// * in the list than the new node.
		// *************************************************************
		for(iters=iterList; iters!=NULL; iters=iters->nextIter)
			{
			if(iters->node==NULL) 
				{
				continue;
				}
			else if(iters->index >= index)
				{
				iters->index++;
				}
			}
		
		// *************************************************************
		// * Update the user provided iterator to point to the
		// * newly inserted node and its correct index and 
		// * increment the count.
		// *************************************************************
		iter.node  = &node;
		iter.index = index;
		count++;
		result = 0;
		}
	else result = -1;
	
	return result;
	}

// *****************************************************************************
// * LinkedList::reindex :
// *	This is an emergency fall-back that should never be called.  
// *	This method will be executed if the indexing/count in the list
// *	or any of its iterators becomes invalid...  It will recount all
// *	of the items in the list and then walk through each of the 
// *	iterators and update their internal indices.
// *****************************************************************************
inline void LinkedList::reindex ( void )
	{
	LinkedListIterator * iters;
	Node               * node = head;
	
	for(count = 0; node!=NULL; node=node->next) count++;
	for(iters=iterList; iters!=NULL; iters = iters->nextIter)
		{
		if(iters->node!=NULL)
			{
			for(iters->index=0, node=head; 
			    node!=NULL && node!=iters->node; 
			    node=node->next)
			    	{
			    	iters->index++;
			    	}
			if(node==NULL) 
				{
				iters->node  = NULL;
				iters->index = 0;
				}
			}
		}
	}

// *****************************************************************************
// * LinkedList::LinkedList :
// *	This is the constructor for the class, it initializes all 
// *	internal variables to there default values.
// *****************************************************************************
inline LinkedList::LinkedList ( void )
	: head(NULL), tail(NULL), iterList(NULL), count(0),
	  constructor(NULL), destructor(NULL)
	{
	}


// *****************************************************************************
// * LinkedList::~LinkedList :
// *	This is the destructor for the class, it deletes all nodes that
// *	may have been created to store data.  It will also invalidate
// *	the listPtr for any existing iterators. This destructor will NOT 
// *	delete the data that is stored in the Nodes.
// *****************************************************************************
inline LinkedList::~LinkedList ( void )
	{
	Node * curr;
	while(head!=NULL)
		{
		curr = head;
		head = curr->next;
		if(destructor) destructor->destroy(curr->data);
		delete curr;
		}
	
	while(iterList!=NULL)
		{
		iterList->list = NULL;
		iterList->node = NULL;
		iterList = iterList->nextIter;
		}
	}

// *****************************************************************************
// * LinkedList::iterator :
// *	This method will return a new linked list iterator that can 
// *	be used to traverse this list.
// *****************************************************************************
inline LinkedListIterator * LinkedList::iterator ( void )
	{
	LinkedListIterator * iter = new LinkedListIterator(this);
	iter->nextIter = iterList;
	iterList       = iter;
	return iter; 
	}

// *****************************************************************************
// * LinkedList::setDestructor :
// *	This inline method allows the caller to set the destructor that
// *	will be used by the class to delete data.
// *****************************************************************************
inline void LinkedList::setDestructor ( LinkedListDataDestructor * Destructor)
	{
	destructor = Destructor;
	}

// *****************************************************************************
// * LinkedList::setConstructor :
// *	This method allows the caller to set the constructor that will
// *	be used by the class to initialize inbound data.
// *****************************************************************************
inline void LinkedList::setConstructor ( LinkedListDataConstructor * Constructor)
	{
	constructor = Constructor;
	}
	
// *****************************************************************************
// * LinkedListIterator::LinkedListIterator :
// *	This is the constructor for the iterator.  It is private to 
// *	prevent it from being instanciated directly.  In order to obtain
// *	a LinkedListIterator the developer must call the iterator method
// *	of the LinkedList.
// *
// *	This method will automatically position the developer at the 
// *	top of the linked list.
// *****************************************************************************
inline LinkedListIterator::LinkedListIterator ( LinkedList * listPtr )
	: nextIter(NULL), list(listPtr), node(NULL), index(-1)
	{
	first();
	}

// *****************************************************************************
// * LinkedListIterator::~LinkedListIterator :
// *	This is the destructor for the iterator. The user must call
// *	this method when the iterator is no longer needed.  It will 
// *	remove itself from teh table of iterators registered with the
// *	LinkedList prior to being deleted.
// *****************************************************************************
inline LinkedListIterator::~LinkedListIterator ( void )
	{
	LinkedListIterator * curr, * prev = NULL;
	
	for(curr=list->iterList; curr!=this; curr=curr->nextIter) prev = curr;
	if(curr!=NULL)
		{
		if(prev) prev->nextIter = curr->nextIter;
		else list->iterList = curr->nextIter;
		}
	}

// *****************************************************************************
// * LinkedListIterator::first :
// *	This method will position the iterator to the top of the list
// *	of entries in the linked list and set the index to 0.  If the
// *	linked list is empty, then the index will be set to -1 and the
// *	node willbe set to NULL.
// *****************************************************************************
inline void LinkedListIterator::first ( void )
	{
	node  = list->head;
	index = node?0:-1;
	}	

// *****************************************************************************
// * LinkedListIterator::last :
// *	This method will position the iterator to the bottom of the 
// *	list of entries and set the index to the appropriate 
// *	value (count-1).  If the list is empty the index will be set to 
// *	-1 and the node will be set to NULL.
// *****************************************************************************
inline void LinkedListIterator::last ( void )
	{
	node = list->tail;
	index = node?list->count-1:-1;
	}

// *****************************************************************************
// * LinkedListIterator::prev :
// *	This method will position the iterator to the previous entry 
// *	in the list.  
// * 
// *	If the iterator is already at the top of the list or the list is 
// *	empty, then a -1 will be returned and the current entry will be 
// *	marked as invalid.  
// * 
// *	If the iterator is passed the bottom of the list, this method 
// *	will reposition to the tail.
// * 
// *	On success a value of 0 is returned.
// *****************************************************************************
inline int LinkedListIterator::prev ( void )
	{
	int result;

	if(node!=NULL && node->prev!=NULL)
		{
		node = node->prev;
		index--;
		result = 0;
		}
	else if (node==NULL && index==INT_MAX)
		{
		last();
		result = isvalid()?0:-1;
		}
	else	{
		node   = NULL;
		index  = -1;
		result = -1;
		}

	return result;
	}

// *****************************************************************************
// * LinkedListIterator::next :
// *	This method will position the iterator to the next entry in the 
// *	list. 
// * 
// *	If the iterator is already at the bottom of the list or the list 
// *	is  empty, then a -1 will be returned and the current entry will 
// *	be marked as invalid.  
// * 
// *	If the iterator is above the top of the list, this method 
// *	will reposition to the head.
// * 
// *	On success a value of 0 is returned.
// *****************************************************************************
inline int LinkedListIterator::next ( void )
	{
	int result;
	
	if(node!=NULL && node->next!=NULL)
		{
		node = node->next;
		index++;
		result = 0;
		}
	else if (node==NULL && index<0)
		{
		first();
		result = isvalid()?0:-1;
		}
	else	{
		node  = NULL;
		index = INT_MAX;
		result = -1;
		}
		
	return result;
	}

// *****************************************************************************
// * LinkedListIterator::remove :
// *	This method is called to remove the current entry from the
// *	linked list.  It will return 0 if the entry is successful 
// *	removed, or -1 if an error occurs.
// *****************************************************************************
inline int LinkedListIterator::remove ( void )
	{
	return list->remove(*this);
	}


// *****************************************************************************
// * LinkedListIterator::append :
// *	This method is called to append an entry to the bottom of the
// *	list.  It will return 0 if the entry is successfully added, or
// *	-1 if an error occurs.
// *****************************************************************************
inline int LinkedListIterator::append ( void * data )
	{
	int result;
	
	LinkedList::Node * newNode = new LinkedList::Node(data);
	
	if((result = list->append(*this, *newNode))!=0)
		{
		delete newNode;
		}
	return result;
	}

// *****************************************************************************
// * LinkedListIterator::insert :
// *	This method is called to insert a new entry at the current 
// *	position in the linked list.  It will return 0 on success, or
// *	-1 if an error occurs.
// *
// *	The above flag (TRUE by default) indicates that the new entry
// *	should be inserted above or below the current entry.
// *****************************************************************************
inline int LinkedListIterator::insert ( void * data, int above )
	{
	int result;
	
	LinkedList::Node * newNode = new LinkedList::Node(data);
	
	if((result = list->insert(*this, *newNode, above))!=0)
		{
		delete newNode;
		}
	return result;
	}
	
// *****************************************************************************
// * LinkedListIterator::replace :
// *	This method will replace the data in the current node with the
// *	user provided data.  It is the responsibility of the user to 
// *	delete the old data if necessary.  this method will return 0
// *	on success, or -1 if there is no current entry.
// *****************************************************************************
inline int LinkedListIterator::replace ( void * data )
	{
	int result;
	
	if(node!=NULL)
		{
		if(list->destructor) list->destructor->destroy(node->data);

		if(list->constructor==NULL) node->data = data;
		else node->data = list->constructor->construct(data);
		
		result = 0;
		}
	else result = -1;
	
	return result;
	}

// *****************************************************************************
// * LinkedListIterator::isvalid :
// *	This method allows the developer to determine if the iterator
// *	is currently pointing at a valid entry.  This method returns
// *	1 if the entry is valid or 0 if the entry is bogus.
// *****************************************************************************
inline int LinkedListIterator::isvalid ( void )
	{
	return node==NULL?0:1;
	}

// *****************************************************************************
// * LinkedListIterator::get_index :
// *	This method returns the index of the current data item.  If the
// *	data item is invalid, then an index of -1 is returned.
// *****************************************************************************
inline int LinkedListIterator::get_index ( void )
	{
	return (node && index>=0 && index<INT_MAX)?index:-1;
	}

// *****************************************************************************
// * LinkedListIterator::get_count :
// *	This method will return the total number of entries in the list.
// *****************************************************************************
inline int LinkedListIterator::get_count ( void )
	{
	return list->count;
	}

// *****************************************************************************
// * LinkedListIterator::get_value :
// *	This method returns the value of the current entry in the list.
// *	If the current entry is invalid, a value of NULL is returned.
// *****************************************************************************
inline void * LinkedListIterator::get_value ( void )
	{
	return node?node->data:NULL;

	}

// *****************************************************************************
// * LinkedList::operator [];
// *	This method returns the value of the entry in the list at the 
// *	specified index.  If the index is out of range, then a value
// *	of NULL will be returned.
// *
// *	Note that the index operator cannot be used to replace the 
// *	pointer used by the list.  Use the replace method to install
// *	a new pointer.
// *****************************************************************************
inline void * LinkedListIterator::operator [] ( size_t idx )
	{
	// *********************************************************************
	// * Ensure that the index is within range.
	// *********************************************************************
	if(idx<list->count)
		{
		// *************************************************************
		// * If the desired position is above the current entry
		// * reposition to it by going down from the top or
		// * up from the current - whichever is a shorter trip.
		// *************************************************************
		if(idx<index)
			{
			if(idx < index-idx)
				{
				node  = list->head;
				index = 0;
				
				while(index!=idx && node!=NULL) 
					{
					node = node->next;
					index++;
					}
				}
			else	{
				while(index!=idx && node!=NULL)
					{
					node = node->prev;
					index--;
					}
				}
			}
		// *************************************************************
		// * If the desired position is below the current entry
		// * reposition to it by going up from the bottom or
		// * down from the current - whichever is a shorter trip.
		// *************************************************************
		else	{
			if(idx > list->count-idx-1)
				{
				node  = list->tail;
				index = list->count-1;
				
				while(index!=idx && node!=NULL)
					{
					node = node->prev;
					index--;
					}
				}
			else	{
				while(index!=idx && node!=NULL)
					{
					node = node->next;
					index++;
					}
				}
			}
		
		// *************************************************************
		// * If an error occurs, then it means that the indexing
		// * has somehow become invalid.  Set the node to NULL 
		// * and the index to -1 and recount the items in the
		// * linked list...  Logically, this should never 
		// * happen.
		// *************************************************************
		if(node==NULL)
			{
			index  = -1;
			list->reindex();
			}
		}
	else	{
		node   = NULL;
		index  = -1;
		}

	return node?node->data:NULL;
	}



#endif /* _LINKED_LIST_H_ */