1092 lines
40 KiB
C++
1092 lines
40 KiB
C++
//-----------------------------------------------------------------------------
|
|
// 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_ */
|