5 #ifndef __IRR_ARRAY_H_INCLUDED__ 6 #define __IRR_ARRAY_H_INCLUDED__ 21 template <
class T,
typename TAlloc = irrAllocator<T> >
29 : data(0), allocated(0), used(0),
38 : data(0), allocated(0), used(0),
69 if (allocated==new_size)
71 if (!canShrink && (new_size < allocated))
76 data = allocator.allocate(new_size);
80 s32 end = used < new_size ? used : new_size;
82 for (
s32 i=0; i<end; ++i)
85 allocator.construct(&data[i], old_data[i]);
89 for (
u32 j=0; j<used; ++j)
90 allocator.destruct(&old_data[j]);
95 allocator.deallocate(old_data);
105 strategy = newStrategy;
139 if (used + 1 > allocated)
151 newAlloc = used + 1 + (allocated < 500 ?
152 (allocated < 5 ? 5 : used) : used >> 2);
163 for (
u32 i=used; i>index; --i)
166 allocator.destruct(&data[i]);
167 allocator.construct(&data[i], data[i-1]);
171 allocator.destruct(&data[index]);
172 allocator.construct(&data[index], e);
180 allocator.construct(&data[used], data[used-1]);
183 for (
u32 i=used-1; i>index; --i)
188 data[index] = element;
193 allocator.construct(&data[index], element);
205 if (free_when_destroyed)
207 for (
u32 i=0; i<used; ++i)
208 allocator.destruct(&data[i]);
210 allocator.deallocate(data);
234 is_sorted = _is_sorted;
235 free_when_destroyed=_free_when_destroyed;
249 free_when_destroyed = f;
259 if (allocated < usedNow)
271 strategy = other.strategy;
277 if (other.allocated == 0)
280 data = allocator.allocate(other.allocated);
283 free_when_destroyed =
true;
284 is_sorted = other.is_sorted;
285 allocated = other.allocated;
287 for (
u32 i=0; i<other.used; ++i)
288 allocator.construct(&data[i], other.data[i]);
297 if (used != other.used)
300 for (
u32 i=0; i<other.used; ++i)
301 if (data[i] != other[i])
310 return !(*
this==other);
396 if (!is_sorted && used>1)
448 if (element < data[m])
453 }
while((element < data[m] || data[m] < element) && left<=right);
460 if (!(element < data[m]) && !(data[m] < element))
486 while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
491 while ( last < (
s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )
508 for (
u32 i=0; i<used; ++i)
509 if (element == data[i])
524 for (
s32 i=used-1; i>=0; --i)
525 if (data[i] == element)
540 for (
u32 i=index+1; i<used; ++i)
542 allocator.destruct(&data[i-1]);
543 allocator.construct(&data[i-1], data[i]);
546 allocator.destruct(&data[used-1]);
559 if (index>=used || count<1)
561 if (index+count>used)
565 for (i=index; i<index+count; ++i)
566 allocator.destruct(&data[i]);
568 for (i=index+count; i<used; ++i)
570 if (i-count >= index+count)
571 allocator.destruct(&data[i-count]);
573 allocator.construct(&data[i-count], data[i]);
576 allocator.destruct(&data[i]);
586 is_sorted = _is_sorted;
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;
618 bool free_when_destroyed:1;
void set_used(u32 usedNow)
Sets the size of the array and allocates new elements if necessary.
T & operator[](u32 index)
Direct access operator.
void reallocate(u32 new_size, bool canShrink=true)
Reallocates the array, make it bigger or smaller.
s32 binary_search(const T &element) const
Performs a binary search for an element if possible, returns -1 if not found.
array()
Default constructor for empty array.
bool operator==(const array< T, TAlloc > &other) const
Equality operator.
const T * const_pointer() const
Gets a const pointer to the array.
void sort()
Sorts the array using heapsort.
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.
Everything in the Irrlicht Engine can be found in this namespace.
u32 allocated_size() const
Get amount of memory allocated.
T & getLast()
Gets last element.
void setAllocStrategy(eAllocStrategy newStrategy=ALLOC_STRATEGY_DOUBLE)
set a new allocation strategy
s32 binary_search(const T &element, s32 left, s32 right) const
Performs a binary search for an element, returns -1 if not found.
const array< T, TAlloc > & operator=(const array< T, TAlloc > &other)
Assignment operator.
void push_back(const T &element)
Adds an element at back of array.
bool empty() const
Check if array is empty.
eAllocStrategy
defines an allocation strategy
void set_sorted(bool _is_sorted)
Sets if the array is sorted.
s32 linear_reverse_search(const T &element) const
Finds an element in linear time, which is very slow.
s32 binary_search_multi(const T &element, s32 &last)
signed int s32
32 bit signed variable.
void erase(u32 index, s32 count)
Erases some elements from the array.
bool operator!=(const array< T, TAlloc > &other) const
Inequality operator.
unsigned int u32
32 bit unsigned variable.
s32 binary_search(const T &element)
Performs a binary search for an element, returns -1 if not found.
void heapsort(T *array_, s32 size)
Sorts an array with size 'size' using heapsort.
u32 size() const
Get number of occupied elements of the array.
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
void swap(array< T, TAlloc > &other)
Swap the content of this array container with the content of another array.
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
void erase(u32 index)
Erases an element from the array.
void insert(const T &element, u32 index=0)
Insert item into array at specified position.
s32 linear_search(const T &element) const
Finds an element in linear time, which is very slow.
Self reallocating template array (like stl vector) with additional features.
void clear()
Clears the array and deletes all allocated memory.
array(u32 start_count)
Constructs an array and allocates an initial chunk of memory.
void push_front(const T &element)
Adds an element at the front of the array.
array(const array< T, TAlloc > &other)
Copy constructor.
const T & getLast() const
Gets last element.
T * pointer()
Gets a pointer to the array.
void set_free_when_destroyed(bool f)
Sets if the array should delete the memory it uses upon destruction.