/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1991, 1992
 *	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"

class CcuAllocator;

typedef void CcuHashItem;

class CcuHashCell {
protected:
friend	class	CcuHashTable;
friend	class	CcuHashCellIter;
static	CcuAllocator*	HashCellMem;
static	void	ClassInit ();

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

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

	void*	operator new (unsigned long);
	void	operator delete (void*);
};

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


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 CcuHashTable {
private:
friend	class	CcuHashCellIter;
friend	class	CcuHashCellRef;

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

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

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

		CcuHashTable (unsigned int, HASH_F = 0, HCP_F = 0, HDEL_F = 0, HCMP_F = 0);
		CcuHashTable (const CcuHashTable&);
		~CcuHashTable ();
	CcuHashCell*	Add (const void*, int* = 0);
	CcuHashCell*	Get (const void*);
	CcuHashItem*	Remove (const void*, int* = 0);
	void	Clear ();
	void	Resize (int);
inline	int	GetSize () const		{ return Size; }
	CcuHashCellRef operator [] (const void*) const;

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

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


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

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


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

protected:
	const CcuHashTable&	TheTable;
	int	CurIndex;
	CcuHashCell*	CurCell;

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

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

class CcuHashIter : public CcuHashCellIter {
public:
inline		CcuHashIter (const CcuHashTable& t) : CcuHashCellIter (t) { }
inline		~CcuHashIter () {}

inline	CcuHashIter&	operator ++ ()	{ ++((CcuHashCellIter) (*this)); return *this; }
inline	CcuHashItem*	operator * () const	{ return CurCell ? CurCell->GetInfo () : 0; }
};

#ifndef CPLUS_BUG19

template <class ITEM> class CcuHashTableOf;
template <class ITEM> class CcuDictionnaryOf;

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

template <class ITEM> class CcuHashCellRefOf : public CcuHashCellRef {
friend	class	CcuHashTableOf<ITEM>;
friend	class	CcuDictionnaryOf<ITEM>;
protected:
inline	CcuHashCellRefOf (const CcuHashTableOf<ITEM>& t, const void* key) : CcuHashCellRef (t, key)	{}
#ifdef CPLUS_BUG1
inline	CcuHashCellRefOf (const CcuHashCellRefOf<ITEM>& t) : CcuHashCellRef (t)	{}
#endif
public:
inline	ITEM*	operator = (ITEM* it)		{ return (ITEM*) (CcuHashCellRef::operator = (it)); }
inline		operator ITEM* ()		{ return (ITEM*) (CcuHashCellRef::operator CcuHashItem* ()); }
};


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

template <class ITEM> class CcuDictionnaryOf : public CcuDictionnary {
public:
inline		CcuDictionnaryOf (unsigned int size, HASH_F hash = 0) : CcuDictionnary (size, hash)	{}
inline		~CcuDictionnaryOf ()	{}
inline	CcuHashCellOf<ITEM>*	Add (const void* key, int* found = 0)	{ return (CcuHashCellOf<ITEM>*) CcuDictionnary::Add (key, found); }
inline	CcuHashCellOf<ITEM>*	Get (const void* key)		{ return (CcuHashCellOf<ITEM>*) CcuDictionnary::Get (key); }
inline	ITEM*	Remove (const void* key, int* found = 0)	{ return (ITEM*) CcuDictionnary::Remove (key, found); }
inline		operator const CcuHashTableOf<ITEM>& () const	{ return *(const CcuHashTableOf<ITEM>*) this; }
inline	CcuHashCellRefOf<ITEM> operator [] (const char* key) const	{ return CcuHashCellRefOf<ITEM> (*(const CcuHashTableOf<ITEM>*)this, key); }
};


template <class ITEM> class CcuHashIterOf : public CcuHashIter {
public:
inline		CcuHashIterOf (const CcuHashTableOf<ITEM>& t) : CcuHashIter (t) { }
inline		~CcuHashIterOf () {}
inline	CcuHashIterOf<ITEM>&	operator ++ ()	{ ++((CcuHashIter) (*this)); return *this; }
inline	ITEM*	operator * () const	{ return (ITEM*) (CcuHashIter::operator  * ()); }
};

#endif	/* CPLUS_BUG19 */

#endif	/* HashTable_H_ */