A port of the irrlicht XML parser library.
Diff: irrArray.h
- Revision:
- 0:41a49a73580c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/irrArray.h Wed Nov 17 20:19:41 2010 +0000 @@ -0,0 +1,443 @@ +// 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), used(0), allocated(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), used(0), allocated(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