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