//! HASH.H: HASH TABLE TEMPLATE DECLARATION
//. J.L.Villar 7/20/95 (BorlandC++ 4.0)
//. Revised 12/03/2019 for Linux
//. Use of <iostream> is replaced by printf()
//. An abstract identifier class Id is added. 
//.
//. The hash table owns the items inserted.
//.
//. Each item must have a constant identifier, that is accesible by
//. comparison and hashing methods. The item can have additional mutable info.
//.
//. It is assumed that the item class T is derived from the identifier class Id.
//.
//. Empty items must exist (with a trivial or empty mutable part).
//.
//. Colliding items are sorted in binary trees attached to the hash table
//. entries.
//.
//. The only way to remove one item from the hash table is by deleting the
//. whole hash table.
//.
//. Error conditions throw exceptions.

#ifndef _HASH_H_
#define _HASH_H_	1
#ifndef __cplusplus
#error	HASH.H requires C++.
#endif

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef
unsigned int HashValue;	// must be an unsigned integer type

typedef
int CompType;		// must be a signed integer type

class x_NoMem {};

HashValue default_hash(const char *s);


// Provide the following methods
// Initialization of an empty item (with a constant identifier):
//   T::T(const Id&,bool own = false)
// own = true means that the Id buffers must be replicated
// and deleted afterwards by T's destructor.
// Comparison (of the identifiers):
//   CompType Id::operator != (const Id&) const
//   CompType operator != (const Id&,const Id&)
// Hashing (the identifier):
//   HashValue Id::hash() const
// Printing (the identifier):
//   Id::operator const char * () const
//
// The simplest way to implement Id is via operator const char *
// together with a hash(const char *) function and the strcmp()
// for comparisons.
//

class BasicId {
	const char *id;
	HashValue h;
	bool owns;
	void dupid(const char *s,bool transferownership = false) {
		if (owns && id) {delete[] id; id = 0;}
		if (owns && !transferownership) {
			char *tempid = new char[strlen(s)+1];
			strcpy(tempid,s);
			id = tempid;
		} else id = s;
	}
public:
	BasicId(const BasicId &_i,bool _owns = false) : id(0), h(_i.h), owns(_owns) {
		dupid(_i.id);
//printf("Replicating BasicId object (%p) hash(\"%s\")=%u into object %p (%s)\n",&_i,id,h,this,owns?"owned":"not owned");fflush(stdout);
	}
	BasicId(const char *s,bool _owns = false) : id(0), owns(_owns) {
		dupid(s);
		h=::default_hash(id);
//printf("Creating BasicId object (%p) hash(\"%s\")=%u (%s)\n",this,id,h,owns?"owned":"not owned");fflush(stdout);
	}
	~BasicId() {
//printf("Destroying BasicId object (%p) hash(\"%s\")=%u (%s)\n",this,id,h,owns?"owned":"not owned");fflush(stdout);
		if (owns && id) delete[] id;
		id = 0;
	}
	HashValue hash() const {return h;}
	CompType operator != (const BasicId& _i) const {return strcmp(id,_i.id);}
	operator const char * () const {return id;}
};

template<class T,class Id>
class HashTable;

//: BTREE class template
//. (public usage not recomended)
template<class T,class Id>
class HashItem {
	friend class HashTable<T,Id>;
	T theitem;
	HashItem<T,Id> *pg,*pl;
	HashItem(const Id &id,bool own = false) : pg(0),pl(0),theitem(id,own) {}
	~HashItem() {
		// Delete the underlying binary tree.
		if (pg) delete pg;
		if (pl) delete pl;
	}
	unsigned int size() const {
		unsigned int s = 1;
		if (pg) s += pg->size();
		if (pl) s += pl->size();
		return s;
	}
	void write() const;
};

//: HASHTABLE class template
template <class T,class Id>
class HashTable {
	const unsigned int size;
	HashItem<T,Id> **table;
public:
	HashTable(unsigned int s);
	~HashTable();
	double avcoll() const;
	T *find(const Id &id,bool insert = false,bool own = false);
	T *insert(const Id &id,bool own = true) {return find(id,true,own);}
	HashTable<T,Id> &operator << (const Id &id) {
		insert(id);
		return *this;
	}
	void write() const;
};

template<class T,class Id>
HashTable<T,Id>::HashTable(unsigned int s) : size(s) {
	table = new HashItem<T,Id> *[size];
	for (unsigned int i = size; i--; table[i] = 0);
}

template<class T,class Id>
HashTable<T,Id>::~HashTable() {
	for (unsigned int i = size; i--; delete table[i]);
	delete table;
}

//: Write Hash Table contents
template<class T,class Id>
void HashTable<T,Id>::write() const {
	printf("\nCONTENTS:\n");
	for (HashValue i = 0; i < size; i++) {
		HashItem<T,Id> *p = table[i];
		if (!p) continue;
		printf("[%d]\t",i);
		p->write();
		printf("\n");
	}
	printf("STATISTICS:\n");
	printf("Av. collisions: %g\n",avcoll());
}

//: Write btree contents
template<class T,class Id>
void HashItem<T,Id>::write() const {
	if (pl) pl->write();
	printf("\"%s\";",(const char *) theitem);
	if (pg) pg->write();
}

//: Find item
template<class T,class Id>
T *HashTable<T,Id>::find(const Id &id,bool ins,bool own) {
	HashItem<T,Id> **pp = table + (id.hash() % size);
	CompType c;
	while ((*pp) && (c = (id != (*pp)->theitem)) != 0)
		pp = (c > 0) ? &((*pp)->pg) : &((*pp)->pl);
	if (!*pp) {
		if (ins) {
			*pp = new HashItem<T,Id> (id,own);
			if (!*pp) throw x_NoMem();
		}
		else return 0;
	}
	return &(*pp)->theitem;
}

//: Compute collision statistics
template<class T,class Id>
double HashTable<T,Id>::avcoll() const {
	double ac = 0;
	unsigned int n = 0;
	for (unsigned int i = size; i--;)
		if (table[i]) {
			ac += table[i]->size()-1;
			n++;
		}
	return n? ac/n : 0;
}

#endif	// _HASH_H_
//@