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

/*
 * Generic map.
 *
 * Usage -
 *	declareArrayMap(MapType,KeyType,ValueType,Equal)
 *	implementArrayMap(MapType,KeyType,ElementType,Equal)
 *
 *	- 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);
 */

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

#define ArrayMapEntry(MapType) name2(MapType,_Entry)
#define ArrayMapArray(MapType) name2(MapType,_Array)
#define ArrayMapIterator(MapType) name2(MapType,_Iterator)

#define declareArrayMap(MapType,KeyType,ValueType,Equal)		      \
class MapType;								      \
									      \
struct ArrayMapEntry(MapType) {						      \
    KeyType	key;							      \
    ValueType	value;							      \
};									      \
									      \
class ArrayMapIterator(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;							      \
    int index;								      \
									      \
    friend MapType;							      \
};									      \
									      \
declareArray(ArrayMapArray(MapType),ArrayMapEntry(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. */  \
									      \
    ArrayMapIterator(MapType) elements() const;				      \
    /* REQUIRES: No modifications while iterator is active. */		      \
    /* EFFECTS:  Returns an iterator that scans thru map elements */	      \
  private:								      \
    int find_index(KeyType key, int& index) const;			      \
    /* EFFECTS: If there exists I such that this->list[i].key = KEY, then */  \
    /*		sets INDEX to I and returns true.  Else returns false. */     \
									      \
    ArrayMapArray(MapType) list;					      \
    friend ArrayMapIterator(MapType);					      \
};									      \
									      \
inline MapType::MapType() : list() { }					      \
inline MapType::~MapType() { }						      \
									      \
inline int MapType::size() const {					      \
    return list.size();							      \
}									      \
									      \
inline int MapType::contains(KeyType key) const {			      \
    int junk;								      \
    return find_index(key, junk);					      \
}									      \
									      \
inline ValueType MapType::operator [] (KeyType key) const {		      \
    int index;								      \
    find_index(key, index);						      \
    return list[index].value;						      \
}									      \
									      \
inline int MapType::find(KeyType key, ValueType& value) const {		      \
    int index;								      \
    if (find_index(key, index)) {					      \
	value = list[index].value;					      \
	return 1;							      \
    }									      \
    else {								      \
	return 0;							      \
    }									      \
}									      \
									      \
inline void MapType::insert(KeyType key, ValueType value) {		      \
    ArrayMapEntry(MapType) entry;					      \
    entry.key = key;							      \
    entry.value = value;						      \
    list.append(entry);							      \
}									      \
									      \
inline void MapType::replace(KeyType key, ValueType value) {		      \
    int index;								      \
    if (find_index(key, index)) {					      \
	list[index].value = value;					      \
    }									      \
    else {								      \
	insert(key, value);						      \
    }									      \
}									      \
									      \
inline void MapType::remove(KeyType key) {				      \
    int index;								      \
    if (find_index(key, index)) {					      \
	list[index] = list.high();					      \
	list.remove();							      \
    }									      \
}									      \
									      \
inline ArrayMapIterator(MapType) MapType::elements() const {		      \
    ArrayMapIterator(MapType) iter;					      \
    iter.map = this;							      \
    iter.index = 0;							      \
    return iter;							      \
}									      \
									      \
inline int ArrayMapIterator(MapType)::valid() {				      \
    return (index < map->list.size());					      \
}									      \
									      \
inline void ArrayMapIterator(MapType)::next() {				      \
    index++;								      \
}									      \
									      \
inline KeyType ArrayMapIterator(MapType)::key() {			      \
    return map->list[index].key;					      \
}									      \
									      \
inline ValueType ArrayMapIterator(MapType)::value() {			      \
    return map->list[index].value;					      \
}									      \

#define implementArrayMap(MapType,KeyType,ElementType,Equal)		      \
implementArray(ArrayMapArray(MapType),ArrayMapEntry(MapType));		      \
									      \
int MapType::find_index(KeyType key, int& index) const {		      \
    for (int i = 0; i < list.size(); i++) {				      \
	if (Equal(list[i].key, key)) {					      \
	    index = i;							      \
	    return 1;							      \
	}								      \
    }									      \
    return 0;								      \
}									      \

#endif /* _ARRAYMAP_H */
