Free Electron
Classes | Public Member Functions | Private Member Functions | List of all members
fe::List< T > Class Template Reference

Fully Bidirectional Doubly-Linked List. More...

#include <List.h>

Inheritance diagram for fe::List< T >:
Inheritance graph
[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...
 
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...
 
toHead (Context &rContext) const
 Rewind the context to the beginning of the list and return the first element. More...
 
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...
 
postIncrement (Context &rContext) const
 Return the current element before incrementing to the next. More...
 
postDecrement (Context &rContext) const
 Return the current element before decrementing to the previous. More...
 
head (void) const
 Return the first element of the list (no context required) More...
 
tail (void) const
 Return the last element of the list (no context required) More...
 
current (Context &rContext) const
 Return the current element of the context. More...
 
preIncrement (Context &rContext) const
 Increment the context and return the next element. More...
 
preDecrement (Context &rContext) const
 Decrement the context and return the previous element. More...
 
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?

What is a Context?

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:

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 ( 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 ( 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,
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,
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 ( 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 ( 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 ( 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,
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: