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

List< T > Class Template Reference

A Doubly-Linked List Class. More...

#include <List.H>

Inheritance diagram for List< T >:

Inheritance graph
[legend]
Collaboration diagram for List< T >:

Collaboration graph
[legend]
List of all members.

Public Methods

 List ()
 Construct an empty List<T>.

 List (const List< T > &rhs)
 The copy constructor.

List< T > & operator= (const List< T > &rhs)
 The assignment operator.

 ~List ()
 The destructor.

void prepend (const T &value)
 Adds a copy of the value to the beginning of the List<T>.

void append (const T &value)
 Adds a copy of the value to the end of the List<T>.

void add (const T &value)
 Adds a copy of the value to the end of the List<T>.

void join (const List< T > &src)
 Appends a copy of all items in List<T> src to this List<T>.

void catenate (List< T > &src)
 Appends a copy of all items in List<T> src to this List<T>.

void clear ()
 Removes all objects from the List<T>.

List< T > * copy () const
 Returns a copy of this List<T> on the heap.

T & firstElement () const
 Returns a reference to the first element in the List<T>.

T & lastElement () const
 Returns a reference to the last element in the List<T>.

bool includes (const T &value) const
 Returns true if the List<T> contains an object identical to value.

bool operator== (const List< T > &rhs) const
 Returns true if the this and rhs are memberwise equal.

bool operator!= (const List< T > &rhs) const
 Returns true if the this and rhs are not equal.

bool isEmpty () const
 Returns true if the List<T> is empty.

bool isNotEmpty () const
 Returns true if the List<T> is not empty.

int length () const
 Returns the number of objects in the List<T>.

void removeFirst ()
 Removes the first element in the List<T>.

void removeLast ()
 Removes the last element in the List<T>.

const T & operator[] (const ListIterator< T > &li) const
 Returns reference to object pointed to by the ListIterator<T>.

T & operator[] (const ListIterator< T > &li)
 Returns reference to object pointed to by the ListIterator<T>.

void remove (const T &value)
 Removes all objects in the List<T> equal to value.

void remove (const List< T > &lst)
 Removes all objects in the List<T> equal to any of the values in \rm lst.

void remove (ListIterator< T > &lit)
 Removes the object pointed to by the ListIterator<T>.

void transfer (ListIterator< T > &lit)
 Transfer the object pointed to by lit from the List<T> lit is associated with to this one.

void replace (ListIterator< T > &li, const T &val)
 Replace the value pointed to by the ListIterator<T> by val.

void addAfter (ListIterator< T > &lit, const T &val)
 Insert val into List<T> after the object pointed to by lit.

void addBefore (ListIterator< T > &lit, const T &val)
 Insert val into List<T> before the object pointed to by lit.

ListIterator< T > listIterator () const
 Returns a ListIterator<T> to the first object in this List<T>.

ListIterator< T > first () const
 Returns a ListIterator<T> to the first object in this List<T>.

ListIterator< T > last () const
 Returns a ListIterator<T> to the last object in this List<T>.


Protected Methods

void remove (ListLink< T > *ln)
void removeLink (ListLink< T > *ln)
ListLink< T > * addBefore (ListLink< T > *ln, const T &val)
ListLink< T > * addAfter (ListLink< T > *ln, const T &val)

Protected Attributes

ListLink< T > * head
ListLink< T > * tail

Static Protected Attributes

Pool linkPool

Friends

class ListIterator< T >

Detailed Description

template<class T>
class List< T >

A Doubly-Linked List Class.

The List<T> class is a template class that implements a doubly-linked list of objects. A List<T> is a useful container class when the number of objects in the collection is not known ahead of time. A List<T> can contain an arbitrary number of elements; operations such as insertion, deletion, and catenation are easily implemented and inexpensive.

The only difficulty when defining a list class is devising a mechanism to access the elements. In an array, an element is accessed using an integer index. Since the elements in a List<T> are ordered by position, we could define an integer indexing operation that walks along the List<T> links from the beginning until the numbered element is found. Unfortunately, this would be very inefficient when accessing elements near the end of a long list. Another solution is to allow user access to the individual link objects that contain the element as well as the forward and backward pointers. This is not a satisfactory solution since it allows user access to the internal representation of the class. The solution chosen is to define a ListIterator<T> template class.

Think of a ListIterator<T> as a pointer to an object in the List<T>. You can access the element currently pointed to by the iterator, move the iterator forward and backward through the List<T>, and use it as a mechanism to define where elements should be inserted and deleted. If the iterator is moved off the end of the list it behaves as a null pointer.

This is a concrete class, not a polymorphic one.


Constructor & Destructor Documentation

template<class T>
List< T >::List   [inline]
 

Construct an empty List<T>.

template<class T>
List< T >::List const List< T > &    rhs
 

The copy constructor.

template<class T>
List< T >::~List   [inline]
 

The destructor.


Member Function Documentation

template<class T>
void List< T >::add const T &    value
 

Adds a copy of the value to the end of the List<T>.

template<class T>
ListLink< T > * List< T >::addAfter ListLink< T > *    ln,
const T &    val
[protected]
 

A helper function for adding nodes.

template<class T>
void List< T >::addAfter ListIterator< T > &    lit,
const T &    val
[inline]
 

Insert val into List<T> after the object pointed to by lit.

template<class T>
ListLink< T > * List< T >::addBefore ListLink< T > *    ln,
const T &    val
[protected]
 

A helper function for adding nodes.

template<class T>
void List< T >::addBefore ListIterator< T > &    lit,
const T &    val
[inline]
 

Insert val into List<T> before the object pointed to by lit.

template<class T>
void List< T >::append const T &    value [inline]
 

Adds a copy of the value to the end of the List<T>.

template<class T>
void List< T >::catenate List< T > &    src
 

Appends a copy of all items in List<T> src to this List<T>.

This differs from join() in that it unlinks the objects from the List<T> src and glues them to the end of this List<T>, leaving List<T> src empty. This is more efficient that join() if src is no longer needed.

template<class T>
void List< T >::clear  
 

Removes all objects from the List<T>.

template<class T>
List< T > * List< T >::copy   const [inline]
 

Returns a copy of this List<T> on the heap.

It is the user's responsibility to delete this when no longer needed.

template<class T>
ListIterator< T > List< T >::first   const [inline]
 

Returns a ListIterator<T> to the first object in this List<T>.

template<class T>
T & List< T >::firstElement   const [inline]
 

Returns a reference to the first element in the List<T>.

template<class T>
bool List< T >::includes const T &    value const
 

Returns true if the List<T> contains an object identical to value.

Type T must have an operator==() defined, or be an intrinsic type.

template<class T>
bool List< T >::isEmpty   const [inline]
 

Returns true if the List<T> is empty.

template<class T>
bool List< T >::isNotEmpty   const [inline]
 

Returns true if the List<T> is not empty.

template<class T>
void List< T >::join const List< T > &    src
 

Appends a copy of all items in List<T> src to this List<T>.

template<class T>
ListIterator< T > List< T >::last   const [inline]
 

Returns a ListIterator<T> to the last object in this List<T>.

template<class T>
T & List< T >::lastElement   const [inline]
 

Returns a reference to the last element in the List<T>.

template<class T>
int List< T >::length   const
 

Returns the number of objects in the List<T>.

template<class T>
ListIterator< T > List< T >::listIterator   const [inline]
 

Returns a ListIterator<T> to the first object in this List<T>.

template<class T>
bool List< T >::operator!= const List< T > &    rhs const
 

Returns true if the this and rhs are not equal.

template<class T>
List< T > & List< T >::operator= const List< T > &    rhs
 

The assignment operator.

template<class T>
bool List< T >::operator== const List< T > &    rhs const
 

Returns true if the this and rhs are memberwise equal.

Lists are memberwise equal if he two lists are the same size and each of the elements in the list compare equal. Type T must have an operator==() defined, or be an intrinsic type.

template<class T>
T & List< T >::operator[] const ListIterator< T > &    li [inline]
 

Returns reference to object pointed to by the ListIterator<T>.

template<class T>
const T & List< T >::operator[] const ListIterator< T > &    li const [inline]
 

Returns reference to object pointed to by the ListIterator<T>.

template<class T>
void List< T >::prepend const T &    value [inline]
 

Adds a copy of the value to the beginning of the List<T>.

template<class T>
void List< T >::remove ListLink< T > *    ln [protected]
 

A helper function for removing nodes.

template<class T>
void List< T >::remove ListIterator< T > &    lit
 

Removes the object pointed to by the ListIterator<T>.

template<class T>
void List< T >::remove const List< T > &    lst
 

Removes all objects in the List<T> equal to any of the values in \rm lst.

template<class T>
void List< T >::remove const T &    value
 

Removes all objects in the List<T> equal to value.

template<class T>
void List< T >::removeFirst   [inline]
 

Removes the first element in the List<T>.

template<class T>
void List< T >::removeLast   [inline]
 

Removes the last element in the List<T>.

template<class T>
void List< T >::removeLink ListLink< T > *    ln [protected]
 

template<class T>
void List< T >::replace ListIterator< T > &    li,
const T &    val
[inline]
 

Replace the value pointed to by the ListIterator<T> by val.

template<class T>
void List< T >::transfer ListIterator< T > &    lit
 

Transfer the object pointed to by lit from the List<T> lit is associated with to this one.


Friends And Related Function Documentation

template<class T>
friend class ListIterator< T > [friend]
 

Our good and trusted friend.


Member Data Documentation

template<class T>
ListLink<T>* List< T >::head [protected]
 

The head of the list.

template<class T>
Pool List< T >::linkPool [static, protected]
 

A new member that hopefully will make our List snappier. In particular when you have a large number of items, like in Particle code.

template<class T>
ListLink<T>* List< T >::tail [protected]
 

The tail of the list.


The documentation for this class was generated from the following files:
Generated on Wed Jan 19 17:56:14 2005 for Chombo&INSwithParticles by doxygen1.2.16