1 /// \file DS_Multilist.h 2 /// \internal 3 /// \brief ADT that can represent an unordered list, ordered list, stack, or queue with a common interface 4 /// 5 /// This file is part of RakNet Copyright 2003 Jenkins Software LLC 6 /// 7 /// Raknet is available under the terms of the GPLv3 license, see /usr/local/share/licenses/raknet-3.9.2_10,1/GPLv3. 8 9 10 #ifndef __MULTILIST_H 11 #define __MULTILIST_H 12 13 #include "RakAssert.h" 14 #include <string.h> // memmove 15 #include "Export.h" 16 #include "RakMemoryOverride.h" 17 #include "NativeTypes.h" 18 19 20 #ifdef _MSC_VER 21 #pragma warning( push ) 22 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant 23 #pragma warning( disable : 4512 ) // warning C4512: assignment operator could not be generated 24 #endif 25 26 /// What algorithm to use to store the data for the Multilist 27 enum MultilistType 28 { 29 /// Removing from the middle of the list will swap the end of the list rather than shift the elements. Push and Pop operate on the tail. 30 ML_UNORDERED_LIST, 31 /// A normal list, with the list order preserved. Push and Pop operate on the tail. 32 ML_STACK, 33 /// A queue. Push and Pop operate on the head 34 ML_QUEUE, 35 /// A list that is always kept in order. Elements must be unique, and compare against each other consistently using <, ==, and > 36 ML_ORDERED_LIST, 37 /// A list whose type can change at runtime 38 ML_VARIABLE_DURING_RUNTIME 39 }; 40 41 /// The namespace DataStructures was only added to avoid compiler errors for commonly named data structures 42 /// As these data structures are stand-alone, you can use them outside of RakNet for your own projects if you wish. 43 namespace DataStructures 44 { 45 /// Can be used with Multilist::ForEach 46 /// Assuming the Multilist holds pointers, will delete those pointers 47 template <class templateType> DeletePtr_RakNet(templateType & ptr,const char * file,unsigned int line)48 void DeletePtr_RakNet(templateType &ptr, const char *file, unsigned int line ) {RakNet::OP_DELETE(ptr, file, line);} 49 50 /// Can be used with Multilist::ForEach 51 /// Assuming the Multilist holds pointers, will delete those pointers 52 template <class templateType> DeletePtr(templateType & ptr)53 void DeletePtr(templateType &ptr) {delete ptr;} 54 55 /// The following is invalid. 56 /// bool operator<( const MyClass *myClass, const int &inputKey ) {return myClass->value < inputKey;} 57 /// At least one type has to be a reference to a class 58 /// MLKeyRef is a helper class to turn a native type into a class, so you can compare that native type against a pointer to a different class 59 /// Used for he Multilist, when _DataType != _KeyType 60 template < class templateType > 61 class MLKeyRef 62 { 63 public: MLKeyRef(const templateType & input)64 MLKeyRef(const templateType& input) : val(input) {} Get(void)65 const templateType &Get(void) const {return val;} 66 bool operator<( const templateType &right ) {return val < right;} 67 bool operator>( const templateType &right ) {return val > right;} 68 bool operator==( const templateType &right ) {return val == right;} 69 protected: 70 const templateType &val; 71 }; 72 73 /// For the Multilist, when _DataType != _KeyType, you must define the comparison operators between the key and the data 74 /// This is non-trivial due to the need to use MLKeyRef in case the type held is a pointer to a structure or class and the key type is not a class 75 /// For convenience, this macro will implement the comparison operators under the following conditions 76 /// 1. _DataType is a pointer to a class or structure 77 /// 2. The key is a member variable of _DataType 78 #define DEFINE_MULTILIST_PTR_TO_MEMBER_COMPARISONS( _CLASS_NAME_, _KEY_TYPE_, _MEMBER_VARIABLE_NAME_ ) \ 79 bool operator<( const DataStructures::MLKeyRef<_KEY_TYPE_> &inputKey, const _CLASS_NAME_ *cls ) {return inputKey.Get() < cls->_MEMBER_VARIABLE_NAME_;} \ 80 bool operator>( const DataStructures::MLKeyRef<_KEY_TYPE_> &inputKey, const _CLASS_NAME_ *cls ) {return inputKey.Get() > cls->_MEMBER_VARIABLE_NAME_;} \ 81 bool operator==( const DataStructures::MLKeyRef<_KEY_TYPE_> &inputKey, const _CLASS_NAME_ *cls ) {return inputKey.Get() == cls->_MEMBER_VARIABLE_NAME_;} 82 83 typedef uint32_t DefaultIndexType; 84 85 /// \brief The multilist, representing an abstract data type that generally holds lists. 86 /// \param[in] _MultilistType What type of list this is, \sa MultilistType 87 /// \param[in] _DataType What type of data this list holds. 88 /// \param[in] _KeyType If a function takes a key to sort on, what type of key this is. The comparison operator between _DataType and _KeyType must be defined 89 /// \param[in] _IndexType What variable type to use for indices 90 template <const MultilistType _MultilistType, class _DataType, class _KeyType=_DataType, class _IndexType=DefaultIndexType> 91 class RAK_DLL_EXPORT Multilist 92 { 93 public: 94 Multilist(); 95 ~Multilist(); 96 Multilist( const Multilist& source ); 97 Multilist& operator= ( const Multilist& source ); 98 _DataType& operator[] ( const _IndexType position ) const; 99 /// Unordered list, stack is LIFO 100 /// QUEUE is FIFO 101 /// Ordered list is inserted in order 102 void Push(const _DataType &d, const char *file=__FILE__, unsigned int line=__LINE__ ); 103 void Push(const _DataType &d, const _KeyType &key, const char *file=__FILE__, unsigned int line=__LINE__ ); 104 105 /// \brief Gets or removes and gets an element from the list, according to the same rules as Push(). 106 /// Ordered list is LIFO for the purposes of Pop and Peek. 107 _DataType &Pop(const char *file=__FILE__, unsigned int line=__LINE__); 108 _DataType &Peek(void) const; 109 110 /// \brief Same as Push(), except FIFO and LIFO are reversed. 111 /// Ordered list still inserts in order. 112 void PushOpposite(const _DataType &d, const char *file=__FILE__, unsigned int line=__LINE__ ); 113 void PushOpposite(const _DataType &d, const _KeyType &key, const char *file=__FILE__, unsigned int line=__LINE__ ); 114 115 /// \brief Same as Pop() and Peek(), except FIFO and LIFO are reversed. 116 _DataType &PopOpposite(const char *file=__FILE__, unsigned int line=__LINE__); 117 _DataType &PeekOpposite(void) const; 118 119 /// \brief Stack,Queue: Inserts at index indicated, elements are shifted. 120 /// Ordered list: Inserts, position is ignored 121 void InsertAtIndex(const _DataType &d, _IndexType index, const char *file=__FILE__, unsigned int line=__LINE__); 122 123 /// \brief Unordered list, removes at index indicated, swaps last element with that element. 124 /// Otherwise, array is shifted left to overwrite removed element 125 /// \details Index[0] returns the same as Pop() for a queue. 126 /// Same as PopOpposite() for the list and ordered list 127 void RemoveAtIndex(_IndexType position, const char *file=__FILE__, unsigned int line=__LINE__); 128 129 /// \brief Find the index of \a key, and remove at that index. 130 bool RemoveAtKey(_KeyType key, bool assertIfDoesNotExist, const char *file=__FILE__, unsigned int line=__LINE__); 131 132 /// \brief Finds the index of \a key. Return -1 if the key is not found. 133 _IndexType GetIndexOf(_KeyType key) const; 134 135 /// \brief Returns where in the list we should insert the item, to preserve list order. 136 /// Returns -1 if the item is already in the list 137 _IndexType GetInsertionIndex(_KeyType key) const; 138 139 /// \brief Finds the index of \a key. Return 0 if the key is not found. Useful if _DataType is always non-zero pointers. 140 _DataType GetPtr(_KeyType key) const; 141 142 /// \brief Iterate over the list, calling the function pointer on each element. 143 void ForEach(void (*func)(_DataType &item, const char *file, unsigned int line), const char *file, unsigned int line); 144 void ForEach(void (*func)(_DataType &item)); 145 146 /// \brief Returns if the list is empty. 147 bool IsEmpty(void) const; 148 149 /// \brief Returns the number of elements used in the list. 150 _IndexType GetSize(void) const; 151 152 /// \brief Empties the list. The list is not deallocated if it is small, 153 /// unless \a deallocateSmallBlocks is true 154 void Clear( bool deallocateSmallBlocks=true, const char *file=__FILE__, unsigned int line=__LINE__ ); 155 156 /// \brief Empties the list, first calling RakNet::OP_Delete on all items. 157 /// \details The list is not deallocated if it is small, unless \a deallocateSmallBlocks is true 158 void ClearPointers( bool deallocateSmallBlocks=true, const char *file=__FILE__, unsigned int line=__LINE__ ); 159 160 /// \brief Empty one item from the list, first calling RakNet::OP_Delete on that item. 161 void ClearPointer( _KeyType key, const char *file=__FILE__, unsigned int line=__LINE__ ); 162 163 /// \brief Reverses the elements in the list, and flips the sort order 164 /// returned by GetSortOrder() if IsSorted() returns true at the time the function is called 165 void ReverseList(void); 166 167 /// \brief Reallocates the list to a larger size. 168 /// If \a size is smaller than the value returned by GetSize(), the call does nothing. 169 void Reallocate(_IndexType size, const char *file=__FILE__, unsigned int line=__LINE__); 170 171 /// \brief Sorts the list unless it is an ordered list, in which it does nothing as the list is assumed to already be sorted. 172 /// \details However, if \a force is true, it will also resort the ordered list, useful if the comparison operator between _KeyType and _DataType would now return different results 173 /// Once the list is sorted, further operations to lookup by key will be log2(n) until the list is modified 174 void Sort(bool force); 175 176 /// \brief Sets the list to be remembered as sorted. 177 /// \details Optimization if the source is sorted already 178 void TagSorted(void); 179 180 /// \brief Defaults to ascending. 181 /// \details Used by Sort(), and by ML_ORDERED_LIST 182 void SetSortOrder(bool ascending); 183 184 /// \brief Returns true if ascending. 185 bool GetSortOrder(void) const; 186 187 /// \brief Returns true if the list is currently believed to be in a sorted state. 188 /// \details Doesn't actually check for sortedness, just if Sort() 189 /// was recently called, or MultilistType is ML_ORDERED_LIST 190 bool IsSorted(void) const; 191 192 /// Returns what type of list this is 193 MultilistType GetMultilistType(void) const; 194 195 /// \brief Changes what type of list this is. 196 /// \pre Template must be defined with ML_VARIABLE_DURING_RUNTIME for this to do anything 197 /// \param[in] mlType Any value of the enum MultilistType, except ML_VARIABLE_DURING_RUNTIME 198 void SetMultilistType(MultilistType newType); 199 200 /// \brief Returns the intersection of two lists. 201 /// Intersection is items common to both lists. 202 static void FindIntersection( 203 Multilist& source1, 204 Multilist& source2, 205 Multilist& intersection, 206 Multilist& uniqueToSource1, 207 Multilist& uniqueToSource2); 208 209 protected: 210 void ReallocateIfNeeded(const char *file, unsigned int line); 211 void DeallocateIfNeeded(const char *file, unsigned int line); 212 void ReallocToSize(_IndexType newAllocationSize, const char *file, unsigned int line); 213 void ReverseListInternal(void); 214 void InsertInOrderedList(const _DataType &d, const _KeyType &key); 215 _IndexType GetIndexFromKeyInSortedList(const _KeyType &key, bool *objectExists) const; 216 void InsertShiftArrayRight(const _DataType &d, _IndexType index); 217 void DeleteShiftArrayLeft(_IndexType index); 218 void QSortAscending(_IndexType left, _IndexType right); 219 void QSortDescending(_IndexType left, _IndexType right); 220 void CopySource( const Multilist& source ); 221 222 /// An array of user values 223 _DataType* data; 224 225 /// Number of elements in the list 226 _IndexType dataSize; 227 228 /// Size of \a array 229 _IndexType allocationSize; 230 231 /// Array index for the head of the queue 232 _IndexType queueHead; 233 234 /// Array index for the tail of the queue 235 _IndexType queueTail; 236 237 /// How many bytes the user chose to preallocate 238 /// Won't automatically deallocate below this 239 _IndexType preallocationSize; 240 241 enum 242 { 243 ML_UNSORTED, 244 ML_SORTED_ASCENDING, 245 ML_SORTED_DESCENDING 246 } sortState; 247 248 bool ascendingSort; 249 250 // In case we are using the variable type multilist 251 MultilistType variableMultilistType; 252 }; 253 254 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Multilist()255 Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Multilist() 256 { 257 data=0; 258 dataSize=0; 259 allocationSize=0; 260 ascendingSort=true; 261 sortState=ML_UNSORTED; 262 queueHead=0; 263 queueTail=0; 264 preallocationSize=0; 265 266 if (_MultilistType==ML_ORDERED_LIST) 267 sortState=ML_SORTED_ASCENDING; 268 else 269 sortState=ML_UNSORTED; 270 271 if (_MultilistType==ML_VARIABLE_DURING_RUNTIME) 272 variableMultilistType=ML_UNORDERED_LIST; 273 } 274 275 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ~Multilist()276 Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::~Multilist() 277 { 278 if (data!=0) 279 RakNet::OP_DELETE_ARRAY(data, __FILE__, __LINE__); 280 } 281 282 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Multilist(const Multilist & source)283 Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Multilist( const Multilist& source ) 284 { 285 CopySource(source); 286 } 287 288 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> 289 Multilist<_MultilistType, _DataType, _KeyType, _IndexType>& Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::operator= ( const Multilist& source ) 290 { 291 Clear(true); 292 CopySource(source); 293 return *this; 294 } 295 296 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> CopySource(const Multilist & source)297 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::CopySource( const Multilist& source ) 298 { 299 dataSize=source.GetSize(); 300 ascendingSort=source.ascendingSort; 301 sortState=source.sortState; 302 queueHead=0; 303 queueTail=dataSize; 304 preallocationSize=source.preallocationSize; 305 variableMultilistType=source.variableMultilistType; 306 if (source.data==0) 307 { 308 data=0; 309 allocationSize=0; 310 } 311 else 312 { 313 allocationSize=dataSize; 314 data = RakNet::OP_NEW_ARRAY<_DataType>(dataSize,__FILE__,__LINE__); 315 _IndexType i; 316 for (i=0; i < dataSize; i++) 317 data[i]=source[i]; 318 } 319 } 320 321 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> 322 _DataType& Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::operator[] ( const _IndexType position ) const 323 { 324 RakAssert(position<GetSize()); 325 326 if (GetMultilistType()==ML_QUEUE) 327 { 328 if ( queueHead + position >= allocationSize ) 329 return data[ queueHead + position - allocationSize ]; 330 else 331 return data[ queueHead + position ]; 332 } 333 334 return data[position]; 335 } 336 337 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Push(const _DataType & d,const char * file,unsigned int line)338 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Push(const _DataType &d, const char *file, unsigned int line ) 339 { 340 Push(d,d,file,line); 341 } 342 343 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Push(const _DataType & d,const _KeyType & key,const char * file,unsigned int line)344 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Push(const _DataType &d, const _KeyType &key, const char *file, unsigned int line ) 345 { 346 ReallocateIfNeeded(file,line); 347 348 if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK) 349 { 350 data[dataSize]=d; 351 dataSize++; 352 } 353 else if (GetMultilistType()==ML_QUEUE) 354 { 355 data[queueTail++] = d; 356 357 if ( queueTail == allocationSize ) 358 queueTail = 0; 359 dataSize++; 360 } 361 else 362 { 363 RakAssert(GetMultilistType()==ML_ORDERED_LIST); 364 InsertInOrderedList(d,key); 365 } 366 367 if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_QUEUE) 368 { 369 // Break sort if no longer sorted 370 if (sortState!=ML_UNSORTED && dataSize>1) 371 { 372 if (ascendingSort) 373 { 374 if ( MLKeyRef<_KeyType>(key) < operator[](dataSize-2) ) 375 sortState=ML_UNSORTED; 376 } 377 else 378 { 379 if ( MLKeyRef<_KeyType>(key) > operator[](dataSize-2) ) 380 sortState=ML_UNSORTED; 381 } 382 383 sortState=ML_UNSORTED; 384 } 385 } 386 } 387 388 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Pop(const char * file,unsigned int line)389 _DataType &Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Pop(const char *file, unsigned int line) 390 { 391 RakAssert(IsEmpty()==false); 392 DeallocateIfNeeded(file,line); 393 if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST) 394 { 395 dataSize--; 396 return data[dataSize]; 397 } 398 else 399 { 400 RakAssert(GetMultilistType()==ML_QUEUE); 401 402 if ( ++queueHead == allocationSize ) 403 queueHead = 0; 404 405 if ( queueHead == 0 ) 406 return data[ allocationSize -1 ]; 407 408 dataSize--; 409 return data[ queueHead -1 ]; 410 } 411 } 412 413 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Peek(void)414 _DataType &Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Peek(void) const 415 { 416 RakAssert(IsEmpty()==false); 417 if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST) 418 { 419 return data[dataSize-1]; 420 } 421 else 422 { 423 RakAssert(GetMultilistType()==ML_QUEUE); 424 return data[ queueHead ]; 425 } 426 } 427 428 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> PushOpposite(const _DataType & d,const char * file,unsigned int line)429 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::PushOpposite(const _DataType &d, const char *file, unsigned int line ) 430 { 431 PushOpposite(d,d,file,line); 432 } 433 434 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> PushOpposite(const _DataType & d,const _KeyType & key,const char * file,unsigned int line)435 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::PushOpposite(const _DataType &d, const _KeyType &key, const char *file, unsigned int line ) 436 { 437 ReallocateIfNeeded(file,line); 438 439 // Unordered list Push at back 440 if (GetMultilistType()==ML_UNORDERED_LIST) 441 { 442 data[dataSize]=d; 443 dataSize++; 444 } 445 else if (GetMultilistType()==ML_STACK) 446 { 447 // Stack push at front of the list, instead of back as normal 448 InsertAtIndex(d,0,file,line); 449 } 450 else if (GetMultilistType()==ML_QUEUE) 451 { 452 // Queue push at front of the list, instead of back as normal 453 InsertAtIndex(d,0,file,line); 454 } 455 else 456 { 457 RakAssert(GetMultilistType()==ML_ORDERED_LIST); 458 InsertInOrderedList(d,key); 459 } 460 461 if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_QUEUE) 462 { 463 // Break sort if no longer sorted 464 if (sortState!=ML_UNSORTED && dataSize>1) 465 { 466 if (ascendingSort) 467 { 468 if ( MLKeyRef<_KeyType>(key) > operator[](1) ) 469 sortState=ML_UNSORTED; 470 } 471 else 472 { 473 if ( MLKeyRef<_KeyType>(key) < operator[](1) ) 474 sortState=ML_UNSORTED; 475 } 476 } 477 } 478 } 479 480 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> PopOpposite(const char * file,unsigned int line)481 _DataType &Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::PopOpposite(const char *file, unsigned int line) 482 { 483 RakAssert(IsEmpty()==false); 484 if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST) 485 { 486 // Copy leftmost to end 487 ReallocateIfNeeded(file,line); 488 data[dataSize]=data[0]; 489 DeleteShiftArrayLeft(0); 490 --dataSize; 491 // Assuming still leaves at least one element past the end of the list allocated 492 DeallocateIfNeeded(file,line); 493 // Return end 494 return data[dataSize+1]; 495 } 496 else 497 { 498 RakAssert(GetMultilistType()==ML_QUEUE); 499 // Deallocate first, since we are returning off the existing list 500 DeallocateIfNeeded(file,line); 501 dataSize--; 502 503 if (queueTail==0) 504 queueTail=allocationSize-1; 505 else 506 --queueTail; 507 508 return data[queueTail]; 509 } 510 } 511 512 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> PeekOpposite(void)513 _DataType &Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::PeekOpposite(void) const 514 { 515 RakAssert(IsEmpty()==false); 516 if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST) 517 { 518 return data[0]; 519 } 520 else 521 { 522 RakAssert(GetMultilistType()==ML_QUEUE); 523 _IndexType priorIndex; 524 if (queueTail==0) 525 priorIndex=allocationSize-1; 526 else 527 priorIndex=queueTail-1; 528 529 return data[priorIndex]; 530 } 531 } 532 533 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> InsertAtIndex(const _DataType & d,_IndexType index,const char * file,unsigned int line)534 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::InsertAtIndex(const _DataType &d, _IndexType index, const char *file, unsigned int line) 535 { 536 ReallocateIfNeeded(file,line); 537 538 if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST) 539 { 540 if (index>=dataSize) 541 { 542 // insert at end 543 data[dataSize]=d; 544 545 dataSize++; 546 } 547 else 548 { 549 // insert at index 550 InsertShiftArrayRight(d,index); 551 } 552 } 553 else 554 { 555 data[queueTail++] = d; 556 557 if ( queueTail == allocationSize ) 558 queueTail = 0; 559 560 ++dataSize; 561 562 if (dataSize==1) 563 return; 564 565 _IndexType writeIndex, readIndex, trueWriteIndex, trueReadIndex; 566 writeIndex=dataSize-1; 567 readIndex=writeIndex-1; 568 while (readIndex >= index) 569 { 570 if ( queueHead + writeIndex >= allocationSize ) 571 trueWriteIndex = queueHead + writeIndex - allocationSize; 572 else 573 trueWriteIndex = queueHead + writeIndex; 574 575 if ( queueHead + readIndex >= allocationSize ) 576 trueReadIndex = queueHead + readIndex - allocationSize; 577 else 578 trueReadIndex = queueHead + readIndex; 579 580 data[trueWriteIndex]=data[trueReadIndex]; 581 582 if (readIndex==0) 583 break; 584 writeIndex--; 585 readIndex--; 586 } 587 588 if ( queueHead + index >= allocationSize ) 589 trueWriteIndex = queueHead + index - allocationSize; 590 else 591 trueWriteIndex = queueHead + index; 592 593 data[trueWriteIndex]=d; 594 } 595 596 if (_MultilistType!=ML_ORDERED_LIST) 597 sortState=ML_UNSORTED; 598 } 599 600 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> RemoveAtIndex(_IndexType position,const char * file,unsigned int line)601 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::RemoveAtIndex(_IndexType position, const char *file, unsigned int line) 602 { 603 RakAssert(position < dataSize); 604 RakAssert(IsEmpty()==false); 605 606 if (GetMultilistType()==ML_UNORDERED_LIST) 607 { 608 // Copy tail to current 609 data[position]=data[dataSize-1]; 610 } 611 else if (GetMultilistType()==ML_STACK || GetMultilistType()==ML_ORDERED_LIST) 612 { 613 DeleteShiftArrayLeft(position); 614 } 615 else 616 { 617 RakAssert(GetMultilistType()==ML_QUEUE); 618 619 _IndexType index, next; 620 621 if ( queueHead + position >= allocationSize ) 622 index = queueHead + position - allocationSize; 623 else 624 index = queueHead + position; 625 626 next = index + 1; 627 628 if ( next == allocationSize ) 629 next = 0; 630 631 while ( next != queueTail ) 632 { 633 // Overwrite the previous element 634 data[ index ] = data[ next ]; 635 index = next; 636 //next = (next + 1) % allocationSize; 637 638 if ( ++next == allocationSize ) 639 next = 0; 640 } 641 642 // Move the queueTail back 643 if ( queueTail == 0 ) 644 queueTail = allocationSize - 1; 645 else 646 --queueTail; 647 } 648 649 650 dataSize--; 651 DeallocateIfNeeded(file,line); 652 } 653 654 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> RemoveAtKey(_KeyType key,bool assertIfDoesNotExist,const char * file,unsigned int line)655 bool Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::RemoveAtKey(_KeyType key, bool assertIfDoesNotExist, const char *file, unsigned int line) 656 { 657 _IndexType index = GetIndexOf(key); 658 if (index==(_IndexType)-1) 659 { 660 RakAssert(assertIfDoesNotExist==false && "RemoveAtKey element not found"); 661 return false; 662 } 663 RemoveAtIndex(index,file,line); 664 return true; 665 } 666 667 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> GetIndexOf(_KeyType key)668 _IndexType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetIndexOf(_KeyType key) const 669 { 670 _IndexType i; 671 if (IsSorted()) 672 { 673 bool objectExists; 674 i=GetIndexFromKeyInSortedList(key, &objectExists); 675 if (objectExists) 676 return i; 677 return (_IndexType)-1; 678 } 679 else if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK) 680 { 681 for (i=0; i < dataSize; i++) 682 { 683 if (MLKeyRef<_KeyType>(key)==data[i]) 684 return i; 685 } 686 return (_IndexType)-1; 687 } 688 else 689 { 690 RakAssert( GetMultilistType()==ML_QUEUE ); 691 692 for (i=0; i < dataSize; i++) 693 { 694 if (MLKeyRef<_KeyType>(key)==operator[](i)) 695 return i; 696 } 697 return (_IndexType)-1; 698 } 699 } 700 701 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> GetInsertionIndex(_KeyType key)702 _IndexType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetInsertionIndex(_KeyType key) const 703 { 704 _IndexType i; 705 if (IsSorted()) 706 { 707 bool objectExists; 708 i=GetIndexFromKeyInSortedList(key, &objectExists); 709 if (objectExists) 710 return (_IndexType)-1; 711 return i; 712 } 713 else if (GetMultilistType()==ML_UNORDERED_LIST || GetMultilistType()==ML_STACK) 714 { 715 for (i=0; i < dataSize; i++) 716 { 717 if (MLKeyRef<_KeyType>(key)==data[i]) 718 return (_IndexType)-1; 719 } 720 return dataSize; 721 } 722 else 723 { 724 RakAssert( GetMultilistType()==ML_QUEUE ); 725 726 for (i=0; i < dataSize; i++) 727 { 728 if (MLKeyRef<_KeyType>(key)==operator[](i)) 729 return (_IndexType)-1; 730 } 731 return dataSize; 732 } 733 } 734 735 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> GetPtr(_KeyType key)736 _DataType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetPtr(_KeyType key) const 737 { 738 _IndexType i = GetIndexOf(key); 739 if (i==(_IndexType)-1) 740 return 0; 741 return data[i]; 742 } 743 744 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ForEach(void (* func)(_DataType & item,const char * file,unsigned int line),const char * file,unsigned int line)745 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ForEach(void (*func)(_DataType &item, const char *file, unsigned int line), const char *file, unsigned int line) 746 { 747 _IndexType i; 748 for (i=0; i < dataSize; i++) 749 func(operator[](i), file, line); 750 } 751 752 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ForEach(void (* func)(_DataType & item))753 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ForEach(void (*func)(_DataType &item)) 754 { 755 _IndexType i; 756 for (i=0; i < dataSize; i++) 757 func(operator[](i)); 758 } 759 760 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> IsEmpty(void)761 bool Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::IsEmpty(void) const 762 { 763 return dataSize==0; 764 } 765 766 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> GetSize(void)767 _IndexType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetSize(void) const 768 { 769 return dataSize; 770 } 771 772 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Clear(bool deallocateSmallBlocks,const char * file,unsigned int line)773 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Clear( bool deallocateSmallBlocks, const char *file, unsigned int line ) 774 { 775 dataSize=0; 776 if (GetMultilistType()==ML_ORDERED_LIST) 777 if (ascendingSort) 778 sortState=ML_SORTED_ASCENDING; 779 else 780 sortState=ML_SORTED_DESCENDING; 781 else 782 sortState=ML_UNSORTED; 783 queueHead=0; 784 queueTail=0; 785 786 if (deallocateSmallBlocks && allocationSize < 128 && data) 787 { 788 RakNet::OP_DELETE_ARRAY(data,file,line); 789 data=0; 790 allocationSize=0; 791 } 792 } 793 794 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ClearPointers(bool deallocateSmallBlocks,const char * file,unsigned int line)795 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ClearPointers( bool deallocateSmallBlocks, const char *file, unsigned int line ) 796 { 797 _IndexType i; 798 for (i=0; i < dataSize; i++) 799 RakNet::OP_DELETE(operator[](i), file, line); 800 Clear(deallocateSmallBlocks, file, line); 801 } 802 803 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ClearPointer(_KeyType key,const char * file,unsigned int line)804 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ClearPointer( _KeyType key, const char *file, unsigned int line ) 805 { 806 _IndexType i; 807 i = GetIndexOf(key); 808 if (i!=-1) 809 { 810 RakNet::OP_DELETE(operator[](i), file, line); 811 RemoveAtIndex(i); 812 } 813 } 814 815 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ReverseList(void)816 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ReverseList(void) 817 { 818 if (IsSorted()) 819 ascendingSort=!ascendingSort; 820 821 ReverseListInternal(); 822 } 823 824 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Reallocate(_IndexType size,const char * file,unsigned int line)825 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Reallocate(_IndexType size, const char *file, unsigned int line) 826 { 827 _IndexType newAllocationSize; 828 if (size < dataSize) 829 newAllocationSize=dataSize; 830 else 831 newAllocationSize=size; 832 preallocationSize=size; 833 ReallocToSize(newAllocationSize,file,line); 834 } 835 836 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> Sort(bool force)837 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::Sort(bool force) 838 { 839 if (IsSorted() && force==false) 840 return; 841 842 if (dataSize>1) 843 { 844 if (ascendingSort) 845 QSortAscending(0,dataSize-1); 846 else 847 QSortDescending(0,dataSize-1); 848 } 849 850 TagSorted(); 851 } 852 853 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> TagSorted(void)854 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::TagSorted(void) 855 { 856 if (ascendingSort) 857 sortState=ML_SORTED_ASCENDING; 858 else 859 sortState=ML_SORTED_DESCENDING; 860 } 861 862 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> QSortAscending(_IndexType leftEdge,_IndexType rightEdge)863 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::QSortAscending(_IndexType leftEdge, _IndexType rightEdge) 864 { 865 _DataType temp; 866 _IndexType left=leftEdge; 867 _IndexType right=rightEdge; 868 _IndexType pivotIndex=left++; 869 870 while (left<right) 871 { 872 if (data[left] <= data[pivotIndex]) 873 { 874 ++left; 875 } 876 else 877 { 878 temp=data[left]; 879 data[left]=data[right]; 880 data[right]=temp; 881 --right; 882 } 883 } 884 885 temp=data[pivotIndex]; 886 887 // Move pivot to center 888 if (data[left] > data[pivotIndex]) 889 { 890 --left; 891 892 data[pivotIndex]=data[left]; 893 data[left]=temp; 894 } 895 else 896 { 897 data[pivotIndex]=data[left]; 898 data[left]=temp; 899 900 --left; 901 } 902 903 if (left!=leftEdge) 904 QSortAscending(leftEdge, left); 905 906 if (right!=rightEdge) 907 QSortAscending(right, rightEdge); 908 } 909 910 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> QSortDescending(_IndexType leftEdge,_IndexType rightEdge)911 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::QSortDescending(_IndexType leftEdge, _IndexType rightEdge) 912 { 913 _DataType temp; 914 _IndexType left=leftEdge; 915 _IndexType right=rightEdge; 916 _IndexType pivotIndex=left++; 917 918 while (left<right) 919 { 920 if (data[left] >= data[pivotIndex]) 921 { 922 ++left; 923 } 924 else 925 { 926 temp=data[left]; 927 data[left]=data[right]; 928 data[right]=temp; 929 --right; 930 } 931 } 932 933 temp=data[pivotIndex]; 934 935 // Move pivot to center 936 if (data[left] < data[pivotIndex]) 937 { 938 --left; 939 940 data[pivotIndex]=data[left]; 941 data[left]=temp; 942 } 943 else 944 { 945 data[pivotIndex]=data[left]; 946 data[left]=temp; 947 948 --left; 949 } 950 951 if (left!=leftEdge) 952 QSortDescending(leftEdge, left); 953 954 if (right!=rightEdge) 955 QSortDescending(right, rightEdge); 956 } 957 958 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> SetSortOrder(bool ascending)959 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::SetSortOrder(bool ascending) 960 { 961 if (ascendingSort!=ascending && IsSorted()) 962 { 963 ascendingSort=ascending; 964 // List is sorted, and the sort order has changed. So reverse the list 965 ReverseListInternal(); 966 } 967 else 968 ascendingSort=ascending; 969 } 970 971 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> GetSortOrder(void)972 bool Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetSortOrder(void) const 973 { 974 return ascendingSort; 975 } 976 977 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> IsSorted(void)978 bool Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::IsSorted(void) const 979 { 980 return GetMultilistType()==ML_ORDERED_LIST || sortState!=ML_UNSORTED; 981 } 982 983 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> GetMultilistType(void)984 MultilistType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetMultilistType(void) const 985 { 986 if (_MultilistType==ML_VARIABLE_DURING_RUNTIME) 987 return variableMultilistType; 988 return _MultilistType; 989 } 990 991 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> SetMultilistType(MultilistType newType)992 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::SetMultilistType(MultilistType newType) 993 { 994 RakAssert(_MultilistType==ML_VARIABLE_DURING_RUNTIME); 995 switch (variableMultilistType) 996 { 997 case ML_UNORDERED_LIST: 998 switch (newType) 999 { 1000 case ML_UNORDERED_LIST: 1001 // No change 1002 break; 1003 case ML_STACK: 1004 // Same data format 1005 break; 1006 case ML_QUEUE: 1007 queueHead=0; 1008 queueTail=dataSize; 1009 break; 1010 case ML_ORDERED_LIST: 1011 Sort(false); 1012 break; 1013 } 1014 break; 1015 case ML_STACK: 1016 switch (newType) 1017 { 1018 case ML_UNORDERED_LIST: 1019 // Same data format 1020 break; 1021 case ML_STACK: 1022 // No change 1023 break; 1024 case ML_QUEUE: 1025 queueHead=0; 1026 queueTail=dataSize; 1027 break; 1028 case ML_ORDERED_LIST: 1029 Sort(false); 1030 break; 1031 } 1032 break; 1033 case ML_QUEUE: 1034 switch (newType) 1035 { 1036 case ML_UNORDERED_LIST: 1037 case ML_STACK: 1038 case ML_ORDERED_LIST: 1039 if (queueTail < queueHead) 1040 { 1041 // Realign data if wrapped 1042 ReallocToSize(dataSize, __FILE__, __LINE__); 1043 } 1044 else 1045 { 1046 // Else can just copy starting at head 1047 _IndexType i; 1048 for (i=0; i < dataSize; i++) 1049 data[i]=operator[](i); 1050 } 1051 if (newType==ML_ORDERED_LIST) 1052 Sort(false); 1053 break; 1054 case ML_QUEUE: 1055 // No change 1056 break; 1057 } 1058 break; 1059 case ML_ORDERED_LIST: 1060 switch (newType) 1061 { 1062 case ML_UNORDERED_LIST: 1063 case ML_STACK: 1064 case ML_QUEUE: 1065 // Same data format 1066 // Tag as sorted 1067 if (ascendingSort) 1068 sortState=ML_SORTED_ASCENDING; 1069 else 1070 sortState=ML_SORTED_DESCENDING; 1071 if (newType==ML_QUEUE) 1072 { 1073 queueHead=0; 1074 queueTail=dataSize; 1075 } 1076 break; 1077 case ML_ORDERED_LIST: 1078 // No change 1079 break; 1080 } 1081 break; 1082 } 1083 1084 variableMultilistType=newType; 1085 } 1086 1087 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> FindIntersection(Multilist & source1,Multilist & source2,Multilist & intersection,Multilist & uniqueToSource1,Multilist & uniqueToSource2)1088 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::FindIntersection( 1089 Multilist& source1, 1090 Multilist& source2, 1091 Multilist& intersection, 1092 Multilist& uniqueToSource1, 1093 Multilist& uniqueToSource2) 1094 { 1095 _IndexType index1=0, index2=0; 1096 source1.SetSortOrder(true); 1097 source2.SetSortOrder(true); 1098 source1.Sort(false); 1099 source2.Sort(false); 1100 intersection.Clear(true,__FILE__, __LINE__); 1101 uniqueToSource1.Clear(true,__FILE__, __LINE__); 1102 uniqueToSource2.Clear(true,__FILE__, __LINE__); 1103 1104 while (index1 < source1.GetSize() && index2 < source2.GetSize()) 1105 { 1106 if (source1[index1]<source2[index2]) 1107 { 1108 uniqueToSource1.Push(source1[index1],__FILE__,__LINE__); 1109 index1++; 1110 } 1111 else if (source1[index1]==source2[index2]) 1112 { 1113 intersection.Push(source1[index1],__FILE__,__LINE__); 1114 index1++; 1115 index2++; 1116 } 1117 else 1118 { 1119 uniqueToSource2.Push(source2[index2],__FILE__,__LINE__); 1120 index2++; 1121 } 1122 } 1123 while (index1 < source1.GetSize()) 1124 { 1125 uniqueToSource1.Push(source1[index1],__FILE__,__LINE__); 1126 index1++; 1127 } 1128 while (index2 < source2.GetSize()) 1129 { 1130 uniqueToSource2.Push(source2[index2],__FILE__,__LINE__); 1131 index2++; 1132 } 1133 } 1134 1135 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ReallocateIfNeeded(const char * file,unsigned int line)1136 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ReallocateIfNeeded(const char *file, unsigned int line) 1137 { 1138 if (dataSize<allocationSize) 1139 return; 1140 1141 _IndexType newAllocationSize; 1142 if (allocationSize<16) 1143 newAllocationSize=32; 1144 else if (allocationSize>65536) 1145 newAllocationSize=allocationSize+65536; 1146 else 1147 { 1148 newAllocationSize=allocationSize<<1; // * 2 1149 // Protect against underflow 1150 if (newAllocationSize < allocationSize) 1151 newAllocationSize=allocationSize+65536; 1152 } 1153 1154 ReallocToSize(newAllocationSize,file,line); 1155 } 1156 1157 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> DeallocateIfNeeded(const char * file,unsigned int line)1158 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::DeallocateIfNeeded(const char *file, unsigned int line) 1159 { 1160 if (allocationSize<512) 1161 return; 1162 if (dataSize >= allocationSize/3 ) 1163 return; 1164 if (dataSize <= preallocationSize ) 1165 return; 1166 1167 _IndexType newAllocationSize = dataSize<<1; // * 2 1168 1169 ReallocToSize(newAllocationSize,file,line); 1170 } 1171 1172 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ReallocToSize(_IndexType newAllocationSize,const char * file,unsigned int line)1173 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ReallocToSize(_IndexType newAllocationSize, const char *file, unsigned int line) 1174 { 1175 _DataType* newData = RakNet::OP_NEW_ARRAY<_DataType>(newAllocationSize,file,line); 1176 _IndexType i; 1177 for (i=0; i < dataSize; i++) 1178 newData[i]=operator[](i); 1179 if (dataSize>0) 1180 { 1181 RakNet::OP_DELETE_ARRAY(data,file,line); 1182 if (GetMultilistType()==ML_QUEUE) 1183 { 1184 queueHead=0; 1185 queueTail=dataSize; 1186 } 1187 } 1188 data=newData; 1189 allocationSize=newAllocationSize; 1190 } 1191 1192 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> ReverseListInternal(void)1193 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::ReverseListInternal(void) 1194 { 1195 _DataType temp; 1196 _IndexType i; 1197 for (i=0; i < dataSize/2; i++) 1198 { 1199 temp=operator[](i); 1200 operator[](i)=operator[](dataSize-1-i); 1201 operator[](dataSize-1-i)=temp; 1202 } 1203 } 1204 1205 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> InsertInOrderedList(const _DataType & d,const _KeyType & key)1206 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::InsertInOrderedList(const _DataType &d, const _KeyType &key) 1207 { 1208 RakAssert(GetMultilistType()==ML_ORDERED_LIST); 1209 1210 bool objectExists; 1211 _IndexType index; 1212 index = GetIndexFromKeyInSortedList(key, &objectExists); 1213 1214 // if (objectExists) 1215 // { 1216 // Ordered list only allows unique insertions 1217 // RakAssert("Duplicate insertion into ordered list" && false); 1218 // return; 1219 // } 1220 1221 if (index>=dataSize) 1222 { 1223 // insert at end 1224 data[dataSize]=d; 1225 dataSize++; 1226 } 1227 else 1228 { 1229 // insert at index 1230 InsertShiftArrayRight(d,index); 1231 } 1232 } 1233 1234 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> GetIndexFromKeyInSortedList(const _KeyType & key,bool * objectExists)1235 _IndexType Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::GetIndexFromKeyInSortedList(const _KeyType &key, bool *objectExists) const 1236 { 1237 RakAssert(IsSorted()); 1238 _IndexType index, upperBound, lowerBound; 1239 1240 if (dataSize==0) 1241 { 1242 *objectExists=false; 1243 return 0; 1244 } 1245 1246 upperBound=dataSize-1; 1247 lowerBound=0; 1248 index = dataSize/2; 1249 1250 #ifdef _MSC_VER 1251 #pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant 1252 #endif 1253 while (1) 1254 { 1255 if (MLKeyRef<_KeyType>(key) > operator[](index) ) 1256 { 1257 if (ascendingSort) 1258 lowerBound=index+1; 1259 else 1260 upperBound=index-1; 1261 } 1262 else if (MLKeyRef<_KeyType>(key) < operator[](index) ) 1263 { 1264 if (ascendingSort) 1265 upperBound=index-1; 1266 else 1267 lowerBound=index+1; 1268 } 1269 else 1270 { 1271 // == 1272 *objectExists=true; 1273 return index; 1274 } 1275 1276 index=lowerBound+(upperBound-lowerBound)/2; 1277 1278 if (lowerBound>upperBound || upperBound==(_IndexType)-1) 1279 { 1280 *objectExists=false; 1281 return lowerBound; // No match 1282 } 1283 } 1284 } 1285 1286 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> InsertShiftArrayRight(const _DataType & d,_IndexType index)1287 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::InsertShiftArrayRight(const _DataType &d, _IndexType index) 1288 { 1289 RakAssert(_MultilistType!=ML_QUEUE); 1290 1291 // Move the elements in the list to make room 1292 _IndexType i; 1293 for ( i = dataSize; i != index; i-- ) 1294 data[ i ] = data[ i - 1 ]; 1295 1296 // Insert the new item at the correct spot 1297 data[ index ] = d; 1298 1299 ++dataSize; 1300 } 1301 1302 template <const MultilistType _MultilistType, class _DataType, class _KeyType, class _IndexType> DeleteShiftArrayLeft(_IndexType index)1303 void Multilist<_MultilistType, _DataType, _KeyType, _IndexType>::DeleteShiftArrayLeft( _IndexType index ) 1304 { 1305 RakAssert(index < dataSize); 1306 RakAssert(_MultilistType!=ML_QUEUE); 1307 1308 _IndexType i; 1309 for ( i = index; i < dataSize-1; i++ ) 1310 data[i]=data[i+1]; 1311 } 1312 }; 1313 1314 /* 1315 struct KeyAndValue 1316 { 1317 int key; 1318 short value; 1319 }; 1320 1321 DEFINE_MULTILIST_PTR_TO_MEMBER_COMPARISONS(KeyAndValue,int,key) 1322 1323 void MultilistUnitTest(void) 1324 { 1325 DataStructures::DefaultIndexType oldSize; 1326 DataStructures::Multilist<ML_UNORDERED_LIST, int> ml1; 1327 ml1.Reallocate(64); 1328 RakAssert(ml1.IsEmpty()); 1329 ml1.Push(53); 1330 RakAssert(ml1.Peek()==53); 1331 RakAssert(ml1.IsEmpty()==false); 1332 RakAssert(ml1.Pop()==53); 1333 RakAssert(ml1.IsEmpty()==true); 1334 for (int i=0; i < 512; i++) 1335 ml1.Push(i); 1336 RakAssert(ml1.GetIndexOf(200)==200); 1337 RakAssert(ml1.PeekOpposite()==0); 1338 RakAssert(ml1.PopOpposite()==0); 1339 RakAssert(ml1.PeekOpposite()==1); 1340 RakAssert(ml1.Peek()==511); 1341 ml1.ReverseList(); 1342 for (int i=0; i < 511; i++) 1343 RakAssert(ml1[i]==511-i); 1344 RakAssert(ml1.PeekOpposite()==511); 1345 RakAssert(ml1.Peek()==1); 1346 oldSize = ml1.GetSize(); 1347 ml1.RemoveAtIndex(0); 1348 RakAssert(ml1.GetSize()==oldSize-1); 1349 RakAssert(ml1.PeekOpposite()==1); 1350 ml1.Clear(__FILE__, __LINE__); 1351 RakAssert(ml1.IsEmpty()==true); 1352 1353 ml1.Sort(true); 1354 ml1.Clear(__FILE__, __LINE__); 1355 1356 ml1.Push(100); 1357 ml1.Sort(true); 1358 ml1.Clear(__FILE__, __LINE__); 1359 1360 ml1.Push(50); 1361 ml1.Push(100); 1362 ml1.Sort(true); 1363 ml1.Clear(__FILE__, __LINE__); 1364 1365 ml1.Push(100); 1366 ml1.Push(50); 1367 ml1.Sort(true); 1368 ml1.Clear(__FILE__, __LINE__); 1369 1370 ml1.Push(100); 1371 ml1.Push(50); 1372 ml1.Push(150); 1373 ml1.Push(25); 1374 ml1.Push(175); 1375 ml1.Sort(true); 1376 RakAssert(ml1[0]==25); 1377 RakAssert(ml1[1]==50); 1378 RakAssert(ml1[2]==100); 1379 RakAssert(ml1[3]==150); 1380 RakAssert(ml1[4]==175); 1381 RakAssert(ml1.GetIndexOf(25)==0); 1382 RakAssert(ml1.GetIndexOf(50)==1); 1383 RakAssert(ml1.GetIndexOf(100)==2); 1384 RakAssert(ml1.GetIndexOf(150)==3); 1385 RakAssert(ml1.GetIndexOf(175)==4); 1386 ml1.Clear(__FILE__, __LINE__); 1387 1388 ml1.Push(1); 1389 ml1.Push(2); 1390 ml1.Push(3); 1391 ml1.Push(4); 1392 ml1.Push(5); 1393 ml1.Sort(true); 1394 RakAssert(ml1[0]==1); 1395 RakAssert(ml1[1]==2); 1396 RakAssert(ml1[2]==3); 1397 RakAssert(ml1[3]==4); 1398 RakAssert(ml1[4]==5); 1399 RakAssert(ml1.GetIndexOf(1)==0); 1400 RakAssert(ml1.GetIndexOf(2)==1); 1401 RakAssert(ml1.GetIndexOf(3)==2); 1402 RakAssert(ml1.GetIndexOf(4)==3); 1403 RakAssert(ml1.GetIndexOf(5)==4); 1404 ml1.Clear(__FILE__, __LINE__); 1405 1406 ml1.Push(5); 1407 ml1.Push(4); 1408 ml1.Push(3); 1409 ml1.Push(2); 1410 ml1.Push(1); 1411 ml1.Sort(true); 1412 RakAssert(ml1[0]==1); 1413 RakAssert(ml1[1]==2); 1414 RakAssert(ml1[2]==3); 1415 RakAssert(ml1[3]==4); 1416 RakAssert(ml1[4]==5); 1417 RakAssert(ml1.GetIndexOf(1)==0); 1418 RakAssert(ml1.GetIndexOf(2)==1); 1419 RakAssert(ml1.GetIndexOf(3)==2); 1420 RakAssert(ml1.GetIndexOf(4)==3); 1421 RakAssert(ml1.GetIndexOf(5)==4); 1422 ml1.Sort(true); 1423 RakAssert(ml1[0]==1); 1424 RakAssert(ml1[1]==2); 1425 RakAssert(ml1[2]==3); 1426 RakAssert(ml1[3]==4); 1427 RakAssert(ml1[4]==5); 1428 RakAssert(ml1.GetIndexOf(1)==0); 1429 RakAssert(ml1.GetIndexOf(2)==1); 1430 RakAssert(ml1.GetIndexOf(3)==2); 1431 RakAssert(ml1.GetIndexOf(4)==3); 1432 RakAssert(ml1.GetIndexOf(5)==4); 1433 ml1.Clear(__FILE__, __LINE__); 1434 1435 DataStructures::Multilist<ML_STACK, int> ml2; 1436 ml2.Reallocate(64); 1437 RakAssert(ml2.IsEmpty()); 1438 ml2.Push(53); 1439 RakAssert(ml2.Peek()==53); 1440 RakAssert(ml2.IsEmpty()==false); 1441 RakAssert(ml2.Pop()==53); 1442 RakAssert(ml2.IsEmpty()==true); 1443 for (int i=0; i < 512; i++) 1444 ml2.Push(i); 1445 RakAssert(ml2.GetIndexOf(200)==200); 1446 RakAssert(ml2.PeekOpposite()==0); 1447 RakAssert(ml2.PopOpposite()==0); 1448 RakAssert(ml2.PeekOpposite()==1); 1449 RakAssert(ml2.Peek()==511); 1450 ml2.ReverseList(); 1451 for (int i=0; i < 511; i++) 1452 RakAssert(ml2[i]==511-i); 1453 RakAssert(ml2.PeekOpposite()==511); 1454 RakAssert(ml2.Peek()==1); 1455 oldSize = ml2.GetSize(); 1456 ml2.RemoveAtIndex(0); 1457 RakAssert(ml2.GetSize()==oldSize-1); 1458 RakAssert(ml2.Peek()==1); 1459 RakAssert(ml2.PeekOpposite()==510); 1460 ml2.Clear(__FILE__, __LINE__); 1461 RakAssert(ml2.IsEmpty()==true); 1462 1463 DataStructures::Multilist<ML_QUEUE, int> ml3; 1464 RakAssert(ml3.IsEmpty()); 1465 ml3.Push(53); 1466 RakAssert(ml3.Peek()==53); 1467 RakAssert(ml3.IsEmpty()==false); 1468 RakAssert(ml3.Pop()==53); 1469 RakAssert(ml3.IsEmpty()==true); 1470 for (int i=0; i < 512; i++) 1471 ml3.Push(i); 1472 RakAssert(ml3.GetIndexOf(200)==200); 1473 RakAssert(ml3.PeekOpposite()==511); 1474 RakAssert(ml3.PopOpposite()==511); 1475 RakAssert(ml3.PeekOpposite()==510); 1476 RakAssert(ml3.Peek()==0); 1477 ml3.ReverseList(); 1478 for (int i=0; i < 511; i++) 1479 RakAssert(ml3[i]==511-1-i); 1480 RakAssert(ml3.PeekOpposite()==0); 1481 RakAssert(ml3.Peek()==510); 1482 oldSize = ml3.GetSize(); 1483 ml3.RemoveAtIndex(0); 1484 RakAssert(ml3.GetSize()==oldSize-1); 1485 RakAssert(ml3.Peek()==509); 1486 RakAssert(ml3.PeekOpposite()==0); 1487 ml3.Clear(__FILE__, __LINE__); 1488 RakAssert(ml3.IsEmpty()==true); 1489 1490 ml3.PushOpposite(100); 1491 ml3.PushOpposite(50); 1492 ml3.PushOpposite(150); 1493 ml3.PushOpposite(25); 1494 ml3.PushOpposite(175); 1495 ml3.Sort(true); 1496 RakAssert(ml3[0]==25); 1497 RakAssert(ml3[1]==50); 1498 RakAssert(ml3[2]==100); 1499 RakAssert(ml3[3]==150); 1500 RakAssert(ml3[4]==175); 1501 RakAssert(ml3.GetIndexOf(25)==0); 1502 RakAssert(ml3.GetIndexOf(50)==1); 1503 RakAssert(ml3.GetIndexOf(100)==2); 1504 RakAssert(ml3.GetIndexOf(150)==3); 1505 RakAssert(ml3.GetIndexOf(175)==4); 1506 ml3.Clear(__FILE__, __LINE__); 1507 1508 ml3.PushOpposite(1); 1509 ml3.PushOpposite(2); 1510 ml3.PushOpposite(3); 1511 ml3.PushOpposite(4); 1512 ml3.PushOpposite(5); 1513 ml3.Sort(true); 1514 RakAssert(ml3[0]==1); 1515 RakAssert(ml3[1]==2); 1516 RakAssert(ml3[2]==3); 1517 RakAssert(ml3[3]==4); 1518 RakAssert(ml3[4]==5); 1519 RakAssert(ml3.GetIndexOf(1)==0); 1520 RakAssert(ml3.GetIndexOf(2)==1); 1521 RakAssert(ml3.GetIndexOf(3)==2); 1522 RakAssert(ml3.GetIndexOf(4)==3); 1523 RakAssert(ml3.GetIndexOf(5)==4); 1524 ml3.Clear(__FILE__, __LINE__); 1525 1526 ml3.PushOpposite(5); 1527 ml3.PushOpposite(4); 1528 ml3.PushOpposite(3); 1529 ml3.PushOpposite(2); 1530 ml3.PushOpposite(1); 1531 ml3.Sort(true); 1532 RakAssert(ml3[0]==1); 1533 RakAssert(ml3[1]==2); 1534 RakAssert(ml3[2]==3); 1535 RakAssert(ml3[3]==4); 1536 RakAssert(ml3[4]==5); 1537 RakAssert(ml3.GetIndexOf(1)==0); 1538 RakAssert(ml3.GetIndexOf(2)==1); 1539 RakAssert(ml3.GetIndexOf(3)==2); 1540 RakAssert(ml3.GetIndexOf(4)==3); 1541 RakAssert(ml3.GetIndexOf(5)==4); 1542 ml3.Sort(true); 1543 RakAssert(ml3[0]==1); 1544 RakAssert(ml3[1]==2); 1545 RakAssert(ml3[2]==3); 1546 RakAssert(ml3[3]==4); 1547 RakAssert(ml3[4]==5); 1548 RakAssert(ml3.GetIndexOf(1)==0); 1549 RakAssert(ml3.GetIndexOf(2)==1); 1550 RakAssert(ml3.GetIndexOf(3)==2); 1551 RakAssert(ml3.GetIndexOf(4)==3); 1552 RakAssert(ml3.GetIndexOf(5)==4); 1553 1554 ml3.SetSortOrder(false); 1555 ml3.Sort(false); 1556 RakAssert(ml3[0]==5); 1557 RakAssert(ml3[1]==4); 1558 RakAssert(ml3[2]==3); 1559 RakAssert(ml3[3]==2); 1560 RakAssert(ml3[4]==1); 1561 RakAssert(ml3.GetIndexOf(1)==4); 1562 RakAssert(ml3.GetIndexOf(2)==3); 1563 RakAssert(ml3.GetIndexOf(3)==2); 1564 RakAssert(ml3.GetIndexOf(4)==1); 1565 RakAssert(ml3.GetIndexOf(5)==0); 1566 1567 ml3.Clear(__FILE__, __LINE__); 1568 1569 DataStructures::Multilist<ML_ORDERED_LIST, int> ml4; 1570 ml4.Reallocate(64); 1571 RakAssert(ml4.IsEmpty()); 1572 ml4.Push(53); 1573 RakAssert(ml4.Peek()==53); 1574 RakAssert(ml4.IsEmpty()==false); 1575 RakAssert(ml4.Pop()==53); 1576 RakAssert(ml4.IsEmpty()==true); 1577 for (int i=0; i < 512; i++) 1578 ml4.Push(i); 1579 RakAssert(ml4.GetIndexOf(200)==200); 1580 RakAssert(ml4.PeekOpposite()==0); 1581 RakAssert(ml4.PopOpposite()==0); 1582 RakAssert(ml4.PeekOpposite()==1); 1583 RakAssert(ml4.Peek()==511); 1584 ml4.ReverseList(); 1585 for (int i=0; i < 511; i++) 1586 RakAssert(ml4[i]==511-i); 1587 RakAssert(ml4.PeekOpposite()==511); 1588 RakAssert(ml4.Peek()==1); 1589 oldSize = ml4.GetSize(); 1590 ml4.RemoveAtIndex(0); 1591 RakAssert(ml4.GetSize()==oldSize-1); 1592 RakAssert(ml4.Peek()==1); 1593 RakAssert(ml4.PeekOpposite()==510); 1594 ml4.Clear(__FILE__, __LINE__); 1595 RakAssert(ml4.IsEmpty()==true); 1596 1597 DataStructures::Multilist<ML_ORDERED_LIST, KeyAndValue*, int> ml5; 1598 1599 for (int i=0; i < 16; i++) 1600 { 1601 KeyAndValue *kav = new KeyAndValue; 1602 kav->key=i; 1603 kav->value=i+100; 1604 ml5.Push(kav,kav->key); 1605 } 1606 1607 RakAssert(ml5.GetIndexOf(0)==0); 1608 RakAssert(ml5.GetIndexOf(5)==5); 1609 RakAssert(ml5.GetIndexOf(15)==15); 1610 RakAssert(ml5.GetIndexOf(16)==-1); 1611 ml5.RemoveAtKey(0,true); 1612 RakAssert(ml5.GetIndexOf(1)==0); 1613 KeyAndValue *iPtr = ml5.GetPtr(5); 1614 RakAssert(iPtr); 1615 RakAssert(iPtr->value=105); 1616 iPtr = ml5.GetPtr(1234); 1617 RakAssert(iPtr==0); 1618 ml5.ForEach(DataStructures::DeletePtr<KeyAndValue*>); 1619 1620 1621 DataStructures::Multilist<ML_VARIABLE_DURING_RUNTIME, int> ml6; 1622 ml6.Push(2); 1623 ml6.Push(1); 1624 ml6.Push(6); 1625 ml6.Push(3); 1626 RakAssert(ml6.Peek()==3); 1627 ml6.SetMultilistType(ML_STACK); 1628 RakAssert(ml6.Peek()==3); 1629 ml6.SetMultilistType(ML_QUEUE); 1630 RakAssert(ml6.Peek()==2); 1631 ml6.SetMultilistType(ML_ORDERED_LIST); 1632 RakAssert(ml6.Peek()=6); 1633 ml6.SetMultilistType(ML_STACK); 1634 RakAssert(ml6.Peek()==6); 1635 ml6.SetMultilistType(ML_QUEUE); 1636 RakAssert(ml6.Peek()==1); 1637 } 1638 1639 #ifdef _MSC_VER 1640 #pragma warning( pop ) 1641 #endif 1642 */ 1643 1644 #endif 1645