/****************************************************************************/
/*                                                                          */
/*  Copyright (c) 1994-2002                                                 */
/*  Jeremy Levitt                                                           */
/*                                                                          */
/****************************************************************************/

#ifndef _dict_h_
#define _dict_h_

#include <assert.h>
#include <iostream.h>

#ifndef NULL
#define NULL 0
#endif

typedef void *void_ptr;
template <class _Key, class _Data> class Dict;
template <class _Key, class _Data> class Dict_Entry;
template <class _Key, class _Data> class Dict_Ptr;

/****************************************************************************/
/*  class Dict_Entry                                                        */
/****************************************************************************/
template <class _Key, class _Data>
class Dict_Entry {
  friend class Dict<_Key, _Data>;
  friend class Dict_Ptr<_Key, _Data>;

private:
  _Key _key;
  _Data _data;
  Dict_Entry *_next;

  ~Dict_Entry() {}
  
public:
  _Key Key() const { return _key; }
  _Data& Data() { return _data; }
};


/****************************************************************************/
/*  class Dict                                                              */
/****************************************************************************/
template <class _Key, class _Data>
class Dict {
  friend class Dict_Ptr<_Key, _Data>;

private:
  Dict_Entry<_Key, _Data> *_list;
  int (*_cmpFunc)(_Key, _Key);     // return (k1<k2) ? -1 : ((k1==k2) 0 : 1)
  int _numEntries;

  Dict_Entry<_Key, _Data>** Find_Insert_Point(_Key&);
  void Copy(const Dict &rhs);
  void Destroy();
  
public:
  Dict(int (*cmpFunc)(_Key, _Key)) 
    : _list(NULL), _cmpFunc(cmpFunc), _numEntries(0) {}
  Dict(const Dict &dict) { Copy(dict); }
  ~Dict() { Destroy(); }

  int NumEntries() { return _numEntries; }
  int Insert(_Key key, _Data data);
  int Delete(_Key key);
  Dict& operator= (const Dict &rhs);
  _Data* Fetch(_Key key);
  _Data& operator[] (_Key key);
};


/****************************************************************************/
/*  class Dict_Ptr                                                          */
/****************************************************************************/
template <class _Key, class _Data>
class Dict_Ptr {
private:
  Dict_Entry<_Key, _Data> *_link;
  
public:
  Dict_Ptr(Dict<_Key, _Data> *dict) : _link(dict->_list) {}
  Dict_Entry<_Key, _Data>* operator-> () { return _link; }
  Dict_Entry<_Key, _Data>& operator* () { assert(_link);  return *_link; }
  operator void_ptr() const { return void_ptr(_link); }
  void operator++ () { if (_link!=NULL) _link=_link->_next; }
  void Reset(Dict<_Key, _Data> *dict) { _link=dict->_list; }
};   


/****************************************************************************/
/*    Dict::Destroy()                                                       */
/****************************************************************************/
template <class _Key, class _Data>
void Dict<_Key, _Data>::Destroy()
{
  Dict_Entry<_Key, _Data> *tmp = _list;
  while(tmp != NULL) {
    Dict_Entry<_Key, _Data> *next = tmp->_next;
    delete tmp;
    tmp = next;
  }
}


/****************************************************************************/
/*    Dict::Copy()                                                          */
/****************************************************************************/
template <class _Key, class _Data>
void Dict<_Key, _Data>::Copy(const Dict<_Key, _Data> &rhs)
{
  _cmpFunc = rhs._cmpFunc;
  _numEntries = rhs._numEntries;

  Dict_Entry<_Key, _Data> *tmp = rhs._list;
  Dict_Entry<_Key, _Data> **copy = &(_list = NULL);

  while(tmp != NULL) {
    *copy = new Dict_Entry<_Key, _Data>();
    (*copy)->_key = tmp->_key;
    (*copy)->_data = tmp->_data;
    (*copy)->_next = NULL;
    copy = &(*copy)->_next;
    tmp = tmp->_next;
  }
}


/****************************************************************************/
/*   Dict::operator=                                                        */
/****************************************************************************/
template <class _Key, class _Data>
Dict<_Key, _Data>& Dict<_Key, _Data>::operator=
(const Dict<_Key, _Data> &rhs)
{
  if (this != &rhs) {
    Destroy();
    Copy(rhs);
  }

  return *this;
}


/****************************************************************************/
/*    Dict::Find_Insert_Point()                                             */
/*                                                                          */
/*    Return a pointer-pointer to where the element should be inserted.     */
/****************************************************************************/
template <class _Key, class _Data>
Dict_Entry<_Key, _Data>** 
Dict<_Key, _Data>::Find_Insert_Point(_Key &key)
{
  Dict_Entry<_Key, _Data>** link = &_list;
  while (*link != NULL && ((*_cmpFunc)((*link)->_key, key))>0)
    link = &((*link)->_next);
  return link;
}


/****************************************************************************/
/*    Dict::Insert()                                                        */
/*                                                                          */
/*    Return 0 if the element was successfully inserted                     */
/*    Return 1 if insertion fails becuase an entry with the same key        */
/*    is already present                                                    */
/****************************************************************************/
template <class _Key, class _Data>
int Dict<_Key, _Data>::Insert(_Key key, _Data data)
{
  Dict_Entry<_Key, _Data>** link = Find_Insert_Point(key);

  if (*link && (*_cmpFunc)((*link)->_key, key)==0)
    return 1;
  
  _numEntries++;
  Dict_Entry<_Key, _Data>* dict_entry = new Dict_Entry<_Key, _Data>();
  dict_entry->_key = key;
  dict_entry->_data = data;
  dict_entry->_next = *link;
  *link = dict_entry;
  return 0;
}


/****************************************************************************/
/*    Dict::Delete()                                                        */
/*                                                                          */
/*    Return 0 if the element was successfully deleted and 1                */
/*    if the deletion failed because the entry could not be found.          */
/****************************************************************************/
template <class _Key, class _Data>
int Dict<_Key, _Data>::Delete(_Key key)
{
  Dict_Entry<_Key, _Data>** link = Find_Insert_Point(key);
  Dict_Entry<_Key, _Data>* tmp;
  
  if (!*link || (*_cmpFunc)((*link)->_key, key)!=0)
    return 1;
  
  _numEntries--;
  tmp = (*link);
  *link = (*link)->_next;
  delete tmp;
  return 0;
}


/****************************************************************************/
/*    Dict::Fetch()                                                         */
/*                                                                          */
/*    Return a pointer to the element if it was found, otherwise return     */
/*    a NULL pointer.                                                       */
/****************************************************************************/
template <class _Key, class _Data>
_Data* Dict<_Key, _Data>::Fetch(_Key key)
{
  Dict_Entry<_Key, _Data>** link = Find_Insert_Point(key);

  if (*link && (*_cmpFunc)((*link)->_key, key)==0)
    return &(*link)->Data();

  return (_Data *)NULL;
}


/****************************************************************************/
/*    Dict::operator[]                                                      */
/****************************************************************************/
template <class _Key, class _Data>
_Data& Dict<_Key, _Data>::operator[] (_Key key)
{
  _Data* result = Fetch(key);
  assert(result != NULL);
  return *result;
}


/****************************************************************************/
/*    Dict_Entry::operator<<                                                */
/****************************************************************************/
template <class _Key, class _Data>
ostream& operator<< (ostream &cout, Dict_Entry<_Key, _Data> &element)
{ 
  return cout << "key: \"" << element.Key() 
    << "\" data: " << element.Data() << '\n';
}


/****************************************************************************/
/*    Dict::operator<<                                                      */
/****************************************************************************/
template <class _Key, class _Data>
ostream& operator<< (ostream &cout, Dict<_Key, _Data> &dict)
{ 
  for (Dict_Ptr<_Key, _Data> ptr(&dict); ptr!=NULL; ++ptr) 
    cout << *ptr;
  return cout;
}

#endif /* _dict_h_ */