Objektorientierte Programmierung
LVA 185.162, VL 2.0, 2010 W

5. Laborübungsaufgabe

Themen:

Generizität, Container und Iteratoren; nebenbei auch Sichtbarkeit, Zusicherungen und Ersetzbarkeit

Termine:

Ausgabe:	17.11.2010
reguläre Abgabe:	24.11.2010, 13:45 Uhr
nachträgliche Abgabe:	01.12.2010, 13:45 Uhr

Abgabeverzeichnis:

Gruppe/Aufgabe5

Programmaufruf:

java Test

Grundlage:

Skriptum bis Seite 115, Schwerpunkt auf Abschnitt 3.1

Aufgabe

Entwickeln Sie in Java generische Interfaces und Klassen wie folgt:

• Das Interface Iter enthält nur die Iterator-Methoden next und hasNext.
• In einigen Aggregaten sind Elemente mit weiteren Objekten assoziiert, die Instanzen eines durch einen zusätzlichen Typparameter bestimmten Typs sind. Das Interface AssocIter erweitert Iter um folgende Methoden:
  • assoc liefert ein Objekt zurück, das mit dem zuletzt von next zurückgegebenen Element assoziiert ist. Das Ergebnis ist null wenn noch kein Aufruf von next erfolgt ist oder der letzte Aufruf von next ebenso null geliefert hat.
  • insert kann ein neues Element (an nicht näher definierter Stelle und ohne Angabe assoziierter Objekte) in das Aggregat einfügen, über das iteriert wird. Das Ergebnis eines Aufrufs ist true wenn das Element tatsächlich eingefügt wurde, sonst false.
  • delete entfernt das zuletzt von next zurückgegebe Element aus dem Aggregat. Das Aggregat bleibt unverändert, wenn zuvor kein Element von next zurückgegeben wurde oder das Element schon entfernt ist. Das Ergebnis eines Aufrufs ist true wenn tatsächlich ein Element entfernt wurde, sonst false.
• Wir brauchen eine Art von Iteratoren, die uns direkten Zugriff auf einen Wert (eines durch einen weiteren Typparameter bestimmten Typs) des Aggregats gibt. Das Interface ValueIter erweitert AssocIter um diese Methoden:
  • set setzt den Wert im Aggregat auf den Parameter von set (unabhängig vom Zustand des Iterators).
  • get retourniert den Wert des Aggregats (unabhängig vom Zustand des Iterators).
• Eine Instanz der Klasse Tree stellt einen baumförmigen gerichteten Graphen dar, in dem von jedem Knoten beliebig viele, mit einem Label versehene Kanten ausgehen. Die Label auf Kanten sind sortierbar; das heißt, sie unterstützen eine Methode compareTo (wie auf Seite 103 des Skriptums). Knoten des Graphen werden nach außen nicht direkt, sondern nur durch Iteratoren über die von den Knoten ausgehenden Kanten dargestellt. Je zwei Iteratoren haben unterschiedliche Identitäten, auch wenn sie über die vom selben Knoten ausgehenden Kanten iterieren. Auf Tree werden folgende Methoden benötigt:
  • assoc retourniert einen Iterator des Typs AssocIter (mit geeigneten Typparameterersetzungen), der über die Label aller von der Wurzel des Baums ausgehenden Kanten in aufsteigender Reihenfolge (entsprechend compareTo) iteriert. Die Methode insert des Iterators fügt nur dann eine neue Kante mit einem neuen Label hinzu, wenn es vom selben Knoten aus noch keine Kante mit einem gleichen Label (entsprechend compareTo) gibt. Die über den Iterator zugänglichen assoziierten Objekte entsprechen Iteratoren des Typs AssocIter, welche (so wie hier für den Wurzelknoten beschrieben) über die Label der Kanten iterieren, die von dem Knoten ausgehen, der über die Kante erreichbar ist, dessen Label zuletzt von next zurückgegeben wurde. Jeder Aufruf von assoc (sowohl in Instanzen von Tree als auch in Iteratoren) erzeugt einen neuen Iterator.
  • allLabels erzeugt einen neuen Iterator des Typs Iter, der eine Tiefensuche über dem Baum macht und die Label der dabei besuchten Kanten sowie für jeden besuchten Blatt-Knoten (also jeden Knoten ohne ausgehende Kanten) null zurückgibt. Tiefensuche bedeutet, dass für jede ausgehende Kante der gesamte darunter hängende Teilbaum abgearbeitet wird, bevor die nächsten Kante an die Reihe kommt. Die von einem Knoten ausgehenden Kanten werden dabei in der Reihenfolge bearteitet, wie sie von durch assoc erzeugten Iteratoren zurückgegeben werden. Die Methode allLabels ist beim Testen hilfreich.
  Eine frisch erzeugte Instanz von Tree enthält nur den Wurzelknoten ohne ausgehende Kanten.
• Die Klasse ValueTree ähnelt Tree, jedoch ist jeder Knoten mit einem Wert (als Instanz eines durch einen Typparameter bestimmten Typs) versehen. Die Methoden von ValueTree entsprechen denen von Tree, wobei aber assoc (sowohl in ValueTree als auch in den Iteratoren) je eine Instanz von ValueIter zurückgibt. Wird kein Wert für einen Knoten über set im Iterator gesetzt, so ist der Wert null. Wenn möglich soll ValueTree mit geeigneten Typparameterersetzungen Untertyp von Tree sein.

Weiters wird zum Testen obiger Klassen und Interfaces Folgendes benötigt:

• Descriptor ist eine abstrakte Klasse, die einen durch den Konstruktor gesetzten String enthält und die Methode compareTo unterstützt, welche die Strings in zwei Instanzen von Descriptor lexikalisch miteinander vergleicht. Die vordefinierte Methode toString soll den String selbst zurückgeben.
• ADescriptor ist eine Unterklasse von Descriptor, in der eine zusätzliche Methode as die Anzahl aller Vorkommen der Buchstaben a und A im String zurückgibt.
• BDescriptor ist eine weitere Unterklasse von Descriptor, in der eine Methode bs einen Wahrheitswert zurückgibt, der besagt, ob im String der Buchstabe b oder B vorkommt.
• Die Klasse MyInt kapselt eine durch den Konstruktor gesetzte ganze Zahl und unterstützt die Methode compareTo, die einfach nur die Zahlen vergleicht. Die vordefinierte Methode toString soll die Zahl als String zurückgeben. MyInt ist weder Untertyp noch Obertyp von Descriptor.

Von allen oben beschriebenen Interfaces, Klassen und Methoden wird erwartet, dass sie überall verwendbar sind. Der Bereich, in dem weitere eventuell benötigte Klassen, Methoden, Variablen, etc. sichtbar sind, soll jedoch so klein wie möglich gehalten werden.

Alle Klassen in dieser Aufgabe sind ohne Verwendung von Arrays, ohne vorgefertigte Container-Klassen (wie LinkedList, HashSet, etc.) und ohne vorgefertigte Iterator-Implementierungen zu lösen. Die benötigten Container und Iteratoren sind selbst zu schreiben.

Typsicherheit soll so weit wie möglich vom Compiler garantiert werden. Auf die Verwendung von Typumwandlungen (casts) und ähnliche Techniken ist daher zu verzichten, und der Compiler darf keine Hinweise auf mögliche Probleme im Zusammenhang mit Generizität geben. Entsprechende Überprüfungen durch den Compiler dürfen nicht ausgeschaltet werden.

Ein Aufruf von java Test soll wie gewohnt Testfälle ausführen und die Ergebnisse in allgemein verständlicher Form darstellen. Anders als in bisherigen Aufgaben sind die Überprüfungen jedoch vorgegeben und in dieser Reihenfolge auszuführen:

1. Erzeugen Sie einen Baum als Instanz von Tree, in dem Labels auf Kanten vom Typ MyInt sind, und überprüfen Sie die Funktionalität. Das heißt, fügen Sie Kanten auf mehreren Ebenen ein (also auch Kanten, die nicht von der Wurzel ausgehen), entfernen Sie Kanten, und so weiter. Überprüfen Sie die Korrektheit durch Ausgabe der über Iteratoren ermittelten Labels.
2. Erzeugen Sie einen Baum als Instanz von ValueTree, in dem Labels auf Kanten vom Typ ADescriptor und Werte der Knoten vom Typ BDescriptor sind, und machen Sie entsprechende Überprüfungen wie in Punkt 1. Geben Sie auch die Ergebnisse der Aufrufe von as in Labels auf Kanten und bs in Werten von Knoten aus.
3. Falls ValueTree mit entsprechenden Typparameterersetzungen ein Untertyp von Tree ist, betrachten Sie den in Punkt 2 erzeugten Baum als Instanz von Tree, das heißt, weisen Sie den Baum an eine Variable vom deklarierten Typ Tree (mit entsprechenden Typparameterersetzungen) zu, und führen Sie die folgenden Tests auf dieser Variablen durch: Fügen Sie noch einige Kanten ein, entfernen Sie einige Kanten, lesen Sie die Labels der Kanten über Iteratoren aus, und geben Sie auch die Ergebnisse der Aufrufe von as in den Labels aus. Falls ValueTree kein Untertyp von Tree ist, geben Sie an Stelle dieser Testergebnisse eine Begründung dafür aus, warum zwischen diesen Typen keine Untertypbeziehung bestehen kann.
4. Erzeugen Sie einen weiteren Baum als Instanz von Tree, in dem Labels auf Kanten vom Typ Descriptor sind. Lesen Sie alle Labels auf Kanten und Werte von Knoten vom in Punkt 2 erzeugten (und möglicherweise in Punkt 3 veränderten) Baum aus, und fügen Sie diese (sowohl Instanzen von ADescriptor als auch von BDescriptor wenn ungleich null) als Labels von Kanten in den neuen Baum ein. Lesen Sie die Labels der Kanten über Iteratoren aus.

Warum die Aufgabe diese Form hat:

Die Aufgabe ist so konstruiert, dass dabei einige Schwierigkeiten auftauchen, für die wir Lösungsmöglichkeiten kennengelernt haben. Beispielsweise wird gebundene Generizität benötigt, und vermutlich ist in diesem Zusammenhang ein Typ erforderlich, der in der Aufgabenstellung nicht vorkommt. Eine weitere Schwierigkeit kommt durch die binäre Methode compareTo hinein. Mittels Untertypbeziehungen lässt sich der Parametertyp der Methode nicht vernünftig ausdrücken, wohl aber durch Generizität, aber nur über eine Typebene hinweg. Durch die Typhierarchie auf Descriptor, ADescriptor und BDescriptor muss Generizität über mehrere Ebenen hinweg betrachtet werden, da vereinfachende Sichtweisen durch den von dieser Hierarchie unabhängigen Typ MyInt ausgeschlossen sind. Dieser Teil der Aufgabe ist z.B. durch Verwendung von Typ-Wildcards einfach lösbar (ähnlich wie im Beispiel auf einer Vorlesungsfolie). Vorgegebene Testfälle stellen sicher, dass die Schwierigkeiten erkannt werden. Um Umgehungen zu vermeiden sind Typumwandlungen verboten, und Hinweise des Compilers auf unsichere Verwendungen von Generizität dürfen nicht ausgeschaltet werden.

Neben Techniken zur Lösung der speziellen Schwierigkeiten wird in dieser Aufgabe auch der Umgang mit Sichtbarkeit und Untertypbeziehungen auf generischen Typen geübt. Am Beispiel von Iteratoren soll intuitiv klar werden, welchen Einfluss die Verwendung oder Nichtverwendung von inneren Klassen (speziell für Iteratoren) auf die Sichtbarkeit von Implementierungsdetails nach außen hat.

Was im Hinblick auf die Beurteilung zu beachten ist:

Der wichtigste Schwerpunkt bei der Beurteilung liegt auf der sinnvollen und korrekten Verwendung von Generizität. Dementsprechend gibt es bedeutende Punkteabzüge, wenn der Compiler mögliche Probleme im Zusammenhang mit Generizität meldet oder wichtige Teilaufgaben nicht gelöst oder (durch Nichtbefolgung von Teilen der Aufgabenstellung) umgangen werden.

Ein zusätzlicher Schwerpunkt liegt auf dem gezielten Einsatz von Sichtbarkeit. Es gibt Punkteabzüge, wenn Programmteile, die überall sichtbar sein sollten, nicht public sind, oder Teile, die nicht für die allgemeine Verwendung bestimmt sind, unnötig weit sichtbar sind. Durch die Verwendung von inneren Klassen kann das Sichtbarmachen mancher Programmteile nach außen verhindert werden.

Weiters bilden Untertypbeziehungen (basierend auf Zusicherungen) einen Schwerpunkt. Punkte werden abgezogen, wenn nicht richtig erkannt wurde, ob ValueTree ein Untertyp von Tree ist und wenn Zusicherungen Mängel aufweisen. Interfaces und Klassen müssen mit informativen Zusicherungen versehen sein. Der Begriff informativ ist dabei nicht mit lang, ausführlich oder jede Trivialität beschreibend zu verwechseln, sondern das Wesentliche soll kurz und bündig und möglichst eindeutig beschrieben sein – alles, was der Client über ein Service wissen muss, und alles, was der Server vom Client erwartet. Aus praktischen Gründen gehen Zusicherungen in Testklassen nicht in die Beurteilung ein.

Generell führen Abänderungen der Aufgabenstellung (beispielsweise die Verwendung von Typumwandlungen, Arrays oder vorgefertigten Containern und Iteratoren oder das Ausschalten von Überprüfungen durch Pragmas) zu bedeutenden Punkteabzügen.

Vermeiden Sie die Verwendung von packages auch schon in Ihrem ersten Entwurf, da diese immer wieder zu Problemen bei der Übertragung und Beurteilung führen. Legen Sie im Abgabeverzeichnis keine Unterverzeichnisse an.

Wie die Aufgabe zu lösen ist:

Diese Aufgabenstellung bietet wenig Interpretationsspielraum. Wahrscheinlich können Sie ohne langwierige Analyse gleich mit dem Entwurf einer Lösung beginnen. Schreiben Sie möglichst frühzeitig die Klasse Test, da die Wahrscheinlichkeit groß ist, dass Sie beim Implementieren der vorgegebenen Testfälle schwerwiegende Probleme in Ihrem Lösungsansatz finden. Lassen Sie sich beim Entwurf der Lösung am besten von den Testfällen leiten.

Achten Sie besonders darauf, dass der Compiler keine Meldung (z.B. Note: ...) ausgibt, die Sie möglicherweise nicht verstehen. Sehr häufig haben solche Meldungen mit einer fehlerhaften Verwendung von Generizität (vor allem mit fehlenden Typparameterersetzungen) zu tun. Informative Meldungen bekommen Sie durch javac -Xlint:unchecked *.java. Verschleiern Sie keine Probleme im Umgang mit Generizität beispielsweise durch Typumwandlungen.

Achtung: Es gibt noch immer Java-Compiler (vor allem unter Eclipse), die nicht alle Fehler im Zusammenhang mit Generizität richtig erkennen oder gar nicht mit Generizität umgehen können. Verwenden Sie daher einen einigermaßen aktuellen Compiler und testen Sie Ihre Lösung rechtzeitig auf der g0. Beachten Sie auch, dass in einigen Fällen fehlende Typparameterersetzungen auch mit aktuellen Compilern zu keinen Compiler-Meldungen führen. Solche fehlenden Typparameterersetzungen werden trotzdem als falsch beurteilt.

Zur Terminologie: Im Zusammenhang mit Iteratoren versteht man unter einem Aggregat die Datenstruktur, über die der Iterator iteriert. In dieser Aufgabe sind das im Wesentlichen Bäume und Baumknoten (bzw. Mengen von ausgehenden Kanten). Oft, wie auch hier, werden solche Begriffe nicht in ihrer genauen Bedeutung verwendet, um das Einsatzspektrum von Iteratoren zu erhöhen. Zum Beispiel soll insert in einer Instanz von AssocIter als Seiteneffekt eine neue Kante (mit Label) und einen neuen Knoten in einen Baum einfügen, obwohl der Iterator eigentlich nur über Labels läuft und insert nur ein Label als Argument bekommt. In diesem Fall ist ein schlampiger Umgang mit Begriffen hilfreich.

Halten Sie Ihr Programm so kurz wie möglich und vermeiden Sie mehrfache Implementierungen derselben Funktionalität. Das ist sehr hilfreich, wenn es darum geht, den Überblick zu bewahren und Fehler zu vermeiden.