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

/*
 * Generic set.
 *
 * Usage -
 *	declareHashSet(SetType,ElemType,Equal,Hasher)
 *	implementHashSet(SetType,ElemType,Equal,Hasher)
 *
 *	- SetType is the name of the resulting set class.
 *	- Equal is a function or macro that takes two ElemType args
 *	  and returns true iff the elems are equal.
 *		int Equal(ElemType, ElemType);
 *
 *	- Hasher is a function that takes a ElemType and returns a hash value.
 *		unsigned int Hasher(ElemType);
 *
 * Implementation is a hash table with chained buckets.
 */

#include <generic.h>

#define _HSE(SetType) name2(SetType,_Entry)
#define _HSI(SetType) name2(SetType,_Iterator)

#define declareHashSet(SetType,ElemType,Equal,Hasher)			      \
class SetType;								      \
									      \
struct _HSE(SetType) {							      \
    ElemType	   elem;						      \
    _HSE(SetType)* next;						      \
};									      \
									      \
class _HSI(SetType) {							      \
  public:								      \
    int valid();							      \
    /* EFFECTS: Returns true iff iterator hasn't finished yet */	      \
									      \
    void next();							      \
    /* EFFECTS: Advance to next entry in the set */			      \
									      \
    ElemType value();							      \
    /* REQUIRES: valid() */						      \
    /* EFFECTS:  Returns the element for the current entry. */		      \
  private:								      \
    const SetType* set;							      \
    _HSE(SetType)*       entry;						      \
    int		         next_bucket;					      \
									      \
    friend SetType;							      \
};									      \
									      \
class SetType {								      \
  public:								      \
    SetType(int default_size = 211);					      \
    /* EFFECTS:	Returns a new empty set. */				      \
									      \
    ~SetType();								      \
    /* EFFECTS: Destroys the set. */					      \
									      \
    int size() const;							      \
									      \
    int contains(ElemType elem) const;					      \
    /* EFFECTS: Returns true iff THIS contains ELEM. */			      \
									      \
    void insert(ElemType elem);						      \
    /* REQUIRES: THIS does not contain ELEM. */				      \
    /* EFFECTS:	 Inserts ELEM into THIS. */				      \
									      \
    void remove(ElemType elem);						      \
    /* EFFECTS: If THIS contains ELEM, removes it. */			      \
									      \
    _HSI(SetType) elements() const;					      \
    /* REQUIRES: No modifications while iterator is active. */		      \
    /* EFFECTS:  Returns an iterator that scans thru set elements */	      \
  private:								      \
    _HSE(SetType)** buckets;						      \
    int		    num_buckets;					      \
    int		    num_entries;					      \
									      \
    friend _HSI(SetType);						      \
									      \
    _HSE(SetType)* find_entry(ElemType elem) const;			      \
    /* EFFECTS: If THIS contains ELEM, then return ptr to */		      \
    /*		corresponding entry.  Else return 0 */			      \
};									      \

#define implementHashSet(SetType,ElemType,Equal,Hasher)			      \
SetType::SetType(int bsize) {						      \
    buckets = new _HSE(SetType)*[bsize];				      \
    num_buckets = bsize;						      \
    for (int i = 0; i < bsize; i++) {					      \
	buckets[i] = 0;							      \
    }									      \
    num_entries = 0;							      \
}									      \
									      \
SetType::~SetType() {							      \
    for (int i = 0; i < num_buckets; i++) {				      \
	_HSE(SetType)* temp = buckets[i];				      \
	while (temp != 0) {						      \
	    _HSE(SetType)* next = temp->next;				      \
	    delete temp;						      \
	    temp = next;						      \
	}								      \
    }									      \
    delete [] buckets;							      \
}									      \
									      \
int SetType::size() const {						      \
    return num_entries;							      \
}									      \
									      \
int SetType::contains(ElemType elem) const {				      \
    return (find_entry(elem) !=0);					      \
}									      \
									      \
void SetType::insert(ElemType elem) {					      \
    unsigned int b = Hasher(elem) % num_buckets;			      \
									      \
    _HSE(SetType)* entry = new _HSE(SetType);				      \
    entry->elem = elem;							      \
    entry->next = buckets[b];						      \
									      \
    buckets[b] = entry;							      \
    num_entries++;							      \
}									      \
									      \
void SetType::remove(ElemType elem) {					      \
    unsigned int b = Hasher(elem) % num_buckets;			      \
									      \
    _HSE(SetType)** next_ref = &(buckets[b]);				      \
    _HSE(SetType)*  next = *next_ref;					      \
									      \
    /* Invariant: next == *next_ref */					      \
    while (next !=0){							      \
	if (Equal(elem, next->elem)) {					      \
	    /* Delete it */						      \
	    *next_ref = next->next;					      \
	    delete next;						      \
	    num_entries--;						      \
	    break;							      \
	}								      \
	next_ref = &(next->next);					      \
	next = *next_ref;						      \
    }									      \
}									      \
									      \
_HSI(SetType) SetType::elements() const {				      \
    _HSI(SetType) iter;							      \
									      \
    iter.set = 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 _HSI(SetType)::valid() {						      \
    return (entry != 0);						      \
}									      \
									      \
void _HSI(SetType)::next() {						      \
    entry = entry->next;						      \
    while ((entry == 0) && (next_bucket < set->num_buckets)) {		      \
	entry = set->buckets[next_bucket];				      \
	next_bucket++;							      \
    }									      \
}									      \
									      \
ElemType _HSI(SetType)::value() {					      \
    return entry->elem;							      \
}									      \
									      \
_HSE(SetType)* SetType::find_entry(ElemType elem) const {		      \
    unsigned int b = Hasher(elem) % num_buckets;			      \
    _HSE(SetType)* index = buckets[b];					      \
    while (index != 0) {						      \
	if (Equal(index->elem, elem)) {					      \
	    return index;						      \
	}								      \
	index = index->next;						      \
    }									      \
    return 0;								      \
}									      \

#endif /* _HASHSET_H */
