| // Copyright (C) 2002-2005 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" |
| |
| namespace irr |
| { |
| namespace core |
| { |
| |
| //! Self reallocating template array (like stl vector) with additional features. |
| /** Some features are: Heap sorting, binary search methods, easier debugging. |
| */ |
| template <class T> |
| class array |
| { |
| |
| public: |
| |
| array() |
| : data(0), allocated(0), used(0), |
| free_when_destroyed(true), is_sorted(true) |
| { |
| } |
| |
| //! Constructs a array and allocates an initial chunk of memory. |
| //! \param start_count: Amount of elements to allocate. |
| array(u32 start_count) |
| : data(0), allocated(0), used(0), |
| free_when_destroyed(true), is_sorted(true) |
| { |
| reallocate(start_count); |
| } |
| |
| |
| //! Copy constructor |
| array(const array<T>& other) |
| : data(0) |
| { |
| *this = other; |
| } |
| |
| |
| |
| //! Destructor. Frees allocated memory, if set_free_when_destroyed |
| //! was not set to false by the user before. |
| ~array() |
| { |
| if (free_when_destroyed) |
| delete [] data; |
| } |
| |
| |
| |
| //! Reallocates the array, make it bigger or smaller. |
| //! \param new_size: New size of array. |
| void reallocate(u32 new_size) |
| { |
| T* old_data = data; |
| |
| data = new T[new_size]; |
| allocated = new_size; |
| |
| s32 end = used < new_size ? used : new_size; |
| for (s32 i=0; i<end; ++i) |
| data[i] = old_data[i]; |
| |
| if (allocated < used) |
| used = allocated; |
| |
| delete [] old_data; |
| } |
| |
| //! Adds an element at back of array. If the array is to small to |
| //! add this new element, the array is made bigger. |
| //! \param element: Element to add at the back of the array. |
| void push_back(const T& element) |
| { |
| if (used + 1 > allocated) |
| { |
| // reallocate(used * 2 +1); |
| // 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 |
| |
| T e; |
| e = element; // copy element |
| reallocate(used * 2 +1); // increase data block |
| data[used++] = e; // push_back |
| is_sorted = false; |
| return; |
| } |
| |
| data[used++] = element; |
| is_sorted = false; |
| } |
| |
| |
| //! Adds an element at the front of the array. If the array is to small to |
| //! add this new element, the array is made bigger. Please note that this |
| //! is slow, because the whole array needs to be copied for this. |
| //! \param element: Element to add at the back of the array. |
| void push_front(const T& element) |
| { |
| if (used + 1 > allocated) |
| reallocate(used * 2 +1); |
| |
| for (int i=(int)used; i>0; --i) |
| data[i] = data[i-1]; |
| |
| data[0] = element; |
| is_sorted = false; |
| ++used; |
| } |
| |
| |
| //! Insert item into array at specified position. Please use this |
| //! only if you know what you are doing (possible performance loss). |
| //! The preferred method of adding elements should be push_back(). |
| //! \param element: Element to be inserted |
| //! \param index: Where position to insert the new element. |
| void insert(const T& element, u32 index=0) |
| { |
| _IRR_DEBUG_BREAK_IF(index>used) // access violation |
| |
| if (used + 1 > allocated) |
| reallocate(used * 2 +1); |
| |
| for (u32 i=used++; i>index; i--) |
| data[i] = data[i-1]; |
| |
| data[index] = element; |
| is_sorted = false; |
| } |
| |
| |
| |
| |
| //! Clears the array and deletes all allocated memory. |
| void clear() |
| { |
| delete [] data; |
| data = 0; |
| used = 0; |
| allocated = 0; |
| is_sorted = true; |
| } |
| |
| |
| |
| //! Sets pointer to new array, using this as new workspace. |
| //! \param newPointer: Pointer to new array of elements. |
| //! \param size: Size of the new array. |
| void set_pointer(T* newPointer, u32 size) |
| { |
| delete [] data; |
| data = newPointer; |
| allocated = size; |
| used = size; |
| is_sorted = false; |
| } |
| |
| |
| |
| //! Sets if the array should delete the memory it used. |
| //! \param f: If true, the array frees the allocated memory in its |
| //! destructor, otherwise not. The default is true. |
| void set_free_when_destroyed(bool f) |
| { |
| free_when_destroyed = f; |
| } |
| |
| |
| |
| //! Sets the size of the array. |
| //! \param usedNow: Amount of elements now used. |
| void set_used(u32 usedNow) |
| { |
| if (allocated < usedNow) |
| reallocate(usedNow); |
| |
| used = usedNow; |
| } |
| |
| |
| |
| //! Assignement operator |
| void operator=(const array<T>& other) |
| { |
| if (data) |
| delete [] data; |
| |
| //if (allocated < other.allocated) |
| if (other.allocated == 0) |
| data = 0; |
| else |
| data = new T[other.allocated]; |
| |
| used = other.used; |
| free_when_destroyed = other.free_when_destroyed; |
| is_sorted = other.is_sorted; |
| allocated = other.allocated; |
| |
| for (u32 i=0; i<other.used; ++i) |
| data[i] = other.data[i]; |
| } |
| |
| |
| //! Direct access operator |
| T& operator [](u32 index) |
| { |
| _IRR_DEBUG_BREAK_IF(index>=used) // access violation |
| |
| return data[index]; |
| } |
| |
| |
| |
| //! Direct access operator |
| const T& operator [](u32 index) const |
| { |
| _IRR_DEBUG_BREAK_IF(index>=used) // access violation |
| |
| return data[index]; |
| } |
| |
| //! Gets last frame |
| const T& getLast() const |
| { |
| _IRR_DEBUG_BREAK_IF(!used) // access violation |
| |
| return data[used-1]; |
| } |
| |
| //! Gets last frame |
| T& getLast() |
| { |
| _IRR_DEBUG_BREAK_IF(!used) // access violation |
| |
| return data[used-1]; |
| } |
| |
| |
| //! Returns a pointer to the array. |
| //! \return Pointer to the array. |
| T* pointer() |
| { |
| return data; |
| } |
| |
| |
| |
| //! Returns a const pointer to the array. |
| //! \return Pointer to the array. |
| const T* const_pointer() const |
| { |
| return data; |
| } |
| |
| |
| |
| //! Returns size of used array. |
| //! \return Size of elements in the array. |
| u32 size() const |
| { |
| return used; |
| } |
| |
| |
| |
| //! Returns amount memory allocated. |
| //! \return Returns amount of memory allocated. The amount of bytes |
| //! allocated would be allocated_size() * sizeof(ElementsUsed); |
| u32 allocated_size() const |
| { |
| return allocated; |
| } |
| |
| |
| |
| //! Returns true if array is empty |
| //! \return True if the array is empty, false if not. |
| bool empty() const |
| { |
| return used == 0; |
| } |
| |
| |
| |
| //! Sorts the array using heapsort. There is no additional memory waste and |
| //! the algorithm performs (O) n log n in worst case. |
| void sort() |
| { |
| if (is_sorted || used<2) |
| return; |
| |
| heapsort(data, used); |
| is_sorted = true; |
| } |
| |
| |
| |
| //! Performs a binary search for an element, returns -1 if not found. |
| //! The array will be sorted before the binary search if it is not |
| //! already sorted. |
| //! \param element: Element to search for. |
| //! \return Returns position of the searched element if it was found, |
| //! otherwise -1 is returned. |
| s32 binary_search(const T& element) |
| { |
| return binary_search(element, 0, used-1); |
| } |
| |
| |
| |
| //! Performs a binary search for an element, returns -1 if not found. |
| //! The array will be sorted before the binary search if it is not |
| //! already sorted. |
| //! \param element: Element to search for. |
| //! \param left: First left index |
| //! \param right: Last right index. |
| //! \return Returns position of the searched element if it was found, |
| //! otherwise -1 is returned. |
| s32 binary_search(const T& element, s32 left, s32 right) |
| { |
| if (!used) |
| return -1; |
| |
| sort(); |
| |
| 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; |
| } |
| |
| |
| //! Finds an element in linear time, which is very slow. Use |
| //! binary_search for faster finding. Only works if =operator is implemented. |
| //! \param element: Element to search for. |
| //! \return Returns position of the searched element if it was found, |
| //! otherwise -1 is returned. |
| s32 linear_search(T& element) |
| { |
| for (u32 i=0; i<used; ++i) |
| if (!(element < data[i]) && !(data[i] < element)) |
| return (s32)i; |
| |
| return -1; |
| } |
| |
| |
| //! Finds an element in linear time, which is very slow. Use |
| //! binary_search for faster finding. Only works if =operator is implemented. |
| //! \param element: Element to search for. |
| //! \return Returns position of the searched element if it was found, |
| //! otherwise -1 is returned. |
| s32 linear_reverse_search(T& element) |
| { |
| for (s32 i=used-1; i>=0; --i) |
| if (data[i] == element) |
| return (s32)i; |
| |
| return -1; |
| } |
| |
| |
| |
| //! Erases an element from the array. May be slow, because all elements |
| //! following after the erased element have to be copied. |
| //! \param index: Index of element to be erased. |
| void erase(u32 index) |
| { |
| _IRR_DEBUG_BREAK_IF(index>=used || index<0) // access violation |
| |
| for (u32 i=index+1; i<used; ++i) |
| data[i-1] = data[i]; |
| |
| --used; |
| } |
| |
| |
| //! Erases some elements from the array. may be slow, because all elements |
| //! following after the erased element have to be copied. |
| //! \param index: Index of the first element to be erased. |
| //! \param count: Amount of elements to be erased. |
| void erase(u32 index, s32 count) |
| { |
| _IRR_DEBUG_BREAK_IF(index>=used || index<0 || count<1 || index+count>used) // access violation |
| |
| for (u32 i=index+count; i<used; ++i) |
| data[i-count] = data[i]; |
| |
| used-= count; |
| } |
| |
| |
| //! Sets if the array is sorted |
| void set_sorted(bool _is_sorted) |
| { |
| is_sorted = _is_sorted; |
| } |
| |
| |
| private: |
| |
| T* data; |
| u32 allocated; |
| u32 used; |
| bool free_when_destroyed; |
| bool is_sorted; |
| }; |
| |
| |
| } // end namespace core |
| } // end namespace irr |
| |
| |
| |
| #endif |
| |