/*****************************  GeFpHashing.java  *****************************/
/* Autor: Joachim Wagner 
 * Datum: 08. Februar 1998 
 */ 

import AlgoTools.IO;    // fuer Fehlermeldungen IO.error(...);

/** Erweiterung der Klasse GeHashing um eine Sondierfunktion, die 
 *  die Existenz eines generierenden Element ausnutzt, wenn die Groesse 
 *  des Hash-Arrays eine Primzahl ist. 
 */ 

public class GeFpHashing implements Hashing { 

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

  private Compare comp;                     // Vergleichsobjekt
  private Object[] inhalt;                  // Array fuer Elemente
  private int[]    zustand;                 // Array fuer Zustaende

  private int generator;                    // fuer die Sondierung 

  public GeFpHashing(Compare comp, int N) { // Konstruktor fuer Hashtabelle 
    int groesse = (N>2)?N:3;                // vorsichtshalber mindestens 3 
    Liste s1 = null;                        // fuer die Primfaktorzerlegung 
    Liste s2;                               // von groesse und groesse-1 
    s2=primfaktoren(groesse); 
    while (!s2.empty()) {                   // groesse nicht prim 
      s1=s2;                                // Ergebnis merken 
      groesse++;                            // naechste Zahl testen 
      s2=primfaktoren(groesse); 
    } 
    if (s1==null)                           // Zerlegung von groesse-1 noch 
      s1=primfaktoren(groesse-1);           // unbekannt -> berechnen 
    //  
    this.comp = comp;                       // uebernimm Vergleichsobjekt 
    inhalt  = new Object[groesse];          // Platz fuer groesse Objekte 
    zustand = new int[groesse];             // Platz fuer groesse Zustaende 
    for (int i=0; i<groesse; i++)           // setze alle Zustaende 
        zustand[i]=LEER;                    // auf LEER 
    // einen Generator suchen 
    generator=1;                            // 0 ist nie Generator und 1 nur 
    boolean gefunden=false;                 // bei groesse = 2 (ausgeschl.)
    int produkt, exponent, faktor;          // Hilfsvariablen 
    while (!gefunden) {                     // Generator suchen 
      generator++;                          // naechsten Wert testen: 
    /* leider klatt dieser Algorithmus nicht so
      s1.reset();                           // vorne in der Listen starten 
      gefunden = true; 
      while (!s1.endpos()) {                // Primfaktoren durchlaufen 
        produkt=1; 
        faktor=((Integer)s1.elem()).intValue();
        s1.advance();
        exponent=(groesse-1)/faktor;        // (groesse-1)/i-ter Primfakt. 
        while (exponent-->1)
           produkt=(produkt*generator)%groesse;// generator hoch exponent 
        if (produkt==1) {                   // generator ist 
          gefunden=false;                   // kein Generator 
          break;                            // Test abbrechen 
        } 
      }
     */
      // ein einfacherer Test
      gefunden=true;            // Annahme
      produkt=generator; 
      zustand[0]=BELEGT;                    // 0 wird nicht generiert 
      for (int i=1; i<groesse; i++) { 
        zustand[produkt]=BELEGT;            // mit generator versuchen, 
        produkt=(produkt*generator)%groesse;// alle Felder zu belegen 
      } 
      for (int i=0; i<groesse; i++) {       // prüfen, ob alle Felder er- 
        if (zustand[i]!=BELEGT)             // reicht
          gefunden=false;
          // IO.error("in GeFpHashing: Generator " + generator + 
          //         " generiert nicht in F(" + groesse +")"); 
        zustand[i]=LEER;                    // Felder wiederherstellen 
      } 
    } 
  } 
  
  private int hash(Object 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;
  }

  // primfaktoren gibt eine Liste alle Primfaktoren von n 
  // Die Liste ist leer, wenn n Primzahl ist 

  private Liste primfaktoren(int n) { 
    Liste s = new Liste(); 
    int faktor=2; 
    int quadrat=4; 
    int zuwachs=5; 
    while (quadrat<=n) { 
      if ((n%faktor)==0) {                  // teilt faktor n ? 
        s.insert(new Integer(faktor));      // merken 
        while ((n%faktor)==0) n/=faktor;    // faktor herausziehen 
      } 
      faktor++; 
      quadrat+=zuwachs; 
      zuwachs+=2; 
    } 
    return s; 
  } 
  
  // 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). 
  // Benutzt wird das Sondieren der Methode sondiere 

  private int find(Object x) {              // sucht x in der Hashtabelle 
                                            // liefert Position, falls gefunden 
                                            // oder negierte Pos. zum Einfuegen 
    int versuche          = 0;              // Zahl der Sondierungen 
    boolean loch_gefunden = false;          // true, falls Loch gefunden 
    int lochindex         = 0;              // Vorschlag zum spaeteren Einfuegen 
    int index             = hash(x);        // berechne Hash-Wert 
    int basis_index       = index;          // zugleich Ausgangspunkt des Gen.
    int offset            = generator;      

    while (!(((zustand[index]==BELEGT)      // Abbruch, falls 
     && (comp.compare(x,inhalt[index])==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 = basis_index + offset;        // mache einen Sondierschritt
       index%= inhalt.length;
       offset= offset * generator;          // naechster offset
       offset%=inhalt.length;
       versuche++;                          // erhoehe Zahl der Versuche 
    } 

    if ((zustand[index]==BELEGT) &&         // falls belegtes Feld 
        (comp.compare(x,inhalt[index])==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 Object lookup(Object 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(Object 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(Object 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
  }
}