Half Life Game Level Viewer

//
//	Map.h
//
//	Templated class to encapsulate a sorted collection of key/value pairs.
//	Sort order is kept through a continually sorted array.  Reallocation of array will occur as necessary
//	when a new array element is added.
//	Does not allow duplicate elements in set.
//	Adding an element has an O(N) run time.
//	Finding an element has an O(ln(N)) run time.
//	Requires array object types that support copy constructor, default constructor, and assignment operator.
//
//	Copyright 2005 Paul Higinbotham
//

#ifndef __MAP_H_
#define __MAP_H_


#include <cassert>


namespace ZGraphics
{

template <typename TK, typename TV>
class MapPair;


template <typename TK, typename TV, typename CF>
class Map
{
public:
	Map() 
	{
		_initMembers();
	}
	Map(int tSize)
	{
		_initMembers();
		_reallocateArray(tSize);
	}
	Map(int tSize, CF * pCompareFn)
	{
		_initMembers();
		m_pCompareFn = pCompareFn;
		_reallocateArray(tSize);
	}
	virtual ~Map()
	{
		delete [] m_pArray;
	}

	// Operator overloading
	const MapPair<TK, TV> & operator[] (size_t tIndex) const { return Get(tIndex); }
	MapPair<TK, TV> & operator[] (size_t tIndex) { return Get(tIndex); }

	virtual void Add(const TK & key, const TV & value);
	virtual const MapPair<TK, TV> & Get(size_t tIndex) const;
	virtual MapPair<TK, TV> & Get(size_t tIndex);
	virtual void Remove(TK & key);
	virtual const TV * IsInMap(const TK & key) const;

	virtual void SetSize(size_t tSize);

	virtual void Clear();
	
	// Accessors
	size_t GetGrowSize() const { return m_tGrow; }
	void SetGrowSize(size_t tSize) { m_tGrow = tSize; }
	size_t GetArraySize() const { return m_tSize; }
	size_t GetMapCount() const { return m_tCount; }
	void SetCompareFn(CF * pCompareFn) { m_pCompareFn = pCompareFn; }

protected:
	virtual void _reallocateArray(size_t tNewSize);
	virtual bool _findIndex(const TK & key, size_t & tMid) const;
	virtual void _remove(size_t tIndex);

private:
	inline void _initMembers()
	{
		m_pArray = 0;
		m_tSize = 0;
		m_tCount = 0;
		m_tGrow = m_sDefaultGrow;

		m_pCompareFn = 0;
	}
	Map(const Map & rhs);					// Prevent copying Map object
	Map & operator= (const Map & rhs);		// Prevent assigning Map object

private:
	MapPair<TK, TV> *	m_pArray;			// Pointer to allocated array of type key/value pairs
	size_t				m_tSize;			// Current size of array allocation (number of key/value elements)
	size_t				m_tCount;			// Current count of elements added to 
	size_t				m_tGrow;			// Amount to grow array when new element is added to full array

	CF *				m_pCompareFn;		// Compare function for sorting elements

	static const size_t m_sDefaultGrow = 50;
};


template <typename TK, typename TV>
class MapPair
{
public:
	MapPair() {}
	MapPair(TK key, TV value)
	{
		this->key = key;
		this->value = value;
	}
	~MapPair() {}

	TK	key;
	TV	value;
};


// Include inline implementation file
#include "Map.inl"


} /* namespace ZGraphics */


#endif /* __MAP_H_ */