/* Copyright (c) 1993 by Sanjay Ghemawat */
#ifndef _OPENHASHMAP_H
#define _OPENHASHMAP_H

/*
 * Generic map.
 *
 * Usage -
 *	declareOpenHashMap(MapType,KeyType,ValueType,Equal,Hasher)
 *	implementOpenHashMap(MapType,KeyType,ValueType,Equal,Hasher)
 *
 *	- MapType is the name of the resulting table class.
 *	- Equal is a function or macro that takes two KeyType args
 *	  and returns true iff the keys are equal.
 *		int Equal(KeyType, KeyType);
 *
 *	- Hasher is a function that takes a KeyType and returns a hash value.
 *		unsigned int Hasher(KeyType);
 *
 * Implementation is a hash table with chained buckets.
 */

#include <generic.h>
#include "Array.h"

/*
 * Status of hash table cells.
 */
enum OpenHashMapStatus {
    OHM_Empty,			/* Cell is empty */
    OHM_Full,			/* Cell is full */
    OHM_Deleted			/* Cell has been deleted */
    };

#define OpenHashMapEntry(MapType) name2(MapType,_Entry)
#define OpenHashMapArray(MapType) name2(MapType,_Array)
#define OpenHashMapIterator(MapType) name2(MapType,_Iterator)

#define declareOpenHashMap(MapType,KeyType,ValueType,Equal,Hasher)	      \
class MapType;								      \
									      \
struct OpenHashMapEntry(MapType) {					      \
    OpenHashMapStatus status;						      \
    KeyType	      key;						      \
    ValueType	      value;						      \
};									      \
									      \
declareArray(OpenHashMapArray(MapType),OpenHashMapEntry(MapType))	      \
									      \
class OpenHashMapIterator(MapType) {					      \
  public:								      \
    int valid();							      \
    /* EFFECTS: Returns true iff iterator hasn't finished yet */	      \
									      \
    void next();							      \
    /* EFFECTS: Advance to next entry in the map */			      \
									      \
    KeyType key();							      \
    /* REQUIRES: valid() */						      \
    /* EFFECTS:  Returns the key for the current entry. */		      \
									      \
    ValueType value();							      \
    /* REQUIRES: valid() */						      \
    /* EFFECTS:  Returns the value for the current entry. */		      \
  private:								      \
    OpenHashMapArray(MapType) const* list;				      \
    int index;								      \
									      \
    friend MapType;							      \
};									      \
									      \
class MapType {								      \
  public:								      \
    MapType();								      \
    /* EFFECTS:	Returns a new empty map. */				      \
									      \
    ~MapType();								      \
    /* EFFECTS: Destroys the map. */					      \
									      \
    int size() const;							      \
									      \
    int contains(KeyType key) const;					      \
    /* EFFECTS: Returns true iff THIS provides mapping for KEY. */	      \
									      \
    ValueType operator [] (KeyType key) const;				      \
    /* REQUIRES: THIS provides mapping for KEY. */			      \
    /* EFFECTS:  Returns value that KEY maps to. */			      \
									      \
    int find(KeyType key, ValueType& value) const;			      \
    /* EFFECTS: If THIS provides mapping for KEY, sets VALUE to the mapped */ \
    /*		value and returns true.  Else returns false. */		      \
									      \
    void replace(KeyType key, ValueType value);				      \
    /* EFFECTS: Changes THIS to map KEY to VALUE.  Any old mapping for KEY */ \
    /*		is forgotten. */					      \
									      \
    void insert(KeyType key, ValueType value);				      \
    /* REQUIRES: THIS does not contain mapping for KEY. */		      \
    /* EFFECTS:	 Inserts mapping from KEY to VALUE. */			      \
									      \
    void remove(KeyType key);						      \
    /* EFFECTS: If THIS contains a mapping for KEY, removes that mapping. */  \
									      \
    OpenHashMapIterator(MapType) elements() const;			      \
    /* REQUIRES: No modifications while iterator is active. */		      \
    /* EFFECTS:  Returns an iterator that scans thru map elements */	      \
  private:								      \
    static unsigned int search(OpenHashMapArray(MapType) const& l,	      \
			       KeyType key);				      \
    /* EFFECTS: If there exists I such that L[i].key = KEY, then */	      \
    /*		returns I.  Else returns empty hash entry for KEY. */	      \
									      \
    static unsigned int hash2(unsigned int key);				      \
    /* EFFECTS: Returns odd prime as secondary hash value based on KEY */  \
									      \
    void enlarge();							      \
    /* EFFECTS: Increase hash table size if it is too full */		      \
									      \
    void shrink();							      \
    /* EFFECTS: Decrease hash table size if it is too empty */		      \
									      \
    void resize(int newsize);						      \
    /* REQUIRES: full < NEWSIZE */					      \
    /* EFFECTS:  Changes hash table size to NEWSIZE */			      \
									      \
    int full;				/* Count of full entries */	      \
    int empty;				/* Count of empty entries */	      \
    int deleted;			/* Count of deleted entries */	      \
									      \
    OpenHashMapArray(MapType) list;					      \
									      \
    /* REP INVARIANTS */						      \
    /*   full == number of entries with status == OHM_Full */		      \
    /*   empty == number of entries with status == OHM_Empty */		      \
    /*   deleted == number of entries with status == OHM_Deleted */	      \
    /*   list.size() == full + empty + deleted */			      \
    /*   list.size() >= 1 */						      \
    /*   list.size() is a power of two */				      \
    /*   empty >= 1 */							      \
};									      \

#define implementOpenHashMap(MapType,KeyType,ValueType,Equal,Hasher)	      \
implementArray(OpenHashMapArray(MapType),OpenHashMapEntry(MapType))	      \
									      \
MapType::MapType() : list() {						      \
    /* Add dummy entry */						      \
    OpenHashMapEntry(MapType) entry;					      \
    entry.status = OHM_Empty;						      \
    list.append(entry);							      \
									      \
    full = 0;								      \
    deleted = 0;							      \
    empty = 1;								      \
}									      \
									      \
MapType::~MapType() { }							      \
									      \
int MapType::size() const {						      \
    return full;							      \
}									      \
									      \
int MapType::contains(KeyType key) const {				      \
    return (list[search(list, key)].status == OHM_Full);		      \
}									      \
									      \
ValueType MapType::operator [] (KeyType key) const {			      \
    return list[search(list, key)].value;				      \
}									      \
									      \
int MapType::find(KeyType key, ValueType& value) const {		      \
    unsigned int index = search(list, key);				      \
    if (list[index].status == OHM_Full) {				      \
	value = list[index].value;					      \
	return 1;							      \
    }									      \
    else {								      \
	return 0;							      \
    }									      \
}									      \
									      \
void MapType::insert(KeyType key, ValueType value) {			      \
    unsigned int index = search(list, key);				      \
									      \
    list[index].key = key;						      \
    list[index].value = value;						      \
    list[index].status = OHM_Full;					      \
    full++;								      \
    empty--;								      \
									      \
    enlarge();								      \
}									      \
									      \
void MapType::replace(KeyType key, ValueType value) {			      \
    unsigned int index = search(list, key);				      \
									      \
    if (list[index].status == OHM_Full) {				      \
	list[index].value = value;					      \
    }									      \
    else {								      \
	list[index].key = key;						      \
	list[index].value = value;					      \
	list[index].status = OHM_Full;					      \
	full++;								      \
	empty--;							      \
									      \
	enlarge();							      \
    }									      \
}									      \
									      \
void MapType::remove(KeyType key) {					      \
    unsigned int index = search(list, key);				      \
									      \
    if (list[index].status == OHM_Full) {				      \
	list[index].status = OHM_Deleted;				      \
	full--;								      \
	deleted++;							      \
	shrink();							      \
    }									      \
}									      \
									      \
OpenHashMapIterator(MapType) MapType::elements() const {		      \
    OpenHashMapIterator(MapType) iter;					      \
    iter.list = &list;							      \
    iter.index = -1;							      \
    iter.next();							      \
									      \
    return iter;							      \
}									      \
									      \
int OpenHashMapIterator(MapType)::valid() {				      \
    return (index < list->size());					      \
}									      \
									      \
void OpenHashMapIterator(MapType)::next() {				      \
    index++;								      \
    while ((index < list->size())&&(list->slot(index).status != OHM_Full)) {  \
	index++;							      \
    }									      \
}									      \
									      \
KeyType OpenHashMapIterator(MapType)::key() {				      \
    return list->slot(index).key;					      \
}									      \
									      \
ValueType OpenHashMapIterator(MapType)::value() {			      \
    return list->slot(index).value;					      \
}									      \
									      \
void MapType::enlarge() {						      \
    if ((empty < 1) || (empty < ((list.size() * 20) / 100))) {		      \
	/* Array is more than 80 percent in use */			      \
	resize(list.size() * 2);					      \
    }									      \
}									      \
									      \
void MapType::shrink() {						      \
    /* No shrinking yet */						      \
}									      \
									      \
void MapType::resize(int newsize) {					      \
    /* Save away old entries */						      \
    OpenHashMapArray(MapType) save(full);				      \
    for (int i = 0; i < list.size(); i++) {				      \
	if (list[i].status == OHM_Full) {				      \
	    save.append(list[i]);					      \
	}								      \
    }									      \
									      \
    /* Enlarge array */							      \
    OpenHashMapEntry(MapType) emptyEntry;				      \
    emptyEntry.status = OHM_Empty;					      \
									      \
    list.clear();							      \
    list.append(emptyEntry, newsize);					      \
									      \
    /* Hash saved elements into new array */				      \
    for (i = 0; i < save.size(); i++) {					      \
	list[search(list, save[i].key)] = save[i];			      \
    }									      \
									      \
    /* Update status counts */						      \
    deleted = 0;							      \
    empty = newsize - full;						      \
}									      \
									      \
unsigned int MapType::search(OpenHashMapArray(MapType) const& l,	      \
			     KeyType key) {				      \
    unsigned int h1 = Hasher(key);					      \
    unsigned int h2 = hash2(h1);					      \
									      \
    unsigned int i = h1 % l.size();					      \
    while (l[i].status != OHM_Empty) {					      \
	if ((l[i].status == OHM_Full) && (Equal(l[i].key, key))) {	      \
	    return i;							      \
	}								      \
	i = (i + h2) % l.size();					      \
    }									      \
    /* Loop will terminate because at least one entry is empty, */	      \
    /* and the list size is a power of two and the secondary */		      \
    /* hash value is an odd prime. */					      \
									      \
    return i;								      \
}									      \
									      \
unsigned int MapType::hash2(unsigned int key) {				      \
    /* A few odd primes to use as second hash value. */			      \
    /* We have 16 primes so that the modulus to the array size is fast. */    \
    static unsigned int primes[] = {					      \
	3,								      \
	5,								      \
	7,								      \
	11,								      \
	13,								      \
	17,								      \
	19,								      \
	23,								      \
	29,								      \
	31,								      \
	37,								      \
	41,								      \
	43,								      \
	47,								      \
	53,								      \
	59								      \
	};								      \
									      \
    return primes[(key % (sizeof(primes) / sizeof(int)))];		      \
}									      \

#endif /* _OPENHASHMAP_H */
