/**
* @file RList.java Listenverwaltung in Form einer <b>doppelt
* verketteten Ringliste</b>.
*
* <ul>
* <li> Jedes Listenelement m ist mit einer Referenz m.n auf den
* Nachfolger und einer Referenz m.p auf den Vorgänger versehen
* (sog. doppelte Verkettung).
* <li> Jede Liste enthält immer ein sog. <b>Ankerelement</b>.
* Dieses trägt niemals
* Nutzdaten (Komponente 'data' ist die null-Referenz).
* <li> Die leere Liste wird allein durch das Ankerelement
* repräsentiert, bei dem Nachfolger
* und Vorgänger auf sich selbst zeigen.
* <li> Bei einer nicht leeren Liste ist der Nachfolger
* des Ankerelementes der <b>Listenkopf</b>, d.h.
* das erste Nutzdaten tragende Element der Liste. Der
* Vorgänger des Ankerelementes ist das <b>letzte Element</b>
* der Liste. Umgekehrt hat der Listenkopf immer das
* Ankerelement als Vorgänger, und das letzte Element der
* Liste hat immer das Ankerelement als Nachfolger.
* </ul>
*
* Der Vorteil einer doppelt verketteten Ringliste besteht darin,
* dass Einfüge- und Löschoperationen, sowie Konkatenation
* ohne spezielle Fallunterscheidungen
* "Liste leer/nicht leer", "Löschen des letzten Elementes" etc.
* auskommen.
*/
/**
* Aus der Klasse Rlist werden einzelne Listenelemente instanziiert.
* Gleichzeitig repräsentiert das Ankerelement der Liste die
* gesamte Liste, denn vom Ankerelement aus lässt sich jedes
* Listenelement erreichen.
*/
class Rlist<T extends Comparable<T>> {
/** Jeder Listeneintrag hat ein Objekt vom Typ T als Nutzdaten.
* Das Ankerelement l der Liste ist durch die Bedingung
*
* <code>l.data == null</code>
*
* eindeutig gekennzeichnet.
*/
private T data;
/** Referenz auf das Nachfolger-Listenelement */
private Rlist<T> n;
/** Referenz auf das Vorgänger-Listenelement */
private Rlist<T> p;
/**
* Konstruktor Rlist() erzeugt eine neue leere
* Liste.
*
* @return Korrekt initialisiertes Ankerelement und damit
* eine leere Liste, die allein durch das Ankerelement
* repräsentiert ist.
*/
public Rlist(){
data = null;
n = this;
p = this;
}
/**
* Methode isEmpty() prüft, ob eine Liste
* leer ist.
*
*
* @return Gibt genau dann true zurück, wenn die Liste leer ist,
* d.h. wenn Vorgänger und Nachfolger wieder
* auf das Listenelement zeigen, auf dem empty()
* aufgerufen wird: Damit ist nachgewiesen, dass
* die Liste allein aus dem Ankerelement besteht.
*
*/
public boolean isEmpty() {
return ( n == this && p == this);
}
/**
* Methode size() berechnet die Länge
* einer Liste. Das Ankerelement wird
* dabei <b>nicht</b> mit gezählt.
*
* @return Anzahl der Listenelemente,
* abzüglich des Ankerelements.
*
* @note Wegen der Ringverkettung kann die Methode auf ein
* beliebiges Listenelement aufgerufen werden.
* Die Zählung endet, wenn bei der Traversion der List wieder
* das Ursprungselement erreicht wurde.
*
*/
public int size() {
int counter=0;
Rlist<T> e = this;
while(e.n != this){
counter++;
e = e.n;
}
return counter;
}
/**
* Methode clear() löscht den Listeninhalt, so dass
* die leere Liste zurück bleibt.
* Diese Methode darf nur auf das Ankerelement aufgerufen
* werden.
*
*/
public void clear() {
if(this.data==null){
n = this;
p = this;
}
}
/**
* Methode add() fügt ein neues Listenelement
* <b>hinter</b> dem Element ein, auf welchem
* die Methode aufgerufen wurde.
*
* @param d Einzufügendes Nutzdatenobjekt.
*
* @note Die Operation lässt sich ohne ein
* einziges if-statement realisieren.
*
* @note add(null) ist nicht zulässig,
* weil ansonsten das Ankerelement nicht eindeutig
* bestimmbar wäre.
*
*/
public void add(T d){
Rlist<T> m = new Rlist<T>();
m.data = d;
this.n = m;
m.p = this;
m.n = this.n;
this.n.p = m;
}
/**
* Methode insert() fügt ein neues Listenelement
* <b>vor</b> demjenigen ein, auf welchem die Operation
* aufgerufen wird.
*
* @param d Nutzdaten für das neu
* anzulegende Listenelement.
*
* @note Die Operation lässt sich ohne ein
* einziges if-statement realisieren.
*
* @note insert(null) ist nicht zulässig,
* weil ansonsten das Ankerelement nicht eindeutig
* bestimmbar wäre.
*/
public void insert(T d) {
Rlist<T> m = new Rlist<T>();
m.data = d;
this.p = m;
m.n = this;
m.p = this.p;
this.p.n = m;
}
/**
* Methode get() gibt den Inhalt (Nutzdaten) des
* Listenelements zurück, auf dem die Operation
* aufgerufen wird.
*
* @return Referenz auf die Nutzdaten (kann null sein,
* falls es sich um das Ankerelement handelt)
*
*/
public T get() {
return this.data;
}
/**
* Methode next() gibt die Referenz auf
* den Nachfolger des Listenelements l zurück,
* auf dem die Methode aufgerufen wird.
*
* @return Nachfolger l.n von l.
*
*/
public Rlist<T> next() {
return this.n;
}
/**
* Methode prev() gibt die Referenz auf
* den Vorgänger des Listenelements l zurück, auf dem
* die Methode aufgerufen wird.
*
* @return Vorgänger l.p von l.
*
*/
public Rlist<T> prev() {
return this.p;
}
/**
* Methode find() sucht nach einem Listenelement l,
* welches ein vorgegebenes Nutzdatenelement enthält,
* und gibt die Referenz auf dieses Element l zurück,
* falls vorhanden.
*
* @param d Nutzdatenobjekt, das unter den Listenelementen
* gesucht werden soll.
* @return null, falls d bei keinem Element als Nutzdaten
* eingetragen ist.
* @return Referenz auf das erste gefundene Listenelement sonst.
*
* @note Zum Vergleich der Nutzdaten wird die Methode equals()
* verwendet.
*/
public Rlist<T> find(T d) {
Rlist e = this;
do {
if ( e.data != null && e.data.equals(d) ) {
return e;
}
e = e.n;
} while ( e != this );
return null;
}
/**
* Methode remove() löscht das Listenelement aus der Liste,
* auf welchem die Methode aufgerufen wurde.
* Wirkungslos, wenn auf dem Ankerelement aufgerufen.
*
*
* @note Diese Operation benötigt eine if-Abfrage.
* Warum?
*/
public void remove() {
if(this.data != null){
this.p.n = this.n;
this.n.p = this.p;
}
}
/**
* Methode toString() gibt den Nutzdateninhalt der Liste als String zurück.
*
* Der String ist eine durch spitze Klammern eingefasste und durch Komma
* separierte Auflistung der einzelnen Nutzdaten in der entsprechenden
* Reihenfolge. Die einzelnen Elemente werden selbst wieder mit der
* Methode toString() formatiert.
* Beispielrückgabe: "<1, 2, 4, 3>"
*
* Diese Methode darf nur auf das Ankerelement aufgerufen
* werden.
*
* @return Der String.
*/
public String toString() {
String s = new String();
if(this.data == null){
for(Rlist e = this.n; e != this; e.next() ){
s += e.get().toString() + ",";
}
}
return "<" + s + ">";
}
/**
* Methode equals() vergleicht zwei Listen auf
* inhaltliche Gleichheit.
*
* Diese Methode darf nur auf das Ankerelement aufgerufen
* werden.
*
* @param o Referenz auf Ankerelement der zweiten Liste.
* Die Liste darf leer sein.
*
* @return false, wenn o nicht vom Typ RList ist.
* @return false, wenn die Listen unterschiedliche Länge haben.
* @return false, wenn sich die Listen bei mindestens einem Element
* in den Nutzdaten unterscheiden.
* @return true, falls die Listen dieselbe Länge, dieselben
* Nutzdaten und dieselbe Sortierung besitzen.
*/
public boolean equals(Object o) {
return false;
}
/**
* Methode addSorted() fügt das Element d in die Liste
* ein, so dass eine vorher aufsteigend sortierte Liste
* nach Ausführung von addSorted() immer noch aufsteigend
* sortiert ist.
* Diese Methode darf nur auf das Ankerelement aufgerufen
* werden.
*
* @param d Das einzufügende Element.
*
* @note Nutzdaten werden mit der Funktion compareTo() verglichen.
*/
public void addSorted(T d) {
}
/**
* Methode isSorted() überprüft, ob die Liste aufsteigend
* sortiert ist. Diese Methode darf nur auf das
* Ankerelement aufgerufen werden.
*
* @return Gibt genau dann true zurück, wenn die Liste sortiert ist.
*
* @note Nutzdaten werden mit der Funktion compareTo() verglichen.
*/
public boolean isSorted() {
return false;
}
}
)
