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