Line data Source code
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 1129799 : array()
29 : : data(0), allocated(0), used(0),
30 1129799 : strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
31 : {
32 1129799 : }
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 1137385 : ~array()
56 : {
57 1137385 : clear();
58 1137385 : }
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 1190428 : void reallocate(u32 new_size, bool canShrink=true)
68 : {
69 1190428 : if (allocated==new_size)
70 0 : return;
71 1190428 : if (!canShrink && (new_size < allocated))
72 0 : return;
73 :
74 1190428 : T* old_data = data;
75 :
76 1190428 : data = allocator.allocate(new_size); //new T[new_size];
77 1190428 : allocated = new_size;
78 :
79 : // copy old data
80 1190428 : s32 end = used < new_size ? used : new_size;
81 :
82 16722804 : for (s32 i=0; i<end; ++i)
83 : {
84 : // data[i] = old_data[i];
85 15532376 : allocator.construct(&data[i], old_data[i]);
86 : }
87 :
88 : // destruct old data
89 16722804 : for (u32 j=0; j<used; ++j)
90 15532376 : allocator.destruct(&old_data[j]);
91 :
92 1190428 : if (allocated < used)
93 0 : used = allocated;
94 :
95 1190428 : 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 42486392 : void push_back(const T& element)
113 : {
114 42486392 : insert(element, used);
115 42486392 : }
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 43205252 : void insert(const T& element, u32 index=0)
136 : {
137 : _IRR_DEBUG_BREAK_IF(index>used) // access violation
138 :
139 43205252 : 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 135768 : const T e(element);
145 :
146 : // increase data block
147 : u32 newAlloc;
148 131082 : switch ( strategy )
149 : {
150 : case ALLOC_STRATEGY_DOUBLE:
151 262164 : newAlloc = used + 1 + (allocated < 500 ?
152 131082 : (allocated < 5 ? 5 : used) : used >> 2);
153 131082 : break;
154 : default:
155 : case ALLOC_STRATEGY_SAFE:
156 0 : newAlloc = used + 1;
157 0 : break;
158 : }
159 131082 : reallocate( newAlloc);
160 :
161 : // move array content and construct new element
162 : // first move end one up
163 131082 : for (u32 i=used; i>index; --i)
164 : {
165 0 : if (i<used)
166 0 : allocator.destruct(&data[i]);
167 0 : allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];
168 : }
169 : // then add new element
170 131082 : if (used > index)
171 0 : allocator.destruct(&data[index]);
172 131082 : allocator.construct(&data[index], e); // data[index] = e;
173 : }
174 : else
175 : {
176 : // element inserted not at end
177 43074170 : if ( used > index )
178 : {
179 : // create one new element at the end
180 0 : allocator.construct(&data[used], data[used-1]);
181 :
182 : // move the rest of the array content
183 0 : for (u32 i=used-1; i>index; --i)
184 : {
185 0 : data[i] = data[i-1];
186 : }
187 : // insert the new element
188 0 : data[index] = element;
189 : }
190 : else
191 : {
192 : // insert the new element to the end
193 43074170 : allocator.construct(&data[index], element);
194 : }
195 : }
196 : // set to false as we don't know if we have the comparison operators
197 43205245 : is_sorted = false;
198 43205245 : ++used;
199 43205245 : }
200 :
201 :
202 : //! Clears the array and deletes all allocated memory.
203 1137385 : void clear()
204 : {
205 1137385 : if (free_when_destroyed)
206 : {
207 44319583 : for (u32 i=0; i<used; ++i)
208 43182198 : allocator.destruct(&data[i]);
209 :
210 1137385 : allocator.deallocate(data); // delete [] data;
211 : }
212 1137385 : data = 0;
213 1137385 : used = 0;
214 1137385 : allocated = 0;
215 1137385 : is_sorted = true;
216 1137385 : }
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 2 : void set_used(u32 usedNow)
258 : {
259 2 : if (allocated < usedNow)
260 2 : reallocate(usedNow);
261 :
262 2 : used = usedNow;
263 2 : }
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 62875973 : T& operator [](u32 index)
316 : {
317 : _IRR_DEBUG_BREAK_IF(index>=used) // access violation
318 :
319 62875973 : return data[index];
320 : }
321 :
322 :
323 : //! Direct const access operator
324 5240388 : const T& operator [](u32 index) const
325 : {
326 : _IRR_DEBUG_BREAK_IF(index>=used) // access violation
327 :
328 5240388 : 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 2739834 : T* pointer()
353 : {
354 2739834 : return data;
355 : }
356 :
357 :
358 : //! Gets a const pointer to the array.
359 : /** \return Pointer to the array. */
360 2912336 : const T* const_pointer() const
361 : {
362 2912336 : 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 27087578 : u32 size() const
369 : {
370 27087578 : 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 694050 : bool empty() const
386 : {
387 694050 : 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 0 : void erase(u32 index)
537 : {
538 : _IRR_DEBUG_BREAK_IF(index>=used) // access violation
539 :
540 0 : for (u32 i=index+1; i<used; ++i)
541 : {
542 0 : allocator.destruct(&data[i-1]);
543 0 : allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];
544 : }
545 :
546 0 : allocator.destruct(&data[used-1]);
547 :
548 0 : --used;
549 0 : }
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 :
|
