aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/src/others/irrlicht-1.8.1/include/irrArray.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/others/irrlicht-1.8.1/include/irrArray.h')
-rw-r--r--src/others/irrlicht-1.8.1/include/irrArray.h627
1 files changed, 627 insertions, 0 deletions
diff --git a/src/others/irrlicht-1.8.1/include/irrArray.h b/src/others/irrlicht-1.8.1/include/irrArray.h
new file mode 100644
index 0000000..7dab593
--- /dev/null
+++ b/src/others/irrlicht-1.8.1/include/irrArray.h
@@ -0,0 +1,627 @@
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
13namespace irr
14{
15namespace 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*/
21template <class T, typename TAlloc = irrAllocator<T> >
22class array
23{
24
25public:
26
27 //! Default constructor for empty 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. */
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
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. */
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. */
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. */
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.
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. */
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. */
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.
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
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. */
352 T* pointer()
353 {
354 return data;
355 }
356
357
358 //! Gets a const pointer to the array.
359 /** \return Pointer to the array. */
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. */
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); */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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. */
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
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 */
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
612private:
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
generated by cgit v1.1 at 2024-06-27 09:18:01 +0000