/*****************************  GeHashing.java  *******************************/

/** Implementation des Interface Menge
 *  durch ein geschlossenes Hashing mit einem Array von Objekten.
 */

public class GeHashing implements Menge {

  private final static byte LEER      = 0;  // noch nie belegt, jetzt frei
  private final static byte BELEGT    = 1;  // zur Zeit belegt
  private final static byte GELOESCHT = 2;  // war schon mal belegt, jetzt frei

  private Comparable[] inhalt;              // Array fuer Elemente
  private byte[]       zustand;             // Array fuer Zustaende

  public GeHashing(int N) {                 // Konstruktor fuer Hashtabelle
    inhalt  = new Comparable[N];            // besorge Platz fuer N Objekte
    zustand = new byte[N];                  // besorge Platz fuer N Zustaende
    for (int i=0; i<N; i++)                 // setze alle Zustaende
        zustand[i]=LEER;                    // auf LEER 
  }

  private int hash(Comparable x) {          // berechne Hash-Wert fuer x
    int i, summe = 0;                       // Hilfsvariablen
    String s = x.toString();                // berechne Stringdarstellung von x
    for (i=0; i<s.length(); i++)            // durchlaufe den String
        summe += s.charAt(i);               // und addiere alle Zeichen
    return summe % inhalt.length;           // liefere summe mod Tabellenlaenge 
  }



  public String toString() {                // liefert den Aufbau der Tabelle
    String s = new String();                // als String zurueck
    for (int i=0; i< inhalt.length; i++){   // durchlaufe Tabelle
      s += i;                               // notiere Index
      switch(zustand[i]) {                  // je nach eingetragenem Zustand
        case LEER:      s+="  L  "; break;  // notiere L 
        case BELEGT:    s+="  B  "; break;  // notiere B
        case GELOESCHT: s+="  G  "; break;  // notiere G
      }
      if (zustand[i]==BELEGT) s+=inhalt[i]; // notiere Objektdarstellung
      s += '\n';                            // notiere Zeilenvorschub
    }    
    return s;                               // liefere Stringdarstellung
  }
 
  // Unter Verwendung der Hashfunktion hash wird eine Hilfsmethode
  // implementiert, welche das Objekt in der Tabelle sucht und durch
  // - einen positiven Rueckgabewert den Index angibt, wo es gefunden wurde
  // - einen negativen Rueckgabewert den bitweise negierten Index angibt,
  //   wo es eingefuegt werden koennte (d.h., es wurde nicht gefunden).
  // Implementiert ist ein quadratisches Sondieren: Die Sondierschrittweite d
  // wird mit eins initialisiert und in jedem Sondierschritt um zwei erhoeht.
  
  private int find(Comparable x) {          // sucht x in der Hashtabelle
                                            // liefert Position, falls gefunden
                                            // oder negierte Pos. zum Einfuegen 
    int versuche          = 0;              // Zahl der Sondierungen
    int d                 = 1;              // Sondierschrittweite
    boolean loch_gefunden = false;          // true, falls Loch gefunden    
    int lochindex         = 0;              // Vorschlag zum spaeteren Einfuegen
    int index             = hash(x);        // berechne Hash-Wert

    while (!(((zustand[index] == BELEGT)    // Abbruch, falls 
     && (inhalt[index].compareTo(x) == 0))  // Element gefunden
     || (zustand[index] == LEER)            // oder leeres Feld gefunden
     || (versuche == inhalt.length))) {     // oder Zahl der Versuche zu gross

                                            // nur wegen spaeterem insert:
        if ((!loch_gefunden) &&             // falls noch kein Loch gefunden 
            (zustand[index] == GELOESCHT)){ // und GELOESCHT vorliegt,
            loch_gefunden = true;           // merke, dass Loch gefunden
            lochindex     = index;          // und seine Position
        }
       index = (index + d) % inhalt.length; // mache einen Sondierschritt 
       d    += 2;                           // erhoehe Schrittweite
       versuche++;                          // erhoehe Zahl der Versuche
    }
    if ((zustand[index]==BELEGT) &&         // falls belegtes Feld
        (inhalt[index].compareTo(x) == 0))  // und x gefunden
        return index;                       // liefere Position zurueck
    if (loch_gefunden) return ~lochindex;   // liefere Loch (bitweise negiert)
                  else return ~index;       // sonst letzte Einfuegeposition
  }                                         // als negierte Zahl zurueck

  // Unter Verwendung der Hilfsmethode find
  // werden die oeffentlichen Methoden lookup, insert, delete implementiert


  public Comparable lookup(Comparable x) {  // versucht, x nachzuschlagen 
    int pos = find(x);                      // versuche, x zu finden
    if (pos >= 0) return inhalt[pos];       // falls gefunden: liefere Objekt,
           else return null;                // sonst melde Misserfolg
  }


  public boolean insert(Comparable x) {     // versucht, x einzufuegen 
    int pos = find(x);                      // versuche, x zu finden
    if ((pos < 0) &&                        // falls x nicht gefunden
        (zustand[~pos]!=BELEGT)) {          // und falls Platz vorhanden:
       inhalt[~pos] = x;                    // fuege x ein
       zustand[~pos]= BELEGT;               // setze Zustand auf BELEGT
       return true;                         // melde Erfolg
    } else return false;                    // melde Misserfolg
  }


  public boolean delete(Comparable x) {     // versucht, x zu loeschen 
    int pos = find(x);                      // versuche, x zu finden
    if (pos >= 0) {                         // falls x gefunden:
        zustand[pos] = GELOESCHT;           // setze Zustand auf GELOESCHT
        inhalt[pos]  = null;                // gib Verweis auf Objekt frei
        return true;                        // melde Erfolg
    } else return false;                    // melde Misserfolg
  }
}