Home | Namespaces | Hierarchy | Alphabetical List | Class list | Files | Namespace Members | Class members | File members | Tutorials
irrArray.h
Go to the documentation of this file.
1 // Copyright (C) 2002-2010 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 
63  void reallocate(u32 new_size)
64  {
65  T* old_data = data;
66 
67  data = allocator.allocate(new_size); //new T[new_size];
68  allocated = new_size;
69 
70  // copy old data
71  s32 end = used < new_size ? used : new_size;
72 
73  for (s32 i=0; i<end; ++i)
74  {
75  // data[i] = old_data[i];
76  allocator.construct(&data[i], old_data[i]);
77  }
78 
79  // destruct old data
80  for (u32 j=0; j<used; ++j)
81  allocator.destruct(&old_data[j]);
82 
83  if (allocated < used)
84  used = allocated;
85 
86  allocator.deallocate(old_data); //delete [] old_data;
87  }
88 
89 
91 
95  {
96  strategy = newStrategy;
97  }
98 
99 
101 
103  void push_back(const T& element)
104  {
105  insert(element, used);
106  }
107 
108 
110 
114  void push_front(const T& element)
115  {
116  insert(element);
117  }
118 
119 
121 
126  void insert(const T& element, u32 index=0)
127  {
128  _IRR_DEBUG_BREAK_IF(index>used) // access violation
129 
130  if (used + 1 > allocated)
131  {
132  // this doesn't work if the element is in the same
133  // array. So we'll copy the element first to be sure
134  // we'll get no data corruption
135  const T e(element);
136 
137  // increase data block
138  u32 newAlloc;
139  switch ( strategy )
140  {
142  newAlloc = used + 1 + (allocated < 500 ?
143  (allocated < 5 ? 5 : used) : used >> 2);
144  break;
145  default:
146  case ALLOC_STRATEGY_SAFE:
147  newAlloc = used + 1;
148  break;
149  }
150  reallocate( newAlloc);
151 
152  // move array content and construct new element
153  // first move end one up
154  for (u32 i=used; i>index; --i)
155  {
156  if (i<used)
157  allocator.destruct(&data[i]);
158  allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];
159  }
160  // then add new element
161  if (used > index)
162  allocator.destruct(&data[index]);
163  allocator.construct(&data[index], e); // data[index] = e;
164  }
165  else
166  {
167  // element inserted not at end
168  if ( used > index )
169  {
170  // create one new element at the end
171  allocator.construct(&data[used], data[used-1]);
172 
173  // move the rest of the array content
174  for (u32 i=used-1; i>index; --i)
175  {
176  data[i] = data[i-1];
177  }
178  // insert the new element
179  data[index] = element;
180  }
181  else
182  {
183  // insert the new element to the end
184  allocator.construct(&data[index], element);
185  }
186  }
187  // set to false as we don't know if we have the comparison operators
188  is_sorted = false;
189  ++used;
190  }
191 
192 
194  void clear()
195  {
196  if (free_when_destroyed)
197  {
198  for (u32 i=0; i<used; ++i)
199  allocator.destruct(&data[i]);
200 
201  allocator.deallocate(data); // delete [] data;
202  }
203  data = 0;
204  used = 0;
205  allocated = 0;
206  is_sorted = true;
207  }
208 
209 
211 
219  void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)
220  {
221  clear();
222  data = newPointer;
223  allocated = size;
224  used = size;
225  is_sorted = _is_sorted;
226  free_when_destroyed=_free_when_destroyed;
227  }
228 
229 
231 
239  {
240  free_when_destroyed = f;
241  }
242 
243 
245 
248  void set_used(u32 usedNow)
249  {
250  if (allocated < usedNow)
251  reallocate(usedNow);
252 
253  used = usedNow;
254  }
255 
256 
259  {
260  if (this == &other)
261  return *this;
262  strategy = other.strategy;
263 
264  if (data)
265  clear();
266 
267  //if (allocated < other.allocated)
268  if (other.allocated == 0)
269  data = 0;
270  else
271  data = allocator.allocate(other.allocated); // new T[other.allocated];
272 
273  used = other.used;
274  free_when_destroyed = true;
275  is_sorted = other.is_sorted;
276  allocated = other.allocated;
277 
278  for (u32 i=0; i<other.used; ++i)
279  allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i];
280 
281  return *this;
282  }
283 
284 
286  bool operator == (const array<T, TAlloc>& other) const
287  {
288  if (used != other.used)
289  return false;
290 
291  for (u32 i=0; i<other.used; ++i)
292  if (data[i] != other[i])
293  return false;
294  return true;
295  }
296 
297 
299  bool operator != (const array<T, TAlloc>& other) const
300  {
301  return !(*this==other);
302  }
303 
304 
306  T& operator [](u32 index)
307  {
308  _IRR_DEBUG_BREAK_IF(index>=used) // access violation
309 
310  return data[index];
311  }
312 
313 
315  const T& operator [](u32 index) const
316  {
317  _IRR_DEBUG_BREAK_IF(index>=used) // access violation
318 
319  return data[index];
320  }
321 
322 
324  T& getLast()
325  {
326  _IRR_DEBUG_BREAK_IF(!used) // access violation
327 
328  return data[used-1];
329  }
330 
331 
333  const T& getLast() const
334  {
335  _IRR_DEBUG_BREAK_IF(!used) // access violation
336 
337  return data[used-1];
338  }
339 
340 
342 
343  T* pointer()
344  {
345  return data;
346  }
347 
348 
350 
351  const T* const_pointer() const
352  {
353  return data;
354  }
355 
356 
358 
359  u32 size() const
360  {
361  return used;
362  }
363 
364 
366 
369  {
370  return allocated;
371  }
372 
373 
375 
376  bool empty() const
377  {
378  return used == 0;
379  }
380 
381 
383 
385  void sort()
386  {
387  if (!is_sorted && used>1)
388  heapsort(data, used);
389  is_sorted = true;
390  }
391 
392 
394 
400  s32 binary_search(const T& element)
401  {
402  sort();
403  return binary_search(element, 0, used-1);
404  }
405 
406 
408 
413  s32 binary_search(const T& element) const
414  {
415  if (is_sorted)
416  return binary_search(element, 0, used-1);
417  else
418  return linear_search(element);
419  }
420 
421 
423 
428  s32 binary_search(const T& element, s32 left, s32 right) const
429  {
430  if (!used)
431  return -1;
432 
433  s32 m;
434 
435  do
436  {
437  m = (left+right)>>1;
438 
439  if (element < data[m])
440  right = m - 1;
441  else
442  left = m + 1;
443 
444  } while((element < data[m] || data[m] < element) && left<=right);
445  // this last line equals to:
446  // " while((element != array[m]) && left<=right);"
447  // but we only want to use the '<' operator.
448  // the same in next line, it is "(element == array[m])"
449 
450 
451  if (!(element < data[m]) && !(data[m] < element))
452  return m;
453 
454  return -1;
455  }
456 
457 
460 
466  s32 binary_search_multi(const T& element, s32 &last)
467  {
468  sort();
469  s32 index = binary_search(element, 0, used-1);
470  if ( index < 0 )
471  return index;
472 
473  // The search can be somewhere in the middle of the set
474  // look linear previous and past the index
475  last = index;
476 
477  while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
478  {
479  index -= 1;
480  }
481  // look linear up
482  while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )
483  {
484  last += 1;
485  }
486 
487  return index;
488  }
489 
490 
492 
497  s32 linear_search(const T& element) const
498  {
499  for (u32 i=0; i<used; ++i)
500  if (element == data[i])
501  return (s32)i;
502 
503  return -1;
504  }
505 
506 
508 
513  s32 linear_reverse_search(const T& element) const
514  {
515  for (s32 i=used-1; i>=0; --i)
516  if (data[i] == element)
517  return i;
518 
519  return -1;
520  }
521 
522 
524 
527  void erase(u32 index)
528  {
529  _IRR_DEBUG_BREAK_IF(index>=used) // access violation
530 
531  for (u32 i=index+1; i<used; ++i)
532  {
533  allocator.destruct(&data[i-1]);
534  allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];
535  }
536 
537  allocator.destruct(&data[used-1]);
538 
539  --used;
540  }
541 
542 
544 
548  void erase(u32 index, s32 count)
549  {
550  if (index>=used || count<1)
551  return;
552  if (index+count>used)
553  count = used-index;
554 
555  u32 i;
556  for (i=index; i<index+count; ++i)
557  allocator.destruct(&data[i]);
558 
559  for (i=index+count; i<used; ++i)
560  {
561  if (i-count >= index+count) // not already destructed before loop
562  allocator.destruct(&data[i-count]);
563 
564  allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i];
565 
566  if (i >= used-count) // those which are not overwritten
567  allocator.destruct(&data[i]);
568  }
569 
570  used-= count;
571  }
572 
573 
575  void set_sorted(bool _is_sorted)
576  {
577  is_sorted = _is_sorted;
578  }
579 
580 
582 
585  void swap(array<T, TAlloc>& other)
586  {
587  core::swap(data, other.data);
588  core::swap(allocated, other.allocated);
589  core::swap(used, other.used);
590  core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation
591  eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields
592  strategy = other.strategy;
593  other.strategy = helper_strategy;
594  bool helper_free_when_destroyed(free_when_destroyed);
595  free_when_destroyed = other.free_when_destroyed;
596  other.free_when_destroyed = helper_free_when_destroyed;
597  bool helper_is_sorted(is_sorted);
598  is_sorted = other.is_sorted;
599  other.is_sorted = helper_is_sorted;
600  }
601 
602 
603 private:
604  T* data;
605  u32 allocated;
606  u32 used;
607  TAlloc allocator;
608  eAllocStrategy strategy:4;
609  bool free_when_destroyed:1;
610  bool is_sorted:1;
611 };
612 
613 
614 } // end namespace core
615 } // end namespace irr
616 
617 #endif
618 

The Irrlicht Engine
The Irrlicht Engine Documentation © 2003-2010 by Nikolaus Gebhardt. Generated on Tue Jun 5 2012 17:57:12 by Doxygen (1.8.1)