Irrlicht 3D Engine
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 
13 namespace irr
14 {
15 namespace core
16 {
17 
19 
21 template <class T, typename TAlloc = irrAllocator<T> >
22 class array
23 {
24 
25 public:
26 
28  array() : data(0), allocated(0), used(0),
29  strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
30  {
31  }
32 
33 
35 
36  explicit array(u32 start_count) : data(0), allocated(0), used(0),
37  strategy(ALLOC_STRATEGY_DOUBLE),
38  free_when_destroyed(true), is_sorted(true)
39  {
40  reallocate(start_count);
41  }
42 
43 
45  array(const array<T, TAlloc>& other) : data(0)
46  {
47  *this = other;
48  }
49 
50 
52 
55  {
56  clear();
57  }
58 
59 
61 
66  void reallocate(u32 new_size, bool canShrink=true)
67  {
68  if (allocated==new_size)
69  return;
70  if (!canShrink && (new_size < allocated))
71  return;
72 
73  T* old_data = data;
74 
75  data = allocator.allocate(new_size); //new T[new_size];
76  allocated = new_size;
77 
78  // copy old data
79  s32 end = used < new_size ? used : new_size;
80 
81  for (s32 i=0; i<end; ++i)
82  {
83  // data[i] = old_data[i];
84  allocator.construct(&data[i], old_data[i]);
85  }
86 
87  // destruct old data
88  for (u32 j=0; j<used; ++j)
89  allocator.destruct(&old_data[j]);
90 
91  if (allocated < used)
92  used = allocated;
93 
94  allocator.deallocate(old_data); //delete [] old_data;
95  }
96 
97 
99 
103  {
104  strategy = newStrategy;
105  }
106 
107 
109 
111  void push_back(const T& element)
112  {
113  insert(element, used);
114  }
115 
116 
118 
122  void push_front(const T& element)
123  {
124  insert(element);
125  }
126 
127 
129 
132  void insert(const T& element, u32 index=0)
133  {
134  _IRR_DEBUG_BREAK_IF(index>used) // access violation
135 
136  if (used + 1 > allocated)
137  {
138  // this doesn't work if the element is in the same
139  // array. So we'll copy the element first to be sure
140  // we'll get no data corruption
141  const T e(element);
142 
143  // increase data block
144  u32 newAlloc;
145  switch ( strategy )
146  {
148  newAlloc = used + 5 + (allocated < 500 ? used : used >> 2);
149  break;
150  default:
151  case ALLOC_STRATEGY_SAFE:
152  newAlloc = used + 1;
153  break;
154  }
155  reallocate( newAlloc);
156 
157  // move array content and construct new element
158  // first move end one up
159  for (u32 i=used; i>index; --i)
160  {
161  if (i<used)
162  allocator.destruct(&data[i]);
163  allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];
164  }
165  // then add new element
166  if (used > index)
167  allocator.destruct(&data[index]);
168  allocator.construct(&data[index], e); // data[index] = e;
169  }
170  else
171  {
172  // element inserted not at end
173  if ( used > index )
174  {
175  // create one new element at the end
176  allocator.construct(&data[used], data[used-1]);
177 
178  // move the rest of the array content
179  for (u32 i=used-1; i>index; --i)
180  {
181  data[i] = data[i-1];
182  }
183  // insert the new element
184  data[index] = element;
185  }
186  else
187  {
188  // insert the new element to the end
189  allocator.construct(&data[index], element);
190  }
191  }
192  // set to false as we don't know if we have the comparison operators
193  is_sorted = false;
194  ++used;
195  }
196 
197 
199  void clear()
200  {
201  if (free_when_destroyed)
202  {
203  for (u32 i=0; i<used; ++i)
204  allocator.destruct(&data[i]);
205 
206  allocator.deallocate(data); // delete [] data;
207  }
208  data = 0;
209  used = 0;
210  allocated = 0;
211  is_sorted = true;
212  }
213 
214 
216 
224  void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)
225  {
226  clear();
227  data = newPointer;
228  allocated = size;
229  used = size;
230  is_sorted = _is_sorted;
231  free_when_destroyed=_free_when_destroyed;
232  }
233 
234 
236 
244  {
245  free_when_destroyed = f;
246  }
247 
248 
250 
253  void set_used(u32 usedNow)
254  {
255  if (allocated < usedNow)
256  reallocate(usedNow);
257 
258  used = usedNow;
259  }
260 
261 
264  {
265  if (this == &other)
266  return *this;
267  strategy = other.strategy;
268 
269  if (data)
270  clear();
271 
272  //if (allocated < other.allocated)
273  if (other.allocated == 0)
274  data = 0;
275  else
276  data = allocator.allocate(other.allocated); // new T[other.allocated];
277 
278  used = other.used;
279  free_when_destroyed = true;
280  is_sorted = other.is_sorted;
281  allocated = other.allocated;
282 
283  for (u32 i=0; i<other.used; ++i)
284  allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i];
285 
286  return *this;
287  }
288 
289 
291  bool operator == (const array<T, TAlloc>& other) const
292  {
293  if (used != other.used)
294  return false;
295 
296  for (u32 i=0; i<other.used; ++i)
297  if (data[i] != other[i])
298  return false;
299  return true;
300  }
301 
302 
304  bool operator != (const array<T, TAlloc>& other) const
305  {
306  return !(*this==other);
307  }
308 
309 
311  T& operator [](u32 index)
312  {
313  _IRR_DEBUG_BREAK_IF(index>=used) // access violation
314 
315  return data[index];
316  }
317 
318 
320  const T& operator [](u32 index) const
321  {
322  _IRR_DEBUG_BREAK_IF(index>=used) // access violation
323 
324  return data[index];
325  }
326 
327 
329  T& getLast()
330  {
331  _IRR_DEBUG_BREAK_IF(!used) // access violation
332 
333  return data[used-1];
334  }
335 
336 
338  const T& getLast() const
339  {
340  _IRR_DEBUG_BREAK_IF(!used) // access violation
341 
342  return data[used-1];
343  }
344 
345 
347 
348  T* pointer()
349  {
350  return data;
351  }
352 
353 
355 
356  const T* const_pointer() const
357  {
358  return data;
359  }
360 
361 
363 
364  u32 size() const
365  {
366  return used;
367  }
368 
369 
371 
374  {
375  return allocated;
376  }
377 
378 
380 
381  bool empty() const
382  {
383  return used == 0;
384  }
385 
386 
388 
390  void sort()
391  {
392  if (!is_sorted && used>1)
393  heapsort(data, used);
394  is_sorted = true;
395  }
396 
397 
399 
405  s32 binary_search(const T& element)
406  {
407  sort();
408  return binary_search(element, 0, used-1);
409  }
410 
411 
413 
418  s32 binary_search(const T& element) const
419  {
420  if (is_sorted)
421  return binary_search(element, 0, used-1);
422  else
423  return linear_search(element);
424  }
425 
426 
428 
433  s32 binary_search(const T& element, s32 left, s32 right) const
434  {
435  if (!used)
436  return -1;
437 
438  s32 m;
439 
440  do
441  {
442  m = (left+right)>>1;
443 
444  if (element < data[m])
445  right = m - 1;
446  else
447  left = m + 1;
448 
449  } while((element < data[m] || data[m] < element) && left<=right);
450  // this last line equals to:
451  // " while((element != array[m]) && left<=right);"
452  // but we only want to use the '<' operator.
453  // the same in next line, it is "(element == array[m])"
454 
455 
456  if (!(element < data[m]) && !(data[m] < element))
457  return m;
458 
459  return -1;
460  }
461 
462 
465 
471  s32 binary_search_multi(const T& element, s32 &last)
472  {
473  sort();
474  s32 index = binary_search(element, 0, used-1);
475  if ( index < 0 )
476  return index;
477 
478  // The search can be somewhere in the middle of the set
479  // look linear previous and past the index
480  last = index;
481 
482  while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
483  {
484  index -= 1;
485  }
486  // look linear up
487  while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )
488  {
489  last += 1;
490  }
491 
492  return index;
493  }
494 
495 
497 
502  s32 linear_search(const T& element) const
503  {
504  for (u32 i=0; i<used; ++i)
505  if (element == data[i])
506  return (s32)i;
507 
508  return -1;
509  }
510 
511 
513 
518  s32 linear_reverse_search(const T& element) const
519  {
520  for (s32 i=used-1; i>=0; --i)
521  if (data[i] == element)
522  return i;
523 
524  return -1;
525  }
526 
527 
529 
532  void erase(u32 index)
533  {
534  _IRR_DEBUG_BREAK_IF(index>=used) // access violation
535 
536  for (u32 i=index+1; i<used; ++i)
537  {
538  allocator.destruct(&data[i-1]);
539  allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];
540  }
541 
542  allocator.destruct(&data[used-1]);
543 
544  --used;
545  }
546 
547 
549 
553  void erase(u32 index, s32 count)
554  {
555  if (index>=used || count<1)
556  return;
557  if (index+count>used)
558  count = used-index;
559 
560  u32 i;
561  for (i=index; i<index+count; ++i)
562  allocator.destruct(&data[i]);
563 
564  for (i=index+count; i<used; ++i)
565  {
566  if (i-count >= index+count) // not already destructed before loop
567  allocator.destruct(&data[i-count]);
568 
569  allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i];
570 
571  if (i >= used-count) // those which are not overwritten
572  allocator.destruct(&data[i]);
573  }
574 
575  used-= count;
576  }
577 
578 
580  void set_sorted(bool _is_sorted)
581  {
582  is_sorted = _is_sorted;
583  }
584 
585 
587 
590  void swap(array<T, TAlloc>& other)
591  {
592  core::swap(data, other.data);
593  core::swap(allocated, other.allocated);
594  core::swap(used, other.used);
595  core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation
596  eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields
597  strategy = other.strategy;
598  other.strategy = helper_strategy;
599  bool helper_free_when_destroyed(free_when_destroyed);
600  free_when_destroyed = other.free_when_destroyed;
601  other.free_when_destroyed = helper_free_when_destroyed;
602  bool helper_is_sorted(is_sorted);
603  is_sorted = other.is_sorted;
604  other.is_sorted = helper_is_sorted;
605  }
606 
607  typedef TAlloc allocator_type;
608  typedef T value_type;
609  typedef u32 size_type;
610 
611 private:
612  T* data;
613  u32 allocated;
614  u32 used;
615  TAlloc allocator;
616  eAllocStrategy strategy:4;
617  bool free_when_destroyed:1;
618  bool is_sorted:1;
619 };
620 
621 
622 } // end namespace core
623 } // end namespace irr
624 
625 #endif
626 
void set_used(u32 usedNow)
Sets the size of the array and allocates new elements if necessary.
Definition: irrArray.h:253
void reallocate(u32 new_size, bool canShrink=true)
Reallocates the array, make it bigger or smaller.
Definition: irrArray.h:66
s32 binary_search(const T &element) const
Performs a binary search for an element if possible, returns -1 if not found.
Definition: irrArray.h:418
array()
Default constructor for empty array.
Definition: irrArray.h:28
bool operator==(const array< T, TAlloc > &other) const
Equality operator.
Definition: irrArray.h:291
const T * const_pointer() const
Gets a const pointer to the array.
Definition: irrArray.h:356
void sort()
Sorts the array using heapsort.
Definition: irrArray.h:390
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:224
Everything in the Irrlicht Engine can be found in this namespace.
Definition: aabbox3d.h:12
u32 allocated_size() const
Get amount of memory allocated.
Definition: irrArray.h:373
T & getLast()
Gets last element.
Definition: irrArray.h:329
bool operator !=(const array< T, TAlloc > &other) const
Inequality operator.
Definition: irrArray.h:304
void setAllocStrategy(eAllocStrategy newStrategy=ALLOC_STRATEGY_DOUBLE)
set a new allocation strategy
Definition: irrArray.h:102
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:433
const array< T, TAlloc > & operator=(const array< T, TAlloc > &other)
Assignment operator.
Definition: irrArray.h:263
void push_back(const T &element)
Adds an element at back of array.
Definition: irrArray.h:111
bool empty() const
Check if array is empty.
Definition: irrArray.h:381
eAllocStrategy
defines an allocation strategy (used only by irr::array so far)
Definition: irrAllocator.h:112
void set_sorted(bool _is_sorted)
Sets if the array is sorted.
Definition: irrArray.h:580
s32 linear_reverse_search(const T &element) const
Finds an element in linear time, which is very slow.
Definition: irrArray.h:518
T & operator [](u32 index)
Direct access operator.
Definition: irrArray.h:311
s32 binary_search_multi(const T &element, s32 &last)
Definition: irrArray.h:471
signed int s32
32 bit signed variable.
Definition: irrTypes.h:70
void erase(u32 index, s32 count)
Erases some elements from the array.
Definition: irrArray.h:553
unsigned int u32
32 bit unsigned variable.
Definition: irrTypes.h:62
s32 binary_search(const T &element)
Performs a binary search for an element, returns -1 if not found.
Definition: irrArray.h:405
void heapsort(T *array_, s32 size)
Sorts an array with size 'size' using heapsort.
Definition: heapsort.h:41
u32 size() const
Get number of occupied elements of the array.
Definition: irrArray.h:364
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
Definition: irrTypes.h:185
void swap(array< T, TAlloc > &other)
Swap the content of this array container with the content of another array.
Definition: irrArray.h:590
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition: irrMath.h:178
void erase(u32 index)
Erases an element from the array.
Definition: irrArray.h:532
void insert(const T &element, u32 index=0)
Insert item into array at specified position.
Definition: irrArray.h:132
s32 linear_search(const T &element) const
Finds an element in linear time, which is very slow.
Definition: irrArray.h:502
TAlloc allocator_type
Definition: irrArray.h:607
const T & operator [](u32 index) const
Direct const access operator.
Definition: irrArray.h:320
Self reallocating template array (like stl vector) with additional features.
Definition: irrArray.h:22
void clear()
Clears the array and deletes all allocated memory.
Definition: irrArray.h:199
array(u32 start_count)
Constructs an array and allocates an initial chunk of memory.
Definition: irrArray.h:36
void push_front(const T &element)
Adds an element at the front of the array.
Definition: irrArray.h:122
~array()
Destructor.
Definition: irrArray.h:54
array(const array< T, TAlloc > &other)
Copy constructor.
Definition: irrArray.h:45
const T & getLast() const
Gets last element.
Definition: irrArray.h:338
T * pointer()
Gets a pointer to the array.
Definition: irrArray.h:348
void set_free_when_destroyed(bool f)
Sets if the array should delete the memory it uses upon destruction.
Definition: irrArray.h:243