Loading...
Searching...
No Matches
irrArray.h
Go to the documentation of this file.
// Copyright (C) 2002-2012 Nikolaus Gebhardt
// This file is part of the "Irrlicht Engine" and the "irrXML" project.
// For conditions of distribution and use, see copyright notice in irrlicht.h and irrXML.h
#ifndef __IRR_ARRAY_H_INCLUDED__
#define __IRR_ARRAY_H_INCLUDED__
#include "irrTypes.h"
#include "heapsort.h"
#include "irrAllocator.h"
#include "irrMath.h"
namespace irr
{
namespace core
{
template <class T, typename TAlloc = irrAllocator<T> >
class array
{
public:
array()
: data(0), allocated(0), used(0),
strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
{
}
array(u32 start_count)
: data(0), allocated(0), used(0),
strategy(ALLOC_STRATEGY_DOUBLE), free_when_destroyed(true), is_sorted(true)
{
reallocate(start_count);
}
array(const array<T, TAlloc>& other) : data(0)
{
*this = other;
}
~array()
{
clear();
}
void reallocate(u32 new_size, bool canShrink=true)
{
if (allocated==new_size)
return;
if (!canShrink && (new_size < allocated))
return;
T* old_data = data;
data = allocator.allocate(new_size); //new T[new_size];
allocated = new_size;
// copy old data
s32 end = used < new_size ? used : new_size;
for (s32 i=0; i<end; ++i)
{
// data[i] = old_data[i];
allocator.construct(&data[i], old_data[i]);
}
// destruct old data
for (u32 j=0; j<used; ++j)
allocator.destruct(&old_data[j]);
if (allocated < used)
used = allocated;
allocator.deallocate(old_data); //delete [] old_data;
}
void setAllocStrategy ( eAllocStrategy newStrategy = ALLOC_STRATEGY_DOUBLE )
{
strategy = newStrategy;
}
void push_back(const T& element)
{
insert(element, used);
}
void push_front(const T& element)
{
insert(element);
}
void insert(const T& element, u32 index=0)
{
_IRR_DEBUG_BREAK_IF(index>used) // access violation
if (used + 1 > allocated)
{
// this doesn't work if the element is in the same
// array. So we'll copy the element first to be sure
// we'll get no data corruption
const T e(element);
// increase data block
u32 newAlloc;
switch ( strategy )
{
case ALLOC_STRATEGY_DOUBLE:
newAlloc = used + 1 + (allocated < 500 ?
(allocated < 5 ? 5 : used) : used >> 2);
break;
default:
case ALLOC_STRATEGY_SAFE:
newAlloc = used + 1;
break;
}
reallocate( newAlloc);
// move array content and construct new element
// first move end one up
for (u32 i=used; i>index; --i)
{
if (i<used)
allocator.destruct(&data[i]);
allocator.construct(&data[i], data[i-1]); // data[i] = data[i-1];
}
// then add new element
if (used > index)
allocator.destruct(&data[index]);
allocator.construct(&data[index], e); // data[index] = e;
}
else
{
// element inserted not at end
if ( used > index )
{
// create one new element at the end
allocator.construct(&data[used], data[used-1]);
// move the rest of the array content
for (u32 i=used-1; i>index; --i)
{
data[i] = data[i-1];
}
// insert the new element
data[index] = element;
}
else
{
// insert the new element to the end
allocator.construct(&data[index], element);
}
}
// set to false as we don't know if we have the comparison operators
is_sorted = false;
++used;
}
void clear()
{
if (free_when_destroyed)
{
for (u32 i=0; i<used; ++i)
allocator.destruct(&data[i]);
allocator.deallocate(data); // delete [] data;
}
data = 0;
used = 0;
allocated = 0;
is_sorted = true;
}
void set_pointer(T* newPointer, u32 size, bool _is_sorted=false, bool _free_when_destroyed=true)
{
clear();
data = newPointer;
allocated = size;
used = size;
is_sorted = _is_sorted;
free_when_destroyed=_free_when_destroyed;
}
void set_free_when_destroyed(bool f)
{
free_when_destroyed = f;
}
void set_used(u32 usedNow)
{
if (allocated < usedNow)
reallocate(usedNow);
used = usedNow;
}
const array<T, TAlloc>& operator=(const array<T, TAlloc>& other)
{
if (this == &other)
return *this;
strategy = other.strategy;
if (data)
clear();
//if (allocated < other.allocated)
if (other.allocated == 0)
data = 0;
else
data = allocator.allocate(other.allocated); // new T[other.allocated];
used = other.used;
free_when_destroyed = true;
is_sorted = other.is_sorted;
allocated = other.allocated;
for (u32 i=0; i<other.used; ++i)
allocator.construct(&data[i], other.data[i]); // data[i] = other.data[i];
return *this;
}
bool operator == (const array<T, TAlloc>& other) const
{
if (used != other.used)
return false;
for (u32 i=0; i<other.used; ++i)
if (data[i] != other[i])
return false;
return true;
}
bool operator != (const array<T, TAlloc>& other) const
{
return !(*this==other);
}
T& operator [](u32 index)
{
_IRR_DEBUG_BREAK_IF(index>=used) // access violation
return data[index];
}
const T& operator [](u32 index) const
{
_IRR_DEBUG_BREAK_IF(index>=used) // access violation
return data[index];
}
T& getLast()
{
_IRR_DEBUG_BREAK_IF(!used) // access violation
return data[used-1];
}
const T& getLast() const
{
_IRR_DEBUG_BREAK_IF(!used) // access violation
return data[used-1];
}
T* pointer()
{
return data;
}
const T* const_pointer() const
{
return data;
}
u32 size() const
{
return used;
}
u32 allocated_size() const
{
return allocated;
}
bool empty() const
{
return used == 0;
}
void sort()
{
if (!is_sorted && used>1)
heapsort(data, used);
is_sorted = true;
}
s32 binary_search(const T& element)
{
sort();
return binary_search(element, 0, used-1);
}
s32 binary_search(const T& element) const
{
if (is_sorted)
return binary_search(element, 0, used-1);
else
return linear_search(element);
}
s32 binary_search(const T& element, s32 left, s32 right) const
{
if (!used)
return -1;
s32 m;
do
{
m = (left+right)>>1;
if (element < data[m])
right = m - 1;
else
left = m + 1;
} while((element < data[m] || data[m] < element) && left<=right);
// this last line equals to:
// " while((element != array[m]) && left<=right);"
// but we only want to use the '<' operator.
// the same in next line, it is "(element == array[m])"
if (!(element < data[m]) && !(data[m] < element))
return m;
return -1;
}
s32 binary_search_multi(const T& element, s32 &last)
{
sort();
s32 index = binary_search(element, 0, used-1);
if ( index < 0 )
return index;
// The search can be somewhere in the middle of the set
// look linear previous and past the index
last = index;
while ( index > 0 && !(element < data[index - 1]) && !(data[index - 1] < element) )
{
index -= 1;
}
// look linear up
while ( last < (s32) used - 1 && !(element < data[last + 1]) && !(data[last + 1] < element) )
{
last += 1;
}
return index;
}
s32 linear_search(const T& element) const
{
for (u32 i=0; i<used; ++i)
if (element == data[i])
return (s32)i;
return -1;
}
s32 linear_reverse_search(const T& element) const
{
for (s32 i=used-1; i>=0; --i)
if (data[i] == element)
return i;
return -1;
}
void erase(u32 index)
{
_IRR_DEBUG_BREAK_IF(index>=used) // access violation
for (u32 i=index+1; i<used; ++i)
{
allocator.destruct(&data[i-1]);
allocator.construct(&data[i-1], data[i]); // data[i-1] = data[i];
}
allocator.destruct(&data[used-1]);
--used;
}
void erase(u32 index, s32 count)
{
if (index>=used || count<1)
return;
if (index+count>used)
count = used-index;
u32 i;
for (i=index; i<index+count; ++i)
allocator.destruct(&data[i]);
for (i=index+count; i<used; ++i)
{
if (i-count >= index+count) // not already destructed before loop
allocator.destruct(&data[i-count]);
allocator.construct(&data[i-count], data[i]); // data[i-count] = data[i];
if (i >= used-count) // those which are not overwritten
allocator.destruct(&data[i]);
}
used-= count;
}
void set_sorted(bool _is_sorted)
{
is_sorted = _is_sorted;
}
void swap(array<T, TAlloc>& other)
{
core::swap(data, other.data);
core::swap(allocated, other.allocated);
core::swap(used, other.used);
core::swap(allocator, other.allocator); // memory is still released by the same allocator used for allocation
eAllocStrategy helper_strategy(strategy); // can't use core::swap with bitfields
strategy = other.strategy;
other.strategy = helper_strategy;
bool helper_free_when_destroyed(free_when_destroyed);
free_when_destroyed = other.free_when_destroyed;
other.free_when_destroyed = helper_free_when_destroyed;
bool helper_is_sorted(is_sorted);
is_sorted = other.is_sorted;
other.is_sorted = helper_is_sorted;
}
private:
T* data;
u32 allocated;
u32 used;
TAlloc allocator;
eAllocStrategy strategy:4;
bool free_when_destroyed:1;
bool is_sorted:1;
};
} // end namespace core
} // end namespace irr
#endif
irr::core::array::operator=
const array< T, TAlloc > & operator=(const array< T, TAlloc > &other)
Assignment operator.
Definition irrArray.h:267
irr::core::array::allocated_size
u32 allocated_size() const
Get amount of memory allocated.
Definition irrArray.h:377
irr::core::array::clear
void clear()
Clears the array and deletes all allocated memory.
Definition irrArray.h:203
irr::core::array::push_front
void push_front(const T &element)
Adds an element at the front of the array.
Definition irrArray.h:123
irr::core::array::binary_search
s32 binary_search(const T &element)
Performs a binary search for an element, returns -1 if not found.
Definition irrArray.h:409
irr::core::array::insert
void insert(const T &element, u32 index=0)
Insert item into array at specified position.
Definition irrArray.h:135
irr::core::array::linear_search
s32 linear_search(const T &element) const
Finds an element in linear time, which is very slow.
Definition irrArray.h:506
irr::core::array::array
array(const array< T, TAlloc > &other)
Copy constructor.
Definition irrArray.h:46
irr::core::array::erase
void erase(u32 index)
Erases an element from the array.
Definition irrArray.h:536
irr::core::array::array
array()
Default constructor for empty array.
Definition irrArray.h:28
irr::core::array::binary_search_multi
s32 binary_search_multi(const T &element, s32 &last)
Definition irrArray.h:475
irr::core::array::set_used
void set_used(u32 usedNow)
Sets the size of the array and allocates new elements if necessary.
Definition irrArray.h:257
irr::core::array::getLast
T & getLast()
Gets last element.
Definition irrArray.h:333
irr::core::array::operator!=
bool operator!=(const array< T, TAlloc > &other) const
Inequality operator.
Definition irrArray.h:308
irr::core::array::set_pointer
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
irr::core::array::operator==
bool operator==(const array< T, TAlloc > &other) const
Equality operator.
Definition irrArray.h:295
irr::core::array::setAllocStrategy
void setAllocStrategy(eAllocStrategy newStrategy=ALLOC_STRATEGY_DOUBLE)
set a new allocation strategy
Definition irrArray.h:103
irr::core::array::sort
void sort()
Sorts the array using heapsort.
Definition irrArray.h:394
irr::core::array::swap
void swap(array< T, TAlloc > &other)
Swap the content of this array container with the content of another array.
Definition irrArray.h:594
irr::core::array::operator[]
T & operator[](u32 index)
Direct access operator.
Definition irrArray.h:315
irr::core::array::empty
bool empty() const
Check if array is empty.
Definition irrArray.h:385
irr::core::array::pointer
T * pointer()
Gets a pointer to the array.
Definition irrArray.h:352
irr::core::array::binary_search
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
irr::core::array::getLast
const T & getLast() const
Gets last element.
Definition irrArray.h:342
irr::core::array::~array
~array()
Destructor.
Definition irrArray.h:55
irr::core::array< core::stringc >::size
u32 size() const
Definition irrArray.h:368
irr::core::array::array
array(u32 start_count)
Constructs an array and allocates an initial chunk of memory.
Definition irrArray.h:37
irr::core::array::set_sorted
void set_sorted(bool _is_sorted)
Sets if the array is sorted.
Definition irrArray.h:584
irr::core::array::erase
void erase(u32 index, s32 count)
Erases some elements from the array.
Definition irrArray.h:557
irr::core::array::const_pointer
const T * const_pointer() const
Gets a const pointer to the array.
Definition irrArray.h:360
irr::core::array::push_back
void push_back(const T &element)
Adds an element at back of array.
Definition irrArray.h:112
irr::core::array::reallocate
void reallocate(u32 new_size, bool canShrink=true)
Reallocates the array, make it bigger or smaller.
Definition irrArray.h:67
irr::core::array::binary_search
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
irr::core::array::linear_reverse_search
s32 linear_reverse_search(const T &element) const
Finds an element in linear time, which is very slow.
Definition irrArray.h:522
irr::core::array::set_free_when_destroyed
void set_free_when_destroyed(bool f)
Sets if the array should delete the memory it uses upon destruction.
Definition irrArray.h:247
heapsort.h
irrAllocator.h
irrMath.h
irrTypes.h
_IRR_DEBUG_BREAK_IF
#define _IRR_DEBUG_BREAK_IF(_CONDITION_)
define a break macro for debugging.
Definition irrTypes.h:178
irr::core
Basic classes such as vectors, planes, arrays, lists, and so on can be found in this namespace.
Definition aabbox3d.h:15
irr::core::eAllocStrategy
eAllocStrategy
defines an allocation strategy
Definition irrAllocator.h:113
irr::core::ALLOC_STRATEGY_DOUBLE
@ ALLOC_STRATEGY_DOUBLE
Definition irrAllocator.h:115
irr::core::ALLOC_STRATEGY_SAFE
@ ALLOC_STRATEGY_SAFE
Definition irrAllocator.h:114
irr::core::swap
void swap(T1 &a, T2 &b)
swaps the content of the passed parameters
Definition irrMath.h:177
irr::core::heapsort
void heapsort(T *array_, s32 size)
Sorts an array with size 'size' using heapsort.
Definition heapsort.h:41
irr
Everything in the Irrlicht Engine can be found in this namespace.
Definition aabbox3d.h:13
irr::u32
unsigned int u32
32 bit unsigned variable.
Definition irrTypes.h:58
irr::s32
signed int s32
32 bit signed variable.
Definition irrTypes.h:66
- Irrlicht Engine Documentation © 2003-2012 by Nikolaus Gebhardt. Generated on for Irrlicht 3D Engine by Doxygen 1.15.0