/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1991-1997
 *	Laboratoire de Recherche en Informatique (LRI)
 *	Centre d'Etudes de la Navigation Aerienne (CENA)
 *
 *	plain and generic hash tables and dictionnaries
 *	(Original C version by Michel Beaudouin-Lafon)
 *
 *	$Id$
 *	$CurLog$
 */

#ifndef HashTable_H_
#define HashTable_H_

#include "cplus_bugs.h"
#include <sys/types.h>

class IvlAllocator;

typedef void IvlHashItem;

class IvlHashCell {
protected:
friend	class	IvlHashTable;
friend	class	IvlHashCellIter;
static	IvlAllocator*	HashCellMem;
static	void	ClassInit ();

	const void*	Key;		/* hash key */
	IvlHashItem*	Info;			/* data */
	IvlHashCell*	Next;			/* synonyms */
	
inline		IvlHashCell (const void* k, IvlHashCell* n) : Key (k), Info (0), Next (n)	{}

public:
inline	void	SetInfo (IvlHashItem* p)			{ Info = p; }
inline	IvlHashItem*	GetInfo () const			{ return Info; }
inline	const void*	GetKey () const			{ return Key; }

	void*	operator new (size_t);
	void	operator delete (void*);
};

class IvlHashCellRef {
friend	class	IvlHashTable;
protected:
		const IvlHashTable&	Table;
		const void*	Key;
inline	IvlHashCellRef (const IvlHashTable& t, const void* key) : Table (t), Key (key)	{}
#ifdef CPLUS_BUG1
inline	IvlHashCellRef (const IvlHashCellRef& t) : Table (t.Table), Key (t.Key)	{}
#endif
public:
	IvlHashItem*	operator = (IvlHashItem*);
		operator IvlHashItem* ();
};

typedef unsigned int (*HASH_F) (const void*, int);
typedef int (*HCMP_F) (const void*, const void*);
typedef void* (*HCP_F) (const void*);
typedef void (*HDEL_F) (const void*);

class IvlHashTable {
private:
friend	class	IvlHashCellIter;
friend	class	IvlHashCellRef;

protected :
	IvlHashCell**	Table;
	unsigned int	Size;
	HASH_F	Hash;
	HCP_F	Copy;
	HDEL_F	Delete;
	HCMP_F	Compare;

	IvlHashCell**	HashKey (const void*) const;
	IvlHashCell*	FindCell (IvlHashCell**, const void*) const;
	IvlHashCell*	AddCell (IvlHashCell**, const void*) const;

public:
static	unsigned int	HashPtr (const void*, int);

		IvlHashTable (unsigned int, HASH_F = 0, HCP_F = 0, HDEL_F = 0, HCMP_F = 0);
		IvlHashTable (const IvlHashTable&);
		~IvlHashTable ();
	IvlHashCell*	Add (const void*, int* = 0);
	IvlHashCell*	Get (const void*);
	IvlHashItem*	Remove (const void*, int* = 0);
	void	Clear ();
	void	Resize (int);
inline	int	GetSize () const		{ return Size; }
	IvlHashCellRef operator [] (const void*) const;

#ifdef TUNE
	void	HashStats ();
	void	CollStats ();
#endif
};

class IvlDictionnary : public IvlHashTable {
protected:
static	void*	CopyString (const void*);
static	void	DeleteString (const void*);
static	int	CompareString (const void*, const void*);

public:
		IvlDictionnary (int size, HASH_F = 0);
		~IvlDictionnary ();

	void	KeyCopy (int);
static	unsigned int	HashString (const void*, int);
};

class IvlHashCellIter {
public:
	enum	hashiter_status	{ Normal, StartOfTable, EndOfTable, BadTable };

protected:
	const IvlHashTable&	TheTable;
	int	CurIndex;
	IvlHashCell*	CurCell;

public:
inline		IvlHashCellIter (const IvlHashTable& t) : TheTable (t) { CurIndex = -1; CurCell = 0; }
inline		~IvlHashCellIter () {}

inline	void	Reset ()	{ CurCell = 0; CurIndex = -1; }
	IvlHashCellIter&	operator ++ ();
#ifndef CPLUS_BUG16
	IvlHashCellIter	operator ++ (int);
#endif
inline	IvlHashCell*	operator * () const	{ return CurCell; }
	hashiter_status	GetStatus () const;
inline	operator int () const	{ return CurCell != 0; }
};

class IvlHashIter : public IvlHashCellIter {
public:
inline		IvlHashIter (const IvlHashTable& t) : IvlHashCellIter (t) { }
inline		~IvlHashIter () {}

inline	IvlHashIter&	operator ++ ()	{ return (IvlHashIter&)(this->IvlHashCellIter::operator ++ ()); }
inline	IvlHashItem*	operator * () const	{ return CurCell ? CurCell->GetInfo () : 0; }
};

#ifndef CPLUS_BUG19

template <class ITEM> class IvlHashTableOf;
template <class ITEM> class IvlDictionnaryOf;

template <class ITEM> class IvlHashCellOf : public IvlHashCell {
protected:
inline		IvlHashCellOf (const void* k, IvlHashCellOf<ITEM>* n) : IvlHashCell (k, n)	{}
public:
inline	void	SetInfo (ITEM* p)			{ IvlHashCell::SetInfo (p); }
inline	ITEM*	GetInfo () const			{ return (ITEM*) IvlHashCell::GetInfo (); }
};

template <class ITEM> class IvlHashCellRefOf : public IvlHashCellRef {
public:
inline	IvlHashCellRefOf (const IvlHashTableOf<ITEM>& t, const void* key) : IvlHashCellRef (t, key)	{}
#ifdef CPLUS_BUG1
inline	IvlHashCellRefOf (const IvlHashCellRefOf<ITEM>& t) : IvlHashCellRef (t)	{}
#endif
inline	ITEM*	operator = (ITEM* it)		{ return (ITEM*) (IvlHashCellRef::operator = (it)); }
inline		operator ITEM* ()		{ return (ITEM*) (IvlHashCellRef::operator IvlHashItem* ()); }
};

template <class ITEM> class IvlHashTableOf : public IvlHashTable {
public:
inline		IvlHashTableOf (unsigned int size, HASH_F hash = 0, HCP_F cp = 0, HDEL_F del = 0, HCMP_F cmp= 0)	: IvlHashTable (size, hash, cp, del, cmp)	{}
inline		~IvlHashTableOf ()	{}
inline	IvlHashCellOf<ITEM>*	Add (const void* key, int* found = 0)	{ return (IvlHashCellOf<ITEM>*) IvlHashTable::Add (key, found); }
inline	IvlHashCellOf<ITEM>*	Get (const void* key)		{ return (IvlHashCellOf<ITEM>*) IvlHashTable::Get (key); }
inline	ITEM*	Remove (const void* key, int* found = 0)	{ return (ITEM*) IvlHashTable::Remove (key, found); }
inline	IvlHashCellRefOf<ITEM> operator [] (const void* key) const	{ return IvlHashCellRefOf<ITEM> (*this, key); }
};

template <class ITEM> class IvlDictionnaryOf : public IvlDictionnary {
public:
inline		IvlDictionnaryOf (unsigned int size, HASH_F hash = 0) : IvlDictionnary (size, hash)	{}
inline		~IvlDictionnaryOf ()	{}
inline	IvlHashCellOf<ITEM>*	Add (const void* key, int* found = 0)	{ return (IvlHashCellOf<ITEM>*) IvlDictionnary::Add (key, found); }
inline	IvlHashCellOf<ITEM>*	Get (const void* key)		{ return (IvlHashCellOf<ITEM>*) IvlDictionnary::Get (key); }
inline	ITEM*	Remove (const void* key, int* found = 0)	{ return (ITEM*) IvlDictionnary::Remove (key, found); }
inline		operator const IvlHashTableOf<ITEM>& () const	{ return *(const IvlHashTableOf<ITEM>*) this; }
inline	IvlHashCellRefOf<ITEM> operator [] (const char* key) const	{ return IvlHashCellRefOf<ITEM> (*(const IvlHashTableOf<ITEM>*)this, key); }
};

template <class ITEM> class IvlHashedArrayOf : public IvlHashTable {
public:
inline		IvlHashedArrayOf (unsigned int size, HASH_F hash = 0) : IvlHashTable (size, hash)	{}
inline		~IvlHashedArrayOf ()	{}
inline	IvlHashCellOf<ITEM>*	Add (int key, int* found = 0)	{ return (IvlHashCellOf<ITEM>*) IvlHashTable::Add ((void*)key, found); }
inline	IvlHashCellOf<ITEM>*	Get (int key)		{ return (IvlHashCellOf<ITEM>*) IvlHashTable::Get ((void*)key); }
inline	ITEM*	Remove (int key, int* found = 0)	{ return (ITEM*) IvlHashTable::Remove ((void*) key, found); }
inline		operator const IvlHashTableOf<ITEM>& () const	{ return *(const IvlHashTableOf<ITEM>*) this; }
inline	IvlHashCellRefOf<ITEM> operator [] (int key) const	{ return IvlHashCellRefOf<ITEM> (*(const IvlHashTableOf<ITEM>*)this, (void*)key); }
};

template <class ITEM> class IvlHashIterOf : public IvlHashIter {
public:
inline		IvlHashIterOf (const IvlHashTableOf<ITEM>& t) : IvlHashIter (t) { }
inline		~IvlHashIterOf () {}
inline	IvlHashIterOf<ITEM>&	operator ++ ()	{ return (IvlHashIterOf<ITEM>&)(this->IvlHashIter::operator ++ ()); }
inline	ITEM*	operator * () const	{ return (ITEM*) (IvlHashIter::operator  * ()); }
};

template <class ITEM> class IvlHashCellIterOf : public IvlHashCellIter {
public:
inline		IvlHashCellIterOf (const IvlHashTableOf<ITEM>& t) : IvlHashCellIter (t) { }
inline		~IvlHashCellIterOf () {}
inline	IvlHashCellIterOf<ITEM>&	operator ++ ()	{ return (IvlHashCellIterOf<ITEM>&)(this->IvlHashCellIter::operator ++ ()); }
#ifndef CPLUS_BUG16
inline	IvlHashCellIterOf<ITEM>	operator ++ (int i)	{ return *(IvlHashCellIterOf<ITEM>*)&(this->IvlHashCellIter::operator ++ (i)); }
#endif
inline	IvlHashCellOf<ITEM>*	operator * () const	{ return (IvlHashCellOf<ITEM>*) (IvlHashCellIter::operator  * ()); }
};

#endif	/* CPLUS_BUG19 */

#endif	/* HashTable_H_ */