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 <algorithm>\r
   9 #include <iterator>\r
  10 #include <vector>\r
  11 \r
  12 #include "irrTypes.h"\r
  13 #include "irrMath.h"\r
  14 \r
  15 namespace irr\r
  16 {\r
  17 namespace core\r
  18 {\r
  19 \r
  20 //! Self reallocating template array (like stl vector) with additional features.\r
  21 /** Some features are: Heap sorting, binary search methods, easier debugging.\r
  22 */\r
  23 template <class T>\r
  24 class array\r
  25 {\r
  26 public:\r
  27         static_assert(!std::is_same<T, bool>::value,\r
  28                 "irr::core::array<T> with T = bool not supported. Use std::vector instead.");\r
  29 \r
  30         //! Default constructor for empty array.\r
  31         array() : m_data(), is_sorted(true)\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) : m_data(), is_sorted(true)\r
  37         {\r
  38                 m_data.reserve(start_count);\r
  39         }\r
  40 \r
  41         //! Copy constructor\r
  42         array(const array<T>& other) : m_data(other.m_data), is_sorted(other.is_sorted)\r
  43         { }\r
  44 \r
  45         //! Reallocates the array, make it bigger or smaller.\r
  46         /** \param new_size New size of array.\r
  47         \param canShrink Specifies whether the array is reallocated even if\r
  48         enough space is available. Setting this flag to false can speed up\r
  49         array usage, but may use more memory than required by the data.\r
  50         */\r
  51         void reallocate(u32 new_size, bool canShrink=true)\r
  52         {\r
  53                 size_t allocated = m_data.capacity();\r
  54                 if (new_size < allocated) {\r
  55                         if (canShrink)\r
  56                                 m_data.resize(new_size);\r
  57                 } else {\r
  58                         m_data.reserve(new_size);\r
  59                 }\r
  60         }\r
  61 \r
  62         //! Adds an element at back of array.\r
  63         /** If the array is too small to add this new element it is made bigger.\r
  64         \param element: Element to add at the back of the array. */\r
  65         void push_back(const T& element)\r
  66         {\r
  67                 m_data.push_back(element);\r
  68                 is_sorted = false;\r
  69         }\r
  70 \r
  71         void push_back(T&& element)\r
  72         {\r
  73                 m_data.push_back(std::move(element));\r
  74                 is_sorted = false;\r
  75         }\r
  76 \r
  77 \r
  78         //! Adds an element at the front of the array.\r
  79         /** If the array is to small to add this new element, the array is\r
  80         made bigger. Please note that this is slow, because the whole array\r
  81         needs to be copied for this.\r
  82         \param element Element to add at the back of the array. */\r
  83         void push_front(const T& element)\r
  84         {\r
  85                 m_data.insert(m_data.begin(), element);\r
  86                 is_sorted = false;\r
  87         }\r
  88 \r
  89         void push_front(T&& element)\r
  90         {\r
  91                 m_data.insert(m_data.begin(), std::move(element));\r
  92                 is_sorted = false;\r
  93         }\r
  94 \r
  95 \r
  96         //! Insert item into array at specified position.\r
  97         /**\r
  98         \param element: Element to be inserted\r
  99         \param index: Where position to insert the new element. */\r
 100         void insert(const T& element, u32 index=0)\r
 101         {\r
 102                 _IRR_DEBUG_BREAK_IF(index > m_data.size()) // access violation\r
 103                 auto pos = std::next(m_data.begin(), index);\r
 104                 m_data.insert(pos, element);\r
 105                 is_sorted = false;\r
 106         }\r
 107 \r
 108         //! Clears the array and deletes all allocated memory.\r
 109         void clear()\r
 110         {\r
 111                 // vector::clear() reduces the size to 0, but doesn't free memory.\r
 112                 // This swap is guaranteed to delete the allocated memory.\r
 113                 std::vector<T>().swap(m_data);\r
 114                 is_sorted = true;\r
 115         }\r
 116 \r
 117         //! Set (copy) data from given memory block\r
 118         /** \param newData data to set, must have newSize elements\r
 119         \param newSize Amount of elements in newData\r
 120         \param canShrink When true we reallocate the array even it can shrink. \r
 121         May reduce memory usage, but call is more whenever size changes.\r
 122         \param newDataIsSorted Info if you pass sorted/unsorted data\r
 123         */\r
 124         void set_data(const T* newData, u32 newSize, bool newDataIsSorted=false, bool canShrink=false)\r
 125         {\r
 126                 m_data.resize(newSize);\r
 127                 if (canShrink) {\r
 128                         m_data.shrink_to_fit();\r
 129                 }\r
 130                 std::copy(newData, newData + newSize, m_data.begin());\r
 131                 is_sorted = newDataIsSorted;\r
 132         }\r
 133 \r
 134         //! Compare if given data block is identical to the data in our array\r
 135         /** Like operator ==, but without the need to create the array\r
 136         \param otherData Address to data against which we compare, must contain size elements\r
 137         \param size Amount of elements in otherData     */\r
 138         bool equals(const T* otherData, u32 size) const\r
 139         {\r
 140                 if (m_data.size() != size)\r
 141                         return false;\r
 142                 return std::equal(m_data.begin(), m_data.end(), otherData);\r
 143         }\r
 144 \r
 145         //! Sets the size of the array and allocates new elements if necessary.\r
 146         /** \param usedNow Amount of elements now used. */\r
 147         void set_used(u32 usedNow)\r
 148         {\r
 149                 m_data.resize(usedNow);\r
 150         }\r
 151 \r
 152         //! Assignment operator\r
 153         const array<T>& operator=(const array<T>& other)\r
 154         {\r
 155                 if (this == &other)\r
 156                         return *this;\r
 157                 m_data = other.m_data;\r
 158                 is_sorted = other.is_sorted;\r
 159                 return *this;\r
 160         }\r
 161 \r
 162         array<T>& operator=(const std::vector<T> &other)\r
 163         {\r
 164                 m_data = other;\r
 165                 is_sorted = false;\r
 166                 return *this;\r
 167         }\r
 168 \r
 169         array<T>& operator=(std::vector<T> &&other)\r
 170         {\r
 171                 m_data = std::move(other);\r
 172                 is_sorted = false;\r
 173                 return *this;\r
 174         }\r
 175 \r
 176         //! Equality operator\r
 177         bool operator == (const array<T>& other) const\r
 178         {\r
 179                 return equals(other.const_pointer(), other.size());\r
 180         }\r
 181 \r
 182 \r
 183         //! Inequality operator\r
 184         bool operator != (const array<T>& other) const\r
 185         {\r
 186                 return !(*this==other);\r
 187         }\r
 188 \r
 189 \r
 190         //! Direct access operator\r
 191         T& operator [](u32 index)\r
 192         {\r
 193                 _IRR_DEBUG_BREAK_IF(index >= m_data.size()) // access violation\r
 194 \r
 195                 return m_data[index];\r
 196         }\r
 197 \r
 198 \r
 199         //! Direct const access operator\r
 200         const T& operator [](u32 index) const\r
 201         {\r
 202                 _IRR_DEBUG_BREAK_IF(index >= m_data.size()) // access violation\r
 203 \r
 204                 return m_data[index];\r
 205         }\r
 206 \r
 207 \r
 208         //! Gets last element.\r
 209         T& getLast()\r
 210         {\r
 211                 _IRR_DEBUG_BREAK_IF(m_data.empty()) // access violation\r
 212 \r
 213                 return m_data.back();\r
 214         }\r
 215 \r
 216 \r
 217         //! Gets last element\r
 218         const T& getLast() const\r
 219         {\r
 220                 _IRR_DEBUG_BREAK_IF(m_data.empty()) // access violation\r
 221 \r
 222                 return m_data.back();\r
 223         }\r
 224 \r
 225 \r
 226         //! Gets a pointer to the array.\r
 227         /** \return Pointer to the array. */\r
 228         T* pointer()\r
 229         {\r
 230                 return m_data.empty() ? nullptr : &m_data[0];\r
 231         }\r
 232 \r
 233 \r
 234         //! Gets a const pointer to the array.\r
 235         /** \return Pointer to the array. */\r
 236         const T* const_pointer() const\r
 237         {\r
 238                 return m_data.empty() ? nullptr : &m_data[0];\r
 239         }\r
 240 \r
 241 \r
 242         //! Get number of occupied elements of the array.\r
 243         /** \return Size of elements in the array which are actually occupied. */\r
 244         u32 size() const\r
 245         {\r
 246                 return m_data.size();\r
 247         }\r
 248 \r
 249 \r
 250         //! Get amount of memory allocated.\r
 251         /** \return Amount of memory allocated. The amount of bytes\r
 252         allocated would be allocated_size() * sizeof(ElementTypeUsed); */\r
 253         u32 allocated_size() const\r
 254         {\r
 255                 return m_data.capacity();\r
 256         }\r
 257 \r
 258 \r
 259         //! Check if array is empty.\r
 260         /** \return True if the array is empty false if not. */\r
 261         bool empty() const\r
 262         {\r
 263                 return m_data.empty();\r
 264         }\r
 265 \r
 266 \r
 267         //! Sorts the array using heapsort.\r
 268         /** There is no additional memory waste and the algorithm performs\r
 269         O(n*log n) in worst case. */\r
 270         void sort()\r
 271         {\r
 272                 if (!is_sorted) {\r
 273                         std::sort(m_data.begin(), m_data.end());\r
 274                         is_sorted = true;\r
 275                 }\r
 276         }\r
 277 \r
 278 \r
 279         //! Performs a binary search for an element, returns -1 if not found.\r
 280         /** The array will be sorted before the binary search if it is not\r
 281         already sorted. Caution is advised! Be careful not to call this on\r
 282         unsorted const arrays, or the slower method will be used.\r
 283         \param element Element to search for.\r
 284         \return Position of the searched element if it was found,\r
 285         otherwise -1 is returned. */\r
 286         s32 binary_search(const T& element)\r
 287         {\r
 288                 sort();\r
 289                 return binary_search(element, 0, (s32)m_data.size() - 1);\r
 290         }\r
 291 \r
 292         //! Performs a binary search for an element if possible, returns -1 if not found.\r
 293         /** This method is for const arrays and so cannot call sort(), if the array is\r
 294         not sorted then linear_search will be used instead. Potentially very slow!\r
 295         \param element Element to search for.\r
 296         \return Position of the searched element if it was found,\r
 297         otherwise -1 is returned. */\r
 298         s32 binary_search(const T& element) const\r
 299         {\r
 300                 if (is_sorted)\r
 301                         return binary_search(element, 0, (s32)m_data.size() - 1);\r
 302                 else\r
 303                         return linear_search(element);\r
 304         }\r
 305 \r
 306         //! Performs a binary search for an element, returns -1 if not found.\r
 307         /** \param element: Element to search for.\r
 308         \param left First left index\r
 309         \param right Last right index.\r
 310         \return Position of the searched element if it was found, otherwise -1\r
 311         is returned. */\r
 312         s32 binary_search(const T& element, s32 left, s32 right) const\r
 313         {\r
 314                 if (left > right)\r
 315                         return -1;\r
 316                 auto lpos = std::next(m_data.begin(), left);\r
 317                 auto rpos = std::next(m_data.begin(), right);\r
 318                 auto it = std::lower_bound(lpos, rpos, element);\r
 319                 // *it = first element in [first, last) that is >= element, or last if not found.\r
 320                 if (*it < element || element < *it)\r
 321                         return -1;\r
 322                 return it - m_data.begin();\r
 323         }\r
 324 \r
 325 \r
 326         //! Performs a binary search for an element, returns -1 if not found.\r
 327         //! it is used for searching a multiset\r
 328         /** The array will be sorted before the binary search if it is not\r
 329         already sorted.\r
 330         \param element Element to search for.\r
 331         \param &last return lastIndex of equal elements\r
 332         \return Position of the first searched element if it was found,\r
 333         otherwise -1 is returned. */\r
 334         s32 binary_search_multi(const T& element, s32 &last)\r
 335         {\r
 336                 sort();\r
 337                 auto iters = std::equal_range(m_data.begin(), m_data.end(), element);\r
 338                 if (iters.first == iters.second)\r
 339                         return -1;\r
 340                 last = (iters.second - m_data.begin()) - 1;\r
 341                 return iters.first - m_data.begin();\r
 342         }\r
 343 \r
 344 \r
 345         //! Finds an element in linear time, which is very slow.\r
 346         /** Use binary_search for faster finding. Only works if ==operator is\r
 347         implemented.\r
 348         \param element Element to search for.\r
 349         \return Position of the searched element if it was found, otherwise -1\r
 350         is returned. */\r
 351         s32 linear_search(const T& element) const\r
 352         {\r
 353                 auto it = std::find(m_data.begin(), m_data.end(), element);\r
 354                 if (it == m_data.end())\r
 355                         return -1;\r
 356                 return it - m_data.begin();\r
 357         }\r
 358 \r
 359 \r
 360         //! Finds an element in linear time, which is very slow.\r
 361         /** Use binary_search for faster finding. Only works if ==operator is\r
 362         implemented.\r
 363         \param element: Element to search for.\r
 364         \return Position of the searched element if it was found, otherwise -1\r
 365         is returned. */\r
 366         s32 linear_reverse_search(const T& element) const\r
 367         {\r
 368                 auto it = std::find(m_data.rbegin(), m_data.rend(), element);\r
 369                 if (it == m_data.rend())\r
 370                         return -1;\r
 371                 size_t offset = it - m_data.rbegin();\r
 372                 return m_data.size() - offset - 1;\r
 373         }\r
 374 \r
 375 \r
 376         //! Erases an element from the array.\r
 377         /** May be slow, because all elements following after the erased\r
 378         element have to be copied.\r
 379         \param index: Index of element to be erased. */\r
 380         void erase(u32 index)\r
 381         {\r
 382                 _IRR_DEBUG_BREAK_IF(index >= m_data.size()) // access violation\r
 383                 auto it = std::next(m_data.begin(), index);\r
 384                 m_data.erase(it);\r
 385         }\r
 386 \r
 387 \r
 388         //! Erases some elements from the array.\r
 389         /** May be slow, because all elements following after the erased\r
 390         element have to be copied.\r
 391         \param index: Index of the first element to be erased.\r
 392         \param count: Amount of elements to be erased. */\r
 393         void erase(u32 index, s32 count)\r
 394         {\r
 395                 if (index >= m_data.size() || count < 1)\r
 396                         return;\r
 397                 count = core::min_(count, (s32)m_data.size() - (s32)index);\r
 398                 auto first = std::next(m_data.begin(), index);\r
 399                 auto last = std::next(first, count);\r
 400                 m_data.erase(first, last);\r
 401         }\r
 402 \r
 403         //! Sets if the array is sorted\r
 404         void set_sorted(bool _is_sorted)\r
 405         {\r
 406                 is_sorted = _is_sorted;\r
 407         }\r
 408 \r
 409 \r
 410         //! Swap the content of this array container with the content of another array\r
 411         /** Afterward this object will contain the content of the other object and the other\r
 412         object will contain the content of this object.\r
 413         \param other Swap content with this object */\r
 414         void swap(array<T>& other)\r
 415         {\r
 416                 m_data.swap(other.m_data);\r
 417                 std::swap(is_sorted, other.is_sorted);\r
 418         }\r
 419 \r
 420         //! Pull the contents of this array as a vector.\r
 421         // The array is left empty.\r
 422         std::vector<T> steal()\r
 423         {\r
 424                 std::vector<T> ret = std::move(m_data);\r
 425                 m_data.clear();\r
 426                 is_sorted = true;\r
 427                 return ret;\r
 428         }\r
 429 \r
 430         typedef T value_type;\r
 431         typedef u32 size_type;\r
 432 \r
 433 private:\r
 434         std::vector<T> m_data;\r
 435         bool is_sorted;\r
 436 };\r
 437 \r
 438 } // end namespace core\r
 439 } // end namespace irr\r
 440 \r
 441 #endif\r
 442 \r