1 // Copyright (C) 2002-2005 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 11 namespace irr 12 { 13 namespace core 14 { 15 16 //! Self reallocating template array (like stl vector) with additional features. 17 /** Some features are: Heap sorting, binary search methods, easier debugging. 18 */ 19 template <class T> 20 class array 21 { 22 23 public: 24 array()25 array() 26 : data(0), allocated(0), used(0), 27 free_when_destroyed(true), is_sorted(true) 28 { 29 } 30 31 //! Constructs a array and allocates an initial chunk of memory. 32 //! \param start_count: Amount of elements to allocate. array(u32 start_count)33 array(u32 start_count) 34 : data(0), allocated(0), used(0), 35 free_when_destroyed(true), is_sorted(true) 36 { 37 reallocate(start_count); 38 } 39 40 41 //! Copy constructor array(const array<T> & other)42 array(const array<T>& other) 43 : data(0) 44 { 45 *this = other; 46 } 47 48 49 50 //! Destructor. Frees allocated memory, if set_free_when_destroyed 51 //! was not set to false by the user before. ~array()52 ~array() 53 { 54 if (free_when_destroyed) 55 delete [] data; 56 } 57 58 59 60 //! Reallocates the array, make it bigger or smaller. 61 //! \param new_size: New size of array. reallocate(u32 new_size)62 void reallocate(u32 new_size) 63 { 64 T* old_data = data; 65 66 data = new T[new_size]; 67 allocated = new_size; 68 69 s32 end = used < new_size ? used : new_size; 70 for (s32 i=0; i<end; ++i) 71 data[i] = old_data[i]; 72 73 if (allocated < used) 74 used = allocated; 75 76 delete [] old_data; 77 } 78 79 //! Adds an element at back of array. If the array is to small to 80 //! add this new element, the array is made bigger. 81 //! \param element: Element to add at the back of the array. push_back(const T & element)82 void push_back(const T& element) 83 { 84 if (used + 1 > allocated) 85 { 86 // reallocate(used * 2 +1); 87 // this doesn't work if the element is in the same array. So 88 // we'll copy the element first to be sure we'll get no data 89 // corruption 90 91 T e; 92 e = element; // copy element 93 reallocate(used * 2 +1); // increase data block 94 data[used++] = e; // push_back 95 is_sorted = false; 96 return; 97 } 98 99 data[used++] = element; 100 is_sorted = false; 101 } 102 103 104 //! Adds an element at the front of the array. If the array is to small to 105 //! add this new element, the array is made bigger. Please note that this 106 //! is slow, because the whole array needs to be copied for this. 107 //! \param element: Element to add at the back of the array. push_front(const T & element)108 void push_front(const T& element) 109 { 110 if (used + 1 > allocated) 111 reallocate(used * 2 +1); 112 113 for (int i=(int)used; i>0; --i) 114 data[i] = data[i-1]; 115 116 data[0] = element; 117 is_sorted = false; 118 ++used; 119 } 120 121 122 //! Insert item into array at specified position. Please use this 123 //! only if you know what you are doing (possible performance loss). 124 //! The preferred method of adding elements should be push_back(). 125 //! \param element: Element to be inserted 126 //! \param index: Where position to insert the new element. 127 void insert(const T& element, u32 index=0) 128 { 129 _IRR_DEBUG_BREAK_IF(index>used) // access violation 130 131 if (used + 1 > allocated) 132 reallocate(used * 2 +1); 133 134 for (u32 i=used++; i>index; i--) 135 data[i] = data[i-1]; 136 137 data[index] = element; 138 is_sorted = false; 139 } 140 141 142 143 144 //! Clears the array and deletes all allocated memory. clear()145 void clear() 146 { 147 delete [] data; 148 data = 0; 149 used = 0; 150 allocated = 0; 151 is_sorted = true; 152 } 153 154 155 156 //! Sets pointer to new array, using this as new workspace. 157 //! \param newPointer: Pointer to new array of elements. 158 //! \param size: Size of the new array. set_pointer(T * newPointer,u32 size)159 void set_pointer(T* newPointer, u32 size) 160 { 161 delete [] data; 162 data = newPointer; 163 allocated = size; 164 used = size; 165 is_sorted = false; 166 } 167 168 169 170 //! Sets if the array should delete the memory it used. 171 //! \param f: If true, the array frees the allocated memory in its 172 //! destructor, otherwise not. The default is true. set_free_when_destroyed(bool f)173 void set_free_when_destroyed(bool f) 174 { 175 free_when_destroyed = f; 176 } 177 178 179 180 //! Sets the size of the array. 181 //! \param usedNow: Amount of elements now used. set_used(u32 usedNow)182 void set_used(u32 usedNow) 183 { 184 if (allocated < usedNow) 185 reallocate(usedNow); 186 187 used = usedNow; 188 } 189 190 191 192 //! Assignement operator 193 void operator=(const array<T>& other) 194 { 195 if (data) 196 delete [] data; 197 198 //if (allocated < other.allocated) 199 if (other.allocated == 0) 200 data = 0; 201 else 202 data = new T[other.allocated]; 203 204 used = other.used; 205 free_when_destroyed = other.free_when_destroyed; 206 is_sorted = other.is_sorted; 207 allocated = other.allocated; 208 209 for (u32 i=0; i<other.used; ++i) 210 data[i] = other.data[i]; 211 } 212 213 214 //! Direct access operator 215 T& operator [](u32 index) 216 { 217 _IRR_DEBUG_BREAK_IF(index>=used) // access violation 218 219 return data[index]; 220 } 221 222 223 224 //! Direct access operator 225 const T& operator [](u32 index) const 226 { 227 _IRR_DEBUG_BREAK_IF(index>=used) // access violation 228 229 return data[index]; 230 } 231 232 //! Gets last frame getLast()233 const T& getLast() const 234 { 235 _IRR_DEBUG_BREAK_IF(!used) // access violation 236 237 return data[used-1]; 238 } 239 240 //! Gets last frame getLast()241 T& getLast() 242 { 243 _IRR_DEBUG_BREAK_IF(!used) // access violation 244 245 return data[used-1]; 246 } 247 248 249 //! Returns a pointer to the array. 250 //! \return Pointer to the array. pointer()251 T* pointer() 252 { 253 return data; 254 } 255 256 257 258 //! Returns a const pointer to the array. 259 //! \return Pointer to the array. const_pointer()260 const T* const_pointer() const 261 { 262 return data; 263 } 264 265 266 267 //! Returns size of used array. 268 //! \return Size of elements in the array. size()269 u32 size() const 270 { 271 return used; 272 } 273 274 275 276 //! Returns amount memory allocated. 277 //! \return Returns amount of memory allocated. The amount of bytes 278 //! allocated would be allocated_size() * sizeof(ElementsUsed); allocated_size()279 u32 allocated_size() const 280 { 281 return allocated; 282 } 283 284 285 286 //! Returns true if array is empty 287 //! \return True if the array is empty, false if not. empty()288 bool empty() const 289 { 290 return used == 0; 291 } 292 293 294 295 //! Sorts the array using heapsort. There is no additional memory waste and 296 //! the algorithm performs (O) n log n in worst case. sort()297 void sort() 298 { 299 if (is_sorted || used<2) 300 return; 301 302 heapsort(data, used); 303 is_sorted = true; 304 } 305 306 307 308 //! Performs a binary search for an element, returns -1 if not found. 309 //! The array will be sorted before the binary search if it is not 310 //! already sorted. 311 //! \param element: Element to search for. 312 //! \return Returns position of the searched element if it was found, 313 //! otherwise -1 is returned. binary_search(const T & element)314 s32 binary_search(const T& element) 315 { 316 return binary_search(element, 0, used-1); 317 } 318 319 320 321 //! Performs a binary search for an element, returns -1 if not found. 322 //! The array will be sorted before the binary search if it is not 323 //! already sorted. 324 //! \param element: Element to search for. 325 //! \param left: First left index 326 //! \param right: Last right index. 327 //! \return Returns position of the searched element if it was found, 328 //! otherwise -1 is returned. binary_search(const T & element,s32 left,s32 right)329 s32 binary_search(const T& element, s32 left, s32 right) 330 { 331 if (!used) 332 return -1; 333 334 sort(); 335 336 s32 m; 337 338 do 339 { 340 m = (left+right)>>1; 341 342 if (element < data[m]) 343 right = m - 1; 344 else 345 left = m + 1; 346 347 } while((element < data[m] || data[m] < element) && left<=right); 348 349 // this last line equals to: 350 // " while((element != array[m]) && left<=right);" 351 // but we only want to use the '<' operator. 352 // the same in next line, it is "(element == array[m])" 353 354 if (!(element < data[m]) && !(data[m] < element)) 355 return m; 356 357 return -1; 358 } 359 360 361 //! Finds an element in linear time, which is very slow. Use 362 //! binary_search for faster finding. Only works if =operator is implemented. 363 //! \param element: Element to search for. 364 //! \return Returns position of the searched element if it was found, 365 //! otherwise -1 is returned. linear_search(T & element)366 s32 linear_search(T& element) 367 { 368 for (u32 i=0; i<used; ++i) 369 if (!(element < data[i]) && !(data[i] < element)) 370 return (s32)i; 371 372 return -1; 373 } 374 375 376 //! Finds an element in linear time, which is very slow. Use 377 //! binary_search for faster finding. Only works if =operator is implemented. 378 //! \param element: Element to search for. 379 //! \return Returns position of the searched element if it was found, 380 //! otherwise -1 is returned. linear_reverse_search(T & element)381 s32 linear_reverse_search(T& element) 382 { 383 for (s32 i=used-1; i>=0; --i) 384 if (data[i] == element) 385 return (s32)i; 386 387 return -1; 388 } 389 390 391 392 //! Erases an element from the array. May be slow, because all elements 393 //! following after the erased element have to be copied. 394 //! \param index: Index of element to be erased. erase(u32 index)395 void erase(u32 index) 396 { 397 _IRR_DEBUG_BREAK_IF(index>=used || index<0) // access violation 398 399 for (u32 i=index+1; i<used; ++i) 400 data[i-1] = data[i]; 401 402 --used; 403 } 404 405 406 //! Erases some elements from the array. may be slow, because all elements 407 //! following after the erased element have to be copied. 408 //! \param index: Index of the first element to be erased. 409 //! \param count: Amount of elements to be erased. erase(u32 index,s32 count)410 void erase(u32 index, s32 count) 411 { 412 _IRR_DEBUG_BREAK_IF(index>=used || index<0 || count<1 || index+count>used) // access violation 413 414 for (u32 i=index+count; i<used; ++i) 415 data[i-count] = data[i]; 416 417 used-= count; 418 } 419 420 421 //! Sets if the array is sorted set_sorted(bool _is_sorted)422 void set_sorted(bool _is_sorted) 423 { 424 is_sorted = _is_sorted; 425 } 426 427 428 private: 429 430 T* data; 431 u32 allocated; 432 u32 used; 433 bool free_when_destroyed; 434 bool is_sorted; 435 }; 436 437 438 } // end namespace core 439 } // end namespace irr 440 441 442 443 #endif 444 445