// Klassendeklaration
 
template <class KeyType, class ValueType>
class DictionaryAsHashTable : public Dictionary<KeyType,ValueType>
{
public:
    DictionaryAsHashTable();
    DictionaryAsHashTable(int n = 100); // Größe des Feldes
    ~DictionaryAsHashTable ();
    bool search(const KeyType& k);
    bool insert(const KeyType& k);
    bool remove(const KeyType& k);
    int getNumber() { return size; }
    ValueType& get();
    void print();
 
 
private:
    int h( const string& k );
    int h( const int k );
    struct Entry // Struktur eines Eintrages
    {
        KeyType key;
        ValueType *value;
    };
 
    struct HashEntry // Verkettete Liste aller Einträge
    {
        Entry *entry;
        HashEntry *next;
    };
 
    HashEntry** a;
    ValueType *selected;	// Zeiger auf den Indexwert
    int size;		// Arraygroesse
};
 

// Konstruktor
 
template <class KeyType, class ValueType>
DictionaryAsHashTable<KeyType, ValueType>::DictionaryAsHashTable(int n)
{
    size = n;
    a = new HashEntry*[n];
 
    for ( int i=0; i<n; i++ )
        a[i]=0;
 
    selected = NULL;	//Setzt den Indexwert auf das gefundene/zuletzt eingefuegte Element
}
 

// Destruktor
 
template <class KeyType, class ValueType>
DictionaryAsHashTable<KeyType, ValueType>::~DictionaryAsHashTable( )
{
    for ( int i=0; i<size; i++ )
        if ( a[i] != 0)
        {
            HashEntry *tmp = a[i]; // tmp auf aktuelle Arrayposition setzen
            while ( tmp->next != 0 ) // Durchlaufe alle Knoten bis zum Ende
            {
                HashEntry *hashEntry = NULL;
 
                hashEntry = tmp->next; // HashEntry mit Entry verknüpfen
                tmp = tmp->next; // Array mit HashEntry verknüpfen
                delete hashEntry;
            }
 
            delete tmp;
        }
}
 

/**
* @desc Berechnet den Hash-Schlüssel anhand eines Strings und der Hashtabellengroesse this->size
* @param string k : String für welchen ein Hash-Schlüssel berechnet werden soll.
*/
template <class KeyType, class ValueType>
int DictionaryAsHashTable<KeyType, ValueType>::h( const string& k )
{
    int adr = 0;
    for ( unsigned int i=0; i<k.size(); i++ )
        adr = (adr*128 + k[i]) % size;
 
    return adr;
}
 

/**
* @desc Berechnet den Hash-Schlüssel anhand eines Integers und der Hashtabellengroesse this->size
* @param string k : String für welchen ein Hash-Schlüssel berechnet werden soll.
*/
template <class KeyType, class ValueType>
int DictionaryAsHashTable<KeyType, ValueType>::h( const int k )
{
    return k%size;
}
 

/**
* @desc Sucht Schlüssel k und speichert Wert in selected ab
*	Gibt true zurück, falls Schlüssel k gefunden wird, und sonst false.
* @param KeyType k : Deutscher Name
*/
template <class KeyType, class ValueType>
bool DictionaryAsHashTable<KeyType, ValueType>::search(const KeyType& k)
{
    int adr = h(k); // Adresse berechnen und speichern
 
    if ( adr != 0 )
    {
        HashEntry *tmp = a[adr]; // Adresse des Datensatzes ermitteln
        while ( tmp != 0 ) // Alle Einträge in der verketteten Liste durchlaufen
            if ( tmp->entry->key == k ) // Wenn Eintrag gefunden, dann abspeichern
            {
                selected = tmp->entry->value; // Adresse abspeichern
                return true;
            }
            else
                tmp = tmp->next; // zum nächsten Knoten
    }
 
 
    selected = NULL;
    return false;
}
 

/**
* @desc Fügt neuen Schlüssel k mit Wert v ein. Falls Schlüssel bereits vorhanden ist,
*	wird nicht eingefügt und false zurückgeliefert, sonst true.
* @param KeyType k : Deutscher Name
*/
template <class KeyType, class ValueType>
bool DictionaryAsHashTable<KeyType, ValueType>::insert(const KeyType& k)
{
    if ( !search(k) ) // Wenn Key nicht gefunden wurde
    {
        // Speicher für Entry und HashEntry allokieren und initialisieren
        HashEntry *tmp = a[h(k)];
        HashEntry *hashEntry = new HashEntry;
        Entry *entry = new Entry;
        entry->value = new ValueType;
        hashEntry->next = 0;
 
        if ( tmp == 0 ) // Wenn noch keine verkettete Liste existiert, erstelle diese
        {
            entry->key = k; // Entry mit Daten füllen
            hashEntry->entry = entry; // HashEntry mit Entry verknüpfen
            a[h(k)] = hashEntry; // Array mit HashEntry verknüpfen
 
            selected = entry->value;
            return true; // Beende nach Erstellung
        }
        else // Wenn verkettete Liste existiert, füge Eintrag dort hinzu
        {
            while ( tmp->next != 0 ) // Suche Ende der verketteten Liste
                tmp = tmp->next;
 
            // ValueType in verketteter Liste hinzufügen
            entry->key = k;
            hashEntry->entry = entry;
            tmp->next = hashEntry;
 
            selected = entry->value;
            return true;
        }
    }
 
 
    selected = NULL;
    return false;
}
 

/**
* @desc Löscht Schlüssel k. Falls Schlüssel gelöscht werden konnte, wird true
*	zurückgeliefert und sonst false (d.h. Schlüssel war nicht vorhanden).tmpHashEntry
* @param KeyType k : Deutscher Name
*/
template <class KeyType, class ValueType>
bool DictionaryAsHashTable<KeyType, ValueType>::remove(const KeyType& k)
{
    if ( search(k) ) // Wenn Key gefunden wurde
    {
        HashEntry *tmp = a[h(k)]; // tmp auf aktuelle Arrayposition setzen
        HashEntry *hashEntry = NULL; // Knoten der später mit ELementposition verknüpft und gelöscht wird
 
        if ( tmp->entry->key == k ) // Wenn erster Knoten der zu löschende Eintrag ist
        {
            hashEntry = tmp; // HashEntry mit Entry verknüpfen
            a[h(k)] = hashEntry->next; // Array mit HashEntry verknüpfen
 
            delete hashEntry;
            return true; // Beende nach Erstellung
        }
        else // Wenn der zu löschende Eintrag ist in einem unterknoten ist
        {
            while ( tmp->next->entry->key != k ) // Suche solange bis zu löschender Knoten gefunden wurde
                tmp = tmp->next;
 
            hashEntry = tmp->next; // HashEntry mit Entry verknüpfen
            tmp->next = hashEntry->next; // Array mit HashEntry verknüpfen
 
            delete hashEntry;
            return true; // Beende nach Erstellung
        }
    }
 
 
    selected = NULL;
    return false;
}
 

/**
* @desc liefert eine Referenz auf den ValueType des zugehoerigen
*	zuletzt gesuchten / eingeuegten Keytypes.
* @return Gibt eine Referenz mit Wert 0 zurück, wenn keine Daten vorhanden sind
*/
template <class KeyType, class ValueType>
ValueType& DictionaryAsHashTable<KeyType, ValueType>::get()
{
    //if(selected != NULL)
    return *selected;
}
 

/**
* @desc Listet alle ELemente auf.
*/
template <class KeyType, class ValueType>
void DictionaryAsHashTable<KeyType, ValueType>::print()
{
    // Alle Eintraege ausgeben
    cout << "\n\nKey\t\t\tValue" << endl;
    cout << "-------\t\t\t--------" << endl;
    for (int i = 0; i < size-1; i++)
        if ( a[i] != 0 ) // Wenn Element an Position verfügbar
            for (HashEntry *tmp=a[i]; tmp!=0; tmp=tmp->next)
                cout << tmp->entry->key << "\t\t\t" << *tmp->entry->value << endl;
 
}