DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType > Class Template Reference

#include <DS_Multilist.h>

List of all members.

Public Member Functions

void Push (const _DataType &d, const char *file=__FILE__, unsigned int line=__LINE__)
_DataType & Pop (const char *file=__FILE__, unsigned int line=__LINE__)
void PushOpposite (const _DataType &d, const char *file=__FILE__, unsigned int line=__LINE__)
_DataType & PopOpposite (const char *file=__FILE__, unsigned int line=__LINE__)
 Same as Pop() and Peek(), except FIFO and LIFO are reversed.
void RemoveAtIndex (_IndexType position, const char *file=__FILE__, unsigned int line=__LINE__)
bool RemoveAtKey (_KeyType key, bool assertIfDoesNotExist, const char *file=__FILE__, unsigned int line=__LINE__)
 Find the index of key, and remove at that index.
_IndexType GetIndexOf (_KeyType key) const
 Finds the index of key. Return -1 if the key is not found.
_IndexType GetInsertionIndex (_KeyType key) const
_DataType GetPtr (_KeyType key) const
 Finds the index of key. Return 0 if the key is not found. Useful if _DataType is always non-zero pointers.
void ForEach (void(*func)(_DataType &item, const char *file, unsigned int line), const char *file, unsigned int line)
 Iterate over the list, calling the function pointer on each element.
bool IsEmpty (void) const
 Returns if the list is empty.
_IndexType GetSize (void) const
 Returns the number of elements used in the list.
void Clear (bool deallocateSmallBlocks=true, const char *file=__FILE__, unsigned int line=__LINE__)
 Empties the list. The list is not deallocated if it is small, unless deallocateSmallBlocks is true.
void ClearPointers (bool deallocateSmallBlocks=true, const char *file=__FILE__, unsigned int line=__LINE__)
void ClearPointer (_KeyType key, const char *file=__FILE__, unsigned int line=__LINE__)
 Empty one item from the list, first calling RakNet::OP_Delete on that item.
void ReverseList (void)
 Reverses the elements in the list, and flips the sort order returned by GetSortOrder() if IsSorted() returns true at the time the function is called.
void Reallocate (_IndexType size, const char *file=__FILE__, unsigned int line=__LINE__)
void Sort (bool force)
void TagSorted (void)
void SetSortOrder (bool ascending)
bool GetSortOrder (void) const
 Returns true if ascending.
bool IsSorted (void) const
MultilistType GetMultilistType (void) const
 Returns what type of list this is.
void SetMultilistType (MultilistType newType)

Static Public Member Functions

static void FindIntersection (Multilist &source1, Multilist &source2, Multilist &intersection, Multilist &uniqueToSource1, Multilist &uniqueToSource2)

Protected Attributes

_DataType * data
 An array of user values.
_IndexType dataSize
 Number of elements in the list.
_IndexType allocationSize
 Size of array.
_IndexType queueHead
 Array index for the head of the queue.
_IndexType queueTail
 Array index for the tail of the queue.
_IndexType preallocationSize


Detailed Description

template<const MultilistType _MultilistType, class _DataType, class _KeyType = _DataType, class _IndexType = DefaultIndexType>
class DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >

The multilist, representing an abstract data type that generally holds lists
Parameters:
[in] _MultilistType What type of list this is,
See also:
MultilistType
Parameters:
[in] _DataType What type of data this list holds.
[in] _KeyType If a function takes a key to sort on, what type of key this is. The comparison operator between _DataType and _KeyType must be defined
[in] _IndexType What variable type to use for indices

Member Function Documentation

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ClearPointers ( bool  deallocateSmallBlocks = true,
const char *  file = __FILE__,
unsigned int  line = __LINE__ 
) [inline]

Empties the list, first calling RakNet::OP_Delete on all items. The list is not deallocated if it is small, unless deallocateSmallBlocks is true

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::FindIntersection ( Multilist< _MultilistType, _DataType, _KeyType, _IndexType > &  source1,
Multilist< _MultilistType, _DataType, _KeyType, _IndexType > &  source2,
Multilist< _MultilistType, _DataType, _KeyType, _IndexType > &  intersection,
Multilist< _MultilistType, _DataType, _KeyType, _IndexType > &  uniqueToSource1,
Multilist< _MultilistType, _DataType, _KeyType, _IndexType > &  uniqueToSource2 
) [inline, static]

Returns the intersection of two lists Intersection is items common to both lists

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
_IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetInsertionIndex ( _KeyType  key  )  const [inline]

Returns where in the list we should insert the item, to preserve list order Returns -1 if the item is already in the list

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
bool DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::IsSorted ( void   )  const [inline]

Returns true if the list is currently believed to be in a sorted state Doesn't actually check for sortedness, just if Sort() was recently called, or MultilistType is ML_ORDERED_LIST

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
_DataType & DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Pop ( const char *  file = __FILE__,
unsigned int  line = __LINE__ 
) [inline]

Gets or removes and gets an element from the list, according to the same rules as Push() Ordered list is LIFO for the purposes of Pop and Peek

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Push ( const _DataType &  d,
const char *  file = __FILE__,
unsigned int  line = __LINE__ 
) [inline]

Unordered list, stack is LIFO QUEUE is FIFO Ordered list is inserted in order

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::PushOpposite ( const _DataType &  d,
const char *  file = __FILE__,
unsigned int  line = __LINE__ 
) [inline]

Same as Push(), except FIFO and LIFO are reversed Ordered list still inserts in order

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Reallocate ( _IndexType  size,
const char *  file = __FILE__,
unsigned int  line = __LINE__ 
) [inline]

Reallocates the list to a larger size. If size is smaller than the value returned by GetSize(), the call does nothing.

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::RemoveAtIndex ( _IndexType  position,
const char *  file = __FILE__,
unsigned int  line = __LINE__ 
) [inline]

Unordered list, removes at index indicated, swaps last element with that element Otherwise, array is shifted left to overwrite removed element Index[0] returns the same as Pop() for a queue. Same as PopOpposite() for the list and ordered list

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::SetMultilistType ( MultilistType  newType  )  [inline]

Changes what type of list this is

Precondition:
Template must be defined with ML_VARIABLE_DURING_RUNTIME for this to do anything
Parameters:
[in] mlType Any value of the enum MultilistType, except ML_VARIABLE_DURING_RUNTIME

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::SetSortOrder ( bool  ascending  )  [inline]

Defaults to ascending. Used by Sort(), and by ML_ORDERED_LIST

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Sort ( bool  force  )  [inline]

Sorts the list unless it is an ordered list, in which it does nothing as the list is assumed to already be sorted. However, if force is true, it will also resort the ordered list, useful if the comparison operator between _KeyType and _DataType would now return different results Once the list is sorted, further operations to lookup by key will be log2(n) until the list is modified

template<const MultilistType _MultilistType, class _DataType , class _KeyType , class _IndexType >
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::TagSorted ( void   )  [inline]

Sets the list to be remembered as sorted. Optimization if the source is sorted already


Member Data Documentation

template<const MultilistType _MultilistType, class _DataType , class _KeyType = _DataType, class _IndexType = DefaultIndexType>
_IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::preallocationSize [protected]

How many bytes the user chose to preallocate Won't automatically deallocate below this


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

Generated on Thu Apr 30 08:06:51 2009 for RakNet by  doxygen 1.5.7.1