#include <DS_Multilist.h>
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__) |
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. | |
void | PushOpposite (const _DataType &d, const char *file=__FILE__, unsigned int line=__LINE__) |
Same as Push(), except FIFO and LIFO are reversed. Ordered list still inserts in order. | |
_DataType & | PopOpposite (const char *file=__FILE__, unsigned int line=__LINE__) |
Same as Pop() and Peek(), except FIFO and LIFO are reversed. | |
void | InsertAtIndex (const _DataType &d, _IndexType index, const char *file=__FILE__, unsigned int line=__LINE__) |
Stack,Queue: Inserts at index indicated, elements are shifted. Ordered list: Inserts, position is ignored. | |
void | RemoveAtIndex (_IndexType position, const char *file=__FILE__, unsigned int line=__LINE__) |
Unordered list, removes at index indicated, swaps last element with that element. Otherwise, array is shifted left to overwrite removed element. | |
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 |
Returns where in the list we should insert the item, to preserve list order. Returns -1 if the item is already in the list. | |
_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__) |
Empties the list, first calling RakNet::OP_Delete on all items. | |
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__) |
Reallocates the list to a larger size. If size is smaller than the value returned by GetSize(), the call does nothing. | |
void | Sort (bool force) |
Sorts the list unless it is an ordered list, in which it does nothing as the list is assumed to already be sorted. | |
void | TagSorted (void) |
Sets the list to be remembered as sorted. | |
void | SetSortOrder (bool ascending) |
Defaults to ascending. | |
bool | GetSortOrder (void) const |
Returns true if ascending. | |
bool | IsSorted (void) const |
Returns true if the list is currently believed to be in a sorted state. | |
MultilistType | GetMultilistType (void) const |
Returns what type of list this is. | |
void | SetMultilistType (MultilistType newType) |
Changes what type of list this is. | |
Static Public Member Functions | |
static void | FindIntersection (Multilist &source1, Multilist &source2, Multilist &intersection, Multilist &uniqueToSource1, Multilist &uniqueToSource2) |
Returns the intersection of two lists. Intersection is items common to both lists. | |
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 |
[in] | _MultilistType | What type of list this is, |
[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 |
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
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
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
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
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::SetMultilistType | ( | MultilistType | newType | ) | [inline] |
Changes what type of list this is.
[in] | mlType | Any value of the enum MultilistType, except ML_VARIABLE_DURING_RUNTIME |
void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::SetSortOrder | ( | bool | ascending | ) | [inline] |
Defaults to ascending.
Used by Sort(), and by ML_ORDERED_LIST
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
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
_IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::preallocationSize [protected] |
How many bytes the user chose to preallocate Won't automatically deallocate below this