#include "Col.ph"
#ifdef __GNUG__
#pragma implementation
#endif

#include "HashTable.h"
#include "Class.h"

#include "Math.h"
#include "Error.h"

static const int cMinCapacity= 17;

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

NewAbstractMetaImpl(HashTable,Object, (TP(size), T(capacity), T(lowWatermark), T(highWatermark)));

const int HashTable::cInvalidIndex= -1;

HashTable::HashTable(int initCap, pEqualFunc eq, pHashFunc hs, int *aSize)
{
	CalcBounds(initCap);
	equal= eq;
	hash= hs;
	if (aSize)
		size= aSize;
	else
		size= &mySize;
	*size= 0;
}

void HashTable::CalcBounds(int aCapacity)
{
	capacity= Math::NextPrime(Math::Max(aCapacity, cMinCapacity));
	lowWatermark= Math::Max(cMinCapacity, capacity / 4);
	highWatermark= (capacity * 3 / 4);      // 0.75
}

void HashTable::Empty(int)
{
	AbstractMethod("Empty");
}

void *HashTable::Add(void *op)
{
	int slot;

	if (! SearchFirst(op, slot)) {
		SetKeyAt(op, slot);
		(*size)++;
		if ( *size >= highWatermark )
			Rehash(NewCapacity(TRUE));
		Changed();
		return 0;
	}
	return op;
}

void *HashTable::Remove(void *op, EqualType eq)
{
	int slot;

	op= eq ? SearchFirst(op, slot) : SearchPtr(op, slot);
	if (op) {
		RemoveSlot(slot);
		Changed();
	}
	return op;
}

void *HashTable::Find(void *op, EqualType eq)
{
	int slot;
	return eq ? SearchFirst(op, slot) : SearchPtr(op, slot);
}

int HashTable::IndexOf(void *op, EqualType eq)
{
	int slot;

	op= eq ? SearchFirst(op, slot) : SearchPtr(op, slot);
	if (op)
		return slot;
	return -1;
}

//---- statistics ----

int HashTable::Collisions(void *obj)
{
	int slot0, slot;

	slot0= HashAddress(obj);
	if (SearchFirst(obj, slot)) {
		if (slot >= slot0)
			return slot - slot0 + 1;
		return (slot + capacity) - slot0 + 1;
	}
	return 0;
}

double HashTable::AverageCollisions()
{
	void *obj;

	double cum= 0.0;
	int i= GetInitialIndex();
	while (obj= AtNextIndex(i)) {
		cum+= Collisions(obj);
	}
	if (*size > 0)
		return cum / *size;
	return 0;
}

//---- object i/o ----

OStream &HashTable::PrintOn(OStream &os)
{
	MayNotUse("PrintOn");
	return os;
}

IStream &HashTable::ReadFrom(IStream &is)
{
	MayNotUse("ReadFrom");
	return is;
}

//---- iterator support ----

void *HashTable::AtNextIndex(int &i)
{
	void *op= 0;
	i++;
	while (i < capacity && ! (op= KeyAt(i)))
		i++;
	return op;
}

void *HashTable::AtPrevIndex(int &i)
{
	void *op= 0;
	i--;
	while (i >= 0 && ! (op= KeyAt(i)))
		i--;
	return op;
}

int HashTable::GetInitialIndex()
{
	return -1;
}

//---- algorithm ----

void *HashTable::SearchFirst(void *obj, int &slot)
{
	void *op;

	slot= HashAddress(obj);
	while ((op= KeyAt(slot)) && ! equal(op, obj)) {
		if (++slot == capacity)
			slot= 0;
	}
	return op;
}

void *HashTable::SearchPtr(void *obj, int &slot)
{
	if (SearchFirst(obj, slot) == obj)
		return obj;
	return 0;
}

void HashTable::RemoveSlot(int slot)
{
	NullAt(slot);
	FixCollisions(slot);
	(*size)--;
	if (*size <= lowWatermark && *size > cMinCapacity)
		Rehash(NewCapacity(FALSE));
}

void HashTable::FixCollisions(int slot)
{
	void *cand;
	int candSlot0, emptySlot;
	bool swap;

	emptySlot= slot;
	if (++slot == capacity)
		slot= 0;
	while (cand= KeyAt(slot)) {
#if 0
		SearchFirst(cand, candSlot);        // slow, but easy to understand
		if (candSlot == emptySlot) {
			Swap(emptySlot, slot);
			emptySlot= slot;
		}
#else                                       // fast, but difficult to understand
		candSlot0= HashAddress(cand);
		if (emptySlot < slot)
			swap= ! (emptySlot < candSlot0 && candSlot0 <= slot);
		else
			swap= (slot < candSlot0) && (candSlot0 < emptySlot);
		if (swap) {
			Swap(emptySlot, slot);
			emptySlot= slot;
		}
#endif
		if (++slot == capacity)
			slot= 0;
	}
}

HashTable *HashTable::MakeNew(int)
{
	// virtual constructor - returns a new object of the same class as this
	AbstractMethod("HashTable::MakeNew");
	return 0;
}

void HashTable::Assign(HashTable *ht)
{
	// hook - similar to a copy constructor
	lowWatermark= ht->lowWatermark;
	highWatermark= ht->highWatermark;
	capacity= ht->capacity;
	*size= *ht->size;
}

int HashTable::NewCapacity(bool grow)
{
	if (grow)
		return capacity * 2;
	return capacity / 2;
}

void HashTable::Rehash(int newCapacity)
{
	HashTable *ht= MakeNew(newCapacity);
	DoRehash(ht);
	Assign(ht);
	SafeDelete(ht);
}

void HashTable::DoRehash(HashTable *ht)
{
	void *op;
	int i= GetInitialIndex();
	while (op= AtNextIndex(i))
		ht->Add(op);
}

void *HashTable::KeyAt(int)
{
	AbstractMethod("KeyAt");
	return 0;
}

void HashTable::SetKeyAt(void*, int)
{
	AbstractMethod("SetKeyAt");
}

void HashTable::NullAt(int)
{
	AbstractMethod("NullAt");
}

void HashTable::Swap(int, int)
{
	AbstractMethod("Swap");
}