A Doubly-Linked List Class. More...

#include <List.H>

Inheritance diagram for List< T >:

Public Member Functions
	List ()
	Construct an empty List<T>. More...

	List (bool usePool)

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

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

	~List ()
	The destructor. More...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

void	sort ()
	sort according to operator< (note: currently implemented with BubbleSort) More...

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 >

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

◆ List() [1/3]

template<class T >

List< T >::List ( )

inline

Construct an empty List<T>.

◆ List() [2/3]

template<class T >

List< T >::List ( bool usePool )

inline

◆ List() [3/3]

template<class T>

List< T >::List ( const List< T > & rhs )

The copy constructor.

◆ ~List()

template<class T >

List< T >::~List ( )

inline

The destructor.

Member Function Documentation

◆ operator=()

template<class T>

List< T > & List< T >::operator= ( const List< T > & rhs )

The assignment operator.

◆ prepend()

template<class T>

void List< T >::prepend ( const T & value )

inline

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

◆ append()

template<class T>

void List< T >::append ( const T & value )

inline

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

Referenced by List::add(), buildLocalIndexList(), List::join(), ListBox< T >::linearIn(), BinFab< T >::linearIn(), List::List(), and List::operator=().

◆ add()

template<class T>

void List< T >::add ( const T & value )

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

Referenced by ListBox< T >::addItems(), ListBox< T >::getInvalid(), ListBox< T >::getItems(), and readParticlesFromHDF().

◆ join()

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>.

Referenced by ListBox< T >::getItems().

◆ catenate()

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.

Referenced by ParticleData::fillGhosts(), ListBox< T >::getItemsDestructive(), and BinFab< T >::transfer().

◆ clear()

template<class T >

void List< T >::clear ( )

Removes all objects from the List<T>.

Referenced by ParticleData::clear(), BinFab< T >::linearIn(), BinFab< T >::linearOutDestructive(), List::operator=(), and List::~List().

◆ copy()

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.

◆ firstElement()

template<class T >

T & List< T >::firstElement ( ) const

inline

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

◆ lastElement()

template<class T >

T & List< T >::lastElement ( ) const

inline

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

◆ includes()

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.

◆ 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.

Referenced by List::operator!=().

◆ operator!=()

template<class T>

bool List< T >::operator!= ( const List< T > & rhs ) const

Returns true if the this and rhs are not equal.

◆ isEmpty()

template<class T >

bool List< T >::isEmpty ( ) const

inline

Returns true if the List<T> is empty.

Referenced by List::catenate(), ParticleData::isClosed(), List::isNotEmpty(), List::List(), and ParticleData::remapOutcast().

◆ isNotEmpty()

template<class T >

bool List< T >::isNotEmpty ( ) const

inline

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

Referenced by BinFab< T >::addItems(), ListBox< T >::addItems(), BinFab< T >::addItemsDestructive(), ListBox< T >::addItemsDestructive(), BlockBaseRegister< FArrayBox >::createDstBoxLayout(), BlockBaseRegister< FArrayBox >::createExchangeBoxLayout(), BlockBaseRegister< FArrayBox >::createSrcBoxLayout(), and BinFab< T >::reBin().

◆ length()

template<class T >

int List< T >::length ( ) const

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

Referenced by ListBox< T >::linearOut(), BinFab< T >::linearOut(), ListBox< T >::linearOutDestructive(), BinFab< T >::linearOutDestructive(), ParticleData::numOutcastLocal(), ParticleData::numParticlesLocal(), List::operator==(), and writeParticlesToHDF().

◆ removeFirst()

template<class T >

void List< T >::removeFirst ( )

inline

Removes the first element in the List<T>.

◆ removeLast()

template<class T >

void List< T >::removeLast ( )

inline

Removes the last element in the List<T>.

◆ operator[]() [1/2]

template<class T>

const T & List< T >::operator[] ( const ListIterator< T > & li ) const

inline

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

◆ operator[]() [2/2]

template<class T>

T & List< T >::operator[] ( const ListIterator< T > & li )

inline

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

◆ remove() [1/4]

template<class T>

void List< T >::remove ( const T & value )

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

Referenced by BlockBaseRegister< FArrayBox >::createDstBoxLayout(), BlockBaseRegister< FArrayBox >::createExchangeBoxLayout(), BlockBaseRegister< FArrayBox >::createSrcBoxLayout(), and BinFab< T >::reBin().

◆ remove() [2/4]

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 lst.

◆ remove() [3/4]

template<class T>

void List< T >::remove ( ListIterator< T > & lit )

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

◆ transfer()

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.

Referenced by ListBox< T >::addItemsDestructive(), collectValidParticles(), ListBox< T >::getInvalidDestructive(), ListBox< T >::getItemsDestructive(), and BinFab< T >::reBin().

◆ replace()

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.

◆ addAfter() [1/2]

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.

Referenced by List::addAfter(), and List::append().

◆ addBefore() [1/2]

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.

Referenced by List::addBefore(), and List::prepend().

◆ listIterator()

template<class T >

ListIterator< T > List< T >::listIterator ( ) const

inline

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

◆ first()

template<class T >

ListIterator< T > List< T >::first ( ) const

inline

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

Referenced by BlockBaseRegister< FArrayBox >::createDstBoxLayout(), BlockBaseRegister< FArrayBox >::createExchangeBoxLayout(), and BlockBaseRegister< FArrayBox >::createSrcBoxLayout().

◆ last()

template<class T >

ListIterator< T > List< T >::last ( ) const

inline

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

◆ sort()

template<class T >

void List< T >::sort ( )

sort according to operator< (note: currently implemented with BubbleSort)

◆ checkLinks()

template<class T >

void List< T >::checkLinks ( ) const

◆ remove() [4/4]

template<class T>

void List< T >::remove ( ListLink< T > * ln )

protected

A helper function for removing nodes.

◆ removeLink()

template<class T>

void List< T >::removeLink ( ListLink< T > * ln )

protected

Referenced by List::remove(), and List::transfer().

◆ addBefore() [2/2]

template<class T>

ListLink< T > * List< T >::addBefore	(	ListLink< T > *	ln,
		const T &	val
	)

protected

A helper function for adding nodes.

◆ addAfter() [2/2]

template<class T>

ListLink< T > * List< T >::addAfter	(	ListLink< T > *	ln,
		const T &	val
	)

protected

A helper function for adding nodes.

Friends And Related Function Documentation

◆ ListIterator< T >

template<class T>

friend class ListIterator< T >

friend

Our good and trusted friend.

Member Data Documentation

◆ head

template<class T>

ListLink<T>* List< T >::head

protected

The head of the list.

Referenced by List::addAfter(), List::addBefore(), List::catenate(), List::checkLinks(), List::clear(), List::first(), List::firstElement(), List::isEmpty(), List::List(), List::listIterator(), List::prepend(), List::removeFirst(), List::removeLink(), List::sort(), and List::transfer().

◆ tail

template<class T>

ListLink<T>* List< T >::tail

protected

The tail of the list.

Referenced by List::addAfter(), List::addBefore(), List::append(), List::catenate(), List::checkLinks(), List::clear(), List::isEmpty(), List::last(), List::lastElement(), List::List(), List::removeLast(), List::removeLink(), List::sort(), and List::transfer().

◆ linkPool

template<class T>

Pool List< T >::linkPool

staticprotected

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::addAfter(), List::addBefore(), List::clear(), and List::remove().

◆ m_usePool

template<class T>

bool List< T >::m_usePool

protected

Referenced by List::addAfter(), List::addBefore(), List::clear(), and List::remove().

The documentation for this class was generated from the following files:

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Friends

Detailed Description

template<class T> class List< T >

Constructor & Destructor Documentation

◆ List() [1/3]

◆ List() [2/3]

◆ List() [3/3]

◆ ~List()

Member Function Documentation

◆ operator=()

◆ prepend()

◆ append()

◆ add()

◆ join()

◆ catenate()

◆ clear()

◆ copy()

◆ firstElement()

◆ lastElement()

◆ includes()

◆ operator==()

◆ operator!=()

◆ isEmpty()

◆ isNotEmpty()

◆ length()

◆ removeFirst()

◆ removeLast()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ remove() [1/4]

◆ remove() [2/4]

◆ remove() [3/4]

◆ transfer()

◆ replace()

◆ addAfter() [1/2]

◆ addBefore() [1/2]

◆ listIterator()

◆ first()

◆ last()

◆ sort()

◆ checkLinks()

◆ remove() [4/4]

◆ removeLink()

◆ addBefore() [2/2]

◆ addAfter() [2/2]

Friends And Related Function Documentation

◆ ListIterator< T >

Member Data Documentation

◆ head

◆ tail

◆ linkPool

◆ m_usePool

template<class T>
class List< T >