irrArray.h 16 KB

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