ULAPI  8.0
Public Member Functions | Friends | List of all members
ULList< T > Class Template Reference

A doubly-linked list. More...

#include <ulcontainers.h>

Public Member Functions

 ULList ()
 
 ULList (const ULList< T > &list)
 
 ~ULList ()
 
void clear ()
 
ULList< T > & operator= (const ULList< T > &list)
 
bool operator== (const ULList< T > &list) const
 
T & operator[] (uluint32 n) const
 
T & getAtIndex (uluint32 n) const
 
ULListConstIterator< T > find (const T &data) const
 
void erase (uluint32 n)
 
void erase (ULListIterator< T > &it)
 
void erase (ULListIterator< T > &start, ULListIterator< T > &stop)
 
bool empty () const
 
uluint32 size () const
 
uluint32 length () const
 
void push_front (const T &data)
 
void push_back (const T &data)
 
void append (const T &data)
 
void prepend (const T &data)
 
void add (const T &data)
 
void insert (ULListIterator< T > &it, const T &data)
 
void insert (const T &data)
 
void pop ()
 
T & top ()
 
ULListIterator< T > begin ()
 
ULListConstIterator< T > cbegin () const
 
ULListIterator< T > end ()
 
ULListConstIterator< T > cend () const
 
ULListIterator< T > back ()
 
ULListConstIterator< T > cback () const
 
ULListNode< T > * removeNode (ULListIterator< T > &it)
 
ULListNode< T > * removeFrontNode ()
 
void insertNode (ULListIterator< T > &it, ULListNode< T > *node)
 
void splice (ULList< T > &tail)
 
void sort (int(*func)(T &, T &, void *), void *context)
 
void mergeSort (int(*func)(T &, T &, void *), void *context)
 

Friends

class ULListIterator< T >
 
class ULListConstIterator< T >
 

Detailed Description

template<class T>
class ULList< T >

A doubly-linked list.

Any type used as the template parameter T must have operators == and <.

Keep in mind the efficiency implications of the fact that ULList is a linked list. Notably, operator[] takes time proporation to the index you give it. (The length of the list is stored as an instance variable, however, so length() is a constant-time operation.)

Constructor & Destructor Documentation

template<class T >
ULList< T >::ULList ( )

Default constructor.

template<class T>
ULList< T >::ULList ( const ULList< T > &  list)

Copy constructor.

template<class T >
ULList< T >::~ULList ( )

Destructor.

Member Function Documentation

template<class T>
void ULList< T >::add ( const T &  data)

Appends a node containing the specified data to the end of this list only if the data is not yet in the list.

Parameters
[in]dataThe data to add.
template<class T>
void ULList< T >::append ( const T &  data)

Adds a node containing the specified data to the end of this list. (Synonym: push_back().)

Parameters
[in]dataThe data to be added to the list.
template<class T >
ULListIterator< T > ULList< T >::back ( )
Returns
an iterator pointing to the last node in this list. (Compare to ULList::end().)
template<class T >
ULListIterator< T > ULList< T >::begin ( )
Returns
an iterator pointing to the beginning of this list.
template<class T >
ULListConstIterator< T > ULList< T >::cback ( ) const
Returns
a const iterator pointing to the last node in this list. (Compare to ULList::end().)
template<class T >
ULListConstIterator< T > ULList< T >::cbegin ( ) const
Returns
a const iterator pointing to the beginning of this list.
template<class T >
ULListConstIterator< T > ULList< T >::cend ( ) const
Returns
a const iterator pointing to the end of this list. As with ULListIterator::isAtEnd(), the "end" refers not to the final node in this list, but to the position just beyond the final node. (Compare to ULList::cback().)
template<class T >
void ULList< T >::clear ( )

Makes this list an empty list, freeing any nodes that were in the list before clear() was called.

template<class T >
bool ULList< T >::empty ( ) const
Returns
true if this list has no nodes.
template<class T >
ULListIterator< T > ULList< T >::end ( )
Returns
an iterator pointing to the end of this list. As with ULListIterator::isAtEnd(), the "end" refers not to the final node in this list, but to the position just beyond the final node. (Compare to ULList::back().)
template<class T >
void ULList< T >::erase ( uluint32  n)

Erases the node at the specified index. Note that this operation takes time proportional to n.

Parameters
n]n The 0-based index of the node to be erased.
Precondition
n >= 0 and n < the length of this list.
template<class T>
void ULList< T >::erase ( ULListIterator< T > &  it)

Erases the node pointed to by the specified iterator.

Parameters
[in,out]itAn iterator pointing to the node to be erased. After the erasure, the iterator points to the node immediately following the erased node, or to the end of the list if the erased node was the last one in the list.
template<class T>
void ULList< T >::erase ( ULListIterator< T > &  start,
ULListIterator< T > &  stop 
)

Removes all the nodes starting at start, and ending just before stop. That is, the node pointed to by stop will remain in the list.

Parameters
[in]startThe first node to be erased. Note that the iterators start and stop will be rendered invalid by the erasure.
[in]stopThe node following the last node to be erased. If stop is pointing to the end of the list, then all nodes from stop through the end will be erased.
template<class T>
ULListConstIterator< T > ULList< T >::find ( const T &  data) const

Searches for the specified data in this list.

Returns
an iterator pointing to the first node in the list that contains the specified data.
template<class T >
T & ULList< T >::getAtIndex ( uluint32  n) const
Returns
a reference to the data stored in the node at the specified 0-based index.
Parameters
[in]nThe desired index.
Precondition
n >= 0 and n < the length of this list.
template<class T>
void ULList< T >::insert ( ULListIterator< T > &  it,
const T &  data 
)

Inserts a node containing the specified data into this list immediately before the node pointed to by the specified iterator.

Parameters
[in]itAn iterator pointing to the place to insert the new node.
[in]dataThe data to be inserted.
template<class T>
void ULList< T >::insert ( const T &  data)

Inserts the specified data in its proper location in this sorted list. If this list already has a node with this same data, no new node is added.

Parameters
[in]dataThe data to be inserted.
Precondition
This list is sorted in increasing order.
template<class T>
void ULList< T >::insertNode ( ULListIterator< T > &  it,
ULListNode< T > *  node 
)

Inserts a node into this list at the location of the specified iterator.

Parameters
[in,out]itAn iterator pointing to the node in front of which the new node is to be inserted. After the insertion, this iterator points to the new node.
[in]nodeA pointer to the node to be inserted. (Note that this list becomes responsible for the later deletion of this node.)
template<class T >
uluint32 ULList< T >::length ( ) const
Returns
the number of nodes in this list. (Synonym: size().)
template<class T>
void ULList< T >::mergeSort ( int(*)(T &, T &, void *)  func,
void *  context 
)

Sorts this list using the specified comparison function and mergesort (which runs in O(n log n) time).

Parameters
[in]funcThis funciton pointer takes two objects of type T and the context pointer and returns -1, 0, or 1 to indicate whether the first object is less than, equal to, or greater than the second object.
template<class T>
ULList< T > & ULList< T >::operator= ( const ULList< T > &  list)

Assignment operator. This operator deletes this list's existing nodes, builds a complete new copy of the specified list, and sets up this list to contain the new copy.

template<class T>
bool ULList< T >::operator== ( const ULList< T > &  other) const
Returns
true if this list and the other list contain identical data. Note that this is one of the methods that requires the type T to have an == operator.
template<class T >
T & ULList< T >::operator[] ( uluint32  n) const
Returns
a reference to the data stored in the node at the specified 0-based index.
Parameters
[in]nThe desired index.
Precondition
n >= 0 and n < the length of this list.
template<class T >
void ULList< T >::pop ( )

Removes the last node, if any, from this list.

template<class T>
void ULList< T >::prepend ( const T &  data)

Inserts a node containing the specified data at the front of this list. (Synonym: push_front().)

Parameters
[in]dataThe data to be inserted.
template<class T>
void ULList< T >::push_back ( const T &  data)

Adds a node containing the specified data to the end of this list. (Synonym: append().)

Parameters
[in]dataThe data to be added to the list.
template<class T>
void ULList< T >::push_front ( const T &  data)

Inserts a node containing the specified data at the front of this list. (Synonym: prepend().)

Parameters
[in]dataThe data to be inserted.
template<class T >
ULListNode< T > * ULList< T >::removeFrontNode ( )

Removes the front node from this list.

Returns
a pointer to the removed node. (Note that the caller becomes responsible for the later deletion of this node.)
template<class T>
ULListNode< T > * ULList< T >::removeNode ( ULListIterator< T > &  it)

Removes from this list the node pointed to by the specified iterator.

Returns
a pointer to the node that has been removed. The caller of removeNode becomes responsible for deleting the removed node.
Parameters
[in,out]itAn iterator pointing to the node to be removed. After the node is removed, the iterator points to the node that used to follow the removed node (or the end of the list, if the removed node was at the end of the list).
template<class T >
uluint32 ULList< T >::size ( ) const
Returns
the number of nodes in this list. (Synonym: length().)
template<class T>
void ULList< T >::sort ( int(*)(T &, T &, void *)  func,
void *  context 
)

Sorts this list using the specified comparison function and quicksort.

Parameters
[in]funcThis funciton pointer takes two objects of type T and the context pointer and returns -1, 0, or 1 to indicate whether the first object is less than, equal to, or greater than the second object.
template<class T>
void ULList< T >::splice ( ULList< T > &  tail)

Remove the nodes from the tail list and append them to the end of this list. This operation does not involve copying nodes, and thus runs in constant time.

Parameters
inout]tail The list to be spliced onto this list.
template<class T >
T & ULList< T >::top ( )
Returns
a reference to the data contained in the last node in this list.

Friends And Related Function Documentation

template<class T>
friend class ULListConstIterator< T >
friend
template<class T>
friend class ULListIterator< T >
friend
The documentation for this class was generated from the following file:
Generated on Sat Apr 13 2013 12:59:07 for ULAPI by   doxygen 1.8.2