Irrlicht 3D Engine
 
Loading...
Searching...
No Matches
irrArray.h
Go to the documentation of this file.
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
19
21template <class T, typename TAlloc = irrAllocator<T> >
22class array
23{
24
25public:
26
29 : data(0), allocated(0), used(0),
30 strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
31 {
32 }
33
34
36
38 : data(0), allocated(0), used(0),
39 strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
40 {
42 }
43
44
46 array(const array<T, TAlloc>& other) : data(0)
47 {
48 *this = other;
49 }
50
51
53
56 {
57 clear();
58 }
59
60
62
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
100
107
108
110
112 void push_back(const T& element)
113 {
114 insert(element, used);
115 }
116
117
119
123 void push_front(const T& element)
124 {
126 }
127
128
130
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
148 switch ( strategy )
149 {
151 newAlloc = used + 1 + (allocated < 500 ?
153 break;
154 default:
156 newAlloc = used + 1;
157 break;
158 }
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
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
220
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
240
248 {
249 free_when_destroyed = f;
250 }
251
252
254
258 {
259 if (allocated < usedNow)
261
262 used = usedNow;
263 }
264
265
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
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
309 {
310 return !(*this==other);
311 }
312
313
316 {
317 _IRR_DEBUG_BREAK_IF(index>=used) // access violation
318
319 return data[index];
320 }
321
322
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
334 {
335 _IRR_DEBUG_BREAK_IF(!used) // access violation
336
337 return data[used-1];
338 }
339
340
342 const T& getLast() const
343 {
344 _IRR_DEBUG_BREAK_IF(!used) // access violation
345
346 return data[used-1];
347 }
348
349
351
353 {
354 return data;
355 }
356
357
359
360 const T* const_pointer() const
361 {
362 return data;
363 }
364
365
367
368 u32 size() const
369 {
370 return used;
371 }
372
373
375
378 {
379 return allocated;
380 }
381
382
384
385 bool empty() const
386 {
387 return used == 0;
388 }
389
390
392
394 void sort()
395 {
396 if (!is_sorted && used>1)
397 heapsort(data, used);
398 is_sorted = true;
399 }
400
401
403
410 {
411 sort();
412 return binary_search(element, 0, used-1);
413 }
414
415
417
423 {
424 if (is_sorted)
425 return binary_search(element, 0, used-1);
426 else
427 return linear_search(element);
428 }
429
430
432
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
469
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
501
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
517
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
533
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
553
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
585 {
586 is_sorted = _is_sorted;
587 }
588
589
591
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
Axis aligned bounding box in 3d dimensional space.
Definition aabbox3d.h:22
Self reallocating template array (like stl vector) with additional features.
Definition irrArray.h:23
const array< T, TAlloc > & operator=(const array< T, TAlloc > &other)
Assignment operator.
Definition irrArray.h:267
u32 allocated_size() const
Get amount of memory allocated.
Definition irrArray.h:377
void clear()
Clears the array and deletes all allocated memory.
Definition irrArray.h:203
void push_front(const T &element)
Adds an element at the front of the array.
Definition irrArray.h:123
s32 binary_search(const T &element)
Performs a binary search for an element, returns -1 if not found.
Definition irrArray.h:409
void insert(const T &element, u32 index=0)
Insert item into array at specified position.
Definition irrArray.h:135
s32 linear_search(const T &element) const
Finds an element in linear time, which is very slow.
Definition irrArray.h:506
array(const array< T, TAlloc > &other)
Copy constructor.
Definition irrArray.h:46
void erase(u32 index)
Erases an element from the array.
Definition irrArray.h:536
array()
Default constructor for empty array.
Definition irrArray.h:28
s32 binary_search_multi(const T &element, s32 &last)
Definition irrArray.h:475
void set_used(u32 usedNow)
Sets the size of the array and allocates new elements if necessary.
Definition irrArray.h:257
T & getLast()
Gets last element.
Definition irrArray.h:333
bool operator!=(const array< T, TAlloc > &other) const
Inequality operator.
Definition irrArray.h:308
void set_pointer(T *newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)
Sets pointer to new array, using this as new workspace.
Definition irrArray.h:228
bool operator==(const array< T, TAlloc > &other) const
Equality operator.
Definition irrArray.h:295
void setAllocStrategy(eAllocStrategy newStrategy=ALLOC_STRATEGY_DOUBLE)
set a new allocation strategy
Definition irrArray.h:103
void sort()
Sorts the array using heapsort.
Definition irrArray.h:394
void swap(array< T, TAlloc > &other)
Swap the content of this array container with the content of another array.
Definition irrArray.h:594
T & operator[](u32 index)
Direct access operator.
Definition irrArray.h:315
bool empty() const
Check if array is empty.
Definition irrArray.h:385
T * pointer()
Gets a pointer to the array.
Definition irrArray.h:352
s32 binary_search(const T &element, s32 left, s32 right) const
Performs a binary search for an element, returns -1 if not found.
Definition irrArray.h:437
const T & getLast() const
Gets last element.
Definition irrArray.h:342
~array()
Destructor.
Definition irrArray.h:55
u32 size() const
Get number of occupied elements of the array.
Definition irrArray.h:368
array(u32 start_count)
Constructs an array and allocates an initial chunk of memory.
Definition irrArray.h:37
void set_sorted(bool _is_sorted)
Sets if the array is sorted.
Definition irrArray.h:584
void erase(u32 index, s32 count)
Erases some elements from the array.
Definition irrArray.h:557
const T * const_pointer() const
Gets a const pointer to the array.
Definition irrArray.h:360
void push_back(const T &element)
Adds an element at back of array.
Definition irrArray.h:112
void reallocate(u32 new_size, bool canShrink=true)
Reallocates the array, make it bigger or smaller.
Definition irrArray.h:67
s32 binary_search(const T &element) const
Performs a binary search for an element if possible, returns -1 if not found.
Definition irrArray.h:422
s32 linear_reverse_search(const T &element) const
Finds an element in linear time, which is very slow.
Definition irrArray.h:522
void set_free_when_destroyed(bool f)
Sets if the array should delete the memory it uses upon destruction.
Definition irrArray.h:247
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
Definition irrTypes.h:178
eAllocStrategy
defines an allocation strategy
@ ALLOC_STRATEGY_DOUBLE
@ ALLOC_STRATEGY_SAFE
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition irrMath.h:177
void heapsort(T *array_, s32 size)
Sorts an array with size 'size' using heapsort.
Definition heapsort.h:41
Everything in the Irrlicht Engine can be found in this namespace.
Definition aabbox3d.h:13
unsigned int u32
32 bit unsigned variable.
Definition irrTypes.h:58
signed int s32
32 bit signed variable.
Definition irrTypes.h:66