//=-- ChainedHashTable.h - Chained HashTable implementation ------------------=
//
//  This file defines the HashTable abstract data structure.  This structure
//    defines the buckets of the table using linked lists.
//
//  Could easily have data sorted by binary trees instead of linked lists...
//
//=---------------------------------------------------------------------------=
//
//  The file defines the following three classes:
//
//    ChHashTableData is used internally by the hashtable structure to hold 
//    the data.
//
//    ChainedHashTable is the main class that is typically used by other 
//    programmers.
//    
//    ChainedHashTableIterator defines an interator for stepping through a 
//    hashtable, in no defined order.
//
//=---------------------------------------------------------------------------=
//  This file is copyright (c) 1997-2000 Chris Lattner
//=---------------------------------------------------------------------------=

#ifndef CHAINEDHASHTABLE_H
#define CHAINEDHASHTABLE_H

#ifndef LINKEDLIST_H
#include "LinkedList.h"
#endif

// Predefine class prototype so that we can return classes of this type
//   and so that our "friend" statement works...
template <class Key, class Value> class MSAPI ChainedHashTableIterator;

// ChainedHashTable Class - Main hashtable class for the chained hash table
//   data structure
template <class Key, class Value>
class MSAPI ChainedHashTable : public Object {
  typedef DataPair<Key,Value> HTData;
  typedef ChainedHashTableIterator<Key,Value> Iterator;

  friend class ChainedHashTableIterator<Key,Value>;

public :
  // Constructor - Can optionally receive an initial size and a function to use
  //   to hash the data with
  ChainedHashTable(unsigned int (*HashFn)(const Key &,int) = 0, int Size = 373) {
    if (HashFn)
      Hash = HashFn;
    else
      Hash = Key::Hash;

    Table = 0;
    TableSize = NumElements = 0;
    ChangeTableSize(Size);
  }

  // Destructor.
  inline ~ChainedHashTable() {
    if (Table)
      delete [] Table;
  }

  // Clear - Deletes all stuff in hashtable...
  void Clear() {
    for (int i = 0; i < TableSize; i++) 
      Table[i].ClearList();
    NumElements = 0;
  }

  void Copy(const ChainedHashTable<Key,Value> &T) {
    if (Table)
      delete [] Table;
    TableSize = T.TableSize;
    NumElements = T.NumElements;

    Table = new LinkedList<HTData>[TableSize];

    for (int i = 0; i < TableSize; i++) 
      Table[i].CopyList(T.Table[i]);
  }
  
  // Get an iterator pointing to the first element of the hashtable.  This 
  //   iterator does not step through data in a sorted order.
  inline Iterator GetStartItr() const { 
    return Iterator(*this); 
  }

  // Remove - Remove a key from the hashtable.
  int Remove(const Key &K) {
    // This entry is just a placeholder and does not need to be initialized
    Value V = Value();   // Shut G++ up... :)
    if (Table[Hash(K, TableSize)].RemoveMatchingNodes(HTData(K,V)))
      return 1;
    NumElements--;

    if ((NumElements < TableSize/3) && (NumElements > 15))
      ChangeTableSize(NumElements);
    return 0;
  }

  // Set - Adds a value to the HashTable...
  void Set(const Key &K, const Value &V) { 
    int HashValue = Hash(K, TableSize);

    if (Table[HashValue].SearchList(HTData(K,V)))
      return;   // Already in!

    Table[HashValue].AddToHead(HTData(K, V));
    NumElements++;

    if (NumElements > TableSize*3/2)
      ChangeTableSize(NumElements*2+1);
  }

  // GetEntry - Returns the value associated with the specified key in V, 
  //   returns as success code as result.
  int GetEntry(const Key &K, Value &V) {
    LLLink<HTData> *L = Table[Hash(K, TableSize)].SearchList(HTData(K,V));
    if (!L) return 1;

    V = L->Data.S;
    return 0;
  }

  Value *GetEntry(const Key &K) const {
    // This entry is just a placeholder and does not need to be initialized
    Value V = Value();
    LLLink<HTData> *L = Table[Hash(K, TableSize)].SearchList(HTData(K,V));
    if (!L) return 0;

    return &L->Data.S;
  }

  // InTable - Returns true if the key is in the hashtable already...
  int InTable(const Key &K) const {
    // This entry is just a placeholder and does not need to be initialized
    Value V = Value();
    return Table[Hash(K, TableSize)].SearchList(HTData(K,V)) != 0;
  }

  // Print - Prints out the whole database, not neccesarily in a sorted order.
  ostream &print(ostream &o) const {
    for (int i = 0; i < TableSize; i++) 
      o << Table[i];
    return o;
  }

  // Returns whether or not the DB is empty...
  inline int IsEmpty() const {
    return NumElements == 0;
  }

  inline int GetNumElements() const {
    return NumElements;
  }

  // Make this structure Object compliant
  inline int Compare(const Object &) const { return 0; }


  void ChangeTableSize(int NewSize) {
    if ((NewSize & 1) == 0) NewSize++;   // At least make it odd...

    LinkedList<HTData> *NewTable = new LinkedList<HTData>[NewSize];
#if 0
    cout << "***Resizing a table from " << TableSize << " to " 
         << NewSize << ".\n";
#endif

    if (Table) {
      for (int i = 0; i < TableSize; i++) {
        LLLink<HTData> *L = Table[i].GetHead();
        while (L != 0) {
          NewTable[Hash(L->Data.P, NewSize)].AddToHead(L->Data);
          L = L->GetNext();
        }
      }
    
      delete [] Table;
    }

    Table = NewTable;    
    TableSize = NewSize;
  }

  void ConvertToList(LinkedList<HTData> &List) {
    Iterator I = GetStartItr();
    while (I) {
      List.AddToTail(*I);
      I++;  
    }
  }

private :
  // These two functions (copy constructor and op=) are declared, but not 
  // defined.  This makes it illegal to call either of them, and prevents
  // C++ from automatically creating them for me.
  //
  ChainedHashTable(const ChainedHashTable<Key,Value> &T);
  void operator= (const ChainedHashTable<Key,Value> &T);

  unsigned int (*Hash)(const Key &,int);

  LinkedList<HTData> *Table;
  int TableSize, NumElements;
};

// ChainedHashTableIterator defines an interator for stepping through a 
//   hashtable, in no defined order.
template <class Key, class Value>
class MSAPI ChainedHashTableIterator {
  typedef DataPair<Key,Value> HTData;
public :

  // Create an interator starting at the first element...
  //
  ChainedHashTableIterator<Key,Value>(const ChainedHashTable<Key,Value> &H) {
    HT = &H;
    TablePos = -1;
    Link = 0;
    operator++(0);
  }

  // Copy an iterator...
  ChainedHashTableIterator<Key,Value>(const ChainedHashTableIterator<Key,Value> &HTI) {
    HT = HTI.HT;
    TablePos = HTI.TablePos;
    Link = HTI.Link;
  }

  // Copy an iterator...
  ChainedHashTableIterator<Key,Value> &operator=(const ChainedHashTableIterator<Key,Value> &HTI) {
    HT = HTI.HT;
    TablePos = HTI.TablePos;
    Link = HTI.Link;
    return *this;
  }

  // Operator++ - Move to the next element of the table...
  //
  ChainedHashTableIterator operator++(int) {
    if (TablePos != -2) {
      if ((TablePos == -1) || (Link == 0) || (Link->GetNext() == 0)) {
        if (TablePos >= HT->TableSize-1) 
          TablePos = -2;
        else {
          while (HT->Table[++TablePos].GetHead() == 0) {
            if (TablePos >= HT->TableSize-1) {
              TablePos = -2;
              break;
            }
          }
        }
        
        if (TablePos >= 0) 
          Link = HT->Table[TablePos].GetHead();      
        
      } else {
        Link = Link->GetNext();
      }
    }

    return *this;
  }

  // Operator-- - Move to the previous element of the table...
  //
  ChainedHashTableIterator operator--(int) {
    if (TablePos != -1) {
      if ((TablePos == -2) || (Link->GetPrev() == 0)) {
        if (TablePos == -2) TablePos = HT->TableSize;
        if (TablePos == 0)
          TablePos--;
        else {
          while (HT->Table[--TablePos].GetTail() == 0) {
            if (TablePos == 0) {
              TablePos = -1;
              break;
            }
          }
        }
        
        if (TablePos > 0) 
          Link = HT->Table[TablePos].GetHead();      

      } else {
        Link = Link->GetPrev();
      }
    }

    return *this;
  }

  // Returns 0 at the end of the data structure...
  operator int() {
    return TablePos >= 0;
  }

  // operator* - "Dereference" Iterator
  DataPair<Key,Value> &operator*() {
    return Link->Data;
  }

  DataPair<Key,Value> operator*() const {
    return Link->Data;
  }

  const DataPair<Key,Value> *operator ->() const {
    return &Link->Data;
  }

  DataPair<Key,Value> *operator ->() {
    return &Link->Data;
  }

  inline Key &GetKey() {
    return Link->Data.P;
  }

  inline Value &GetValue() {
    return Link->Data.S;
  }

  inline void SetValue(Value &S) {
    Link->Data.S = S;
  }

private :
  int TablePos;
  LLLink<HTData> *Link;
  const ChainedHashTable<Key,Value> *HT;
};

#endif
