libsst/Include/ZUtil/ZReferenceBuffer.hpp

/*
	ZReferenceBuffer.hpp
	Author: James Russell

	Purpose :	Acts as a means of storing arbitrary types of values in an array which gives back index-based references to
				pointers of those types of values.  Handles, internally, the Buffer overflowing and looping back around 
				the end of the storage array.

	Changelog :
	2/11/10 - Creation (jcr2)
	2/13/10 - Should be working as advertised (jcr)
	3/04/10 - NOW working as advertised (jcr)

*/

#ifndef _ZREFERENCEBUFFER_H
#define _ZREFERENCEBUFFER_H

#include <ZUtil/ZAlloc.hpp>
#include <ZUtil/ZAssert.hpp>
#include <ZSTL/ZArray.hpp>
#include <ZSTL/ZList.hpp>

#define ZRB_DEFAULT_BUFFER_SIZE (10)
#define ZRB_INVALID_HANDLE (-1)

typedef int ZReferenceBufferHandle;

template <typename T>
class ZReferenceBuffer
{
protected:
	//The Current Index Value (next value to be assigned)
	int CurrentIndex;

	//The Current Size of the Buffer (Storage Capacity)
	int BufferSize;

	//The Current Number of Items contained in the Buffer
	int ItemCount;

	//Indicator array used to indicate which indices of the Buffer are valid
	ZArray<int> Indicator;

	//Buffer of T* Values
	ZArray<T*> Buffer;

	//Checks if a given reference is valid
	inline bool IsValid(int index);

	//Checks if a given reference is invalid
	inline bool IsInvalid(int index);

	//Sets the Indicator of an index to valid
	inline void SetValid(int index);

	//Sets the Indicator of an index to invalid
	inline void SetInvalid(int index);

public:

	/*
	Default constructor.
	*/
	ZReferenceBuffer();

	/*
	Constructor.

	@param _size - The starting size of the reference buffer.
	*/
	ZReferenceBuffer(int _size);

	/*
	Constructor.

	@param _allocator - the allocator to use for allocations / deallocations in the reference buffer
	*/
	ZReferenceBuffer(ZArrayAllocator<T> *_allocator);

	/*
	Constructor.

	@param _size - The starting size of the reference buffer.
	@param _allocator - the allocator to use for allocations / deallocations in the reference buffer
	*/
	ZReferenceBuffer( int _size, ZArrayAllocator<T> *_allocator);

	/*
	Destructor.
	*/
	~ZReferenceBuffer();

	/*
	public ZReferenceBuffer::AddItem

	Adds the item to the reference Buffer, returning a handle.  Resizes the Buffer automatically to 
	increase the size of the buffer if full. 
	
	@param _item - the item to add to the buffer
	
	@return (ZReferenceBufferHandle) - a ZReferenceBufferHandle which can be used to reference item, Will never return NULL.
	*/
	ZReferenceBufferHandle AddItem(T _item);

	/*
	public ZReferenceBuffer::GetItem

	Gets an item in the Buffer given a reference handle.

	@param _ref - the reference handle to the item you wish to get
	
	@return (T&) - the item the handle refers to
	*/
	T& GetItem(ZReferenceBufferHandle _ref);

	/*
	public ZReferenceBuffer::SetItem

	Attempts to set the reference to map to the provided item.  Used for updating references.

	@param _ref - a valid reference handle to update.  If NULL, will set the null handle, allowing a NULL reference to be valid.
	@param _item - the item to update the reference to
	
	@return (T) - the overwritten value that ref pointed to
	*/
	T SetItem(ZReferenceBufferHandle _ref, T _item);

	/* 
	public ZReferenceBuffer::RemoveItem

	Removes an item from the Buffer given a reference handle and invalidates the handle (until reassigned). 
	
	@param _ref - the reference handle to the item you wish to remove
	
	@return (T) - the item removed
	*/
	T RemoveItem(ZReferenceBufferHandle _ref);

	/* 
	public ZReferenceBuffer::Remove

	Removes all occurrences of an item from the Buffer given a pointer to the item.
	
	@param _item - the item you wish to remove

	@return (void)
	*/
	void Remove(T _item);

	/* 
	public ZReferenceBuffer::Size

	Gets the current size of the buffer.
	
	@return (int) - the size (capacity) of the buffer
	*/
	int Size();

	/* 
	public ZReferenceBuffer::Count

	Returns the number of elements currently stored in the Buffer 
	
	@return (int) - the count (number of items) in the buffer
	*/
	int Count();

	/* 
	public ZReferenceBuffer::Items

	Returns a ZList containing the elements of the reference Buffer. 
	
	@return (ZList<T>) - a list containing all the values currently in the buffer
	*/
	ZList<T> Items();

	/*
	inline public ZReferenceBuffer::IsFull

	Returns true if the Buffer is full, false otherwise. 
	
	@return (bool) - boolean indicating the buffer is full
	*/
	inline bool IsFull();

	/*
	public ZReferenceBuffer::Resize

	Resizes the Buffer to store _newSize number of elements.  Already existing references remain valid.  Returns true
	on success, false otherwise.  Newsize must be greater than the current size of the reference Buffer.
	
	@param _newSize - the ZNew capacity of the buffer
	
	@return (bool) - boolean indicating success or failure
	*/
	bool Resize( int _newSize);
};

template <typename T>
ZReferenceBuffer<T>::ZReferenceBuffer( int _size, ZArrayAllocator<T>* _allocator)
: CurrentIndex(1), BufferSize(_size+1), ItemCount(0), Allocator(_allocator)
{
	this->Buffer.Resize(BufferSize);
	this->Indicator.Resize(this->BufferSize, false);
}

template <typename T>
ZReferenceBuffer<T>::ZReferenceBuffer( int _size)
: CurrentIndex(1), BufferSize(_size+1), ItemCount(0)
{
	this->Buffer.Resize(BufferSize);
	this->Indicator.Resize(this->BufferSize, false);
}

template <typename T>
ZReferenceBuffer<T>::ZReferenceBuffer(ZArrayAllocator<T>* _allocator)
: CurrentIndex(1), BufferSize(ZRB_DEFAULT_BUFFER_SIZE+1), ItemCount(0), Allocator(_allocator)
{
	this->Buffer.Resize(BufferSize);
	this->Indicator.Resize(this->BufferSize, false);
}

template <typename T>
ZReferenceBuffer<T>::ZReferenceBuffer()
: CurrentIndex(1), BufferSize(ZRB_DEFAULT_BUFFER_SIZE+1), ItemCount(0)
{
	this->Buffer.Resize(BufferSize);
	this->Indicator.Resize(this->BufferSize, false);
}

template <typename T>
ZReferenceBuffer<T>::~ZReferenceBuffer()
{
}

template <typename T>
bool ZReferenceBuffer<T>::IsValid(int _index)
{
	if (_index >= 0)
		return this->Indicator[_index] != 0;

	return false;
}

template <typename T>
bool ZReferenceBuffer<T>::IsInvalid(int _index)
{
	return !IsValid(_index);
}

template <typename T>
void ZReferenceBuffer<T>::SetValid( int _index)
{
	this->Indicator[_index] = 1;
}

template <typename T>
void ZReferenceBuffer<T>::SetInvalid( int _index)
{
	this->Indicator[_index] = 0;
}

template <typename T>
ZReferenceBufferHandle ZReferenceBuffer<T>::AddItem(T _item)
{
	 int startIndex;
	int ref;

	//CurrentIndex should only be zero if Buffer is full
	if (this->CurrentIndex == 0)
		return this->CurrentIndex;

	ref = startIndex = this->CurrentIndex;

	while (this->IsValid(this->CurrentIndex))
	{
		this->CurrentIndex++;
		ref = this->CurrentIndex;

		if (this->CurrentIndex == startIndex)
			this->Resize(this->BufferSize * 2);

		if (this->CurrentIndex >= this->BufferSize)
			ref = this->CurrentIndex = 1;
	}

	if (ref != -1)
	{
		this->Buffer[ref] = _item;
		this->SetValid(ref);

		this->ItemCount++;
	}

	return ref;
}

template <typename T>
T& ZReferenceBuffer<T>::GetItem(ZReferenceBufferHandle _ref)
{
	ZASSERT(this->IsValid(_ref), "ERROR: ZReferenceBuffer::GetItemRef passed invalid reference!");

	return this->Buffer[_ref];
}

template <typename T>
T ZReferenceBuffer<T>::RemoveItem(ZReferenceBufferHandle _ref)
{
	T item;

	ZASSERT( this->IsValid(_ref) , "ERROR: ZReferenceBuffer::RemoveItem passed invalid reference!" );

	this->ItemCount--;
	this->SetInvalid(_ref);
	item = this->Buffer[_ref];

	return item;
}

template <typename T>
void ZReferenceBuffer<T>::Remove(T _item)
{
	for ( int i = 0; i < this->BufferSize; i++)
		if (this->Buffer[i] == _item)
			this->RemoveItem(i);
}

template <typename T>
T ZReferenceBuffer<T>::SetItem(int _ref, T _item)
{	
	T ret;

	ret = this->Buffer[_ref];
	this->Buffer[_ref] = _item;

	this->SetValid(_ref);

	this->ItemCount++;

	return ret;
}

template <typename T>
 int ZReferenceBuffer<T>::Size()
{
	return this->BufferSize;
}

template <typename T>
 int ZReferenceBuffer<T>::Count()
{
	return this->ItemCount;
}

template <typename T>
bool ZReferenceBuffer<T>::IsFull()
{
	return (!this->CurrentIndex);
}

template <typename T>
bool ZReferenceBuffer<T>::Resize( int _newSize)
{
	if (_newSize < this->BufferSize)
		return false;

	this->BufferSize = _newSize + 1;

	ZArray<T*> newBuffer;
	newBuffer.Resize(this->BufferSize);

	for ( int i = 0; i < this->BufferSize; i++)
		newBuffer[i] = this->Buffer[i];

	this->Indicator.Resize(this->BufferSize, false);

	this->Buffer = newBuffer;

	return true;
}

template <typename T>
ZList<T> ZReferenceBuffer<T>::Items()
{
	 int i;
	ZList<T> items;

	for (i = 1; i < this->BufferSize; i++)
	{
		if (this->IsValid(i))
			items.PushBack(this->Buffer[i]);
	}

	return items;
}

#endif