include/irrArray.h

   1 // Copyright (C) 2002-2012 Nikolaus Gebhardt\r
   2 // This file is part of the "Irrlicht Engine" and the "irrXML" project.\r
   3 // For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h\r
   4 \r
   5 #ifndef __IRR_ARRAY_H_INCLUDED__\r
   6 #define __IRR_ARRAY_H_INCLUDED__\r
   7 \r
   8 #include "irrTypes.h"\r
   9 #include "heapsort.h"\r
  10 #include "irrAllocator.h"\r
  11 #include "irrMath.h"\r
  12 \r
  13 namespace irr\r
  14 {\r
  15 namespace core\r
  16 {\r
  17 \r
  18 //! Self reallocating template array (like stl vector) with additional features.\r
  19 /** Some features are: Heap sorting, binary search methods, easier debugging.\r
  20 */\r
  21 template <class T, typename TAlloc = irrAllocator<T> >\r
  22 class array\r
  23 {\r
  24 \r
  25 public:\r
  26 \r
  27         //! Default constructor for empty array.\r
  28         array() : data(0), allocated(0), used(0),\r
  29                         strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)\r
  30         {\r
  31         }\r
  32 \r
  33 \r
  34         //! Constructs an array and allocates an initial chunk of memory.\r
  35         /** \param start_count Amount of elements to pre-allocate. */\r
  36         explicit array(u32 start_count) : data(0), allocated(0), used(0),\r
  37                         strategy(ALLOC_STRATEGY_DOUBLE),\r
  38                         free_when_destroyed(true), is_sorted(true)\r
  39         {\r
  40                 reallocate(start_count);\r
  41         }\r
  42 \r
  43 \r
  44         //! Copy constructor\r
  45         array(const array<T, TAlloc>& other) : data(0)\r
  46         {\r
  47                 *this = other;\r
  48         }\r
  49 \r
  50 \r
  51         //! Destructor.\r
  52         /** Frees allocated memory, if set_free_when_destroyed was not set to\r
  53         false by the user before. */\r
  54         ~array()\r
  55         {\r
  56                 clear();\r
  57         }\r
  58 \r
  59 \r
  60         //! Reallocates the array, make it bigger or smaller.\r
  61         /** \param new_size New size of array.\r
  62         \param canShrink Specifies whether the array is reallocated even if\r
  63         enough space is available. Setting this flag to false can speed up\r
  64         array usage, but may use more memory than required by the data.\r
  65         */\r
  66         void reallocate(u32 new_size, bool canShrink=true)\r
  67         {\r
  68                 if (allocated==new_size)\r
  69                         return;\r
  70                 if (!canShrink && (new_size < allocated))\r
  71                         return;\r
  72 \r
  73                 T* old_data = data;\r
  74 \r
  75                 data = allocator.allocate(new_size); //new T[new_size];\r
  76                 allocated = new_size;\r
  77 \r
  78                 // copy old data\r
  79                 const s32 end = used < new_size ? used : new_size;\r
  80 \r
  81                 for (s32 i=0; i<end; ++i)\r
  82                 {\r
  83                         // data[i] = old_data[i];\r
  84                         allocator.construct(&data[i], old_data[i]);\r
  85                 }\r
  86 \r
  87                 // destruct old data\r
  88                 for (u32 j=0; j<used; ++j)\r
  89                         allocator.destruct(&old_data[j]);\r
  90 \r
  91                 if (allocated < used)\r
  92                         used = allocated;\r
  93 \r
  94                 allocator.deallocate(old_data); //delete [] old_data;\r
  95         }\r
  96 \r
  97 \r
  98         //! set a new allocation strategy\r
  99         /** if the maximum size of the array is unknown, you can define how big the\r
 100         allocation should happen.\r
 101         \param newStrategy New strategy to apply to this array. */\r
 102         void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE )\r
 103         {\r
 104                 strategy = newStrategy;\r
 105         }\r
 106 \r
 107 \r
 108         //! Adds an element at back of array.\r
 109         /** If the array is too small to add this new element it is made bigger.\r
 110         \param element: Element to add at the back of the array. */\r
 111         void push_back(const T& element)\r
 112         {\r
 113                 insert(element, used);\r
 114         }\r
 115 \r
 116 \r
 117         //! Adds an element at the front of the array.\r
 118         /** If the array is to small to add this new element, the array is\r
 119         made bigger. Please note that this is slow, because the whole array\r
 120         needs to be copied for this.\r
 121         \param element Element to add at the back of the array. */\r
 122         void push_front(const T& element)\r
 123         {\r
 124                 insert(element);\r
 125         }\r
 126 \r
 127 \r
 128         //! Insert item into array at specified position.\r
 129         /**\r
 130         \param element: Element to be inserted\r
 131         \param index: Where position to insert the new element. */\r
 132         void insert(const T& element, u32 index=0)\r
 133         {\r
 134                 _IRR_DEBUG_BREAK_IF(index>used) // access violation\r
 135 \r
 136                 if (used + 1 > allocated)\r
 137                 {\r
 138                         // this doesn't work if the element is in the same\r
 139                         // array. So we'll copy the element first to be sure\r
 140                         // we'll get no data corruption\r
 141                         const T e(element);\r
 142 \r
 143                         // increase data block\r
 144                         u32 newAlloc;\r
 145                         switch ( strategy )\r
 146                         {\r
 147                                 case ALLOC_STRATEGY_DOUBLE:\r
 148                                         newAlloc = used + 5 + (allocated < 500 ? used : used >> 2);\r
 149                                         break;\r
 150                                 default:\r
 151                                 case ALLOC_STRATEGY_SAFE:\r
 152                                         newAlloc = used + 1;\r
 153                                         break;\r
 154                         }\r
 155                         reallocate( newAlloc);\r
 156 \r
 157                         // move array content and construct new element\r
 158                         // first move end one up\r
 159                         for (u32 i=used; i>index; --i)\r
 160                         {\r
 161                                 if (i<used)\r
 162                                         allocator.destruct(&data[i]);\r
 163                                 allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];\r
 164                         }\r
 165                         // then add new element\r
 166                         if (used > index)\r
 167                                 allocator.destruct(&data[index]);\r
 168                         allocator.construct(&data[index], e); // data[index] = e;\r
 169                 }\r
 170                 else\r
 171                 {\r
 172                         // element inserted not at end\r
 173                         if ( used > index )\r
 174                         {\r
 175                                 // create one new element at the end\r
 176                                 allocator.construct(&data[used], data[used-1]);\r
 177 \r
 178                                 // move the rest of the array content\r
 179                                 for (u32 i=used-1; i>index; --i)\r
 180                                 {\r
 181                                         data[i] = data[i-1];\r
 182                                 }\r
 183                                 // insert the new element\r
 184                                 data[index] = element;\r
 185                         }\r
 186                         else\r
 187                         {\r
 188                                 // insert the new element to the end\r
 189                                 allocator.construct(&data[index], element);\r
 190                         }\r
 191                 }\r
 192                 // set to false as we don't know if we have the comparison operators\r
 193                 is_sorted = false;\r
 194                 ++used;\r
 195         }\r
 196 \r
 197 \r
 198         //! Clears the array and deletes all allocated memory.\r
 199         void clear()\r
 200         {\r
 201                 if (free_when_destroyed)\r
 202                 {\r
 203                         for (u32 i=0; i<used; ++i)\r
 204                                 allocator.destruct(&data[i]);\r
 205 \r
 206                         allocator.deallocate(data); // delete [] data;\r
 207                 }\r
 208                 data = 0;\r
 209                 used = 0;\r
 210                 allocated = 0;\r
 211                 is_sorted = true;\r
 212         }\r
 213 \r
 214 \r
 215         //! Sets pointer to new array, using this as new workspace.\r
 216         /** Make sure that set_free_when_destroyed is used properly.\r
 217         \param newPointer: Pointer to new array of elements.\r
 218         \param size: Size of the new array.\r
 219         \param _is_sorted Flag which tells whether the new array is already\r
 220         sorted.\r
 221         \param _free_when_destroyed Sets whether the new memory area shall be\r
 222         freed by the array upon destruction, or if this will be up to the user\r
 223         application. */\r
 224         void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)\r
 225         {\r
 226                 clear();\r
 227                 data = newPointer;\r
 228                 allocated = size;\r
 229                 used = size;\r
 230                 is_sorted = _is_sorted;\r
 231                 free_when_destroyed=_free_when_destroyed;\r
 232         }\r
 233 \r
 234         //! Set (copy) data from given memory block\r
 235         /** \param newData data to set, must have newSize elements\r
 236         \param newSize Amount of elements in newData\r
 237         \param canShrink When true we reallocate the array even it can shrink. \r
 238         May reduce memory usage, but call is more whenever size changes.\r
 239         \param newDataIsSorted Info if you pass sorted/unsorted data\r
 240         */\r
 241         void set_data(const T* newData, u32 newSize, bool newDataIsSorted=false, bool canShrink=false)\r
 242         {\r
 243                 reallocate(newSize, canShrink);\r
 244                 set_used(newSize);\r
 245                 for ( u32 i=0; i<newSize; ++i)\r
 246                 {\r
 247                         data[i] = newData[i];\r
 248                 }\r
 249                 is_sorted = newDataIsSorted;\r
 250         }\r
 251 \r
 252         //! Compare if given data block is identical to the data in our array\r
 253         /** Like operator ==, but without the need to create the array\r
 254         \param otherData Address to data against which we compare, must contain size elements\r
 255         \param size Amount of elements in otherData     */\r
 256         bool equals(const T* otherData, u32 size) const\r
 257         {\r
 258                 if (used != size)\r
 259                         return false;\r
 260 \r
 261                 for (u32 i=0; i<size; ++i)\r
 262                         if (data[i] != otherData[i])\r
 263                                 return false;\r
 264                 return true;\r
 265         }\r
 266 \r
 267 \r
 268 \r
 269         //! Sets if the array should delete the memory it uses upon destruction.\r
 270         /** Also clear and set_pointer will only delete the (original) memory\r
 271         area if this flag is set to true, which is also the default. The\r
 272         methods reallocate, set_used, push_back, push_front, insert, and erase\r
 273         will still try to deallocate the original memory, which might cause\r
 274         troubles depending on the intended use of the memory area.\r
 275         \param f If true, the array frees the allocated memory in its\r
 276         destructor, otherwise not. The default is true. */\r
 277         void set_free_when_destroyed(bool f)\r
 278         {\r
 279                 free_when_destroyed = f;\r
 280         }\r
 281 \r
 282 \r
 283         //! Sets the size of the array and allocates new elements if necessary.\r
 284         /** Please note: This is only secure when using it with simple types,\r
 285         because no default constructor will be called for the added elements.\r
 286         \param usedNow Amount of elements now used. */\r
 287         void set_used(u32 usedNow)\r
 288         {\r
 289                 if (allocated < usedNow)\r
 290                         reallocate(usedNow);\r
 291 \r
 292                 used = usedNow;\r
 293         }\r
 294 \r
 295         //! Assignment operator\r
 296         const array<T, TAlloc>& operator=(const array<T, TAlloc>& other)\r
 297         {\r
 298                 if (this == &other)\r
 299                         return *this;\r
 300                 strategy = other.strategy;\r
 301 \r
 302                 // (TODO: we could probably avoid re-allocations of data when (allocated < other.allocated)\r
 303 \r
 304                 if (data)\r
 305                         clear();\r
 306 \r
 307                 used = other.used;\r
 308                 free_when_destroyed = true;\r
 309                 is_sorted = other.is_sorted;\r
 310                 allocated = other.allocated;\r
 311 \r
 312                 if (other.allocated == 0)\r
 313                 {\r
 314                         data = 0;\r
 315                 }\r
 316                 else\r
 317                 {\r
 318                         data = allocator.allocate(other.allocated); // new T[other.allocated];\r
 319 \r
 320                         for (u32 i=0; i<other.used; ++i)\r
 321                                 allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i];\r
 322                 }\r
 323 \r
 324                 return *this;\r
 325         }\r
 326 \r
 327 \r
 328         //! Equality operator\r
 329         bool operator == (const array<T, TAlloc>& other) const\r
 330         {\r
 331                 return equals(other.const_pointer(), other.size());\r
 332         }\r
 333 \r
 334 \r
 335         //! Inequality operator\r
 336         bool operator != (const array<T, TAlloc>& other) const\r
 337         {\r
 338                 return !(*this==other);\r
 339         }\r
 340 \r
 341 \r
 342         //! Direct access operator\r
 343         T& operator [](u32 index)\r
 344         {\r
 345                 _IRR_DEBUG_BREAK_IF(index>=used) // access violation\r
 346 \r
 347                 return data[index];\r
 348         }\r
 349 \r
 350 \r
 351         //! Direct const access operator\r
 352         const T& operator [](u32 index) const\r
 353         {\r
 354                 _IRR_DEBUG_BREAK_IF(index>=used) // access violation\r
 355 \r
 356                 return data[index];\r
 357         }\r
 358 \r
 359 \r
 360         //! Gets last element.\r
 361         T& getLast()\r
 362         {\r
 363                 _IRR_DEBUG_BREAK_IF(!used) // access violation\r
 364 \r
 365                 return data[used-1];\r
 366         }\r
 367 \r
 368 \r
 369         //! Gets last element\r
 370         const T& getLast() const\r
 371         {\r
 372                 _IRR_DEBUG_BREAK_IF(!used) // access violation\r
 373 \r
 374                 return data[used-1];\r
 375         }\r
 376 \r
 377 \r
 378         //! Gets a pointer to the array.\r
 379         /** \return Pointer to the array. */\r
 380         T* pointer()\r
 381         {\r
 382                 return data;\r
 383         }\r
 384 \r
 385 \r
 386         //! Gets a const pointer to the array.\r
 387         /** \return Pointer to the array. */\r
 388         const T* const_pointer() const\r
 389         {\r
 390                 return data;\r
 391         }\r
 392 \r
 393 \r
 394         //! Get number of occupied elements of the array.\r
 395         /** \return Size of elements in the array which are actually occupied. */\r
 396         u32 size() const\r
 397         {\r
 398                 return used;\r
 399         }\r
 400 \r
 401 \r
 402         //! Get amount of memory allocated.\r
 403         /** \return Amount of memory allocated. The amount of bytes\r
 404         allocated would be allocated_size() * sizeof(ElementTypeUsed); */\r
 405         u32 allocated_size() const\r
 406         {\r
 407                 return allocated;\r
 408         }\r
 409 \r
 410 \r
 411         //! Check if array is empty.\r
 412         /** \return True if the array is empty false if not. */\r
 413         bool empty() const\r
 414         {\r
 415                 return used == 0;\r
 416         }\r
 417 \r
 418 \r
 419         //! Sorts the array using heapsort.\r
 420         /** There is no additional memory waste and the algorithm performs\r
 421         O(n*log n) in worst case. */\r
 422         void sort()\r
 423         {\r
 424                 if (!is_sorted && used>1)\r
 425                         heapsort(data, used);\r
 426                 is_sorted = true;\r
 427         }\r
 428 \r
 429 \r
 430         //! Performs a binary search for an element, returns -1 if not found.\r
 431         /** The array will be sorted before the binary search if it is not\r
 432         already sorted. Caution is advised! Be careful not to call this on\r
 433         unsorted const arrays, or the slower method will be used.\r
 434         \param element Element to search for.\r
 435         \return Position of the searched element if it was found,\r
 436         otherwise -1 is returned. */\r
 437         s32 binary_search(const T& element)\r
 438         {\r
 439                 sort();\r
 440                 return binary_search(element, 0, used-1);\r
 441         }\r
 442 \r
 443 \r
 444         //! Performs a binary search for an element if possible, returns -1 if not found.\r
 445         /** This method is for const arrays and so cannot call sort(), if the array is\r
 446         not sorted then linear_search will be used instead. Potentially very slow!\r
 447         \param element Element to search for.\r
 448         \return Position of the searched element if it was found,\r
 449         otherwise -1 is returned. */\r
 450         s32 binary_search(const T& element) const\r
 451         {\r
 452                 if (is_sorted)\r
 453                         return binary_search(element, 0, used-1);\r
 454                 else\r
 455                         return linear_search(element);\r
 456         }\r
 457 \r
 458 \r
 459         //! Performs a binary search for an element, returns -1 if not found.\r
 460         /** \param element: Element to search for.\r
 461         \param left First left index\r
 462         \param right Last right index.\r
 463         \return Position of the searched element if it was found, otherwise -1\r
 464         is returned. */\r
 465         s32 binary_search(const T& element, s32 left, s32 right) const\r
 466         {\r
 467                 if (!used)\r
 468                         return -1;\r
 469 \r
 470                 s32 m;\r
 471 \r
 472                 do\r
 473                 {\r
 474                         m = (left+right)>>1;\r
 475 \r
 476                         if (element < data[m])\r
 477                                 right = m - 1;\r
 478                         else\r
 479                                 left = m + 1;\r
 480 \r
 481                 } while((element < data[m] || data[m] < element) && left<=right);\r
 482                 // this last line equals to:\r
 483                 // " while((element != array[m]) && left<=right);"\r
 484                 // but we only want to use the '<' operator.\r
 485                 // the same in next line, it is "(element == array[m])"\r
 486 \r
 487 \r
 488                 if (!(element < data[m]) && !(data[m] < element))\r
 489                         return m;\r
 490 \r
 491                 return -1;\r
 492         }\r
 493 \r
 494 \r
 495         //! Performs a binary search for an element, returns -1 if not found.\r
 496         //! it is used for searching a multiset\r
 497         /** The array will be sorted before the binary search if it is not\r
 498         already sorted.\r
 499         \param element Element to search for.\r
 500         \param &last return lastIndex of equal elements\r
 501         \return Position of the first searched element if it was found,\r
 502         otherwise -1 is returned. */\r
 503         s32 binary_search_multi(const T& element, s32 &last)\r
 504         {\r
 505                 sort();\r
 506                 s32 index = binary_search(element, 0, used-1);\r
 507                 if ( index < 0 )\r
 508                         return index;\r
 509 \r
 510                 // The search can be somewhere in the middle of the set\r
 511                 // look linear previous and past the index\r
 512                 last = index;\r
 513 \r
 514                 while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )\r
 515                 {\r
 516                         index -= 1;\r
 517                 }\r
 518                 // look linear up\r
 519                 while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )\r
 520                 {\r
 521                         last += 1;\r
 522                 }\r
 523 \r
 524                 return index;\r
 525         }\r
 526 \r
 527 \r
 528         //! Finds an element in linear time, which is very slow.\r
 529         /** Use binary_search for faster finding. Only works if ==operator is\r
 530         implemented.\r
 531         \param element Element to search for.\r
 532         \return Position of the searched element if it was found, otherwise -1\r
 533         is returned. */\r
 534         s32 linear_search(const T& element) const\r
 535         {\r
 536                 for (u32 i=0; i<used; ++i)\r
 537                         if (element == data[i])\r
 538                                 return (s32)i;\r
 539 \r
 540                 return -1;\r
 541         }\r
 542 \r
 543 \r
 544         //! Finds an element in linear time, which is very slow.\r
 545         /** Use binary_search for faster finding. Only works if ==operator is\r
 546         implemented.\r
 547         \param element: Element to search for.\r
 548         \return Position of the searched element if it was found, otherwise -1\r
 549         is returned. */\r
 550         s32 linear_reverse_search(const T& element) const\r
 551         {\r
 552                 for (s32 i=used-1; i>=0; --i)\r
 553                         if (data[i] == element)\r
 554                                 return i;\r
 555 \r
 556                 return -1;\r
 557         }\r
 558 \r
 559 \r
 560         //! Erases an element from the array.\r
 561         /** May be slow, because all elements following after the erased\r
 562         element have to be copied.\r
 563         \param index: Index of element to be erased. */\r
 564         void erase(u32 index)\r
 565         {\r
 566                 _IRR_DEBUG_BREAK_IF(index>=used) // access violation\r
 567 \r
 568                 for (u32 i=index+1; i<used; ++i)\r
 569                 {\r
 570                         allocator.destruct(&data[i-1]);\r
 571                         allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];\r
 572                 }\r
 573 \r
 574                 allocator.destruct(&data[used-1]);\r
 575 \r
 576                 --used;\r
 577         }\r
 578 \r
 579 \r
 580         //! Erases some elements from the array.\r
 581         /** May be slow, because all elements following after the erased\r
 582         element have to be copied.\r
 583         \param index: Index of the first element to be erased.\r
 584         \param count: Amount of elements to be erased. */\r
 585         void erase(u32 index, s32 count)\r
 586         {\r
 587                 if (index>=used || count<1)\r
 588                         return;\r
 589                 if (index+count>used)\r
 590                         count = used-index;\r
 591 \r
 592                 u32 i;\r
 593                 for (i=index; i<index+count; ++i)\r
 594                         allocator.destruct(&data[i]);\r
 595 \r
 596                 for (i=index+count; i<used; ++i)\r
 597                 {\r
 598                         if (i-count >= index+count) // not already destructed before loop\r
 599                                 allocator.destruct(&data[i-count]);\r
 600 \r
 601                         allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i];\r
 602 \r
 603                         if (i >= used-count) // those which are not overwritten\r
 604                                 allocator.destruct(&data[i]);\r
 605                 }\r
 606 \r
 607                 used-= count;\r
 608         }\r
 609 \r
 610 \r
 611         //! Sets if the array is sorted\r
 612         void set_sorted(bool _is_sorted)\r
 613         {\r
 614                 is_sorted = _is_sorted;\r
 615         }\r
 616 \r
 617 \r
 618         //! Swap the content of this array container with the content of another array\r
 619         /** Afterward this object will contain the content of the other object and the other\r
 620         object will contain the content of this object.\r
 621         \param other Swap content with this object */\r
 622         void swap(array<T, TAlloc>& other)\r
 623         {\r
 624                 core::swap(data, other.data);\r
 625                 core::swap(allocated, other.allocated);\r
 626                 core::swap(used, other.used);\r
 627                 core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation\r
 628                 eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields\r
 629                 strategy = other.strategy;\r
 630                 other.strategy = helper_strategy;\r
 631                 bool helper_free_when_destroyed(free_when_destroyed);\r
 632                 free_when_destroyed = other.free_when_destroyed;\r
 633                 other.free_when_destroyed = helper_free_when_destroyed;\r
 634                 bool helper_is_sorted(is_sorted);\r
 635                 is_sorted = other.is_sorted;\r
 636                 other.is_sorted = helper_is_sorted;\r
 637         }\r
 638 \r
 639         typedef TAlloc allocator_type;\r
 640         typedef T value_type;\r
 641         typedef u32 size_type;\r
 642 \r
 643 private:\r
 644         T* data;\r
 645         u32 allocated;\r
 646         u32 used;\r
 647         TAlloc allocator;\r
 648         eAllocStrategy strategy:4;\r
 649         bool free_when_destroyed:1;\r
 650         bool is_sorted:1;\r
 651 };\r
 652 \r
 653 \r
 654 } // end namespace core\r
 655 } // end namespace irr\r
 656 \r
 657 #endif\r
 658 \r