Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy > Class Template Reference

#include <Container.hpp>

List of all members.

---

Detailed Description

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>
class Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >

ChainedList class usage.

ChainedList class usage.

ChainedList is a template double chained list that allow high efficiency access and advantages of chained list.

In usual chained list, parsing the list is an O(N) operation In this list, parsing the list is an O(N/M) operation. The list chains allocated blocks of M pointers. When accessing the i-th element, not all (i-1) elements are accessed, but only (j)/M elements are accessed with j being the minimum distance from both ends.

(Example : For reach the 41st element in a usual list you have to cross the first 40 element. Here, if the array is 16 pointers wide, you will cross 2 array elements and 8 pointer elements, that is 10 operations, not 40)

While appending data is almost a free operation [O(1)], inserting/removing data in such list impose accessing O(N) elements in the worst case in order to preserve list integrity.

If insertion and removing are to be frequent compared to indexed access, then consider using Insert and Remove method instead of Add and Sub.

Insert and Remove both loose list integrity, so next indexed access will be O(j) again, but then the list will act like any standard chained list.

So, if you don't need to use these improvements, simply use the list in a usual way, via inserting and removing functions, it will act as an usual chained list.

Another improvement with this list are the adding functions. You could insert pointer to an element in the list, and they will be deleted when list is deleted (usual owning chained list), OR, you can insert a element in the list, and a copy of it will be insert in the list and deleted. No need to know if you should delete the object.

This list also provide very fast parsing system. If you want extremely fast access to the list call the ParseList method, that return the next pointer.

            // Create a int based chained list
            ChainedList<int>     myList0;

            // Create a int chained list, with 8 = 2^3 pointer wide blocks
            ChainedList<int, 3>  myList1;

            // Add an element to list
            myList0.Add(3); 
            // Or simply myList0.Add(new int(3));
            myList1 += 45; 

            // Access the i-th element
            cout << myList0[i]; 

            // Remove the i-th list element
            myList0.Sub(i); 
            myList0 -= 3; 

            // To insert an element before the i-th position
            myList0.Insert(7896, i);

            // To swap 2 elements, at i and j position
            myList0.Swap(i,j);

            // Change an element value, in the i-th position
            myList0.Change(456,i);

            // To parse the list, first time, beginning with i-th 
            // position
            int * a = myList0.Parse(i);
            // To parse the list, next time
            int * b = myList0.Parse();

            // To find the position of an inserted element
            int pos = myList0.Find(456);

Public Types
enum	{ ChainedEnd = -1, ChainedError = ChainedEnd, ChainedStart = 0, ChainedBS = 1<<pow2 }
	Define the constant that the list can return. More...
Public Member Functions
bool	Add (const ChainedList &, const unsigned int &=ChainedEnd)
	Insert a list to this list.
bool	Add (U *, const unsigned int &=ChainedEnd)
	Add a node to list.
	ChainedList ()
	Default constructor.
bool	Change (DefaultConstParamType, const unsigned int &)
	Allow mutating a node data at the given index.
bool	Free ()
	Delete the list.
unsigned int	getSize () const
	Get the current used node number.
unsigned int	indexOf (DefaultConstParamType)
	Find a node in the list If provided an operator == for U, then this method perform a O(N) search in the list.
bool	Insert (DefaultConstParamType, const unsigned int &=ChainedStart)
	Take care that Insert doesn't preserve list integrity.
unsigned int	lastIndexOf (DefaultConstParamType)
	Find the last matching node in the list If provided an operator == for U, then this method perform a O(N) search in the list.
bool	moveAppendedList (ChainedList &a)
	Move the list from a ChainedList into this one (the parameter's node are then nullified).
bool	moveList (ChainedList &a)
	Move the list from a ChainedList into this one (the parameter's node are then nullified).
ChainedList &	operator+= (const ChainedList &a)
	Append the given list to ours.
ChainedList &	operator+= (DefaultConstParamType a)
	Append the given element to the list end.
ChainedList &	operator-= (DefaultConstParamType a)
	Remove the given element if found.
SearchPolicy::Result	operator[] (const unsigned int &i)
	Operator [] return U type at i-th position.
U *	parseList (const bool &bInit=false) const
	Iterate the list When starting set bInit = true, the method returns the first node, then return each time the next node.
U *	parseListStart (const unsigned int &uiPos=ChainedEnd) const
	Iterate the list from a given position When started (uiPos != ChainedEnd) return the requested node, else return each time the next node.
bool	Remove (const unsigned int &=ChainedStart)
	Remove a node from the list, but in most of case, it doesn't preserve list integrity.
U *	reverseParseList (const bool &bInit=false) const
	Reverse iterate the list When started (ie when bInit = true) return the last node, then return each time the previous node.
U *	reverseParseListStart (const unsigned int &uiPos=ChainedEnd) const
	Reverse parse list from a given position When started (uiPos != ChainedEnd) return the requested node, else return each time the previous node.
bool	Sub (const unsigned int &=ChainedEnd)
	Subtract a node from list.
bool	Swap (const unsigned int &, const unsigned int &)
	Swap two nodes, preserve list integrity for the given indexes.
	~ChainedList ()
	Default destructor which destruct objects linked to list.

---

Member Enumeration Documentation

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>

anonymous enum

Define the constant that the list can return.

Enumerator:

ChainedEnd	This is used to add and or insert at end of list.
ChainedError	Whenever an indexed error occurs, this is the returned value.
ChainedStart	This is used to insert data in the head of the list.
ChainedBS	Process the asked pow once.

---

Constructor & Destructor Documentation

template<class U, unsigned int pow2, class SearchPolicy>

Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::ChainedList

(

)

Default constructor.

template<class U, unsigned int pow2, class SearchPolicy>

Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::~ChainedList

(

)

Default destructor which destruct objects linked to list.

---

Member Function Documentation

template<class U, unsigned int pow2, class SearchPolicy>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::Add	(	const ChainedList< U, pow2, SearchPolicy > &	,
		const unsigned int &	= ChainedEnd
	)

Insert a list to this list.

See also:

virtual bool Add(const U&, const unsigned int &)

Returns:

true on successful insertion

template<class U, unsigned int pow2, class SearchPolicy>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::Add	(	U *	,
		const unsigned int &	= ChainedEnd
	)

Add a node to list.

Warning:

Take care that add function preserve list integrity whereas Insert function doesn't in most of case. Even if Add function can insert node in list just before the given position, it is slower than a Insert function. So, in realtime application, prefer adding node in a preprocessing step, or using Insert function... (Inserting with Add is O(Number of node - position))

Returns:

true if insertion was successful

template<class U, unsigned int pow2, class SearchPolicy>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::Change	(	DefaultConstParamType	,
		const unsigned int &
	)

Allow mutating a node data at the given index.

Returns:

true on successful mutation

template<class U, unsigned int pow2, class SearchPolicy>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::Free

(

)

Delete the list.

Warning:

This function do delete nodes... (and data)

Returns:

true on successful deletion

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>

unsigned int Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::getSize

(

)

const [inline]

Get the current used node number.

template<class U, unsigned int pow2, class SearchPolicy>

unsigned int Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::indexOf

(

DefaultConstParamType

)

Find a node in the list If provided an operator == for U, then this method perform a O(N) search in the list.

Returns:

The node index if found or ChainedError if not

template<class U, unsigned int pow2, class SearchPolicy>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::Insert	(	DefaultConstParamType	,
		const unsigned int &	= ChainedStart
	)

Take care that Insert doesn't preserve list integrity.

See also:

Add function summary for details

Returns:

true if insertion was successful

template<class U, unsigned int pow2, class SearchPolicy>

unsigned int Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::lastIndexOf

(

DefaultConstParamType

)

Find the last matching node in the list If provided an operator == for U, then this method perform a O(N) search in the list.

Returns:

The node index if found or ChainedError if not

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::moveAppendedList

(

ChainedList< U, pow2, SearchPolicy > &

a

)

[inline]

Move the list from a ChainedList into this one (the parameter's node are then nullified).

Warning:

the current nodes is this list are inserted to the beginning of this list

Returns:

true on success, false on error

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::moveList

(

ChainedList< U, pow2, SearchPolicy > &

a

)

[inline]

Move the list from a ChainedList into this one (the parameter's node are then nullified).

Warning:

the operation will fail if the list is not empty (use transferList in that case)

Returns:

true on success, false on error or non empty list

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>

ChainedList& Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::operator+=

(

const ChainedList< U, pow2, SearchPolicy > &

a

)

[inline]

Append the given list to ours.

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>

ChainedList& Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::operator+=

(

DefaultConstParamType

a

)

[inline]

Append the given element to the list end.

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>

ChainedList& Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::operator-=

(

DefaultConstParamType

a

)

[inline]

Remove the given element if found.

template<class U, unsigned int pow2 = 4, class SearchPolicy = NotConstructiblePolicy::SearchPolicy<U>>

SearchPolicy::Result Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::operator[]

(

const unsigned int &

i

)

[inline]

Operator [] return U type at i-th position.

Parameters:

i

the indexed position to retrieve

Returns:

The returned type depends on the selected policy

template<class U, unsigned int pow2, class SearchPolicy>

U * Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::parseList

(

const bool &

bInit = false

)

const

Iterate the list When starting set bInit = true, the method returns the first node, then return each time the next node.

Warning:

No other list function should be used between each parse list call

Returns:

the first node's data pointer when bInit is true, or the next parsed one else

template<class U, unsigned int pow2, class SearchPolicy>

U * Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::parseListStart

(

const unsigned int &

uiPos = ChainedEnd

)

const

Iterate the list from a given position When started (uiPos != ChainedEnd) return the requested node, else return each time the next node.

See also:

ParseList

template<class U, unsigned int pow2, class SearchPolicy>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::Remove

(

const unsigned int &

= ChainedStart

)

Remove a node from the list, but in most of case, it doesn't preserve list integrity.

See also:

Sub method

Returns:

true if insertion was successful

template<class U, unsigned int pow2, class SearchPolicy>

U * Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::reverseParseList

(

const bool &

bInit = false

)

const

Reverse iterate the list When started (ie when bInit = true) return the last node, then return each time the previous node.

Warning:

No other list function should be used between each parse list call

Returns:

the last node's data pointer when bInit is true, or the previous parsed one else

template<class U, unsigned int pow2, class SearchPolicy>

U * Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::reverseParseListStart

(

const unsigned int &

uiPos = ChainedEnd

)

const

Reverse parse list from a given position When started (uiPos != ChainedEnd) return the requested node, else return each time the previous node.

See also:

ReverseParseList

template<class U, unsigned int pow2, class SearchPolicy>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::Sub

(

const unsigned int &

= ChainedEnd

)

Subtract a node from list.

Warning:

Please note, that Sub conserve list integrity, whereas Remove function does not. However, Sub is slower than Remove, because of list reconstruction... So, in realtime, prefer using remove (that is faster)

Returns:

true if removing was successful

template<class U, unsigned int pow2, class SearchPolicy>

bool Container::PrivateNotConstructibleImplementation::ChainedList< U, pow2, SearchPolicy >::Swap	(	const unsigned int &	,
		const unsigned int &
	)

Swap two nodes, preserve list integrity for the given indexes.

Returns:

true on successful swapping

---

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

• include/Containers/Container.hpp

(C) An X-Ryl669 project 2007

This document describes Unlimited Zooming Interface source code. UZI stands for Unlimited Zooming Interface, and source code license is