Fully Bidirectional Doubly-Linked List. More...

#include <List.h>

Inheritance diagram for fe::List< T >:

[legend]

Classes
class	Iterator
	Type-specific Iterator for an fe::List <> More...

Public Member Functions
T *	insertBefore (Context &rContext, T pEntry)
	Insert a new element before the context. More...

T *	insertAfter (Context &rContext, T pEntry)
	Insert a new element after the context. More...

T *	prepend (T pEntry)
	Insert a new element at the beginning of the list. More...

T *	append (T pEntry)
	Insert a new element at the end of the list. More...

void	append (List< T > &list)
	Append a copy of an entire list of identical type. More...

BWORD	remove (T pEntry)
	This is the straightforward remove implementation. More...

BWORD	remove (T pEntry, Context &hint)
	This remove() method uses a hint Context to check current, next, and prev nodes (in that order) before reverting to a head to tail scan. More...

BWORD	removeCurrent (Context &rContext)
	Remove the current node on the given context. More...

T	replaceCurrent (Context &rContext, T pSubstitute)
	Replace the current pointer on the given context. More...

void	deleteAll (void)
	Remove all nodes and delete their pointers. More...

BWORD	deleteCurrent (Context &rContext)
	Remove and delete the current node on the given context. More...

BWORD	deleteElement (T pEntry)
	Remove and delete the first entry that matches the argument. More...

T	toHead (Context &rContext) const
	Rewind the context to the beginning of the list and return the first element. More...

T	toTail (Context &rContext) const
	Move the context to the end of the list and return the last element. More...

T *	searchForElement (Context &rContext, const T pEntry) const
	Return the location of the first element matching the given pointer or smart pointer. More...

T *	searchForContent (Context &rContext, const T pValue) const
	Return the location of the first pointed-to element with the same value. More...

T	postIncrement (Context &rContext) const
	Return the current element before incrementing to the next. More...

T	postDecrement (Context &rContext) const
	Return the current element before decrementing to the previous. More...

T	head (void) const
	Return the first element of the list (no context required) More...

T	tail (void) const
	Return the last element of the list (no context required) More...

T	current (Context &rContext) const
	Return the current element of the context. More...

T	preIncrement (Context &rContext) const
	Increment the context and return the next element. More...

T	preDecrement (Context &rContext) const
	Decrement the context and return the previous element. More...

T	operator[] (I32 index) const
	Get an element by index. More...

Public Member Functions inherited from fe::ListCore
void	setAutoDestruct (BWORD set)
	Set the AutoDestruct flag. More...

BWORD	autoDestruct (void)
	Get the AutoDestruct flag. More...

U32	size (void) const
	Returns the number of elements on the list. More...

void	removeAll (void)
	Remove and delete nodes, but don't delete contents. More...

BWORD	moveNodeBefore (Context &from, Context &to)
	Moves the node at the first context before the node at the second context. More...

BWORD	moveNodeAfter (Context &from, Context &to)
	Moves the node at the first context after the node at the second context. More...

BWORD	isAtHeadNull (Context &rContext) const
	Returns TRUE if the context is before the first element. More...

BWORD	isAtTailNull (Context &rContext) const
	Returns TRUE if the context is after the last element. More...

Private Member Functions
virtual NodeCore *	newNode (void) const

Additional Inherited Members
Protected Member Functions inherited from fe::ListCore
NodeCore *	coreGetElement (I32 index) const

NodeCore *	coreInsert (BWORD before, Context &rContext, NodeCore *existingNode)

BWORD	coreRemoveNode (NodeCore *node)

BWORD	coreMoveNode (BWORD before, Context &from, Context &to)

void	internalToHead (Context &rContext) const

void	internalPostIncrement (Context &rContext) const

void	internalDetachNode (NodeCore *node)

NodeCore *	internalGetCurrent (Context &rContext) const

Protected Attributes inherited from fe::ListCore
NodeCore *	m_pHead

NodeCore *	m_pTail

I32	m_length

BWORD	m_autodestruct

Detailed Description

template<typename T>
class fe::List< T >

Fully Bidirectional Doubly-Linked List.

Why would you use this list?

Truly bidirectional: no need for reverse lists or reverse iterators
Retainable iterators: designed to endure long term access
Complete iterators: you don't have to go back to the list for any subset of the functionality. The iterators can do everything.
Delete anything you want, whenever you want: you can erase nodes that other contexts are looking at or even a list itself with still outstanding contexts. Cascading references will adapt on next usage as though the other contexts were watching along with every step (but they aren't).

What is a Context?

A Context is basically the typeless state of an Iterator. But really, the Iterator is a Context permanently associated with a specific instance of a typed List.
You can manipulate a List through Context's, Iterator's, or directly through the List itself.
Context's can be reused between multiple Lists of different types, but Iterator's don't require you to keep track of which List you're looking into.

Since the List is fully bidirectional, there is a NULL entry at both beginning and the end. The toHead and toTail methods move to the first entry next to the NULL on either end (if a non-NULL entry exists).

If SearchForContent() is to be used and type T has non-trivial data complexity, the operator == should probably be defined for type T. Some examples of data complexity are:

pointer data members
data members that do not contribute to 'equality'
data whose equality can be more efficiently determined with something other than the default bytewise comparison.
fuzzy or soft data

A new Context defaults to pointing at the NULL at the start of the list. A new Iterator defaults to pointing at the head of the list.

Example using a fe::List::Iterator:

List<MyClass*> list;
List<MyClass*>::Iterator iterator(list);
MyClass* one=new MyClass();
// add element
list.append(one);
// read element
MyClass* two= *iterator;
// do something to all elements
MyClass* node;
iterator.toHead();
while((node= *iterator++)!=NULL)
{
    node->doSomething();
}

Example using a fe::ListCore::Context:

List<MyClass*> list;
ListCore::Context context;
MyClass* one=new MyClass();
// add element
list.append(one);
// read element
MyClass* two=list.current(context);
// do something to all elements
MyClass* node;
list.toHead(context);
while( (node=list.postIncrement(context)) != NULL)
{
    node->doSomething();
}

No Context's or Iterator's will lose place if elements are removed, even if removed with a different Context or Iterator. Reference counting prevents invalid pointers and heir chains follow destruction chains to find valid nodes.

Note that much of the functionality of this class is implemented in the non-template class ListCore. This is done to reduce template instantiation size.

By using setAutoDestruct(true), all elements remaining on the list are deleted when the list is destructed.

WARNING: if pointer-to elements were not created with new(), failures during auto-delete will probably occur. Note that setAutoDestruct(true) is especially precarious when elements may be in more than one list. In that case, it is very possible for elements to be deleted that are still members of other lists.

NOTE: Modern mechanisms are in place that attempt to do the right delete operation for a variety of types. See fe::deleteByType<> for details.

Member Function Documentation

◆ append() [1/2]

template<typename T>

T* fe::List< T >::append ( T pEntry )

inline

Insert a new element at the end of the list.

Returns the location of the new element or NULL if the internal node allocation failed.

◆ append() [2/2]

template<typename T>

void fe::List< T >::append ( List< T > & list )

inline

Append a copy of an entire list of identical type.

◆ current()

template<typename T>

T fe::List< T >::current ( Context & rContext ) const

inline

Return the current element of the context.

◆ deleteAll()

template<typename T>

void fe::List< T >::deleteAll ( void )

inline

Remove all nodes and delete their pointers.

◆ deleteCurrent()

template<typename T>

BWORD fe::List< T >::deleteCurrent ( Context & rContext )

inline

Remove and delete the current node on the given context.

◆ deleteElement()

template<typename T>

BWORD fe::List< T >::deleteElement ( T pEntry )

inline

Remove and delete the first entry that matches the argument.

If a match is not found, the argument is still deleted.

◆ head()

template<typename T>

T fe::List< T >::head ( void ) const

inline

Return the first element of the list (no context required)

◆ insertAfter()

template<typename T>

T* fe::List< T >::insertAfter	(	Context &	rContext,
		T	pEntry
	)

inline

Insert a new element after the context.

Returns the location of the new element or NULL if the internal node allocation failed.

◆ insertBefore()

template<typename T>

T* fe::List< T >::insertBefore	(	Context &	rContext,
		T	pEntry
	)

inline

Insert a new element before the context.

Returns the location of the new element or NULL if the internal node allocation failed.

◆ operator[]()

template<typename T>

T fe::List< T >::operator[] ( I32 index ) const

inline

Get an element by index.

This is not an array, so this can be an inefficient operation

◆ postDecrement()

template<typename T>

T fe::List< T >::postDecrement ( Context & rContext ) const

inline

Return the current element before decrementing to the previous.

◆ postIncrement()

template<typename T>

T fe::List< T >::postIncrement ( Context & rContext ) const

inline

Return the current element before incrementing to the next.

Referenced by fe::List< fe::sp< fe::Component > >::append().

◆ preDecrement()

template<typename T>

T fe::List< T >::preDecrement ( Context & rContext ) const

inline

Decrement the context and return the previous element.

◆ preIncrement()

template<typename T>

T fe::List< T >::preIncrement ( Context & rContext ) const

inline

Increment the context and return the next element.

◆ prepend()

template<typename T>

T* fe::List< T >::prepend ( T pEntry )

inline

Insert a new element at the beginning of the list.

Returns the location of the new element or NULL if the internal node allocation failed.

◆ remove() [1/2]

template<typename T>

BWORD fe::List< T >::remove ( T pEntry )

inline

This is the straightforward remove implementation.

This Remove() will look for the entry in the list by simply checking each member entry in order. This can be very slow in some cases. See remove(T entry, Context& hint) for a faster alternative.

◆ remove() [2/2]

template<typename T>

BWORD fe::List< T >::remove	(	T	pEntry,
		Context &	hint
	)

inline

This remove() method uses a hint Context to check current, next, and prev nodes (in that order) before reverting to a head to tail scan.

In most cases this significantly reduces execution time.

◆ removeCurrent()

template<typename T>

BWORD fe::List< T >::removeCurrent ( Context & rContext )

inline

Remove the current node on the given context.

◆ replaceCurrent()

template<typename T>

T fe::List< T >::replaceCurrent	(	Context &	rContext,
		T	pSubstitute
	)

inline

Replace the current pointer on the given context.

◆ searchForContent()

template<typename T>

T* fe::List< T >::searchForContent	(	Context &	rContext,
		const T	pValue
	)		const

inline

Return the location of the first pointed-to element with the same value.

The elements are compared to the contents of *value. The value argument is passed by pointer instead of value or reference to prevent a requirement the T be an instantiable class.

◆ searchForElement()

template<typename T>

T* fe::List< T >::searchForElement	(	Context &	rContext,
		const T	pEntry
	)		const

inline

Return the location of the first element matching the given pointer or smart pointer.

Only the pointers are compared. Matches are not made by the content they point to.

◆ tail()

template<typename T>

T fe::List< T >::tail ( void ) const

inline

Return the last element of the list (no context required)

◆ toHead()

template<typename T>

T fe::List< T >::toHead ( Context & rContext ) const

inline

Rewind the context to the beginning of the list and return the first element.

Referenced by fe::List< fe::sp< fe::Component > >::append(), and fe::Profiler::report().

◆ toTail()

template<typename T>

T fe::List< T >::toTail ( Context & rContext ) const

inline

Move the context to the end of the list and return the last element.

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

List.h

Classes

Public Member Functions

Private Member Functions

Additional Inherited Members

Detailed Description

template<typename T> class fe::List< T >

Member Function Documentation

◆ append() [1/2]

◆ append() [2/2]

◆ current()

◆ deleteAll()

◆ deleteCurrent()

◆ deleteElement()

◆ head()

◆ insertAfter()

◆ insertBefore()

◆ operator[]()

◆ postDecrement()

◆ postIncrement()

◆ preDecrement()

◆ preIncrement()

◆ prepend()

◆ remove() [1/2]

◆ remove() [2/2]

◆ removeCurrent()

◆ replaceCurrent()

◆ searchForContent()

◆ searchForElement()

◆ tail()

◆ toHead()

◆ toTail()

template<typename T>
class fe::List< T >