 |
Shadowrun: Awakened 29 September 2011 - Build 871
|
|
Shadowrun: Awakened 29 September 2011 - Build 871
|
The multilist, representing an abstract data type that generally holds lists. More...
#include <DS_Multilist.h>
Inheritance diagram for DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >:Public Member Functions | |
| 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 | 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 | ClearPointers (bool deallocateSmallBlocks=true, const char *file=__FILE__, unsigned int line=__LINE__) |
| Empties the list, first calling RakNet::OP_Delete on all items. | |
| void | ForEach (void(*func)(_DataType &item)) |
| 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. | |
| _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. | |
| MultilistType | GetMultilistType (void) const |
| Returns what type of list this is. | |
| _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. | |
| _IndexType | GetSize (void) const |
| Returns the number of elements used in the list. | |
| bool | GetSortOrder (void) const |
| Returns true if ascending. | |
| 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. | |
| bool | IsEmpty (void) const |
| Returns if the list is empty. | |
| bool | IsSorted (void) const |
| Returns true if the list is currently believed to be in a sorted state. | |
| Multilist () | |
| Multilist (const Multilist &source) | |
| Multilist & | operator= (const Multilist &source) |
| _DataType & | operator[] (const _IndexType position) const |
| _DataType & | Peek (void) const |
| _DataType & | PeekOpposite (void) const |
| _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. | |
| _DataType & | PopOpposite (const char *file=__FILE__, unsigned int line=__LINE__) |
| Same as Pop() and Peek(), except FIFO and LIFO are reversed. | |
| void | Push (const _DataType &d, const char *file=__FILE__, unsigned int line=__LINE__) |
| void | Push (const _DataType &d, const _KeyType &key, const char *file=__FILE__, unsigned int line=__LINE__) |
| 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. | |
| void | PushOpposite (const _DataType &d, const _KeyType &key, const char *file=__FILE__, unsigned int line=__LINE__) |
| 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 | 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. | |
| 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 | SetMultilistType (MultilistType newType) |
| Changes what type of list this is. | |
| void | SetSortOrder (bool ascending) |
| Defaults to ascending. | |
| 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. | |
| ~Multilist () | |
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 Types | |
| enum | { ML_UNSORTED, ML_SORTED_ASCENDING, ML_SORTED_DESCENDING } |
Protected Member Functions | |
| void | CopySource (const Multilist &source) |
| void | DeallocateIfNeeded (const char *file, unsigned int line) |
| void | DeleteShiftArrayLeft (_IndexType index) |
| _IndexType | GetIndexFromKeyInSortedList (const _KeyType &key, bool *objectExists) const |
| void | InsertInOrderedList (const _DataType &d, const _KeyType &key) |
| void | InsertShiftArrayRight (const _DataType &d, _IndexType index) |
| void | QSortAscending (_IndexType left, _IndexType right) |
| void | QSortDescending (_IndexType left, _IndexType right) |
| void | ReallocateIfNeeded (const char *file, unsigned int line) |
| void | ReallocToSize (_IndexType newAllocationSize, const char *file, unsigned int line) |
| void | ReverseListInternal (void) |
Protected Attributes | |
| _IndexType | allocationSize |
| Size of array. | |
| bool | ascendingSort |
| _DataType * | data |
| An array of user values. | |
| _IndexType | dataSize |
| Number of elements in the list. | |
| _IndexType | preallocationSize |
| _IndexType | queueHead |
| Array index for the head of the queue. | |
| _IndexType | queueTail |
| Array index for the tail of the queue. | |
| enum DataStructures::Multilist:: { ... } | sortState |
| MultilistType | variableMultilistType |
| [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 |
Definition at line 91 of file DS_Multilist.h.
anonymous enum [protected] |
Definition at line 241 of file DS_Multilist.h.
| DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Multilist | ( | ) |
Definition at line 255 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_UNORDERED_LIST, and ML_VARIABLE_DURING_RUNTIME.
{
data=0;
dataSize=0;
allocationSize=0;
ascendingSort=true;
sortState=ML_UNSORTED;
queueHead=0;
queueTail=0;
preallocationSize=0;
if (_MultilistType==ML_ORDERED_LIST)
sortState=ML_SORTED_ASCENDING;
else
sortState=ML_UNSORTED;
if (_MultilistType==ML_VARIABLE_DURING_RUNTIME)
variableMultilistType=ML_UNORDERED_LIST;
}
| DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::~Multilist | ( | ) |
Definition at line 276 of file DS_Multilist.h.
References _FILE_AND_LINE_, and RakNet::OP_DELETE_ARRAY().
{
if (data!=0)
RakNet::OP_DELETE_ARRAY(data, _FILE_AND_LINE_);
}
| DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Multilist | ( | const Multilist< _MultilistType, _DataType, _KeyType, _IndexType > & | source | ) |
Definition at line 283 of file DS_Multilist.h.
{
CopySource(source);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Clear | ( | bool | deallocateSmallBlocks = true, |
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 773 of file DS_Multilist.h.
References ML_ORDERED_LIST, and RakNet::OP_DELETE_ARRAY().
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::FindIntersection().
{
dataSize=0;
if (GetMultilistType()==ML_ORDERED_LIST)
if (ascendingSort)
sortState=ML_SORTED_ASCENDING;
else
sortState=ML_SORTED_DESCENDING;
else
sortState=ML_UNSORTED;
queueHead=0;
queueTail=0;
if (deallocateSmallBlocks && allocationSize < 128 && data)
{
RakNet::OP_DELETE_ARRAY(data,file,line);
data=0;
allocationSize=0;
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ClearPointer | ( | _KeyType | key, |
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 804 of file DS_Multilist.h.
References RakNet::OP_DELETE().
{
_IndexType i;
i = GetIndexOf(key);
if (i!=-1)
{
RakNet::OP_DELETE(operator[](i), file, line);
RemoveAtIndex(i);
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ClearPointers | ( | bool | deallocateSmallBlocks = true, |
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
The list is not deallocated if it is small, unless deallocateSmallBlocks is true
Definition at line 795 of file DS_Multilist.h.
References RakNet::OP_DELETE().
{
_IndexType i;
for (i=0; i < dataSize; i++)
RakNet::OP_DELETE(operator[](i), file, line);
Clear(deallocateSmallBlocks, file, line);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::CopySource | ( | const Multilist< _MultilistType, _DataType, _KeyType, _IndexType > & | source | ) | [protected] |
Definition at line 297 of file DS_Multilist.h.
References _FILE_AND_LINE_, DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ascendingSort, DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::data, DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetSize(), DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::preallocationSize, DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::sortState, and DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::variableMultilistType.
{
dataSize=source.GetSize();
ascendingSort=source.ascendingSort;
sortState=source.sortState;
queueHead=0;
queueTail=dataSize;
preallocationSize=source.preallocationSize;
variableMultilistType=source.variableMultilistType;
if (source.data==0)
{
data=0;
allocationSize=0;
}
else
{
allocationSize=dataSize;
data = RakNet::OP_NEW_ARRAY<_DataType>(dataSize,_FILE_AND_LINE_);
_IndexType i;
for (i=0; i < dataSize; i++)
data[i]=source[i];
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::DeallocateIfNeeded | ( | const char * | file, |
| unsigned int | line | ||
| ) | [protected] |
Definition at line 1158 of file DS_Multilist.h.
{
if (allocationSize<512)
return;
if (dataSize >= allocationSize/3 )
return;
if (dataSize <= preallocationSize )
return;
_IndexType newAllocationSize = dataSize<<1; // * 2
ReallocToSize(newAllocationSize,file,line);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::DeleteShiftArrayLeft | ( | _IndexType | index | ) | [protected] |
| 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 | ||
| ) | [static] |
Definition at line 1088 of file DS_Multilist.h.
References _FILE_AND_LINE_, DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Clear(), DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetSize(), DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Push(), DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::SetSortOrder(), and DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Sort().
{
_IndexType index1=0, index2=0;
source1.SetSortOrder(true);
source2.SetSortOrder(true);
source1.Sort(false);
source2.Sort(false);
intersection.Clear(true,_FILE_AND_LINE_);
uniqueToSource1.Clear(true,_FILE_AND_LINE_);
uniqueToSource2.Clear(true,_FILE_AND_LINE_);
while (index1 < source1.GetSize() && index2 < source2.GetSize())
{
if (source1[index1]<source2[index2])
{
uniqueToSource1.Push(source1[index1],_FILE_AND_LINE_);
index1++;
}
else if (source1[index1]==source2[index2])
{
intersection.Push(source1[index1],_FILE_AND_LINE_);
index1++;
index2++;
}
else
{
uniqueToSource2.Push(source2[index2],_FILE_AND_LINE_);
index2++;
}
}
while (index1 < source1.GetSize())
{
uniqueToSource1.Push(source1[index1],_FILE_AND_LINE_);
index1++;
}
while (index2 < source2.GetSize())
{
uniqueToSource2.Push(source2[index2],_FILE_AND_LINE_);
index2++;
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ForEach | ( | void(*)(_DataType &item, const char *file, unsigned int line) | func, |
| const char * | file, | ||
| unsigned int | line | ||
| ) |
Definition at line 745 of file DS_Multilist.h.
{
_IndexType i;
for (i=0; i < dataSize; i++)
func(operator[](i), file, line);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ForEach | ( | void(*)(_DataType &item) | func | ) |
Definition at line 753 of file DS_Multilist.h.
{
_IndexType i;
for (i=0; i < dataSize; i++)
func(operator[](i));
}
| _IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetIndexFromKeyInSortedList | ( | const _KeyType & | key, |
| bool * | objectExists | ||
| ) | const [protected] |
Definition at line 1235 of file DS_Multilist.h.
References RakAssert.
{
RakAssert(IsSorted());
_IndexType index, upperBound, lowerBound;
if (dataSize==0)
{
*objectExists=false;
return 0;
}
upperBound=dataSize-1;
lowerBound=0;
index = dataSize/2;
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
while (1)
{
if (MLKeyRef<_KeyType>(key) > operator[](index) )
{
if (ascendingSort)
lowerBound=index+1;
else
upperBound=index-1;
}
else if (MLKeyRef<_KeyType>(key) < operator[](index) )
{
if (ascendingSort)
upperBound=index-1;
else
lowerBound=index+1;
}
else
{
// ==
*objectExists=true;
return index;
}
index=lowerBound+(upperBound-lowerBound)/2;
if (lowerBound>upperBound || upperBound==(_IndexType)-1)
{
*objectExists=false;
return lowerBound; // No match
}
}
}
| _IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetIndexOf | ( | _KeyType | key | ) | const |
Definition at line 668 of file DS_Multilist.h.
References ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
_IndexType i;
if (IsSorted())
{
bool objectExists;
i=GetIndexFromKeyInSortedList(key, &objectExists);
if (objectExists)
return i;
return (_IndexType)-1;
}
else if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK)
{
for (i=0; i < dataSize; i++)
{
if (MLKeyRef<_KeyType>(key)==data[i])
return i;
}
return (_IndexType)-1;
}
else
{
RakAssert( GetMultilistType()==ML_QUEUE );
for (i=0; i < dataSize; i++)
{
if (MLKeyRef<_KeyType>(key)==operator[](i))
return i;
}
return (_IndexType)-1;
}
}
| _IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetInsertionIndex | ( | _KeyType | key | ) | const |
Definition at line 702 of file DS_Multilist.h.
References ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
_IndexType i;
if (IsSorted())
{
bool objectExists;
i=GetIndexFromKeyInSortedList(key, &objectExists);
if (objectExists)
return (_IndexType)-1;
return i;
}
else if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK)
{
for (i=0; i < dataSize; i++)
{
if (MLKeyRef<_KeyType>(key)==data[i])
return (_IndexType)-1;
}
return dataSize;
}
else
{
RakAssert( GetMultilistType()==ML_QUEUE );
for (i=0; i < dataSize; i++)
{
if (MLKeyRef<_KeyType>(key)==operator[](i))
return (_IndexType)-1;
}
return dataSize;
}
}
| MultilistType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetMultilistType | ( | void | ) | const |
Definition at line 984 of file DS_Multilist.h.
References ML_VARIABLE_DURING_RUNTIME.
{
if (_MultilistType==ML_VARIABLE_DURING_RUNTIME)
return variableMultilistType;
return _MultilistType;
}
| _DataType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetPtr | ( | _KeyType | key | ) | const |
Definition at line 736 of file DS_Multilist.h.
{
_IndexType i = GetIndexOf(key);
if (i==(_IndexType)-1)
return 0;
return data[i];
}
| _IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetSize | ( | void | ) | const |
Definition at line 767 of file DS_Multilist.h.
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::CopySource(), and DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::FindIntersection().
{
return dataSize;
}
| bool DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::GetSortOrder | ( | void | ) | const |
Definition at line 972 of file DS_Multilist.h.
{
return ascendingSort;
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::InsertAtIndex | ( | const _DataType & | d, |
| _IndexType | index, | ||
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 534 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_STACK, and ML_UNORDERED_LIST.
{
ReallocateIfNeeded(file,line);
if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
{
if (index>=dataSize)
{
// insert at end
data[dataSize]=d;
dataSize++;
}
else
{
// insert at index
InsertShiftArrayRight(d,index);
}
}
else
{
data[queueTail++] = d;
if ( queueTail == allocationSize )
queueTail = 0;
++dataSize;
if (dataSize==1)
return;
_IndexType writeIndex, readIndex, trueWriteIndex, trueReadIndex;
writeIndex=dataSize-1;
readIndex=writeIndex-1;
while (readIndex >= index)
{
if ( queueHead + writeIndex >= allocationSize )
trueWriteIndex = queueHead + writeIndex - allocationSize;
else
trueWriteIndex = queueHead + writeIndex;
if ( queueHead + readIndex >= allocationSize )
trueReadIndex = queueHead + readIndex - allocationSize;
else
trueReadIndex = queueHead + readIndex;
data[trueWriteIndex]=data[trueReadIndex];
if (readIndex==0)
break;
writeIndex--;
readIndex--;
}
if ( queueHead + index >= allocationSize )
trueWriteIndex = queueHead + index - allocationSize;
else
trueWriteIndex = queueHead + index;
data[trueWriteIndex]=d;
}
if (_MultilistType!=ML_ORDERED_LIST)
sortState=ML_UNSORTED;
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::InsertInOrderedList | ( | const _DataType & | d, |
| const _KeyType & | key | ||
| ) | [protected] |
Definition at line 1206 of file DS_Multilist.h.
References ML_ORDERED_LIST, and RakAssert.
{
RakAssert(GetMultilistType()==ML_ORDERED_LIST);
bool objectExists;
_IndexType index;
index = GetIndexFromKeyInSortedList(key, &objectExists);
// if (objectExists)
// {
// Ordered list only allows unique insertions
// RakAssert("Duplicate insertion into ordered list" && false);
// return;
// }
if (index>=dataSize)
{
// insert at end
data[dataSize]=d;
dataSize++;
}
else
{
// insert at index
InsertShiftArrayRight(d,index);
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::InsertShiftArrayRight | ( | const _DataType & | d, |
| _IndexType | index | ||
| ) | [protected] |
Definition at line 1287 of file DS_Multilist.h.
| bool DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::IsEmpty | ( | void | ) | const |
Definition at line 761 of file DS_Multilist.h.
{
return dataSize==0;
}
| bool DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::IsSorted | ( | void | ) | const |
Doesn't actually check for sortedness, just if Sort() was recently called, or MultilistType is ML_ORDERED_LIST
Definition at line 978 of file DS_Multilist.h.
References ML_ORDERED_LIST.
{
return GetMultilistType()==ML_ORDERED_LIST || sortState!=ML_UNSORTED;
}
| Multilist< _MultilistType, _DataType, _KeyType, _IndexType > & DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::operator= | ( | const Multilist< _MultilistType, _DataType, _KeyType, _IndexType > & | source | ) |
Definition at line 289 of file DS_Multilist.h.
{
Clear(true);
CopySource(source);
return *this;
}
| _DataType & DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::operator[] | ( | const _IndexType | position | ) | const |
Definition at line 322 of file DS_Multilist.h.
References ML_QUEUE, and RakAssert.
{
RakAssert(position<GetSize());
if (GetMultilistType()==ML_QUEUE)
{
if ( queueHead + position >= allocationSize )
return data[ queueHead + position - allocationSize ];
else
return data[ queueHead + position ];
}
return data[position];
}
| _DataType & DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Peek | ( | void | ) | const |
Definition at line 414 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
RakAssert(IsEmpty()==false);
if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
{
return data[dataSize-1];
}
else
{
RakAssert(GetMultilistType()==ML_QUEUE);
return data[ queueHead ];
}
}
| _DataType & DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::PeekOpposite | ( | void | ) | const |
Definition at line 513 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
RakAssert(IsEmpty()==false);
if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
{
return data[0];
}
else
{
RakAssert(GetMultilistType()==ML_QUEUE);
_IndexType priorIndex;
if (queueTail==0)
priorIndex=allocationSize-1;
else
priorIndex=queueTail-1;
return data[priorIndex];
}
}
| _DataType & DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Pop | ( | const char * | file = __FILE__, |
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 389 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
RakAssert(IsEmpty()==false);
DeallocateIfNeeded(file,line);
if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
{
dataSize--;
return data[dataSize];
}
else
{
RakAssert(GetMultilistType()==ML_QUEUE);
if ( ++queueHead == allocationSize )
queueHead = 0;
if ( queueHead == 0 )
return data[ allocationSize -1 ];
dataSize--;
return data[ queueHead -1 ];
}
}
| _DataType & DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::PopOpposite | ( | const char * | file = __FILE__, |
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 481 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
RakAssert(IsEmpty()==false);
if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
{
// Copy leftmost to end
ReallocateIfNeeded(file,line);
data[dataSize]=data[0];
DeleteShiftArrayLeft(0);
--dataSize;
// Assuming still leaves at least one element past the end of the list allocated
DeallocateIfNeeded(file,line);
// Return end
return data[dataSize+1];
}
else
{
RakAssert(GetMultilistType()==ML_QUEUE);
// Deallocate first, since we are returning off the existing list
DeallocateIfNeeded(file,line);
dataSize--;
if (queueTail==0)
queueTail=allocationSize-1;
else
--queueTail;
return data[queueTail];
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Push | ( | const _DataType & | d, |
| const _KeyType & | key, | ||
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 344 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
ReallocateIfNeeded(file,line);
if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK)
{
data[dataSize]=d;
dataSize++;
}
else if (GetMultilistType()==ML_QUEUE)
{
data[queueTail++] = d;
if ( queueTail == allocationSize )
queueTail = 0;
dataSize++;
}
else
{
RakAssert(GetMultilistType()==ML_ORDERED_LIST);
InsertInOrderedList(d,key);
}
if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_QUEUE)
{
// Break sort if no longer sorted
if (sortState!=ML_UNSORTED && dataSize>1)
{
if (ascendingSort)
{
if ( MLKeyRef<_KeyType>(key) < operator[](dataSize-2) )
sortState=ML_UNSORTED;
}
else
{
if ( MLKeyRef<_KeyType>(key) > operator[](dataSize-2) )
sortState=ML_UNSORTED;
}
sortState=ML_UNSORTED;
}
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Push | ( | const _DataType & | d, |
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Unordered list, stack is LIFO QUEUE is FIFO Ordered list is inserted in order
Definition at line 338 of file DS_Multilist.h.
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::FindIntersection().
{
Push(d,d,file,line);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::PushOpposite | ( | const _DataType & | d, |
| const _KeyType & | key, | ||
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 435 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
ReallocateIfNeeded(file,line);
// Unordered list Push at back
if (GetMultilistType()==ML_UNORDERED_LIST)
{
data[dataSize]=d;
dataSize++;
}
else if (GetMultilistType()==ML_STACK)
{
// Stack push at front of the list, instead of back as normal
InsertAtIndex(d,0,file,line);
}
else if (GetMultilistType()==ML_QUEUE)
{
// Queue push at front of the list, instead of back as normal
InsertAtIndex(d,0,file,line);
}
else
{
RakAssert(GetMultilistType()==ML_ORDERED_LIST);
InsertInOrderedList(d,key);
}
if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_QUEUE)
{
// Break sort if no longer sorted
if (sortState!=ML_UNSORTED && dataSize>1)
{
if (ascendingSort)
{
if ( MLKeyRef<_KeyType>(key) > operator[](1) )
sortState=ML_UNSORTED;
}
else
{
if ( MLKeyRef<_KeyType>(key) < operator[](1) )
sortState=ML_UNSORTED;
}
}
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::PushOpposite | ( | const _DataType & | d, |
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 429 of file DS_Multilist.h.
{
PushOpposite(d,d,file,line);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::QSortAscending | ( | _IndexType | left, |
| _IndexType | right | ||
| ) | [protected] |
Definition at line 863 of file DS_Multilist.h.
{
_DataType temp;
_IndexType left=leftEdge;
_IndexType right=rightEdge;
_IndexType pivotIndex=left++;
while (left<right)
{
if (data[left] <= data[pivotIndex])
{
++left;
}
else
{
temp=data[left];
data[left]=data[right];
data[right]=temp;
--right;
}
}
temp=data[pivotIndex];
// Move pivot to center
if (data[left] > data[pivotIndex])
{
--left;
data[pivotIndex]=data[left];
data[left]=temp;
}
else
{
data[pivotIndex]=data[left];
data[left]=temp;
--left;
}
if (left!=leftEdge)
QSortAscending(leftEdge, left);
if (right!=rightEdge)
QSortAscending(right, rightEdge);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::QSortDescending | ( | _IndexType | left, |
| _IndexType | right | ||
| ) | [protected] |
Definition at line 911 of file DS_Multilist.h.
{
_DataType temp;
_IndexType left=leftEdge;
_IndexType right=rightEdge;
_IndexType pivotIndex=left++;
while (left<right)
{
if (data[left] >= data[pivotIndex])
{
++left;
}
else
{
temp=data[left];
data[left]=data[right];
data[right]=temp;
--right;
}
}
temp=data[pivotIndex];
// Move pivot to center
if (data[left] < data[pivotIndex])
{
--left;
data[pivotIndex]=data[left];
data[left]=temp;
}
else
{
data[pivotIndex]=data[left];
data[left]=temp;
--left;
}
if (left!=leftEdge)
QSortDescending(leftEdge, left);
if (right!=rightEdge)
QSortDescending(right, rightEdge);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Reallocate | ( | _IndexType | size, |
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 825 of file DS_Multilist.h.
{
_IndexType newAllocationSize;
if (size < dataSize)
newAllocationSize=dataSize;
else
newAllocationSize=size;
preallocationSize=size;
ReallocToSize(newAllocationSize,file,line);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ReallocateIfNeeded | ( | const char * | file, |
| unsigned int | line | ||
| ) | [protected] |
Definition at line 1136 of file DS_Multilist.h.
{
if (dataSize<allocationSize)
return;
_IndexType newAllocationSize;
if (allocationSize<16)
newAllocationSize=32;
else if (allocationSize>65536)
newAllocationSize=allocationSize+65536;
else
{
newAllocationSize=allocationSize<<1; // * 2
// Protect against underflow
if (newAllocationSize < allocationSize)
newAllocationSize=allocationSize+65536;
}
ReallocToSize(newAllocationSize,file,line);
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ReallocToSize | ( | _IndexType | newAllocationSize, |
| const char * | file, | ||
| unsigned int | line | ||
| ) | [protected] |
Definition at line 1173 of file DS_Multilist.h.
References ML_QUEUE, and RakNet::OP_DELETE_ARRAY().
{
_DataType* newData = RakNet::OP_NEW_ARRAY<_DataType>(newAllocationSize,file,line);
_IndexType i;
for (i=0; i < dataSize; i++)
newData[i]=operator[](i);
if (dataSize>0)
{
RakNet::OP_DELETE_ARRAY(data,file,line);
if (GetMultilistType()==ML_QUEUE)
{
queueHead=0;
queueTail=dataSize;
}
}
data=newData;
allocationSize=newAllocationSize;
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::RemoveAtIndex | ( | _IndexType | position, |
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Index[0] returns the same as Pop() for a queue. Same as PopOpposite() for the list and ordered list
Definition at line 601 of file DS_Multilist.h.
References ML_ORDERED_LIST, ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, and RakAssert.
{
RakAssert(position < dataSize);
RakAssert(IsEmpty()==false);
if (GetMultilistType()==ML_UNORDERED_LIST)
{
// Copy tail to current
data[position]=data[dataSize-1];
}
else if (GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
{
DeleteShiftArrayLeft(position);
}
else
{
RakAssert(GetMultilistType()==ML_QUEUE);
_IndexType index, next;
if ( queueHead + position >= allocationSize )
index = queueHead + position - allocationSize;
else
index = queueHead + position;
next = index + 1;
if ( next == allocationSize )
next = 0;
while ( next != queueTail )
{
// Overwrite the previous element
data[ index ] = data[ next ];
index = next;
//next = (next + 1) % allocationSize;
if ( ++next == allocationSize )
next = 0;
}
// Move the queueTail back
if ( queueTail == 0 )
queueTail = allocationSize - 1;
else
--queueTail;
}
dataSize--;
DeallocateIfNeeded(file,line);
}
| bool DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::RemoveAtKey | ( | _KeyType | key, |
| bool | assertIfDoesNotExist, | ||
| const char * | file = __FILE__, |
||
| unsigned int | line = __LINE__ |
||
| ) |
Definition at line 655 of file DS_Multilist.h.
References RakAssert.
{
_IndexType index = GetIndexOf(key);
if (index==(_IndexType)-1)
{
RakAssert(assertIfDoesNotExist==false && "RemoveAtKey element not found");
return false;
}
RemoveAtIndex(index,file,line);
return true;
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ReverseList | ( | void | ) |
Definition at line 816 of file DS_Multilist.h.
{
if (IsSorted())
ascendingSort=!ascendingSort;
ReverseListInternal();
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ReverseListInternal | ( | void | ) | [protected] |
Definition at line 1193 of file DS_Multilist.h.
{
_DataType temp;
_IndexType i;
for (i=0; i < dataSize/2; i++)
{
temp=operator[](i);
operator[](i)=operator[](dataSize-1-i);
operator[](dataSize-1-i)=temp;
}
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::SetMultilistType | ( | MultilistType | newType | ) |
| [in] | mlType | Any value of the enum MultilistType, except ML_VARIABLE_DURING_RUNTIME |
Definition at line 992 of file DS_Multilist.h.
References _FILE_AND_LINE_, ML_ORDERED_LIST, ML_QUEUE, ML_STACK, ML_UNORDERED_LIST, ML_VARIABLE_DURING_RUNTIME, and RakAssert.
{
RakAssert(_MultilistType==ML_VARIABLE_DURING_RUNTIME);
switch (variableMultilistType)
{
case ML_UNORDERED_LIST:
switch (newType)
{
case ML_UNORDERED_LIST:
// No change
break;
case ML_STACK:
// Same data format
break;
case ML_QUEUE:
queueHead=0;
queueTail=dataSize;
break;
case ML_ORDERED_LIST:
Sort(false);
break;
}
break;
case ML_STACK:
switch (newType)
{
case ML_UNORDERED_LIST:
// Same data format
break;
case ML_STACK:
// No change
break;
case ML_QUEUE:
queueHead=0;
queueTail=dataSize;
break;
case ML_ORDERED_LIST:
Sort(false);
break;
}
break;
case ML_QUEUE:
switch (newType)
{
case ML_UNORDERED_LIST:
case ML_STACK:
case ML_ORDERED_LIST:
if (queueTail < queueHead)
{
// Realign data if wrapped
ReallocToSize(dataSize, _FILE_AND_LINE_);
}
else
{
// Else can just copy starting at head
_IndexType i;
for (i=0; i < dataSize; i++)
data[i]=operator[](i);
}
if (newType==ML_ORDERED_LIST)
Sort(false);
break;
case ML_QUEUE:
// No change
break;
}
break;
case ML_ORDERED_LIST:
switch (newType)
{
case ML_UNORDERED_LIST:
case ML_STACK:
case ML_QUEUE:
// Same data format
// Tag as sorted
if (ascendingSort)
sortState=ML_SORTED_ASCENDING;
else
sortState=ML_SORTED_DESCENDING;
if (newType==ML_QUEUE)
{
queueHead=0;
queueTail=dataSize;
}
break;
case ML_ORDERED_LIST:
// No change
break;
}
break;
}
variableMultilistType=newType;
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::SetSortOrder | ( | bool | ascending | ) |
Used by Sort(), and by ML_ORDERED_LIST
Definition at line 959 of file DS_Multilist.h.
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::FindIntersection().
{
if (ascendingSort!=ascending && IsSorted())
{
ascendingSort=ascending;
// List is sorted, and the sort order has changed. So reverse the list
ReverseListInternal();
}
else
ascendingSort=ascending;
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::Sort | ( | bool | force | ) |
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
Definition at line 837 of file DS_Multilist.h.
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::FindIntersection().
{
if (IsSorted() && force==false)
return;
if (dataSize>1)
{
if (ascendingSort)
QSortAscending(0,dataSize-1);
else
QSortDescending(0,dataSize-1);
}
TagSorted();
}
| void DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::TagSorted | ( | void | ) |
Optimization if the source is sorted already
Definition at line 854 of file DS_Multilist.h.
{
if (ascendingSort)
sortState=ML_SORTED_ASCENDING;
else
sortState=ML_SORTED_DESCENDING;
}
_IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::allocationSize [protected] |
Definition at line 229 of file DS_Multilist.h.
bool DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::ascendingSort [protected] |
Definition at line 248 of file DS_Multilist.h.
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::CopySource().
_DataType* DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::data [protected] |
Definition at line 223 of file DS_Multilist.h.
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::CopySource().
_IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::dataSize [protected] |
Definition at line 226 of file DS_Multilist.h.
_IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::preallocationSize [protected] |
How many bytes the user chose to preallocate Won't automatically deallocate below this
Definition at line 239 of file DS_Multilist.h.
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::CopySource().
_IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::queueHead [protected] |
Definition at line 232 of file DS_Multilist.h.
_IndexType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::queueTail [protected] |
Definition at line 235 of file DS_Multilist.h.
enum { ... } DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::sortState [protected] |
MultilistType DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::variableMultilistType [protected] |
Definition at line 251 of file DS_Multilist.h.
Referenced by DataStructures::Multilist< _MultilistType, _DataType, _KeyType, _IndexType >::CopySource().
Copyright © 2007-2010 by The Shadowrun: Awakened Team. This work is licensed under the GNU Lesser General Public License 3.
 |