//=============================================================================
// dictionary.h - a simple hashtable class
//=============================================================================

//-----------------------------------------------------------------------------
// Association
//-----------------------------------------------------------------------------
struct Association
{
  void* key;
  void* value;
};

//-----------------------------------------------------------------------------
// Dictionary
//
//   Abstract class for dictionaries. The class must be inherited
//   to use it. Implement the following methods:
//     hash()   returns the hash code of a key
//     match()  compare two keys
//
//   Instance variables:
//     associations    buffer to all associations
//     size            total number of slots
//     tally           number of used slots
//     collisions      maximum of collisions occured
//
//     collisions is an upper bound: after removing an association the
//     value may be wrong
//
//-----------------------------------------------------------------------------
class Dictionary
{
private:
  Association*  associations;
  int           size;
  int           tally;
  int           references;
  int           collisions;

  int  slot(void* k) const { return ((unsigned int)hash(k)) % size; }

  void increaseTally();
  void decreaseTally();
  void resize(int);
  void fillUp(int);

public:
  Dictionary();
  ~Dictionary();

  void*      value(void* key) const;
  void*      add(void* key, void* value);
  void       remove(void* key);

  bool isEmpty () const;
  bool notEmpty() const;

  // Direct accessors
  // ----------------
  // made public for simple iterators
  void* key      (int i) const;
  void* value    (int i) const;
  bool  isEmpty  (int i) const;
  bool  notEmpty (int i) const;

  int   getSize  () const;

  void setKey   (int i, void* k);
  void setValue (int i, void* v);
  void clear    (int i);

  // Methods to implement
  // --------------------
  virtual int  hash(void* k) const = 0;
  virtual bool match(void* k1, void* k2) const = 0;
};