Objektorientierte Programmierung
LVA 185.162, VL 2.0, 2009 W

5. Laborübungsaufgabe

Themen:

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

Termine:

Ausgabe:	18.11.2009
reguläre Abgabe:	25.11.2009, 13:45 Uhr
nachträgliche Abgabe:	02.12.2009, 13:45 Uhr

Abgabeverzeichnis:

Gruppe/Aufgabe5

Programmaufruf:

java Test

Grundlage:

Skriptum bis Seite 113, Schwerpunkt auf Abschnitt 3.1

Aufgabe

Entwickeln Sie in Java Interfaces und Klassen wie folgt:

• Das generische Interface Iter enthält nur die Iterator-Methoden next und hasNext.
• Eine Instanz der generischen Klasse Tree entspricht einem Knoten in einem baumförmigen gerichteten Graphen zusammen mit maximal einer eingehenden und beliebig vielen ausgehenden Kanten auf andere Instanzen eines passenden Typs. Der Knoten hat einen (von einem Typparameter abhängigen) Inhalt. Folgende Methoden werden benötigt:
  • parent gibt jene Instanz von Tree zurück, von der aus eine Kante auf this zeigt (eingehende Kante), falls this keinen Wurzelknoten darstellt. Für Wurzelknoten gibt parent nur null zurück. Eine frisch erzeugte Instanz von Tree stellt immer einen Wurzelknoten dar.
  • children retourniert einen Iterator (des Typs Iter mit geeigneten Typparameterersetzungen), der über alle Instanzen von Tree, auf die es eine von this ausgehende Kante gibt, in beliebiger Reihenfolge iteriert. Eine frisch erzeugte Instanz von Tree hat keine ausgehenden Kanten, children gibt also nur einen leeren Iterator zurück.
  • setParent ändert den von parent zurückgegebenen Wert und wird zum Hinzufügen und Entfernen von Kanten verwendet. Dabei müssen auch in den Instanzen von Tree, die von parent vor und nach der Änderung zurückgegeben werden, die Mengen der ausgehenden Kanten entsprechend angepasst werden.
  • get liest den Inhalt des Knotens.
  • set setzt den Inhalt des Knotens ebenso wie der Konstruktor von Tree.
  • contents gibt einen Iterator (Iter) zurück, der über die Inhalte aller Knoten des Baums bzw. Teilbaums mit this als angenommener Wurzel in beliebiger Reihenfolge iteriert.
• Das (möglicherweise generische) Interface Reducible enthält eine Methode reduce mit einem Argument, die das Argument zusammen mit this auf nicht näher bestimmte Weise zu einem einzigen Objekt vereinfacht. Das Ergebnis von reduce hat denselben deklarierten Typ wie das Argument, und auch this soll Instanz dieses Typs sein.
• Die Klasse AccTree (akkumulierender Baum) entspricht Tree, der durch set und get gesetzte und gelesene Inhalt muss jedoch Instanz von Reducible sein. Das gilt auch für alle anderen Knoten eines akkumulierenden Baumes.
  Zusätzlich gibt es die Methode reduced, die durch wiederholte Anwendungen von reduce alle Inhalte des Baums bzw. Teilbaums mit this als Wurzel (in der Reihenfolge wie von contents geliefert) zu einem einzigen Wert reduziert und diesen retourniert. Besteht der Baum nur aus einem Knoten, dann gibt reduced dasselbe Objekt zurück wie get.
  Außerdem soll AccTree selbst (mit geeigneten Typparameterersetzungen) Untertyp von Reducible sein, wobei reduce den als Argument übergebenen Baum als Teilbaum in this einhängt und this zurückgibt.
  Wenn möglich soll AccTree Untertyp von Tree sein (jeweils mit geeigneten Typparameterersetzungen).

Daneben werden als Anwendungsbeispiel folgende nicht-generische Klassen benötigt:

• Die abstrakte Klasse Component implementiert Reducible und kapselt (wie Integer) eine ganze Zahl, die Kosten (in einer nicht näher spezifizierten Einheit) darstellt. Die Methode reduce gibt die gekapselte Summe der in this und dem Argument gekapselten Zahlen zurück. Ein Baum über Instanzen von Component stellt ein abstraktes Gerät dar, das aus einzelnen Komponenten (Blattknoten im Baum) und daraus erzeugten größeren Einheiten (Teilbäume mit mehreren Knoten) besteht.
• Die Klasse Device erweitert Component um eine Methode weight, die eine im Konstruktor gesetzte ganze Zahl zurückgibt. Der von toString erzeugte String enthält die Information, dass es sich um ein Device handelt, sowie dessen Kosten und Gewicht (weight).
• Die Klasse Job erweitert Component um eine Methode time, die eine im Konstruktor gesetzte ganze Zahl zurückgibt. Der von toString erzeugte String enthält die Information, dass es sich um einen Job handelt (z.B. einen Verarbeitungsschritt zur Verbesserung eines Devices oder zum Zusammenbau einer Einheit aus mehreren Devices), sowie deren Kosten und Dauer (time).

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 (Instanzen von Tree), dessen Inhalte vom Typ String sind, und überprüfen Sie die Funktionalität. Das heißt, bauen Sie Bäume mit mehreren Ebenen auf, fügen Sie mehrere Bäume zu einem Baum zusammen, trennen Sie Teilbäume ab und fügen sie diese anders wieder zusammen, und so weiter. Überprüfen Sie die Korrektheit durch Ausgabe der Inhalte des Baums sowie aller Teilbäume über Iteratoren.
2. Erzeugen Sie zwei Bäume (Instanzen von AccTree), einen mit Inhalten vom Typ Device und eine mit Inhalten vom Typ Job, und machen Sie ähnliche Überprüfungen wie in Punkt 1. Geben Sie die Ergebnisse der Aufrufe von reduced (auf den beiden Bäumen und auf jedem einzelnen Teilbaum) sowie zur Kontrolle die über Iteratoren ermittelten Inhalte der Bäume und aller Teilbäume aus. Ermitteln Sie durch Verwendung von Iteratoren auch die Summen aller Gewichte von Devices und der Dauer aller Jobs. Dabei dürfen keine Typumwandlungen verwendet werden.
3. Fassen Sie die beiden Bäume aus Punkt 2 zu einem einzigen Baum zusammen (Instanzen von AccTree mit Inhalten vom Typ Component): Erzeugen Sie zuerst Kopien der beiden Bäume (neue Instanzen von AccTree mit Inhalten vom Typ Component) oder bauen Sie entsprechende Bäume wie in Punkt 2 (aber mit anderen Typparameterersetzungen) neu auf. Fassen Sie diese Kopien der Bäume dann durch einen Aufruf von reduce zu einem Baum zusammen. Geben Sie die Ergebnisse der Aufrufe von reduced und die über Iteratoren ermittelten Inhalte des zusammengefassten Baums und seiner Teilbäume aus.
4. Falls AccTree mit entsprechenden Typparameterersetzungen ein Untertyp von Tree ist, betrachten Sie den in Punkt 3 erzeugten Baum als Instanz von Tree, verschieben Sie einen Teilbaum an eine andere Stelle (abtrennen und neu zusammensetzen oder in einem Schritt), und geben Sie den veränderten Baum und dessen Teilbäume (wieder als Instanz von AccTree betrachtet) wie in Punkt 3 über reduced reduziert und über Iteratoren aus. Sollte AccTree kein Untertyp von Tree sein, geben Sie anstelle der Testergebnisse einen Text aus, der eine überzeugende Erklärung dafür gibt.

Warum die Aufgabe diese Form hat:

Die Aufgabe ist so konstruiert, dass dabei einige Schwierigkeiten auftauchen, für die wir bereits Lösungsmöglichkeiten kennengelernt haben. Beispielsweise wird gebundene Generizität benötigt. Eine weitere Schwierigkeit kommt durch die binäre Methode reduce 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 Component, Device und Job muss Generizität über mehrere Ebenen hinweg betrachtet werden (da vereinfachende Sichtweisen durch den von dieser Hierarchie unabhängigen Typ AccTree als weiteren Untertyp von Reducible ausgeschlossen sind). Dieser Teil der Aufgabe ist wahrscheinlich nur durch Verwendung von Typ-Wildcards lösbar (ganz ähnlich wie in einem Beispiel auf einer Vorlesungsfolie). Die vorgegebenen Testfälle stellen sicher, dass die Schwierigkeiten erkannt werden. Deren Umgehung ist unmöglich, da Typumwandlungen verboten sind und der Compiler keine Hinweise auf unsichere Verwendungen von Generizität geben darf.

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 AccTree 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) 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 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. 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.

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.