/*****************************  OfHashing.java  *******************************/

/** Implementation des Interface Menge durch Array von Listen                */

public class OfHashing implements Menge {

  private Liste[] b ;                       // Array fuer Listen 

  public OfHashing(int N) {                 // Konstruktor fuer Hashtabelle
    b  = new Liste[N];                      // besorge Platz fuer N Listen  
    for (int i=0; i<N; i++)                 // konstruiere pro Index
        b[i]=new VerweisListe();            // eine leere Liste 
  }

  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 % b.length;                // liefere summe mod Array-Laenge 
  }

  public String toString() {                // liefert den Aufbau der Tabelle
    String s = new String();                // als String zurueck
    for (int i=0; i< b.length; i++){        // durchlaufe Array 
      s += i + " :";                        // notiere Index
      b[i].reset();                         // gehe an Anfang der Liste
      while (!b[i].endpos()) {              // solange noch nicht am Ende
         s += " " + b[i].elem();            // notiere aktuelles Objekt 
         b[i].advance();                    // schreite in Liste voran
      }
      s += "\n";                            // notiere Zeilenvorschub
    } return s;                             // liefere Stringdarstellung
  }
 
  private boolean find(Liste l, Comparable x) { // sucht x in Liste
    l.reset();                              // gehe an den Anfang der Liste
    while (!l.endpos() &&                   // solange noch nicht am Ende
                                            // und Objekt noch nicht gefunden
           ((Comparable)l.elem()).compareTo(x) != 0) 
      l.advance();                          // schreite voran  
    return !l.endpos();                     // liefert true, falls gefunden
  }                                         // sonst false

  // Unter Verwendung der Hashfunktion hash und der Hilfsmethode find 
  // werden die oeffentlichen Methoden implementiert

  public Comparable lookup(Comparable x) {  // versucht x nachzuschlagen 
    int index = hash(x);                    // berechne Hash-Wert
    if (find(b[index],x))                   // falls in Liste gefunden,
        return (Comparable)b[index].elem(); // liefere Verweis auf Objekt
    else return null;                       // liefere Fehlanzeige
  }


  public boolean insert(Comparable x) {     // versucht x einzufuegen 
    int index = hash(x);                    // berechne Hash-Wert
    if (!find(b[index],x)){                 // falls nicht in Liste gefunden,
        b[index].insert(x);                 // fuege in Liste ein
        return true;                        // melde Erfolg
    } else return false;                    // melde Misserfolg
  }


  public boolean delete(Comparable x) {     // versucht x zu loeschen 
    int index = hash(x);                    // berechne Hash-Wert
    if (find(b[index],x)){                  // falls in Liste gefunden,
        b[index].delete();                  // entferne aus Liste
        return true;                        // melde Erfolg 
    } else return false;                    // melde Misserfolg
  }
}