/**
 * AlgoDat SoSe2000, Aufgabe 61
 * Patricia-Baum
 * Teil b: Klasse fuer die Knoten des Baums
 * Teil c: Pseudocode fuer das Suchen im Patriciabaum
 * Teil d: Pseudocode fuer das Einfuegen im Patriciabaum
 *
 * @author Christian Semrau
 * <a href="mailto:gsemrau@cs.uni-magdeburg.de">gsemrau@cs.uni-magdeburg.de</a>
 */

// Teil b: Klasse fuer die Knoten des Baums

class PatriciaNode{
    private String teilschluessel;
    private boolean end;
    private PatriciaNode[] knoten;
    private final String alphabet;
    // final = nachtraeglich nicht mehr veraenderbar

// Konstruiert einen neuen Knoten mit dem Teilschluessel ts,
// mit Endemarkierung (e==true) oder ohne (e==false), mit dem
// Alphabet alph
    public PatriciaNode(String ts, boolean e, String alph){
        teilschluessel = ts;
        end = e;
        alphabet = alph;
        knoten = new PatriciaNode[alphabet.length];
        // hat anfangs keine Unterknoten
    }

// Liefert den Index der Kante, die zum Zeichen c gehoert
    private abstract int indexOf(char c)
    throws IllegalArgumentException{
        int res = alphabet.indexOf(c);
        if (res<0)
            throw new IllegalArgumentException(c+" nicht im Alphabet");
        else
            return res;
    }

// Liefert den Unterknoten, der zum Zeichen c gehoert
    public void getLink(char c)
    throws IllegalArgumentException{
        return knoten[indexOf(c)];
    }

// Liefert den Teilschluessel des Knotens
    public String getKey(){
        return teilschluessel;
    }

// Setzt den Unterknoten, der zum Zeichen c gehoert
    public void setLink(char c, PatriciaNode pn)
    throws IllegalArgumentException{
        knoten[indexOf(c)] = pn;
    }

// Entfernt die ersten l Zeichen des Teilschluessels
    public void truncKeyBegin(int l){
        teilschluessel = teilschluessel.substring(l);
    }

/*
es gehoeren noch ein paar andere Zugriffsfunktionen fuer die Attribute
dazu, aber die lass ich an dieser Stelle mal weg,
man kann sie bei Bedarf leicht selbst schreiben (hoffentlich)
*/

}

// Die beiden folgenden Codefragmente sind Funktionen einer Klasse
// PatriciaTree, die hier nicht deklariert ist!
//
// Ein komplett leerer Patricia-Baum enthaelt nur den obersten Knoten,
// der die leere Zeichenkette als Teilschluessel hat, eine nicht gesetzte
// Ende-Markierung, und keine Unterknoten, dadurch ist zwar ein Knoten im
// Baum, aber kein Schluessel. Im Gegensatz zum Binaerbaum, wo der leere
// Baum nicht mal einen Wurzelknoten enthaelt.

// Teil c: Suchen im Patriciabaum

/*
boolean suche(String Suchbegriff)

Setze den aktuellen Knoten aK auf den obersten Knoten des Baums

Endlosschleife Anfang
// die Schleife wird (mal wieder) durch return beendet
  ermittle die Laenge len des Teilschluessels des aK
  Wenn die ersten len Zeichen des Suchbegriffs mit dem Teilschluessel
    des aK uebereinstimmen,
  // "die ersten len Zeichen" beinhaltet auch den Fall, dass der Suchbegriff
  // weniger als len Zeichen enthaelt, es wird dann der (kuerzere) gesamte
  // Suchbegriff verglichen
  dann
    Wenn der Suchbegriff len Zeichen lang ist,
    dann
      Wenn der aK die Endemarkierung hat,
      dann
        Verlasse die Funktion, Ergebnis: GEFUNDEN
      sonst
        Verlasse die Funktion, Ergebnis: NICHT GEFUNDEN
    sonst
      Entferne die ersten len Zeichen aus dem Suchbegriff
      Wenn der Unterknoten des aK, der zum ersten Zeichen des
        Suchbegriffs gehoert (dieser Knoten sei k1), nicht existiert,
      dann
        Verlasse die Funktion, Ergebnis: NICHT GEFUNDEN
      sonst
        Setze den aK auf den gerade ermittelten Unterknoten k1
  sonst
    Verlasse die Funktion, Ergebnis: NICHT GEFUNDEN
Endlosschleife Ende

*/


// Teil d: Einfuegen im Patriciabaum

/*
Erfordert, dass ein Knoten seinen uebergeordneten Knoten kennt.
Alternativ muss eine Referenz auf den Vorgaenger mitgeschleppt werden.

void insert(String Suchbegriff)

Setze den aktuellen Knoten aK auf den obersten Knoten des Baums

Endlosschleife Anfang
  ermittle die Laenge des Teilschluessels  des aK, nenne sie "len"
  Wenn die ersten len Zeichen des Suchbegriffs mit dem Teilschluessel
    uebereinstimmen,
  // "die ersten len Zeichen" beinhaltet auch den Fall, dass der Suchbegriff
  // weniger als len Zeichen enthaelt, es wird dann der (kuerzere) gesamte
  // Suchbegriff verglichen
  dann
    Wenn der Suchbegriff len Zeichen lang ist,
    dann
      Setze die Ende-Markierung
      Verlasse die Funktion
    sonst
      Entferne die ersten len Zeichen aus dem Suchbegriff
      Wenn der Unterknoten im aK, der zum ersten Zeichen des Suchbegriffs
        gehoert (dieser Knoten sei k1), nicht existiert,
      dann
        Erzeuge einen weiteren Knoten k2, der den Suchbegriff enthaelt,
          mit Ende-Markierung
        haenge k2 an den aK an
        Verlasse die Funktion
      sonst
        Setze den aK auf den gerade ermittelten Unterknoten k1
  sonst
    Ermittle, wieviele Zeichen der Suchbegriff am Anfang mit dem Teilschluessel
      gemeinsam hat, diese Zahl sei "g"
    Erzeuge einen neuen Knoten k1, der als Schluessel die gemeinsamen Zeichen
      hat, ohne Ende-Markierung
    Setze den entsprechenden Unterknoten von k1 auf den aK
    Setze k1 als neuen Unterknoten im Vorgaenger des aK (ersetzt damit den
      Zeiger auf aK durch den Zeiger auf k1)
    Wenn der Suchbegriff laenger ist als g Zeichen,
    dann
      Erzeuge einen weiteren Knoten k2, der alle Zeichen nach dem g-ten vom
        Suchbegriff enthaelt, mit Ende-Markierung
      haenge k2 an k1 an
      Verlasse die Funktion
    sonst
      setze die Ende-Markierung im neuen Knoten
      Verlasse die Funktion
Endlosschleife Ende

*/