GPL_DoubleList
GPL_DoubleList
gpl
1998 12-05
CLASS
GPL_DoubleList - C++ non-intrusive doubly linked list template
SYNOPSIS
GPL_DoubleList<data_type> idlist();
GPL_IDoubleList<data_type> idlist();
Class GPL_DoubleList is a non-intrusive doubly linked list. It is
non-intrusive in that objects added to the list do not need to have the
data members necessary for linked list operations (such as pointers to
the next and previous objects in the list). Internally an object with
these data members is created that points to the object of type
data_type that is to be added. This newly created object is then
added to the list.
Since the objects are merely pointed to by the list infrastructure, an
object may be in more than one list at a particular time. This is not
possible with the intrusive linked list GPL_IDoubleList.
Class GPL_IDoubleList is an intrusive doubly linked list. It is
intrusive in that the objects in the list must have the data members
necessary for the linked list operations (such as pointers to the next
and previous objects in the list). Therefore, data_type must be
derived from class GPL_DoubleNode which provides the needed data
members.
Since the required data members are embedded in the objects, a single
object may be part of only one list at a time. If this is not
acceptable see GPL_DoubleList which is a non-intrusive linked
list. However, GPL_IDoubleList is more efficient than
GPL_DoubleList.
The list has the concept of a current object pointer. In most cases,
the member functions ToHead() and PostIncrement() are used
to set this pointer to the first object in the list and then go through
the list an object by object.
CONSTRUCTOR
GPL_DoubleList()
GPL_IDoubleList()
Construct an non-intrusive or intrusive doubly linked list for objects
of type data_type.
When a GPL_IDoubleList object is destroyed, all objects that were
a part of the list are destroyed as well.
MEMBER FUNCTIONS
data_type *ToHead(void)
data_type *ToTail(void)
Move the pointer to the beginning or end of the list, respectively, and
return the node at that point.
long InsertBefore(data_type *node)
long InsertAfter(data_type *node)
Insert object specified by node
before or after the current node, respectively. For the intrusive
linked list, if the object is already part of a list, this function will
fail and return FALSE. Otherwise, the function succeeds and
TRUE is returned. The given new node becomes the current node.
void Clear(void)
Remove and delete all nodes on the list.
long SetCurrent(data_type *)
data_type *GetCurrent(void)
Set/Get the current node. The current node can be NULL if the
current node is before the beginning of the list or after the end of the
list. SetCurrent() will return TRUE if the node exists in
the list and FALSE if not.
long GetNumberNodes(void)
Return the number of nodes on the list.
data_type *PostIncrement()
data_type *PostDecrement()
Return the current pointed-to object in the list and move the pointer to
the next or previous object, respectively. If the beginning or end of
the list has already been reached, NULL is returned.
long RemoveNode(data_type *node)
Remove the object specified by node
from the list. If node
was the current node, the next node on the list becomes the new current node.
If node
was also the last node, the ending NULL becomes the new current
node. If the object is not in of a list, this function will fail and
return FALSE. Otherwise, the function succeeds and TRUE is
returned.
CONVENIENCE MEMBER FUNCTIONS
data_type *ToIndex(long index)
Resets to head and increments down the list to the specified index.
Returns the node at that location.
long AppendNode(data_type *node)
Move to the end of the list and append the object specified by
node after the last node. For the intrusive linked list, if the
object is already part of a list, this function will fail and return
FALSE. Otherwise, the function succeeds and TRUE is
returned. Functionally, this is equivalent to calling ToTail()
then calling and using the return value of
InsertAfter(node).
data_type *PreIncrement()
data_type *PreDecrement()
Move the pointer to the next or previous object, respectively; then
return the newly pointed-to object. If the beginning or end of the list
is reached, NULL is returned. Functionally, this is equivalent to
calling PostIncrement() or PostDecrement() then calling and
using the return value of Current().
OUTDATED MEMBER FUNCTIONS
data_type *Head(void)
Return a pointer the the object at the head of the list.
If the list is empty, this function returns NULL.
Similar to ToHead(),
but does not change ponter to current node.
data_type *Next(void)
Equivalent to PostIncrement().
void Current()
Equivalent to GetCurrent().
void Rewind()
Equivalent to ToHead().
NOTES
There are some caveats with the non-intrusive list. When a node in an
intrusive list is deleted, the destructor will automatically remove it
from the list. However, this cannot happen with the non-intrusive list
because there is no way to connect functionality with the destruction of
a non-intruded object (there is no imformation embedded in the object itself).
Also, for the non-intrusive list, an insertion function will not fail if
the object is already in the list. It will simply be added to the list
again. This means that with a non-intrusive list it is possible for an
object to be in the same list more than once. The function
RemoveNode() will remove the first instance (pointer) to the
object in the list. This means that if an object is in the list more
than once, is then removed once and the actual object deleted, the list
will effectively be corrupt because the remaining pointers will be to a
non-existant object.