RakNet: DS_Multilist.h Source File

Go to the documentation of this file.
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__, __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__,__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__, __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__, __LINE__);
01101                 uniqueToSource1.Clear(true,__FILE__, __LINE__);
01102                 uniqueToSource2.Clear(true,__FILE__, __LINE__);
01103                 
01104                 while (index1 < source1.GetSize() && index2 < source2.GetSize())
01105                 {
01106                         if (source1[index1]<source2[index2])
01107                         {
01108                                 uniqueToSource1.Push(source1[index1],__FILE__,__LINE__);
01109                                 index1++;
01110                         }
01111                         else if (source1[index1]==source2[index2])
01112                         {
01113                                 intersection.Push(source1[index1],__FILE__,__LINE__);
01114                                 index1++;
01115                                 index2++;
01116                         }
01117                         else
01118                         {
01119                                 uniqueToSource2.Push(source2[index2],__FILE__,__LINE__);
01120                                 index2++;
01121                         }
01122                 }
01123                 while (index1 < source1.GetSize())
01124                 {
01125                         uniqueToSource1.Push(source1[index1],__FILE__,__LINE__);
01126                         index1++;
01127                 }
01128                 while (index2 < source2.GetSize())
01129                 {
01130                         uniqueToSource2.Push(source2[index2],__FILE__,__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__, __LINE__);
01351         RakAssert(ml1.IsEmpty()==true);
01352 
01353         ml1.Sort(true);
01354         ml1.Clear(__FILE__, __LINE__);
01355 
01356         ml1.Push(100);
01357         ml1.Sort(true);
01358         ml1.Clear(__FILE__, __LINE__);
01359 
01360         ml1.Push(50);
01361         ml1.Push(100);
01362         ml1.Sort(true);
01363         ml1.Clear(__FILE__, __LINE__);
01364 
01365         ml1.Push(100);
01366         ml1.Push(50);
01367         ml1.Sort(true);
01368         ml1.Clear(__FILE__, __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__, __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__, __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__, __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__, __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__, __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__, __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__, __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__, __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__, __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