vrshoot

annotate libs/assimp/irrXML/irrArray.h @ 0:b2f14e535253

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