Shadowrun: Awakened: DS_Multilist.h Source File

Shadowrun: Awakened 29 September 2011 - Build 871
00001 
00002 
00003 
00004 
00005 
00006 
00007 
00008 
00009 
00010 #ifndef __MULTILIST_H
00011 #define __MULTILIST_H 
00012 
00013 #include "RakAssert.h"
00014 #include <string.h> // memmove
00015 #include "Export.h"
00016 #include "RakMemoryOverride.h"
00017 #include "NativeTypes.h"
00018 
00019 
00020 #ifdef _MSC_VER
00021 #pragma warning( push )
00022 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
00023 #pragma warning( disable : 4512 ) // warning C4512: assignment operator could not be generated
00024 #endif
00025 
00027 enum MultilistType
00028 {
00030     ML_UNORDERED_LIST,
00032     ML_STACK,
00034     ML_QUEUE,
00036     ML_ORDERED_LIST,
00038     ML_VARIABLE_DURING_RUNTIME
00039 };
00040 
00043 namespace DataStructures
00044 {
00047     template <class templateType>
00048     void DeletePtr_RakNet(templateType &ptr, const char *file, unsigned int line ) {RakNet::OP_DELETE(ptr, file, line);}
00049 
00052     template <class templateType>
00053     void DeletePtr(templateType &ptr) {delete ptr;}
00054 
00060     template < class templateType >
00061     class MLKeyRef
00062     {
00063     public:
00064         MLKeyRef(const templateType& input) : val(input) {}
00065         const templateType &Get(void) const {return val;}
00066         bool operator<( const templateType &right ) {return val < right;}
00067         bool operator>( const templateType &right ) {return val > right;}
00068         bool operator==( const templateType &right ) {return val == right;}
00069     protected:
00070         const templateType &val;
00071     };
00072 
00078     #define DEFINE_MULTILIST_PTR_TO_MEMBER_COMPARISONS( _CLASS_NAME_, _KEY_TYPE_, _MEMBER_VARIABLE_NAME_ ) \
00079     bool operator<( const DataStructures::MLKeyRef<_KEY_TYPE_> &inputKey, const _CLASS_NAME_ *cls ) {return inputKey.Get() < cls->_MEMBER_VARIABLE_NAME_;} \
00080     bool operator>( const DataStructures::MLKeyRef<_KEY_TYPE_> &inputKey, const _CLASS_NAME_ *cls ) {return inputKey.Get() > cls->_MEMBER_VARIABLE_NAME_;} \
00081     bool operator==( const DataStructures::MLKeyRef<_KEY_TYPE_> &inputKey, const _CLASS_NAME_ *cls ) {return inputKey.Get() == cls->_MEMBER_VARIABLE_NAME_;}
00082 
00083     typedef uint32_t DefaultIndexType;
00084 
00090     template <const MultilistType _MultilistType, class _DataType, class _KeyType=_DataType, class _IndexType=DefaultIndexType>
00091     class RAK_DLL_EXPORT Multilist
00092     {
00093     public:
00094         Multilist();
00095         ~Multilist();
00096         Multilist( const Multilist& source );
00097         Multilist& operator= ( const Multilist& source );
00098         _DataType& operator[] ( const _IndexType position ) const;
00102         void Push(const _DataType &d, const char *file=__FILE__, unsigned int line=__LINE__ );
00103         void Push(const _DataType &d, const _KeyType &key, const char *file=__FILE__, unsigned int line=__LINE__ );
00104 
00107         _DataType &Pop(const char *file=__FILE__, unsigned int line=__LINE__);
00108         _DataType &Peek(void) const;
00109 
00112         void PushOpposite(const _DataType &d, const char *file=__FILE__, unsigned int line=__LINE__ );
00113         void PushOpposite(const _DataType &d, const _KeyType &key, const char *file=__FILE__, unsigned int line=__LINE__ );
00114 
00116         _DataType &PopOpposite(const char *file=__FILE__, unsigned int line=__LINE__);
00117         _DataType &PeekOpposite(void) const;
00118 
00121         void InsertAtIndex(const _DataType &d, _IndexType index, const char *file=__FILE__, unsigned int line=__LINE__);    
00122         
00127         void RemoveAtIndex(_IndexType position, const char *file=__FILE__, unsigned int line=__LINE__);
00128 
00130         bool RemoveAtKey(_KeyType key, bool assertIfDoesNotExist, const char *file=__FILE__, unsigned int line=__LINE__);
00131 
00133         _IndexType GetIndexOf(_KeyType key) const;
00134 
00137         _IndexType GetInsertionIndex(_KeyType key) const;
00138 
00140         _DataType GetPtr(_KeyType key) const;
00141 
00143         void ForEach(void (*func)(_DataType &item, const char *file, unsigned int line), const char *file, unsigned int line);
00144         void ForEach(void (*func)(_DataType &item));    
00145 
00147         bool IsEmpty(void) const;
00148 
00150         _IndexType GetSize(void) const;
00151 
00154         void Clear( bool deallocateSmallBlocks=true, const char *file=__FILE__, unsigned int line=__LINE__ );
00155 
00158         void ClearPointers( bool deallocateSmallBlocks=true, const char *file=__FILE__, unsigned int line=__LINE__ );
00159 
00161         void ClearPointer( _KeyType key, const char *file=__FILE__, unsigned int line=__LINE__ );
00162 
00165         void ReverseList(void);
00166 
00169         void Reallocate(_IndexType size, const char *file=__FILE__, unsigned int line=__LINE__);
00170 
00174         void Sort(bool force);
00175 
00178         void TagSorted(void);
00179 
00182         void SetSortOrder(bool ascending);
00183 
00185         bool GetSortOrder(void) const;
00186 
00190         bool IsSorted(void) const;
00191 
00193         MultilistType GetMultilistType(void) const;
00194 
00198         void SetMultilistType(MultilistType newType);
00199 
00202         static void FindIntersection(
00203             Multilist& source1,
00204             Multilist& source2, 
00205             Multilist& intersection,
00206             Multilist& uniqueToSource1,
00207             Multilist& uniqueToSource2);
00208 
00209     protected:
00210         void ReallocateIfNeeded(const char *file, unsigned int line);
00211         void DeallocateIfNeeded(const char *file, unsigned int line);
00212         void ReallocToSize(_IndexType newAllocationSize, const char *file, unsigned int line);
00213         void ReverseListInternal(void);
00214         void InsertInOrderedList(const _DataType &d, const _KeyType &key);
00215         _IndexType GetIndexFromKeyInSortedList(const _KeyType &key, bool *objectExists) const;
00216         void InsertShiftArrayRight(const _DataType &d, _IndexType index);
00217         void DeleteShiftArrayLeft(_IndexType index);
00218         void QSortAscending(_IndexType left, _IndexType right);
00219         void QSortDescending(_IndexType left, _IndexType right);
00220         void CopySource( const Multilist& source );
00221 
00223         _DataType* data;
00224         
00226         _IndexType dataSize;
00227         
00229         _IndexType allocationSize;
00230 
00232         _IndexType queueHead;
00233 
00235         _IndexType queueTail;
00236 
00239         _IndexType preallocationSize;
00240 
00241         enum
00242         {
00243             ML_UNSORTED,
00244             ML_SORTED_ASCENDING,
00245             ML_SORTED_DESCENDING
00246         } sortState;
00247 
00248         bool ascendingSort;
00249 
00250         // In case we are using the variable type multilist
00251         MultilistType variableMultilistType;
00252     };
00253 
00254     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00255     Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Multilist()
00256     {
00257         data=0;
00258         dataSize=0;
00259         allocationSize=0;
00260         ascendingSort=true;
00261         sortState=ML_UNSORTED;
00262         queueHead=0;
00263         queueTail=0;
00264         preallocationSize=0;
00265 
00266         if (_MultilistType==ML_ORDERED_LIST)
00267             sortState=ML_SORTED_ASCENDING;
00268         else
00269             sortState=ML_UNSORTED;
00270 
00271         if (_MultilistType==ML_VARIABLE_DURING_RUNTIME)
00272             variableMultilistType=ML_UNORDERED_LIST;
00273     }
00274 
00275     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00276     Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::~Multilist()
00277     {
00278         if (data!=0)
00279             RakNet::OP_DELETE_ARRAY(data, _FILE_AND_LINE_);
00280     }
00281 
00282     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00283     Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Multilist( const Multilist& source )
00284     {
00285         CopySource(source);
00286     }
00287 
00288     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00289     Multilist<_MultilistType, _DataType, _KeyType, _IndexType>& Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::operator= ( const Multilist& source )
00290     {
00291         Clear(true);
00292         CopySource(source);
00293         return *this;
00294     }
00295 
00296     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00297     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::CopySource( const Multilist& source )
00298     {
00299         dataSize=source.GetSize();
00300         ascendingSort=source.ascendingSort;
00301         sortState=source.sortState;
00302         queueHead=0;
00303         queueTail=dataSize;
00304         preallocationSize=source.preallocationSize;
00305         variableMultilistType=source.variableMultilistType;
00306         if (source.data==0)
00307         {
00308             data=0;
00309             allocationSize=0;
00310         }
00311         else
00312         {
00313             allocationSize=dataSize;
00314             data = RakNet::OP_NEW_ARRAY<_DataType>(dataSize,_FILE_AND_LINE_);
00315             _IndexType i;
00316             for (i=0; i < dataSize; i++)
00317                 data[i]=source[i];
00318         }
00319     }
00320 
00321     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00322     _DataType& Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::operator[] ( const _IndexType position ) const
00323     {
00324         RakAssert(position<GetSize());
00325 
00326         if (GetMultilistType()==ML_QUEUE)
00327         {
00328             if ( queueHead + position >= allocationSize )
00329                 return data[ queueHead + position - allocationSize ];
00330             else
00331                 return data[ queueHead + position ];
00332         }
00333         
00334         return data[position];
00335     }
00336 
00337     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00338     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Push(const _DataType &d, const char *file, unsigned int line )
00339     {
00340         Push(d,d,file,line);
00341     }
00342 
00343     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00344     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Push(const _DataType &d, const _KeyType &key, const char *file, unsigned int line )
00345     {
00346         ReallocateIfNeeded(file,line);
00347 
00348         if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK)
00349         {
00350             data[dataSize]=d;
00351             dataSize++;
00352         }
00353         else if (GetMultilistType()==ML_QUEUE)
00354         {
00355             data[queueTail++] = d;
00356 
00357             if ( queueTail == allocationSize )
00358                 queueTail = 0;
00359             dataSize++;
00360         }
00361         else
00362         {
00363             RakAssert(GetMultilistType()==ML_ORDERED_LIST);
00364             InsertInOrderedList(d,key);
00365         }
00366 
00367         if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_QUEUE)
00368         {
00369             // Break sort if no longer sorted
00370             if (sortState!=ML_UNSORTED && dataSize>1)
00371             {
00372                 if (ascendingSort)
00373                 {
00374                     if ( MLKeyRef<_KeyType>(key) < operator[](dataSize-2) )
00375                         sortState=ML_UNSORTED;
00376                 }
00377                 else
00378                 {
00379                     if ( MLKeyRef<_KeyType>(key) > operator[](dataSize-2) )
00380                         sortState=ML_UNSORTED;
00381                 }
00382 
00383                 sortState=ML_UNSORTED;
00384             }
00385         }
00386     }
00387 
00388     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00389     _DataType &Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Pop(const char *file, unsigned int line)
00390     {
00391         RakAssert(IsEmpty()==false);
00392         DeallocateIfNeeded(file,line);
00393         if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
00394         {
00395             dataSize--;
00396             return data[dataSize];
00397         }
00398         else
00399         {
00400             RakAssert(GetMultilistType()==ML_QUEUE);
00401 
00402             if ( ++queueHead == allocationSize )
00403                 queueHead = 0;
00404 
00405             if ( queueHead == 0 )
00406                 return data[ allocationSize -1 ];
00407 
00408             dataSize--;
00409             return data[ queueHead -1 ];
00410         }
00411     }
00412 
00413     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00414     _DataType &Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Peek(void) const
00415     {
00416         RakAssert(IsEmpty()==false);
00417         if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
00418         {
00419             return data[dataSize-1];
00420         }
00421         else
00422         {
00423             RakAssert(GetMultilistType()==ML_QUEUE);
00424             return data[ queueHead ];
00425         }
00426     }
00427 
00428     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00429     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::PushOpposite(const _DataType &d, const char *file, unsigned int line )
00430     {
00431         PushOpposite(d,d,file,line);
00432     }
00433 
00434     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00435     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::PushOpposite(const _DataType &d, const _KeyType &key, const char *file, unsigned int line )
00436     {
00437         ReallocateIfNeeded(file,line);
00438 
00439         // Unordered list Push at back
00440         if (GetMultilistType()==ML_UNORDERED_LIST)
00441         {
00442             data[dataSize]=d;
00443             dataSize++;
00444         }
00445         else if (GetMultilistType()==ML_STACK)
00446         {
00447             // Stack push at front of the list, instead of back as normal
00448             InsertAtIndex(d,0,file,line);
00449         }
00450         else if (GetMultilistType()==ML_QUEUE)
00451         {
00452             // Queue push at front of the list, instead of back as normal
00453             InsertAtIndex(d,0,file,line);
00454         }
00455         else
00456         {
00457             RakAssert(GetMultilistType()==ML_ORDERED_LIST);
00458             InsertInOrderedList(d,key);
00459         }
00460 
00461         if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_QUEUE)
00462         {
00463             // Break sort if no longer sorted
00464             if (sortState!=ML_UNSORTED && dataSize>1)
00465             {
00466                 if (ascendingSort)
00467                 {
00468                     if ( MLKeyRef<_KeyType>(key) > operator[](1) )
00469                         sortState=ML_UNSORTED;
00470                 }
00471                 else
00472                 {
00473                     if ( MLKeyRef<_KeyType>(key) < operator[](1) )
00474                         sortState=ML_UNSORTED;
00475                 }
00476             }
00477         }
00478     }
00479 
00480     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00481     _DataType &Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::PopOpposite(const char *file, unsigned int line)
00482     {
00483         RakAssert(IsEmpty()==false);
00484         if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
00485         {
00486             // Copy leftmost to end
00487             ReallocateIfNeeded(file,line);
00488             data[dataSize]=data[0];
00489             DeleteShiftArrayLeft(0);
00490             --dataSize;
00491             // Assuming still leaves at least one element past the end of the list allocated
00492             DeallocateIfNeeded(file,line);
00493             // Return end
00494             return data[dataSize+1];
00495         }
00496         else
00497         {
00498             RakAssert(GetMultilistType()==ML_QUEUE);
00499             // Deallocate first, since we are returning off the existing list
00500             DeallocateIfNeeded(file,line);
00501             dataSize--;
00502 
00503             if (queueTail==0)
00504                 queueTail=allocationSize-1;
00505             else
00506                 --queueTail;
00507 
00508             return data[queueTail];
00509         }
00510     }
00511 
00512     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00513     _DataType &Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::PeekOpposite(void) const
00514     {
00515         RakAssert(IsEmpty()==false);
00516         if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
00517         {
00518             return data[0];
00519         }
00520         else
00521         {
00522             RakAssert(GetMultilistType()==ML_QUEUE);
00523             _IndexType priorIndex;
00524             if (queueTail==0)
00525                 priorIndex=allocationSize-1;
00526             else
00527                 priorIndex=queueTail-1;
00528 
00529             return data[priorIndex];
00530         }
00531     }
00532 
00533     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00534     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::InsertAtIndex(const _DataType &d, _IndexType index, const char *file, unsigned int line)
00535     {
00536         ReallocateIfNeeded(file,line);
00537 
00538         if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
00539         {
00540             if (index>=dataSize)
00541             {
00542                 // insert at end
00543                 data[dataSize]=d;
00544 
00545                 dataSize++;
00546             }
00547             else
00548             {
00549                 // insert at index
00550                 InsertShiftArrayRight(d,index);
00551             }
00552         }
00553         else
00554         {
00555             data[queueTail++] = d;
00556 
00557             if ( queueTail == allocationSize )
00558                 queueTail = 0;
00559 
00560             ++dataSize;
00561 
00562             if (dataSize==1)
00563                 return;
00564 
00565             _IndexType writeIndex, readIndex, trueWriteIndex, trueReadIndex;
00566             writeIndex=dataSize-1;
00567             readIndex=writeIndex-1;
00568             while (readIndex >= index)
00569             {
00570                 if ( queueHead + writeIndex >= allocationSize )
00571                     trueWriteIndex = queueHead + writeIndex - allocationSize;
00572                 else
00573                     trueWriteIndex = queueHead + writeIndex;
00574 
00575                 if ( queueHead + readIndex >= allocationSize )
00576                     trueReadIndex = queueHead + readIndex - allocationSize;
00577                 else
00578                     trueReadIndex = queueHead + readIndex;
00579 
00580                 data[trueWriteIndex]=data[trueReadIndex];
00581 
00582                 if (readIndex==0)
00583                     break;
00584                 writeIndex--;
00585                 readIndex--;
00586             }
00587 
00588             if ( queueHead + index >= allocationSize )
00589                 trueWriteIndex = queueHead + index - allocationSize;
00590             else
00591                 trueWriteIndex = queueHead + index;
00592 
00593             data[trueWriteIndex]=d;
00594         }
00595 
00596         if (_MultilistType!=ML_ORDERED_LIST)
00597             sortState=ML_UNSORTED;
00598     }
00599 
00600     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00601     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::RemoveAtIndex(_IndexType position, const char *file, unsigned int line)
00602     {
00603         RakAssert(position < dataSize);
00604         RakAssert(IsEmpty()==false);
00605 
00606         if (GetMultilistType()==ML_UNORDERED_LIST)
00607         {
00608             // Copy tail to current
00609             data[position]=data[dataSize-1];
00610         }
00611         else if (GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST)
00612         {
00613             DeleteShiftArrayLeft(position);
00614         }
00615         else
00616         {
00617             RakAssert(GetMultilistType()==ML_QUEUE);
00618 
00619             _IndexType index, next;
00620 
00621             if ( queueHead + position >= allocationSize )
00622                 index = queueHead + position - allocationSize;
00623             else
00624                 index = queueHead + position;
00625 
00626             next = index + 1;
00627 
00628             if ( next == allocationSize )
00629                 next = 0;
00630 
00631             while ( next != queueTail )
00632             {
00633                 // Overwrite the previous element
00634                 data[ index ] = data[ next ];
00635                 index = next;
00636                 //next = (next + 1) % allocationSize;
00637 
00638                 if ( ++next == allocationSize )
00639                     next = 0;
00640             }
00641 
00642             // Move the queueTail back
00643             if ( queueTail == 0 )
00644                 queueTail = allocationSize - 1;
00645             else
00646                 --queueTail;
00647         }
00648         
00649         
00650         dataSize--;
00651         DeallocateIfNeeded(file,line);
00652     }
00653 
00654     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00655     bool Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::RemoveAtKey(_KeyType key, bool assertIfDoesNotExist, const char *file, unsigned int line)
00656     {
00657         _IndexType index = GetIndexOf(key);
00658         if (index==(_IndexType)-1)
00659         {
00660             RakAssert(assertIfDoesNotExist==false && "RemoveAtKey element not found");
00661             return false;
00662         }
00663         RemoveAtIndex(index,file,line);
00664         return true;
00665     }
00666 
00667     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00668     _IndexType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetIndexOf(_KeyType key) const
00669     {
00670         _IndexType i;
00671         if (IsSorted())
00672         {
00673             bool objectExists;
00674             i=GetIndexFromKeyInSortedList(key, &objectExists);
00675             if (objectExists)
00676                 return i;
00677             return (_IndexType)-1;
00678         }
00679         else if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK)
00680         {
00681             for (i=0; i < dataSize; i++)
00682             {
00683                 if (MLKeyRef<_KeyType>(key)==data[i])
00684                     return i;
00685             }
00686             return (_IndexType)-1;
00687         }
00688         else
00689         {
00690             RakAssert( GetMultilistType()==ML_QUEUE );
00691 
00692             for (i=0; i < dataSize; i++)
00693             {
00694                 if (MLKeyRef<_KeyType>(key)==operator[](i))
00695                     return i;
00696             }
00697             return (_IndexType)-1;
00698         }
00699     }
00700 
00701     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00702     _IndexType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetInsertionIndex(_KeyType key) const
00703     {
00704         _IndexType i;
00705         if (IsSorted())
00706         {
00707             bool objectExists;
00708             i=GetIndexFromKeyInSortedList(key, &objectExists);
00709             if (objectExists)
00710                 return (_IndexType)-1;
00711             return i;
00712         }
00713         else if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK)
00714         {
00715             for (i=0; i < dataSize; i++)
00716             {
00717                 if (MLKeyRef<_KeyType>(key)==data[i])
00718                     return (_IndexType)-1;
00719             }
00720             return dataSize;
00721         }
00722         else
00723         {
00724             RakAssert( GetMultilistType()==ML_QUEUE );
00725 
00726             for (i=0; i < dataSize; i++)
00727             {
00728                 if (MLKeyRef<_KeyType>(key)==operator[](i))
00729                     return (_IndexType)-1;
00730             }
00731             return dataSize;
00732         }
00733     }
00734 
00735     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00736     _DataType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetPtr(_KeyType key) const
00737     {
00738         _IndexType i = GetIndexOf(key);
00739         if (i==(_IndexType)-1)
00740             return 0;
00741         return data[i];
00742     }
00743 
00744     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00745     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ForEach(void (*func)(_DataType &item, const char *file, unsigned int line), const char *file, unsigned int line)
00746     {
00747         _IndexType i;
00748         for (i=0; i < dataSize; i++)
00749             func(operator[](i), file, line);
00750     }
00751 
00752     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00753     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ForEach(void (*func)(_DataType &item))
00754     {
00755         _IndexType i;
00756         for (i=0; i < dataSize; i++)
00757             func(operator[](i));
00758     }
00759 
00760     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00761     bool Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::IsEmpty(void) const
00762     {
00763         return dataSize==0;
00764     }
00765 
00766     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00767     _IndexType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetSize(void) const
00768     {
00769         return dataSize;
00770     }
00771 
00772     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00773     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Clear( bool deallocateSmallBlocks, const char *file, unsigned int line )
00774     {
00775         dataSize=0;
00776         if (GetMultilistType()==ML_ORDERED_LIST)
00777             if (ascendingSort)
00778                 sortState=ML_SORTED_ASCENDING;
00779             else
00780                 sortState=ML_SORTED_DESCENDING;
00781         else
00782             sortState=ML_UNSORTED;
00783         queueHead=0;
00784         queueTail=0;
00785 
00786         if (deallocateSmallBlocks && allocationSize < 128 && data)
00787         {
00788             RakNet::OP_DELETE_ARRAY(data,file,line);
00789             data=0;
00790             allocationSize=0;
00791         }
00792     }
00793 
00794     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00795     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ClearPointers( bool deallocateSmallBlocks, const char *file, unsigned int line )
00796     {
00797         _IndexType i;
00798         for (i=0; i < dataSize; i++)
00799             RakNet::OP_DELETE(operator[](i), file, line);
00800         Clear(deallocateSmallBlocks, file, line);
00801     }
00802 
00803     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00804     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ClearPointer( _KeyType key, const char *file, unsigned int line )
00805     {
00806         _IndexType i;
00807         i = GetIndexOf(key);
00808         if (i!=-1)
00809         {
00810             RakNet::OP_DELETE(operator[](i), file, line);
00811             RemoveAtIndex(i);
00812         }
00813     }
00814 
00815     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00816     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ReverseList(void)
00817     {
00818         if (IsSorted())
00819             ascendingSort=!ascendingSort;
00820 
00821         ReverseListInternal();
00822     }
00823 
00824     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00825     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Reallocate(_IndexType size, const char *file, unsigned int line)
00826     {
00827         _IndexType newAllocationSize;
00828         if (size < dataSize)
00829             newAllocationSize=dataSize;
00830         else
00831             newAllocationSize=size;
00832         preallocationSize=size;
00833         ReallocToSize(newAllocationSize,file,line);
00834     }
00835 
00836     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00837     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Sort(bool force)
00838     {
00839         if (IsSorted() && force==false)
00840             return;
00841 
00842         if (dataSize>1)
00843         {
00844             if (ascendingSort)
00845                 QSortAscending(0,dataSize-1);       
00846             else
00847                 QSortDescending(0,dataSize-1);
00848         }
00849 
00850         TagSorted();
00851     }
00852 
00853     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00854     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::TagSorted(void)
00855     {
00856         if (ascendingSort)
00857             sortState=ML_SORTED_ASCENDING;
00858         else
00859             sortState=ML_SORTED_DESCENDING;
00860     }
00861 
00862     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00863     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::QSortAscending(_IndexType leftEdge, _IndexType rightEdge)
00864     {
00865         _DataType temp;
00866         _IndexType left=leftEdge;
00867         _IndexType right=rightEdge;
00868         _IndexType pivotIndex=left++;
00869 
00870         while (left<right)
00871         {
00872             if (data[left] <= data[pivotIndex])
00873             {
00874                 ++left;
00875             }
00876             else
00877             {
00878                 temp=data[left];
00879                 data[left]=data[right];
00880                 data[right]=temp;
00881                 --right;
00882             }
00883         }
00884 
00885         temp=data[pivotIndex];
00886 
00887         // Move pivot to center
00888         if (data[left] > data[pivotIndex])
00889         {
00890             --left;
00891 
00892             data[pivotIndex]=data[left];
00893             data[left]=temp;
00894         }
00895         else
00896         {
00897             data[pivotIndex]=data[left];
00898             data[left]=temp;
00899 
00900             --left;
00901         }
00902 
00903         if (left!=leftEdge)
00904             QSortAscending(leftEdge, left);
00905 
00906         if (right!=rightEdge)
00907             QSortAscending(right, rightEdge);       
00908     }
00909 
00910     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00911     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::QSortDescending(_IndexType leftEdge, _IndexType rightEdge)
00912     {
00913         _DataType temp;
00914         _IndexType left=leftEdge;
00915         _IndexType right=rightEdge;
00916         _IndexType pivotIndex=left++;
00917 
00918         while (left<right)
00919         {
00920             if (data[left] >= data[pivotIndex])
00921             {
00922                 ++left;
00923             }
00924             else
00925             {
00926                 temp=data[left];
00927                 data[left]=data[right];
00928                 data[right]=temp;
00929                 --right;
00930             }
00931         }
00932 
00933         temp=data[pivotIndex];
00934 
00935         // Move pivot to center
00936         if (data[left] < data[pivotIndex])
00937         {
00938             --left;
00939 
00940             data[pivotIndex]=data[left];
00941             data[left]=temp;
00942         }
00943         else
00944         {
00945             data[pivotIndex]=data[left];
00946             data[left]=temp;
00947 
00948             --left;
00949         }
00950 
00951         if (left!=leftEdge)
00952             QSortDescending(leftEdge, left);
00953 
00954         if (right!=rightEdge)
00955             QSortDescending(right, rightEdge);      
00956     }
00957 
00958     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00959     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::SetSortOrder(bool ascending)
00960     {
00961         if (ascendingSort!=ascending && IsSorted())
00962         {
00963             ascendingSort=ascending;
00964             // List is sorted, and the sort order has changed. So reverse the list
00965             ReverseListInternal();
00966         }
00967         else
00968             ascendingSort=ascending;
00969     }
00970 
00971     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00972     bool Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetSortOrder(void) const
00973     {
00974         return ascendingSort;
00975     }
00976 
00977     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00978     bool Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::IsSorted(void) const
00979     {
00980         return GetMultilistType()==ML_ORDERED_LIST || sortState!=ML_UNSORTED;
00981     }
00982 
00983     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00984     MultilistType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetMultilistType(void) const
00985     {
00986         if (_MultilistType==ML_VARIABLE_DURING_RUNTIME)
00987             return variableMultilistType;
00988         return _MultilistType;
00989     }
00990 
00991     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
00992     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::SetMultilistType(MultilistType newType)
00993     {
00994         RakAssert(_MultilistType==ML_VARIABLE_DURING_RUNTIME);
00995         switch (variableMultilistType)
00996         {
00997         case ML_UNORDERED_LIST:
00998             switch (newType)
00999             {
01000             case ML_UNORDERED_LIST:
01001                 // No change
01002                 break;
01003             case ML_STACK:
01004                 // Same data format
01005                 break;
01006             case ML_QUEUE:
01007                 queueHead=0;
01008                 queueTail=dataSize;
01009                 break;
01010             case ML_ORDERED_LIST:
01011                 Sort(false);
01012                 break;
01013             }
01014             break;
01015         case ML_STACK:
01016             switch (newType)
01017             {
01018             case ML_UNORDERED_LIST:
01019                 // Same data format
01020                 break;
01021             case ML_STACK:
01022                 // No change
01023                 break;
01024             case ML_QUEUE:
01025                 queueHead=0;
01026                 queueTail=dataSize;
01027                 break;
01028             case ML_ORDERED_LIST:
01029                 Sort(false);
01030                 break;
01031             }
01032             break;
01033         case ML_QUEUE:
01034             switch (newType)
01035             {
01036             case ML_UNORDERED_LIST:
01037             case ML_STACK:
01038             case ML_ORDERED_LIST:
01039                 if (queueTail < queueHead)
01040                 {
01041                     // Realign data if wrapped
01042                     ReallocToSize(dataSize, _FILE_AND_LINE_);
01043                 }
01044                 else
01045                 {
01046                     // Else can just copy starting at head
01047                     _IndexType i;
01048                     for (i=0; i < dataSize; i++)
01049                         data[i]=operator[](i);
01050                 }
01051                 if (newType==ML_ORDERED_LIST)
01052                     Sort(false);
01053                 break;
01054             case ML_QUEUE:
01055                 // No change
01056                 break;
01057             }
01058             break;
01059         case ML_ORDERED_LIST:
01060             switch (newType)
01061             {
01062             case ML_UNORDERED_LIST:
01063             case ML_STACK:
01064             case ML_QUEUE:
01065                 // Same data format
01066                 // Tag as sorted
01067                 if (ascendingSort)
01068                     sortState=ML_SORTED_ASCENDING;
01069                 else
01070                     sortState=ML_SORTED_DESCENDING;
01071                 if (newType==ML_QUEUE)
01072                 {
01073                     queueHead=0;
01074                     queueTail=dataSize;
01075                 }
01076                 break;
01077             case ML_ORDERED_LIST:
01078                 // No change
01079                 break;
01080             }
01081             break;
01082         }
01083 
01084         variableMultilistType=newType;
01085     }
01086 
01087     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01088     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::FindIntersection(
01089         Multilist& source1,
01090         Multilist& source2, 
01091         Multilist& intersection,
01092         Multilist& uniqueToSource1,
01093         Multilist& uniqueToSource2)
01094     {
01095         _IndexType index1=0, index2=0;
01096         source1.SetSortOrder(true);
01097         source2.SetSortOrder(true);
01098         source1.Sort(false);
01099         source2.Sort(false);
01100         intersection.Clear(true,_FILE_AND_LINE_);
01101         uniqueToSource1.Clear(true,_FILE_AND_LINE_);
01102         uniqueToSource2.Clear(true,_FILE_AND_LINE_);
01103         
01104         while (index1 < source1.GetSize() && index2 < source2.GetSize())
01105         {
01106             if (source1[index1]<source2[index2])
01107             {
01108                 uniqueToSource1.Push(source1[index1],_FILE_AND_LINE_);
01109                 index1++;
01110             }
01111             else if (source1[index1]==source2[index2])
01112             {
01113                 intersection.Push(source1[index1],_FILE_AND_LINE_);
01114                 index1++;
01115                 index2++;
01116             }
01117             else
01118             {
01119                 uniqueToSource2.Push(source2[index2],_FILE_AND_LINE_);
01120                 index2++;
01121             }
01122         }
01123         while (index1 < source1.GetSize())
01124         {
01125             uniqueToSource1.Push(source1[index1],_FILE_AND_LINE_);
01126             index1++;
01127         }
01128         while (index2 < source2.GetSize())
01129         {
01130             uniqueToSource2.Push(source2[index2],_FILE_AND_LINE_);
01131             index2++;
01132         }
01133     }
01134 
01135     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01136     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ReallocateIfNeeded(const char *file, unsigned int line)
01137     {
01138         if (dataSize<allocationSize)
01139             return;
01140 
01141         _IndexType newAllocationSize;
01142         if (allocationSize<16)
01143             newAllocationSize=32;
01144         else if (allocationSize>65536)
01145             newAllocationSize=allocationSize+65536;
01146         else
01147         {
01148             newAllocationSize=allocationSize<<1; // * 2
01149             // Protect against underflow
01150             if (newAllocationSize < allocationSize)
01151                 newAllocationSize=allocationSize+65536;
01152         }
01153 
01154         ReallocToSize(newAllocationSize,file,line);
01155     }
01156 
01157     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01158     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::DeallocateIfNeeded(const char *file, unsigned int line)
01159     {
01160         if (allocationSize<512)
01161             return;
01162         if (dataSize >= allocationSize/3 )
01163             return;
01164         if (dataSize <= preallocationSize )
01165             return;
01166         
01167         _IndexType newAllocationSize = dataSize<<1; // * 2
01168 
01169         ReallocToSize(newAllocationSize,file,line);
01170     }
01171 
01172     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01173     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ReallocToSize(_IndexType newAllocationSize, const char *file, unsigned int line)
01174     {
01175         _DataType* newData = RakNet::OP_NEW_ARRAY<_DataType>(newAllocationSize,file,line);
01176         _IndexType i;
01177         for (i=0; i < dataSize; i++)
01178             newData[i]=operator[](i);
01179         if (dataSize>0)
01180         {
01181             RakNet::OP_DELETE_ARRAY(data,file,line);
01182             if (GetMultilistType()==ML_QUEUE)
01183             {
01184                 queueHead=0;
01185                 queueTail=dataSize;
01186             }
01187         }
01188         data=newData;
01189         allocationSize=newAllocationSize;
01190     }
01191 
01192     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01193     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ReverseListInternal(void)
01194     {
01195         _DataType temp;
01196         _IndexType i;
01197         for (i=0; i < dataSize/2; i++)
01198         {
01199             temp=operator[](i);
01200             operator[](i)=operator[](dataSize-1-i);
01201             operator[](dataSize-1-i)=temp;
01202         }
01203     }
01204 
01205     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01206     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::InsertInOrderedList(const _DataType &d, const _KeyType &key)
01207     {
01208         RakAssert(GetMultilistType()==ML_ORDERED_LIST);
01209 
01210         bool objectExists;
01211         _IndexType index;
01212         index = GetIndexFromKeyInSortedList(key, &objectExists);
01213 
01214     //  if (objectExists)
01215     //  {
01216             // Ordered list only allows unique insertions
01217     //      RakAssert("Duplicate insertion into ordered list" && false);
01218     //      return;
01219     //  }
01220 
01221         if (index>=dataSize)
01222         {
01223             // insert at end
01224             data[dataSize]=d;
01225             dataSize++;
01226         }
01227         else
01228         {
01229             // insert at index
01230             InsertShiftArrayRight(d,index);
01231         }
01232     }
01233 
01234     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01235     _IndexType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetIndexFromKeyInSortedList(const _KeyType &key, bool *objectExists) const
01236     {
01237         RakAssert(IsSorted());
01238         _IndexType index, upperBound, lowerBound;
01239 
01240         if (dataSize==0)
01241         {
01242             *objectExists=false;
01243             return 0;
01244         }
01245 
01246         upperBound=dataSize-1;
01247         lowerBound=0;
01248         index = dataSize/2;
01249 
01250 #ifdef _MSC_VER
01251     #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
01252 #endif
01253         while (1)
01254         {
01255             if (MLKeyRef<_KeyType>(key) > operator[](index) )
01256             {
01257                 if (ascendingSort)
01258                     lowerBound=index+1;
01259                 else
01260                     upperBound=index-1;
01261             }
01262             else if (MLKeyRef<_KeyType>(key) < operator[](index) )
01263             {
01264                 if (ascendingSort)
01265                     upperBound=index-1;
01266                 else
01267                     lowerBound=index+1;
01268             }
01269             else
01270             {
01271                 // ==
01272                 *objectExists=true;
01273                 return index;
01274             }
01275 
01276             index=lowerBound+(upperBound-lowerBound)/2;
01277 
01278             if (lowerBound>upperBound || upperBound==(_IndexType)-1)
01279             {
01280                 *objectExists=false;
01281                 return lowerBound; // No match
01282             }
01283         }
01284     }
01285 
01286     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01287     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::InsertShiftArrayRight(const _DataType &d, _IndexType index)
01288     {
01289         RakAssert(_MultilistType!=ML_QUEUE);
01290 
01291         // Move the elements in the list to make room
01292         _IndexType i;
01293         for ( i = dataSize; i != index; i-- )
01294             data[ i ] = data[ i - 1 ];
01295 
01296         // Insert the new item at the correct spot
01297         data[ index ] = d;
01298 
01299         ++dataSize;
01300     }
01301 
01302     template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType>
01303     void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::DeleteShiftArrayLeft( _IndexType index )
01304     {
01305         RakAssert(index < dataSize);
01306         RakAssert(_MultilistType!=ML_QUEUE);
01307 
01308         _IndexType i;
01309         for ( i = index; i < dataSize-1; i++ )
01310             data[i]=data[i+1];
01311     }
01312 };
01313 
01314 /*
01315 struct KeyAndValue
01316 {
01317     int key;
01318     short value;
01319 };
01320 
01321 DEFINE_MULTILIST_PTR_TO_MEMBER_COMPARISONS(KeyAndValue,int,key)
01322 
01323 void MultilistUnitTest(void)
01324 {
01325     DataStructures::DefaultIndexType oldSize;
01326     DataStructures::Multilist<ML_UNORDERED_LIST, int> ml1;
01327     ml1.Reallocate(64);
01328     RakAssert(ml1.IsEmpty());
01329     ml1.Push(53);
01330     RakAssert(ml1.Peek()==53);
01331     RakAssert(ml1.IsEmpty()==false);
01332     RakAssert(ml1.Pop()==53);
01333     RakAssert(ml1.IsEmpty()==true);
01334     for (int i=0; i < 512; i++)
01335     ml1.Push(i);
01336     RakAssert(ml1.GetIndexOf(200)==200);
01337     RakAssert(ml1.PeekOpposite()==0);
01338     RakAssert(ml1.PopOpposite()==0);
01339     RakAssert(ml1.PeekOpposite()==1);
01340     RakAssert(ml1.Peek()==511);
01341     ml1.ReverseList();
01342     for (int i=0; i < 511; i++)
01343     RakAssert(ml1[i]==511-i);
01344     RakAssert(ml1.PeekOpposite()==511);
01345     RakAssert(ml1.Peek()==1);
01346     oldSize = ml1.GetSize();
01347     ml1.RemoveAtIndex(0);
01348     RakAssert(ml1.GetSize()==oldSize-1);
01349     RakAssert(ml1.PeekOpposite()==1);
01350     ml1.Clear(_FILE_AND_LINE_);
01351     RakAssert(ml1.IsEmpty()==true);
01352 
01353     ml1.Sort(true);
01354     ml1.Clear(_FILE_AND_LINE_);
01355 
01356     ml1.Push(100);
01357     ml1.Sort(true);
01358     ml1.Clear(_FILE_AND_LINE_);
01359 
01360     ml1.Push(50);
01361     ml1.Push(100);
01362     ml1.Sort(true);
01363     ml1.Clear(_FILE_AND_LINE_);
01364 
01365     ml1.Push(100);
01366     ml1.Push(50);
01367     ml1.Sort(true);
01368     ml1.Clear(_FILE_AND_LINE_);
01369 
01370     ml1.Push(100);
01371     ml1.Push(50);
01372     ml1.Push(150);
01373     ml1.Push(25);
01374     ml1.Push(175);
01375     ml1.Sort(true);
01376     RakAssert(ml1[0]==25);
01377     RakAssert(ml1[1]==50);
01378     RakAssert(ml1[2]==100);
01379     RakAssert(ml1[3]==150);
01380     RakAssert(ml1[4]==175);
01381     RakAssert(ml1.GetIndexOf(25)==0);
01382     RakAssert(ml1.GetIndexOf(50)==1);
01383     RakAssert(ml1.GetIndexOf(100)==2);
01384     RakAssert(ml1.GetIndexOf(150)==3);
01385     RakAssert(ml1.GetIndexOf(175)==4);
01386     ml1.Clear(_FILE_AND_LINE_);
01387 
01388     ml1.Push(1);
01389     ml1.Push(2);
01390     ml1.Push(3);
01391     ml1.Push(4);
01392     ml1.Push(5);
01393     ml1.Sort(true);
01394     RakAssert(ml1[0]==1);
01395     RakAssert(ml1[1]==2);
01396     RakAssert(ml1[2]==3);
01397     RakAssert(ml1[3]==4);
01398     RakAssert(ml1[4]==5);
01399     RakAssert(ml1.GetIndexOf(1)==0);
01400     RakAssert(ml1.GetIndexOf(2)==1);
01401     RakAssert(ml1.GetIndexOf(3)==2);
01402     RakAssert(ml1.GetIndexOf(4)==3);
01403     RakAssert(ml1.GetIndexOf(5)==4);
01404     ml1.Clear(_FILE_AND_LINE_);
01405 
01406     ml1.Push(5);
01407     ml1.Push(4);
01408     ml1.Push(3);
01409     ml1.Push(2);
01410     ml1.Push(1);
01411     ml1.Sort(true);
01412     RakAssert(ml1[0]==1);
01413     RakAssert(ml1[1]==2);
01414     RakAssert(ml1[2]==3);
01415     RakAssert(ml1[3]==4);
01416     RakAssert(ml1[4]==5);
01417     RakAssert(ml1.GetIndexOf(1)==0);
01418     RakAssert(ml1.GetIndexOf(2)==1);
01419     RakAssert(ml1.GetIndexOf(3)==2);
01420     RakAssert(ml1.GetIndexOf(4)==3);
01421     RakAssert(ml1.GetIndexOf(5)==4);
01422     ml1.Sort(true);
01423     RakAssert(ml1[0]==1);
01424     RakAssert(ml1[1]==2);
01425     RakAssert(ml1[2]==3);
01426     RakAssert(ml1[3]==4);
01427     RakAssert(ml1[4]==5);
01428     RakAssert(ml1.GetIndexOf(1)==0);
01429     RakAssert(ml1.GetIndexOf(2)==1);
01430     RakAssert(ml1.GetIndexOf(3)==2);
01431     RakAssert(ml1.GetIndexOf(4)==3);
01432     RakAssert(ml1.GetIndexOf(5)==4);
01433     ml1.Clear(_FILE_AND_LINE_);
01434 
01435     DataStructures::Multilist<ML_STACK, int> ml2;
01436     ml2.Reallocate(64);
01437     RakAssert(ml2.IsEmpty());
01438     ml2.Push(53);
01439     RakAssert(ml2.Peek()==53);
01440     RakAssert(ml2.IsEmpty()==false);
01441     RakAssert(ml2.Pop()==53);
01442     RakAssert(ml2.IsEmpty()==true);
01443     for (int i=0; i < 512; i++)
01444     ml2.Push(i);
01445     RakAssert(ml2.GetIndexOf(200)==200);
01446     RakAssert(ml2.PeekOpposite()==0);
01447     RakAssert(ml2.PopOpposite()==0);
01448     RakAssert(ml2.PeekOpposite()==1);
01449     RakAssert(ml2.Peek()==511);
01450     ml2.ReverseList();
01451     for (int i=0; i < 511; i++)
01452     RakAssert(ml2[i]==511-i);
01453     RakAssert(ml2.PeekOpposite()==511);
01454     RakAssert(ml2.Peek()==1);
01455     oldSize = ml2.GetSize();
01456     ml2.RemoveAtIndex(0);
01457     RakAssert(ml2.GetSize()==oldSize-1);
01458     RakAssert(ml2.Peek()==1);
01459     RakAssert(ml2.PeekOpposite()==510);
01460     ml2.Clear(_FILE_AND_LINE_);
01461     RakAssert(ml2.IsEmpty()==true);
01462 
01463     DataStructures::Multilist<ML_QUEUE, int> ml3;
01464     RakAssert(ml3.IsEmpty());
01465     ml3.Push(53);
01466     RakAssert(ml3.Peek()==53);
01467     RakAssert(ml3.IsEmpty()==false);
01468     RakAssert(ml3.Pop()==53);
01469     RakAssert(ml3.IsEmpty()==true);
01470     for (int i=0; i < 512; i++)
01471     ml3.Push(i);
01472     RakAssert(ml3.GetIndexOf(200)==200);
01473     RakAssert(ml3.PeekOpposite()==511);
01474     RakAssert(ml3.PopOpposite()==511);
01475     RakAssert(ml3.PeekOpposite()==510);
01476     RakAssert(ml3.Peek()==0);
01477     ml3.ReverseList();
01478     for (int i=0; i < 511; i++)
01479     RakAssert(ml3[i]==511-1-i);
01480     RakAssert(ml3.PeekOpposite()==0);
01481     RakAssert(ml3.Peek()==510);
01482     oldSize = ml3.GetSize();
01483     ml3.RemoveAtIndex(0);
01484     RakAssert(ml3.GetSize()==oldSize-1);
01485     RakAssert(ml3.Peek()==509);
01486     RakAssert(ml3.PeekOpposite()==0);
01487     ml3.Clear(_FILE_AND_LINE_);
01488     RakAssert(ml3.IsEmpty()==true);
01489 
01490     ml3.PushOpposite(100);
01491     ml3.PushOpposite(50);
01492     ml3.PushOpposite(150);
01493     ml3.PushOpposite(25);
01494     ml3.PushOpposite(175);
01495     ml3.Sort(true);
01496     RakAssert(ml3[0]==25);
01497     RakAssert(ml3[1]==50);
01498     RakAssert(ml3[2]==100);
01499     RakAssert(ml3[3]==150);
01500     RakAssert(ml3[4]==175);
01501     RakAssert(ml3.GetIndexOf(25)==0);
01502     RakAssert(ml3.GetIndexOf(50)==1);
01503     RakAssert(ml3.GetIndexOf(100)==2);
01504     RakAssert(ml3.GetIndexOf(150)==3);
01505     RakAssert(ml3.GetIndexOf(175)==4);
01506     ml3.Clear(_FILE_AND_LINE_);
01507 
01508     ml3.PushOpposite(1);
01509     ml3.PushOpposite(2);
01510     ml3.PushOpposite(3);
01511     ml3.PushOpposite(4);
01512     ml3.PushOpposite(5);
01513     ml3.Sort(true);
01514     RakAssert(ml3[0]==1);
01515     RakAssert(ml3[1]==2);
01516     RakAssert(ml3[2]==3);
01517     RakAssert(ml3[3]==4);
01518     RakAssert(ml3[4]==5);
01519     RakAssert(ml3.GetIndexOf(1)==0);
01520     RakAssert(ml3.GetIndexOf(2)==1);
01521     RakAssert(ml3.GetIndexOf(3)==2);
01522     RakAssert(ml3.GetIndexOf(4)==3);
01523     RakAssert(ml3.GetIndexOf(5)==4);
01524     ml3.Clear(_FILE_AND_LINE_);
01525 
01526     ml3.PushOpposite(5);
01527     ml3.PushOpposite(4);
01528     ml3.PushOpposite(3);
01529     ml3.PushOpposite(2);
01530     ml3.PushOpposite(1);
01531     ml3.Sort(true);
01532     RakAssert(ml3[0]==1);
01533     RakAssert(ml3[1]==2);
01534     RakAssert(ml3[2]==3);
01535     RakAssert(ml3[3]==4);
01536     RakAssert(ml3[4]==5);
01537     RakAssert(ml3.GetIndexOf(1)==0);
01538     RakAssert(ml3.GetIndexOf(2)==1);
01539     RakAssert(ml3.GetIndexOf(3)==2);
01540     RakAssert(ml3.GetIndexOf(4)==3);
01541     RakAssert(ml3.GetIndexOf(5)==4);
01542     ml3.Sort(true);
01543     RakAssert(ml3[0]==1);
01544     RakAssert(ml3[1]==2);
01545     RakAssert(ml3[2]==3);
01546     RakAssert(ml3[3]==4);
01547     RakAssert(ml3[4]==5);
01548     RakAssert(ml3.GetIndexOf(1)==0);
01549     RakAssert(ml3.GetIndexOf(2)==1);
01550     RakAssert(ml3.GetIndexOf(3)==2);
01551     RakAssert(ml3.GetIndexOf(4)==3);
01552     RakAssert(ml3.GetIndexOf(5)==4);
01553 
01554     ml3.SetSortOrder(false);
01555     ml3.Sort(false);
01556     RakAssert(ml3[0]==5);
01557     RakAssert(ml3[1]==4);
01558     RakAssert(ml3[2]==3);
01559     RakAssert(ml3[3]==2);
01560     RakAssert(ml3[4]==1);
01561     RakAssert(ml3.GetIndexOf(1)==4);
01562     RakAssert(ml3.GetIndexOf(2)==3);
01563     RakAssert(ml3.GetIndexOf(3)==2);
01564     RakAssert(ml3.GetIndexOf(4)==1);
01565     RakAssert(ml3.GetIndexOf(5)==0);
01566 
01567     ml3.Clear(_FILE_AND_LINE_);
01568 
01569     DataStructures::Multilist<ML_ORDERED_LIST, int> ml4;
01570     ml4.Reallocate(64);
01571     RakAssert(ml4.IsEmpty());
01572     ml4.Push(53);
01573     RakAssert(ml4.Peek()==53);
01574     RakAssert(ml4.IsEmpty()==false);
01575     RakAssert(ml4.Pop()==53);
01576     RakAssert(ml4.IsEmpty()==true);
01577     for (int i=0; i < 512; i++)
01578     ml4.Push(i);
01579     RakAssert(ml4.GetIndexOf(200)==200);
01580     RakAssert(ml4.PeekOpposite()==0);
01581     RakAssert(ml4.PopOpposite()==0);
01582     RakAssert(ml4.PeekOpposite()==1);
01583     RakAssert(ml4.Peek()==511);
01584     ml4.ReverseList();
01585     for (int i=0; i < 511; i++)
01586     RakAssert(ml4[i]==511-i);
01587     RakAssert(ml4.PeekOpposite()==511);
01588     RakAssert(ml4.Peek()==1);
01589     oldSize = ml4.GetSize();
01590     ml4.RemoveAtIndex(0);
01591     RakAssert(ml4.GetSize()==oldSize-1);
01592     RakAssert(ml4.Peek()==1);
01593     RakAssert(ml4.PeekOpposite()==510);
01594     ml4.Clear(_FILE_AND_LINE_);
01595     RakAssert(ml4.IsEmpty()==true);
01596 
01597     DataStructures::Multilist<ML_ORDERED_LIST, KeyAndValue*, int> ml5;
01598 
01599     for (int i=0; i < 16; i++)
01600     {
01601         KeyAndValue *kav = new KeyAndValue;
01602         kav->key=i;
01603         kav->value=i+100;
01604         ml5.Push(kav,kav->key);
01605     }
01606 
01607     RakAssert(ml5.GetIndexOf(0)==0);
01608     RakAssert(ml5.GetIndexOf(5)==5);
01609     RakAssert(ml5.GetIndexOf(15)==15);
01610     RakAssert(ml5.GetIndexOf(16)==-1);
01611     ml5.RemoveAtKey(0,true);
01612     RakAssert(ml5.GetIndexOf(1)==0);
01613     KeyAndValue *iPtr = ml5.GetPtr(5);
01614     RakAssert(iPtr);
01615     RakAssert(iPtr->value=105);
01616     iPtr = ml5.GetPtr(1234);
01617     RakAssert(iPtr==0);
01618     ml5.ForEach(DataStructures::DeletePtr<KeyAndValue*>);
01619 
01620 
01621     DataStructures::Multilist<ML_VARIABLE_DURING_RUNTIME, int> ml6;
01622     ml6.Push(2);
01623     ml6.Push(1);
01624     ml6.Push(6);
01625     ml6.Push(3);
01626     RakAssert(ml6.Peek()==3);
01627     ml6.SetMultilistType(ML_STACK);
01628     RakAssert(ml6.Peek()==3);
01629     ml6.SetMultilistType(ML_QUEUE);
01630     RakAssert(ml6.Peek()==2);
01631     ml6.SetMultilistType(ML_ORDERED_LIST);
01632     RakAssert(ml6.Peek()=6);
01633     ml6.SetMultilistType(ML_STACK);
01634     RakAssert(ml6.Peek()==6);
01635     ml6.SetMultilistType(ML_QUEUE);
01636     RakAssert(ml6.Peek()==1);
01637 }
01638 
01639 #ifdef _MSC_VER
01640 #pragma warning( pop )
01641 #endif
01642 */
01643 
01644 #endif