#include <List.H>
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.
Public Member Functions | |
| List () | |
| Construct an empty List<T>. | |
| List (bool usePool) | |
| 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 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>. | |
| void | sort () |
| sort according to operator< (note: currently implemented with BubbleSort) | |
| void | checkLinks () const |
Protected Member Functions | |
| 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 |
| bool | m_usePool |
Static Protected Attributes | |
| static Pool | linkPool |
Friends | |
| class | ListIterator< T > |
The copy constructor.
References List< T >::append(), List< T >::head, List< T >::isEmpty(), and List< T >::tail.
| void List< T >::prepend | ( | const T & | value | ) | [inline] |
Adds a copy of the value to the beginning of the List<T>.
References List< T >::addBefore(), and List< T >::head.
| void List< T >::append | ( | const T & | value | ) | [inline] |
Adds a copy of the value to the end of the List<T>.
References List< T >::addAfter(), and List< T >::tail.
Referenced by List< T >::add(), List< T >::join(), List< T >::List(), and List< T >::operator=().
| void List< T >::add | ( | const T & | value | ) | [inline] |
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.
References List< T >::head, List< T >::isEmpty(), and List< T >::tail.
| void List< T >::clear | ( | ) | [inline] |
Removes all objects from the List<T>.
References List< T >::head, List< T >::linkPool, List< T >::m_usePool, ListIterator< T >::p, Pool::returnPtr(), and List< T >::tail.
Referenced by List< T >::operator=(), and List< T >::~List().
Returns a copy of this List<T> on the heap.
It is the user's responsibility to delete this when no longer needed.
References MayDay::Error().
| T & List< T >::firstElement | ( | ) | const [inline] |
| T & List< T >::lastElement | ( | ) | const [inline] |
| bool List< T >::includes | ( | const T & | value | ) | const [inline] |
Returns true if the List<T> contains an object identical to value.
Type T must have an operator==() defined, or be an intrinsic type.
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.
References List< T >::length().
Referenced by List< T >::operator!=().
| bool List< T >::isEmpty | ( | ) | const [inline] |
Returns true if the List<T> is empty.
References List< T >::head, and List< T >::tail.
Referenced by List< T >::catenate(), List< T >::isNotEmpty(), and List< T >::List().
| bool List< T >::isNotEmpty | ( | ) | const [inline] |
| int List< T >::length | ( | ) | const [inline] |
| void List< T >::removeFirst | ( | ) | [inline] |
| void List< T >::removeLast | ( | ) | [inline] |
| const T & List< T >::operator[] | ( | const ListIterator< T > & | li | ) | const [inline] |
Returns reference to object pointed to by the ListIterator<T>.
References CH_assert, and ListIterator< T >::p.
| T & List< T >::operator[] | ( | const ListIterator< T > & | li | ) | [inline] |
Returns reference to object pointed to by the ListIterator<T>.
References CH_assert, and ListIterator< T >::p.
| void List< T >::remove | ( | const T & | value | ) | [inline] |
Removes all objects in the List<T> equal to value.
Removes all objects in the List<T> equal to any of the values in lst.
| void List< T >::remove | ( | ListIterator< T > & | lit | ) | [inline] |
| void List< T >::transfer | ( | ListIterator< T > & | lit | ) | [inline] |
Transfer the object pointed to by lit from the List<T> lit is associated with to this one.
References CH_assert, List< T >::head, ListIterator< T >::list, ListIterator< T >::p, List< T >::removeLink(), and List< T >::tail.
| void List< T >::replace | ( | ListIterator< T > & | li, | |
| const T & | val | |||
| ) | [inline] |
Replace the value pointed to by the ListIterator<T> by val.
References CH_assert, and ListIterator< T >::p.
| void List< T >::addAfter | ( | ListIterator< T > & | lit, | |
| const T & | val | |||
| ) | [inline] |
Insert val into List<T> after the object pointed to by lit.
References ListIterator< T >::p.
Referenced by List< T >::append().
| void List< T >::addBefore | ( | ListIterator< T > & | lit, | |
| const T & | val | |||
| ) | [inline] |
Insert val into List<T> before the object pointed to by lit.
References ListIterator< T >::p.
Referenced by List< T >::prepend().
| ListIterator< T > List< T >::listIterator | ( | ) | const [inline] |
| ListIterator< T > List< T >::first | ( | ) | const [inline] |
| ListIterator< T > List< T >::last | ( | ) | const [inline] |
| void List< T >::sort | ( | ) | [inline] |
sort according to operator< (note: currently implemented with BubbleSort)
References List< T >::head, ListIterator< T >::p, and List< T >::tail.
| void List< T >::checkLinks | ( | ) | const [inline] |
References MayDay::Abort(), List< T >::head, ListIterator< T >::p, and List< T >::tail.
| void List< T >::remove | ( | ListLink< T > * | ln | ) | [inline, protected] |
A helper function for removing nodes.
References List< T >::linkPool, List< T >::m_usePool, List< T >::removeLink(), and Pool::returnPtr().
| void List< T >::removeLink | ( | ListLink< T > * | ln | ) | [inline, protected] |
References CH_assert, List< T >::head, and List< T >::tail.
Referenced by List< T >::remove(), and List< T >::transfer().
| ListLink< T > * List< T >::addBefore | ( | ListLink< T > * | ln, | |
| const T & | val | |||
| ) | [inline, protected] |
A helper function for adding nodes.
References CH_assert, MayDay::Error(), Pool::getPtr(), List< T >::head, List< T >::linkPool, List< T >::m_usePool, and List< T >::tail.
| ListLink< T > * List< T >::addAfter | ( | ListLink< T > * | ln, | |
| const T & | val | |||
| ) | [inline, protected] |
A helper function for adding nodes.
References CH_assert, MayDay::Error(), Pool::getPtr(), List< T >::head, List< T >::linkPool, List< T >::m_usePool, and List< T >::tail.
friend class ListIterator< T > [friend] |
Our good and trusted friend.
The head of the list.
Referenced by List< T >::addAfter(), List< T >::addBefore(), List< T >::catenate(), List< T >::checkLinks(), List< T >::clear(), List< T >::first(), List< T >::firstElement(), List< T >::isEmpty(), List< T >::List(), List< T >::listIterator(), List< T >::prepend(), List< T >::removeFirst(), List< T >::removeLink(), List< T >::sort(), and List< T >::transfer().
The tail of the list.
Referenced by List< T >::addAfter(), List< T >::addBefore(), List< T >::append(), List< T >::catenate(), List< T >::checkLinks(), List< T >::clear(), List< T >::isEmpty(), List< T >::last(), List< T >::lastElement(), List< T >::List(), List< T >::removeLast(), List< T >::removeLink(), List< T >::sort(), and List< T >::transfer().
A new member that hopefully will make our List snappier. In particular when you have a large number of items, like in Particle code.
Referenced by List< T >::addAfter(), List< T >::addBefore(), List< T >::clear(), and List< T >::remove().
Referenced by List< T >::addAfter(), List< T >::addBefore(), List< T >::clear(), and List< T >::remove().
1.5.5