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 
29  : data(0), allocated(0), used(0),
30  strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
31  {
32  }
33 
34 
36 
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 
46  array(const array<T, TAlloc>& other) : data(0)
47  {
48  *this = other;
49  }
50 
51 
53 
56  {
57  clear();
58  }
59 
60 
62 
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 
100 
104  {
105  strategy = newStrategy;
106  }
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  {
125  insert(element);
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
147  u32 newAlloc;
148  switch ( strategy )
149  {
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 
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 
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 
240 
248  {
249  free_when_destroyed = f;
250  }
251 
252 
254 
257  void set_used(u32 usedNow)
258  {
259  if (allocated < usedNow)
260  reallocate(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 
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 
308  bool operator != (const array<T, TAlloc>& other) const
309  {
310  return !(*this==other);
311  }
312 
313 
315  T& operator [](u32 index)
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 
333  T& getLast()
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 
352  T* pointer()
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 
409  s32 binary_search(const T& element)
410  {
411  sort();
412  return binary_search(element, 0, used-1);
413  }
414 
415 
417 
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 
432 
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 
469 
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 
501 
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 
517 
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 
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 
584  void set_sorted(bool _is_sorted)
585  {
586  is_sorted = _is_sorted;
587  }
588 
589 
591 
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 
void set_used(u32 usedNow)
Sets the size of the array and allocates new elements if necessary.
Definition: irrArray.h:257
T & operator[](u32 index)
Direct access operator.
Definition: irrArray.h:315
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
array()
Default constructor for empty array.
Definition: irrArray.h:28
bool operator==(const array< T, TAlloc > &other) const
Equality operator.
Definition: irrArray.h:295
const T * const_pointer() const
Gets a const pointer to the array.
Definition: irrArray.h:360
void sort()
Sorts the array using heapsort.
Definition: irrArray.h:394
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
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:377
T & getLast()
Gets last element.
Definition: irrArray.h:333
void setAllocStrategy(eAllocStrategy newStrategy=ALLOC_STRATEGY_DOUBLE)
set a new allocation strategy
Definition: irrArray.h:103
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 array< T, TAlloc > & operator=(const array< T, TAlloc > &other)
Assignment operator.
Definition: irrArray.h:267
void push_back(const T &element)
Adds an element at back of array.
Definition: irrArray.h:112
bool empty() const
Check if array is empty.
Definition: irrArray.h:385
eAllocStrategy
defines an allocation strategy
Definition: irrAllocator.h:112
void set_sorted(bool _is_sorted)
Sets if the array is sorted.
Definition: irrArray.h:584
s32 linear_reverse_search(const T &element) const
Finds an element in linear time, which is very slow.
Definition: irrArray.h:522
s32 binary_search_multi(const T &element, s32 &last)
Definition: irrArray.h:475
signed int s32
32 bit signed variable.
Definition: irrTypes.h:66
void erase(u32 index, s32 count)
Erases some elements from the array.
Definition: irrArray.h:557
bool operator!=(const array< T, TAlloc > &other) const
Inequality operator.
Definition: irrArray.h:308
unsigned int u32
32 bit unsigned variable.
Definition: irrTypes.h:58
s32 binary_search(const T &element)
Performs a binary search for an element, returns -1 if not found.
Definition: irrArray.h:409
void heapsort(T *array_, s32 size)
Sorts an array with size &#39;size&#39; using heapsort.
Definition: heapsort.h:41
u32 size() const
Get number of occupied elements of the array.
Definition: irrArray.h:368
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
Definition: irrTypes.h:178
void swap(array< T, TAlloc > &other)
Swap the content of this array container with the content of another array.
Definition: irrArray.h:594
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition: irrMath.h:177
void erase(u32 index)
Erases an element from the array.
Definition: irrArray.h:536
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
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:203
array(u32 start_count)
Constructs an array and allocates an initial chunk of memory.
Definition: irrArray.h:37
void push_front(const T &element)
Adds an element at the front of the array.
Definition: irrArray.h:123
~array()
Destructor.
Definition: irrArray.h:55
array(const array< T, TAlloc > &other)
Copy constructor.
Definition: irrArray.h:46
const T & getLast() const
Gets last element.
Definition: irrArray.h:342
T * pointer()
Gets a pointer to the array.
Definition: irrArray.h:352
void set_free_when_destroyed(bool f)
Sets if the array should delete the memory it uses upon destruction.
Definition: irrArray.h:247