Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members  

XFcLinkedList< T > Class Template Reference

Bidirectional linked list template class. More...

Inheritance diagram for XFcLinkedList< T >:

Inheritance graph
[legend]
List of all members.

Public Types

typedef XFcLinkedListAbstractIterator<
T > 
iterator
 Abstract iterator type.

typedef XFcLinkedListForwardIterator<
T > 
forwardIterator
 Forward iterator type.

typedef XFcLinkedListReverseIterator<
T > 
reverseIterator
 Reverse iterator type.

typedef XFcLinkedListBidirectionalIterator<
T > 
bidirectionalIterator
 Bidirectional iterator type.


Public Member Functions

forwardIterator forwardBegin () const
 Returns a forward iterator pointing to the beginning of list.

forwardIterator forwardEnd () const
 Returns a forward iterator pointing to the end of list.

reverseIterator reverseBegin () const
 Returns a reverse iterator pointing to the beginning of list.

reverseIterator reverseEnd () const
 Returns a reverse iterator pointing to the end of list.

bidirectionalIterator bidirectionalBegin () const
 Returns a bidirectional iterator pointing to the beginning of list.

bidirectionalIterator bidirectionalEnd () const
 Returns a bidirectional iterator pointing to the end of list.

UINT32 size () const
 Returns the amount of nodes in the list.

getFirst () const
 Returns the value of the first node.

getLast () const
 Returns the value of the last node.

INT add (const UINT32 aIndex, const T aNewData)
 Adds a new node by index.

INT addFirst (const T aNewData)
 Adds a new node to the beginning of list.

INT addLast (const T aNewData)
 Adds a new node to the end of list.

INT addBefore (const iterator &aIterator, const T aNewData)
 Adds a new node before the node pointed to by an iterator.

INT addAfter (const iterator &aIterator, const T aNewData)
 Adds a new node after the node pointed to by an iterator.

INT removeIndex (const UINT32 aIndex)
 Removes a node by index.

INT remove (const T aData)
 Removes a node by value.

INT remove (iterator &aIterator, const UINT aMethod=1)
 Removes a node pointed to by an iterator.

 XFcLinkedList ()
 Creates an empty list.

 XFcLinkedList (const UINT32 aPreAlloc)
 Creates an empty list with a number of preallocated nodes.

 ~XFcLinkedList ()
 Destructor.


Protected Member Functions

void preAlloc ()
 Preallocates nodes to the empty nodes list.

void putEmptyNode (XFcLinkedListNode< T > *aNode)
 Puts an empty node into the empty nodes list.

XFcLinkedListNode< T > * getEmptyNode ()
 Returns and removes the first node from the empty nodes list.

void removeNode (XFcLinkedListNode< T > *aNode)
 Removes a node from the list.


Protected Attributes

UINT32 mNodes
 Number of nodes in list.

UINT32 mPreAlloc
 Number of preallocated nodes.

UINT32 mEmptyNodes
 Number of empty preallocated nodes.

XFcLinkedListNode< T > * mHead
 Pointer to the first node in list.

XFcLinkedListNode< T > * mTail
 Pointer to the last node in list.

XFcLinkedListNode< T > * mEmpty
 Pointer to the empty node list, used for faster allocation.


Detailed Description

template<class T>
class XFcLinkedList< T >

Bidirectional linked list template class.

Example:

 // Create the list
 XFcLinkedList<UINT32> *list = new XFcLinkedList<UINT32>();
 list->addLast(1);
 list->addLast(2);
 list->addLast(3);
 list->addLast(4);
 list->removeIndex(2);
 // The list now contains items {1, 2, 4}
 delete list;
 


Member Typedef Documentation

template<class T>
typedef XFcLinkedListBidirectionalIterator<T> XFcLinkedList< T >::bidirectionalIterator
 

Bidirectional iterator type.

template<class T>
typedef XFcLinkedListForwardIterator<T> XFcLinkedList< T >::forwardIterator
 

Forward iterator type.

template<class T>
typedef XFcLinkedListAbstractIterator<T> XFcLinkedList< T >::iterator
 

Abstract iterator type.

template<class T>
typedef XFcLinkedListReverseIterator<T> XFcLinkedList< T >::reverseIterator
 

Reverse iterator type.


Constructor & Destructor Documentation

template<class T>
XFcLinkedList< T >::XFcLinkedList  
 

Creates an empty list.

template<class T>
XFcLinkedList< T >::XFcLinkedList const UINT32    aPreAlloc
 

Creates an empty list with a number of preallocated nodes.

Parameters:
aPreAlloc number of nodes to preallocate.

template<class T>
XFcLinkedList< T >::~XFcLinkedList  
 

Destructor.


Member Function Documentation

template<class T>
INT XFcLinkedList< T >::add const UINT32    aIndex,
const T    aNewData
 

Adds a new node by index.

If the list is empty, the node will be added as the first node in the list.

Note:

Complexity of this method is O(n).

Parameters:
aIndex index where the node should be added.
aNewData value to put in the new node.
Returns:
1 if the addition is successful, 0 otherwise.

template<class T>
INT XFcLinkedList< T >::addAfter const iterator   aIterator,
const T    aNewData
 

Adds a new node after the node pointed to by an iterator.

If the list is empty, the node will be added as the first node in the list. If the iterator is not valid, the operation fails.

Note:
Complexity of this method is O(1).
Parameters:
aIterator iterator to add the new node after.
aNewData value to put in the new node.
Returns:
1 if the addition is successful, 0 otherwise.

template<class T>
INT XFcLinkedList< T >::addBefore const iterator   aIterator,
const T    aNewData
 

Adds a new node before the node pointed to by an iterator.

If the list is empty, the node will be added as the first node in the list. If the iterator is not valid, the operation fails.

Note:
Complexity of this method is O(1).
Parameters:
aIterator iterator to add the new node before.
aNewData value to put in the new node.
Returns:
1 if the addition is successful, 0 otherwise.

template<class T>
INT XFcLinkedList< T >::addFirst const T    aNewData
 

Adds a new node to the beginning of list.

Note:
Complexity of this method is O(1).
Parameters:
aNewData value to put in the new node.

template<class T>
INT XFcLinkedList< T >::addLast const T    aNewData
 

Adds a new node to the end of list.

If the list is empty, the node will be added as the first node in the list.

Note:
Complexity of this method is O(1).
Parameters:
aNewData value to put in the new node.
Returns:
1 if the addition is successful, 0 otherwise.

template<class T>
XFcLinkedList< T >::bidirectionalIterator XFcLinkedList< T >::bidirectionalBegin   const
 

Returns a bidirectional iterator pointing to the beginning of list.

template<class T>
XFcLinkedList< T >::bidirectionalIterator XFcLinkedList< T >::bidirectionalEnd   const
 

Returns a bidirectional iterator pointing to the end of list.

template<class T>
XFcLinkedList< T >::forwardIterator XFcLinkedList< T >::forwardBegin   const
 

Returns a forward iterator pointing to the beginning of list.

template<class T>
XFcLinkedList< T >::forwardIterator XFcLinkedList< T >::forwardEnd   const
 

Returns a forward iterator pointing to the end of list.

template<class T>
XFcLinkedListNode< T > * XFcLinkedList< T >::getEmptyNode   [protected]
 

Returns and removes the first node from the empty nodes list.

Returns:
empty node.

template<class T>
T XFcLinkedList< T >::getFirst   const
 

Returns the value of the first node.

Note:
Complexity of this method is O(1).

template<class T>
T XFcLinkedList< T >::getLast   const
 

Returns the value of the last node.

Note:
Complexity of this method is O(1).

template<class T>
void XFcLinkedList< T >::preAlloc   [protected]
 

Preallocates nodes to the empty nodes list.

template<class T>
void XFcLinkedList< T >::putEmptyNode XFcLinkedListNode< T > *    aNode [protected]
 

Puts an empty node into the empty nodes list.

Parameters:
aNode node to add to the list.

template<class T>
INT XFcLinkedList< T >::remove iterator   aIterator,
const UINT    aMethod = 1
 

Removes a node pointed to by an iterator.

Note:
Complexity of this method is O(1).
Parameters:
aIterator iterator to remove the node from.
aMethod use 0 to make iterator point to the previous node after removal. Use 1 (default) to make iterator point to the next node after removal.
Returns:
1 if the removal is successful, 0 otherwise.

template<class T>
INT XFcLinkedList< T >::remove const T    aData
 

Removes a node by value.

Note:
Complexity of this method is O(n).
Parameters:
aData value of the node to be removed.
Returns:
1 if the removal is successful, 0 otherwise.

template<class T>
INT XFcLinkedList< T >::removeIndex const UINT32    aIndex
 

Removes a node by index.

If the given index is smaller than 0, or bigger than the amount of nodes in the list, the node will not be removed.

Note:
Complexity of this method is O(n).
Parameters:
aIndex index of the node to be removed.
Returns:
1 if the removal is successful, 0 otherwise.

template<class T>
void XFcLinkedList< T >::removeNode XFcLinkedListNode< T > *    aNode [protected]
 

Removes a node from the list.

Parameters:
aNode pointer to the node to be removed.

template<class T>
XFcLinkedList< T >::reverseIterator XFcLinkedList< T >::reverseBegin   const
 

Returns a reverse iterator pointing to the beginning of list.

template<class T>
XFcLinkedList< T >::reverseIterator XFcLinkedList< T >::reverseEnd   const
 

Returns a reverse iterator pointing to the end of list.

template<class T>
UINT32 XFcLinkedList< T >::size   const
 

Returns the amount of nodes in the list.

Note:
Complexity of this method is O(1).


Member Data Documentation

template<class T>
XFcLinkedListNode<T>* XFcLinkedList< T >::mEmpty [protected]
 

Pointer to the empty node list, used for faster allocation.

template<class T>
UINT32 XFcLinkedList< T >::mEmptyNodes [protected]
 

Number of empty preallocated nodes.

template<class T>
XFcLinkedListNode<T>* XFcLinkedList< T >::mHead [protected]
 

Pointer to the first node in list.

template<class T>
UINT32 XFcLinkedList< T >::mNodes [protected]
 

Number of nodes in list.

template<class T>
UINT32 XFcLinkedList< T >::mPreAlloc [protected]
 

Number of preallocated nodes.

template<class T>
XFcLinkedListNode<T>* XFcLinkedList< T >::mTail [protected]
 

Pointer to the last node in list.


   
X-Forge Documentation
Confidential
Copyright © 2002-2003 Fathammer
   
Documentation generated
with doxygen
by Dimitri van Heesch