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

/*
 * Generic map.
 *
 * Usage -
 *	declareHashMap(MapType,KeyType,ValueType,Equal,Hasher)
 *	implementHashMap(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>

#define _HME(MapType) name2(MapType,_Entry)
#define _HMI(MapType) name2(MapType,_Iterator)

#define declareHashMap(MapType,KeyType,ValueType,Equal,Hasher)		      \
class MapType;								      \
									      \
struct _HME(MapType) {							      \
    KeyType	   key;							      \
    ValueType	   value;						      \
    _HME(MapType)* next;						      \
};									      \
									      \
class _HMI(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:								      \
    const MapType* map;							      \
    _HME(MapType)* entry;						      \
    int		   next_bucket;						      \
									      \
    friend MapType;							      \
};									      \
									      \
class MapType {								      \
  public:								      \
    MapType(int default_size = 211);					      \
    /* 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. */  \
									      \
    _HMI(MapType) elements() const;					      \
    /* REQUIRES: No modifications while iterator is active. */		      \
    /* EFFECTS:  Returns an iterator that scans thru map elements */	      \
  private:								      \
    _HME(MapType)** buckets;						      \
    int		    num_buckets;					      \
    int		    num_entries;					      \
									      \
    friend _HMI(MapType);						      \
									      \
    _HME(MapType)* find_entry(KeyType key) const;			      \
    /* EFFECTS: If THIS contains a mapping for KEY, then return ptr to */     \
    /*		corresponding entry.  Else return 0 */			      \
};									      \

#define implementHashMap(MapType,KeyType,ValueType,Equal,Hasher)	      \
MapType::MapType(int bsize) {						      \
    buckets = new _HME(MapType)*[bsize];				      \
    num_buckets = bsize;						      \
    for (int i = 0; i < bsize; i++) {					      \
	buckets[i] = 0;							      \
    }									      \
    num_entries = 0;							      \
}									      \
									      \
MapType::~MapType() {							      \
    for (int i = 0; i < num_buckets; i++) {				      \
	_HME(MapType)* temp = buckets[i];				      \
	while (temp != 0) {						      \
	    _HME(MapType)* next = temp->next;				      \
	    delete temp;						      \
	    temp = next;						      \
	}								      \
    }									      \
    delete [] buckets;							      \
}									      \
									      \
int MapType::size() const {						      \
    return num_entries;							      \
}									      \
									      \
int MapType::contains(KeyType key) const {				      \
    return (find_entry(key) !=0);					      \
}									      \
									      \
ValueType MapType::operator [] (KeyType key) const {			      \
    return (find_entry(key)->value);					      \
}									      \
									      \
int MapType::find(KeyType key, ValueType& value) const {		      \
    _HME(MapType)* index = find_entry(key);				      \
    if (index != 0) {							      \
	value = index->value;						      \
	return 1;							      \
    }									      \
    else {								      \
	return 0;							      \
    }									      \
}									      \
									      \
void MapType::insert(KeyType key, ValueType value) {			      \
    unsigned int b = Hasher(key) % num_buckets;				      \
									      \
    _HME(MapType)* entry = new _HME(MapType);				      \
    entry->key = key;							      \
    entry->value = value;						      \
    entry->next = buckets[b];						      \
									      \
    buckets[b] = entry;							      \
    num_entries++;							      \
}									      \
									      \
void MapType::replace(KeyType key, ValueType value) {			      \
    _HME(MapType)* index = find_entry(key);				      \
    if (index != 0) {							      \
	index->value = value;						      \
    }									      \
    else {								      \
	insert(key, value);						      \
    }									      \
}									      \
									      \
void MapType::remove(KeyType key) {					      \
    unsigned int b = Hasher(key) % num_buckets;				      \
    									      \
    _HME(MapType)** next_ref = &(buckets[b]);				      \
    _HME(MapType)*  next = *next_ref;					      \
									      \
    /* Invariant: next == *next_ref */					      \
    while (next !=0){							      \
	if (Equal(key, next->key)) {					      \
	    /* Delete it */						      \
	    *next_ref = next->next;					      \
	    delete next;						      \
	    num_entries--;						      \
	    break;							      \
	}								      \
	next_ref = &(next->next);					      \
	next = *next_ref;						      \
    }									      \
}									      \
									      \
_HMI(MapType) MapType::elements() const {				      \
    _HMI(MapType) iter;							      \
									      \
    iter.map = this;							      \
									      \
    for (int i = 0; i < num_buckets; i++) {				      \
	if (buckets[i] != 0) {						      \
	    iter.entry = buckets[i];					      \
	    iter.next_bucket = i + 1;					      \
	    return iter;						      \
	}								      \
    }									      \
    iter.next_bucket = num_buckets;					      \
    iter.entry = 0;							      \
    return iter;							      \
}									      \
									      \
int _HMI(MapType)::valid() {						      \
    return (entry != 0);						      \
}									      \
									      \
void _HMI(MapType)::next() {						      \
    entry = entry->next;						      \
    while ((entry == 0) && (next_bucket < map->num_buckets)) {		      \
	entry = map->buckets[next_bucket];				      \
	next_bucket++;							      \
    }									      \
}									      \
									      \
KeyType _HMI(MapType)::key() {						      \
    return entry->key;							      \
}									      \
									      \
ValueType _HMI(MapType)::value() {					      \
    return entry->value;						      \
}									      \
									      \
_HME(MapType)* MapType::find_entry(KeyType key) const {			      \
    unsigned int b = Hasher(key) % num_buckets;				      \
    _HME(MapType)* index = buckets[b];					      \
    while (index != 0) {						      \
	if (Equal(index->key, key)) {					      \
	    return index;						      \
	}								      \
	index = index->next;						      \
    }									      \
    return 0;								      \
}									      \

#endif /* _HASHMAP_H */
