Objektorientierte Programmierung
LVA 185.162, VL 2.0, 2007 W

5. Übungsaufgabe

Themen:

Generizität und Iteratoren

Termine:

Ausgabe:	22.11.2007
reguläre Abgabe:	29.11.2007, 12:45 Uhr
nachträgliche Abgabe:	06.12.2007, 12:45 Uhr

Abgabeverzeichnis:

Aufgabe5

Programmaufruf:

java Test

Grundlage:

Skriptum bis Seite 97 und die Seiten 103 bis 107.

Aufgabe

Welche Aufgabe zu lösen ist:

Entwickeln Sie Java-Klassen entsprechend folgender Beschreibungen:

Jede Instanz der Klasse Tree soll einen Baum (Datenstruktur) mit eindeutig bestimmter Wurzel darstellen. Von jedem Knoten im Baum können beliebig viele Kanten ausgehen. Sowohl Knoten als auch Kanten tragen Bezeichnungen. Über Typparameter ist für Knoten und Kanten getrennt voneinander festlegbar, welche Typen die Bezeichnungen haben. Die Bezeichnungen brauchen nicht eindeutig zu sein, das heißt, es kann mehrere Knoten bzw. Kanten mit derselben Bezeichnung geben. Jeder Baum enthält mindestens einen Knoten (den Wurzelknoten), der im Konstruktor festgelegt wird. Methoden für folgende Aufgaben werden benötigt:

• Abfrage der Bezeichnung des Wurzelknotens.
• Erzeugen eines Iterators, der alle Bezeichner von vom Wurzelknoten ausgehenden Kanten in fixer Reihenfolge (siehe unten) liefert. Neben den üblichen Methoden des Iterators (next und hasNext) hat dieser Iterator eine Methode insert zum Einfügen einer neuen Kante und eines neuen Knotens (deren Bezeichnungen als Argumente übergeben werden). Die neue Kante zeigt auf den neuen Knoten und ist unmittelbar nach der aktuellen Position des Iterators einzufügen, so dass der nächste Aufruf von next den Bezeichner der neuen Kante liefert. Wurde next noch nie aufgerufen, dann werden Kante und Knoten ganz am Anfang eingefügt. Liefert hasNext als Ergebnis false, dann werden sie ganz am Ende eingefügt. Der Iterator findet die Kanten immer an derselben Position, an der sie eingefügt wurden.
• Erzeugen eines Iterators, der alle über die vom Wurzelknoten ausgehenden Kanten erreichbaren Teilbäume des Baumes in derselben Reihenfolge wie der Iterator über den Kanten liefert. Teilbäume sind Bäume, die durch Entfernen des Wurzelknotens und der vom Wurzelknoten ausgehenden Kanten entstehen. Wenn der Iterator über Kanten beim n-ten Zugriff die Bezeichnung der Kante x liefert, soll der Iterator über Teilbäumen beim n-ten Zugriff den über x erreichbaren Teilbaum liefern. Das Einfügen neuer Knoten und Kanten (siehe oben) wirkt sich auch unmittelbar auf die Reihenfolge der Teilbäume aus, solange der Iterator vor der Stelle der Einfügung steht. Wird ein Teilbaum (durch Einfügen einer Kante und eines Knotens) verändert, so wird auf gleiche Weise der Baum, der diesen Teilbaum enthält, verändert.

Außer diesen Methoden soll es keinerlei Möglichkeit geben, auf interne Details von Bäumen oder Teilbäumen zuzugreifen, auch nicht von Unterklassen aus oder zu Testzwecken.

Die Klasse ISTree soll ein Untertyp von Tree sein, wobei Bezeichnungen von Kanten vom Typ String und Bezeichnungen von Knoten vom Typ Integer sind. Neben den Methoden von Tree soll eine Methode unterstützt werden, die als Ergebnis die Summe (vom Typ int) der Bezeichnungen aller Knoten zurückgibt, auf die eine Kante mit einer als Argument gegebenen Bezeichnung zeigt. Zwei Instanzen x und y von String werden als gleich betrachtet, wenn x.equals(y) als Ergebnis true liefert. Iteratoren über Knotenbezeichnungen liefern Instanzen von Tree als Teilbäume, nicht von ISTree.

CTree soll Tree um eine Methode connected (mit zwei Argumenten vom Typ der Bezeichnungen von Knoten) erweitern, die als Ergebnis true liefert, wenn es im Baum zwei verschiedene Knoten A und B mit folgenden Eigenschaften gibt, sonst false:

• Das erste Argument von connected ist identisch mit der Bezeichnung von A.
• Das zweite Argument von connected ist identisch mit der Bezeichnung von B.
• Es gibt einen Pfad von A nach B. Ein Pfad von einem Knoten X nach B existiert, wenn über eine ausgehende Kante von X ein Knoten Y erreichbar ist und entweder Y gleich B ist oder es einen Pfad von Y nach B gibt.

Teilbäume von Instanzen von CTree sind stets vom Typ Tree und unterstützen connected nicht.

Die Klasse Test soll die wichtigsten Normal- und Grenzfälle (nicht interaktiv) überprüfen und die Ergebnisse in allgemein verständlicher Form in der Standardausgabe darstellen. Unter anderem soll Test eine generische Methode copy bereitstellen, die von einem beliebigen Baum (vom Typ Tree, kann tatsächlich auch von einem Untertyp davon sein, wobei Typen von Knoten- und Kantenbezeichnungen durch Typparameter festgelegt sind) eine Kopie erstellt. Das Ergebnis ist jedenfalls vom Typ Tree (und kein Untertyp davon). Zur Analyse des zu kopierenden Baums und zum Aufbau des neuen Baums sollen ausschließlich die oben beschriebenen Methoden von Tree verwendet werden; die Verwendung von clone ist verboten. Auch copy ist zu testen.

Wie die Aufgabe zu lösen ist:

Achten Sie auf einen sinnvollen Umgang mit Generizität und Iteratoren. Vermeiden Sie die Verwendung von gebundener Generizität (noch nicht gelernt). Verwenden Sie keine vorgefertigten Container (wie List, Set, Vector, etc.) sondern schreiben Sie entsprechende Klassen selbst. Verwenden Sie auch keine vorgefertigten Iteratoren (eventuell abgesehen vom Interface Iterator) sondern schreiben Sie diese selbst. Vermeiden Sie unnötigen Code; insbesondere soll Funktionalität, die in einer Oberklasse bereits (in ähnlicher Form) vorhanden ist, in der Unterklasse nicht nochmals implementiert werden. Schreiben Sie alle nötigen Zusicherungen. Vermeiden Sie Kommentare, die keine Zusicherungen darstellen, sowie unklare Zusicherungen. Achten Sie auf die Sichtbarkeit, wobei angenommen wird, dass alle in der Aufgabenstellung angeführten Methoden von außen zugegreifbar sein sollen. Benennen Sie Ihre Klassen so, wie sie in der Aufgabenstellung heißen. Überlegen Sie, ob und wie Sie geschachtelte Klassen in dieser Aufgabe einsetzen können. Vermeiden Sie die Verwendung von Paketen.

Hinweise zur Beurteilung:

Der Schwerpunkt bei der Beurteilung liegt auf Generizität und Iteratoren (so weit wie in der Vorlesung bereits behandelt). Starke Punkteabzüge gibt es für vermeidbare Warnungen des Compilers, die mit (der falschen Verwendung von) Generizität in Zusammenhang stehen, vor allem für die Verwendung von raw types bzw. type erasures. Entsprechende Warnungen haben ihre Ursache hauptsächlich in vergessenen Typangaben bei Verwendung generischer Typen. Punkteabzüge gibt es auch für unnötigen (oder unnötig komplexen) Code, mangelhafte Zusicherungen, inkorrekte Untertypbeziehungen, schlechte Verwendung von Sichtbarkeit, sowie fehlende oder nicht der Aufgabenstellung entsprechende Funktionalität.

Was im Hinblick auf die Abgabe zu beachten ist:

Schreiben Sie Ihre Lösung in das bereits existierende Verzeichnis Gruppe/Aufgabe5. Das Programm soll von diesem Verzeichnis aus durch java Test aufrufbar sein. Schreiben Sie (abgesehen von geschachtelten Klassen) nicht mehr als eine Klasse in jede Datei. Das Verzeichnis soll zu den Abgabezeitpunkten alle .java-Dateien enthalten, die Sie für Ihre Lösung benötigen. Bitte entfernen Sie alle .java-Dateien, die nicht zur Abgabe gehören. Dateien mit anderen Endungen werden bei der Beurteilung nicht berücksichtigt. Verzichten Sie auf die Verwendung von Verzeichnissen innerhalb von Gruppe/Aufgabe5. Stellen Sie sicher, dass ein Aufruf von javac *.java in Gruppe/Aufgabe5 keine Fehlermeldungen und keine Warnungen, die mit Generizität in Zusammenhang stehen, liefert.