diff options
Diffstat (limited to 'libraries/irrlicht-1.8.1/include/irrArray.h')
-rw-r--r-- | libraries/irrlicht-1.8.1/include/irrArray.h | 627 |
1 files changed, 627 insertions, 0 deletions
diff --git a/libraries/irrlicht-1.8.1/include/irrArray.h b/libraries/irrlicht-1.8.1/include/irrArray.h new file mode 100644 index 0000000..7dab593 --- /dev/null +++ b/libraries/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 | |||
13 | namespace irr | ||
14 | { | ||
15 | namespace 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 | */ | ||
21 | template <class T, typename TAlloc = irrAllocator<T> > | ||
22 | class array | ||
23 | { | ||
24 | |||
25 | public: | ||
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 | |||
612 | private: | ||
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 | |||