#ifndef HashTable_First
#define HashTable_First
#ifdef __GNUG__
#pragma interface
#endif

#include "Object.h"
#include "ContainerTypes.h"
#include "Container.h"

//---- HashTable ---------------------------------------------------------------

class HashTable : public Object {
public:
	MetaDef(HashTable);
	HashTable();
	HashTable(int initCap, pEqualFunc eq, pHashFunc hs, int *aSize);

	int Size();
	int Capacity();
	virtual void Empty(int initCapacity= cContainerInitCap);

	virtual void *Add(void *obj);
	virtual void *Remove(void *obj, EqualType equal);
	virtual void *Find(void *obj, EqualType equal);
	virtual int IndexOf(void *obj, EqualType equal);
	virtual void Rehash(int newCapacity);
	
	//---- statistics
	int Collisions(void *obj);
	double AverageCollisions();

	//---- object i/o (may not use)
	OStream &PrintOn(OStream &os);
	IStream &ReadFrom(IStream &is);

	//---- iterator support
	void *AtIndex(int idx);
	virtual void *AtNextIndex(int &idx);
	virtual void *AtPrevIndex(int &idx);
	virtual int GetInitialIndex();

protected:
	void CalcBounds(int aCapacity);

	//---- table primitives
	virtual void *KeyAt(int i);
	virtual void SetKeyAt(void *obj, int i);
	virtual void NullAt(int i);
	virtual void Swap(int i, int j);

	//---- algorithm
	int HashAddress(void *obj);
	void *SearchFirst(void *obj, int &slot);
	void *SearchPtr(void *obj, int &slot);
	virtual void RemoveSlot(int slot);
	void FixCollisions(int slot);

	virtual void DoRehash(HashTable *ht);
	virtual HashTable *MakeNew(int newCapacity);
	virtual void Assign(HashTable *ht);
	virtual int NewCapacity(bool grow);
protected:
	pEqualFunc equal;
	pHashFunc hash;
	int lowWatermark, highWatermark;
	int capacity;
	int mySize;     // used if size not provided by the client
	int *size;
public:
	static const int cInvalidIndex;
};

//---- HashTable inlines -------------------------------------------------------

inline int HashTable::HashAddress(void *obj)
	{ return (int) (hash(obj) % capacity); }

inline int HashTable::Size()
	{ return *size; }

inline int HashTable::Capacity()
	{ return capacity; }

inline void *HashTable::AtIndex(int idx)
	{ return KeyAt(idx); }

#endif