michael.eichberg@dhbw.de, Raum 149B
1.0
Wiederholung von allg. Programmierkonzepten und Motivation für Generics.
Speichern von Wertepaaren
Implementieren Sie die Datenstruktur Pair die zwei Werte (vom Typ Object) speichern kann. Die Klasse soll folgende Methoden bereitstellen:
Pair(..., ...): Konstruktor zum Erzeugen eines Pairs.
getFirst() und getSecond(): Liefert den ersten/zweiten Wert zurück
void setFirst(...) und void setSecond(...): Setzt den ersten/zweiten Wert
toString(): Liefert eine String-Repräsentation des Paares
Erzeugen Sie ein Pair-Objekt mit zwei Integer-Werten (z. B. 1 und 2).
Nutzen Sie die Methoden der Klasse, um die Werte abzufragen und zu addieren.
Speichern Sie das Ergebnis an zweiter Stelle im Pair-Objekt als String.
Geben Sie den zweiten Wert auf der Konsole aus.
Was wäre bei der Addition passiert, wenn an zweiter Stelle ein String gespeichert gewesen wäre? Wann wäre das Verhalten aufgefallen?
Welchen statischen Typ hat der Wert, den die Methode getFirst() zurückgibt?
Datenstruktur zum Speichern von ganz vielen Werten
Implementieren Sie eine Datenstruktur List zum Speichern beliebig vieler Werte im Package ds. Die Klasse soll folgende Methoden bereitstellen:
List(): Konstruktor
List(int size): Konstruktor
void add(...): Fügt ein Element hinzu
eine Varargs Methode void addAll(...):, die alle übergebenen Werte hinzufügt.
int size(): Liefert die Anzahl der Elemente zurück
Object get(int index): Liefert das Element an der Stelle index zurück oder wirft eine IndexOutOfBoundsException, wenn der Index ungültig ist
void set(int index, Object value): Setzt das Element an der Stelle index auf den Wert value oder wirft eine IndexOutOfBoundsException, wenn der Index ungültig ist
String toString(): Liefert eine String-Repräsentation der Liste
void remove(int index): Entfernt das Element an der Stelle index oder wirft eine IndexOutOfBoundsException, wenn der Index ungültig ist
void clear(): Entfernt alle Elemente
Nutzen Sie als zugrunde liegende Datenstruktur ein Array. D. h. speichern Sie die Elemente in einem Array und vergrößern Sie das Array, wenn es voll ist. Wenn das Array zu groß ist, verkleinern Sie es. Eine Vergrößerung soll das Array verdoppeln aber um nicht mehr als 1000 Elemente. Eine Verkleinerung soll das Array halbieren, wenn weniger als ein Viertel des Arrays belegt ist. Die Mindestgröße des Arrays soll 16 Elemente betragen.
Nutzen Sie java.lang.System.arraycopy(...) zum Vergrößern/Verkleinern des zugrunde liegenden Arrays.
Schreiben Sie eine Klasse ListTest, die die Klasse List testet. Die Klasse soll jede der Methoden der Klasse List testen; d. h. mindestens einmal aufrufen.
List erweitern
Schreiben Sie eine Klasse Stack im Package ds, die Ihre Klasse List erweitert; d. h. von List erbt. Die Klasse soll folgende Methoden bereitstellen:
Stack(): Konstruktor
void push(... value): Legt ein Element auf den Stack
... pop(): Entfernt das oberste Element vom Stack und liefert es zurück oder wirft eine java.util.NoSuchElementException, wenn der Stack leer ist
... peek(): Liefert das oberste Element zurück, ohne es zu entfernen oder wirft eine NoSuchElementException, wenn der Stack leer ist
Schreiben Sie eine Klasse RPN (im Default Package), die einen String von der Kommandozeile übernimmt (als einzelne "args") und diesen als umgekehrte polnische Notation interpretiert (d. h. erst kommen die Operanden, dann ein Operator) und berechnet.
Beispielinteraktion:
1$ java --enable-preview RPN 1 2 "+" 3 "*"29.0
Nutzen Sie Ihre Klasse Stack zum Zwischenspeichern der Operanden.
Wenn Sie sich den Code des RPN ansehen - wo sehen Sie insbesondere Verbesserungspotential?
wir haben zwei grundlegende Datenstrukturen kennen gelernt sowie mögliche Implementierungen dafür:
Listen basierend auf Arrays
Stacks basierend auf Listen
wir haben gesehen, dass die Verwendung von Datenstrukturen, die nichts über den Typ der gespeicherten Elemente wissen, zu Problemen führen kann (Fehler zur Laufzeit und nicht zur Compilezeit). Weiterhin sind viele explizite Typumwandlungen notwendig, die den Code unübersichtlich machen.
Generics erlauben die Definition generischer und typsicherer Datentypen, die über die Typen der Elemente abstrahieren.
D. h. wir können zum Beispiel angeben, dass wir nur Elemente vom statischen Typ Person speichern wollen. Dies hat folgende Vorteile:
Kompakterer / besser wartbarer Code
Fehler, die sonst erst zur Laufzeit auftreten würden, können zur Compilezeit erkannt werden (z. B. das versehentliche Speichern eines Strings in einer Liste für Integer Werte.)
StacksVerwendung eines einfachen Stacks ohne Typparametrisierung
1Stack stack = new Stack();2for (String arg : args) {3switch (arg) {4case "+":5stack.push((double) stack.pop() + (double) stack.pop());6break;7case "*":8stack.push((double) stack.pop() * (double) stack.pop());9break;10default:11stack.push(Double.parseDouble(arg));12}13}
In diesem Beispiel würden wir insbesondere gerne auf die Casts (2 Mal in Zeile 5 und 2 man in Zeile 8) verzichten wollen. Dies Casts sind nicht nur unschön, sondern können auch (in komplexeren Fällen) zu Laufzeitfehlern führen.
Verwendung eines Stacks für Double Werte
1Stack<Double> stack = new Stack<>(); // <- Typ der Elemente ist Double2for (String arg : args) {3switch (arg) {4case "+":5stack.push(stack.pop() + stack.pop());6break;7case "*":8stack.push(stack.pop() * stack.pop());9break;10default:11stack.push(Double.parseDouble(arg));12}13}
1public interface Collection<E> {2void add(E x);3Iterator<E> iterator();4}56public interface Comparable<T> {7int compareTo(T o);8}
Mittels <E> oder <T> in der Klassendefinition deklarieren wird einen formalen Typparameter E bzw. T.
Dieser kann dann in der Klasse als Typ genutzt werden. Wenn wir dann eine Instanz der Klasse erzeugen, müssen wir den konkreten Typ für den Typparameter E bzw. T angeben.
Bei der Instanziierung von Generics muss für alle generischen Typen ein konkreter Datentyp (z.B. Integer) definiert werden:
Der konkrete Datentyp muss eine Klasse sein, d. h. es darf kein primitiver Datentyp (z.B. int) sein.
Der konkrete Datentyp kann allerdings auch bei der Verwendung weggelassen werden (dann spricht man von Raw-Types).
Wenn ein generischer Datentyp instanziiert wird, und direkt einer entsprechend getypten Variable zugewiesen wird, dann kann der konkrete Datentyp weggelassen werden (es muss aber der Diamond Operator <> verwendet werden).
Pair mit Typparametern
Erweitern Sie Ihre Klasse Pair um zwei generische Typparameter U und V für die beiden Werte, die gespeichert werden sollen.
Nutzen Sie dann die entsprechenden Typen U und V für die entsprechenden Attribute der Klasse und ggf. auch für Methodenparameter/-rückgabewerte und lokale Variablen.
Passen Sie auch die main Methode entsprechend an.
Eine häufig benötigte Form von Datenstrukturen ist eine Collection (Sammlung), die unterschiedliche Datenelemente speichert.
entweder genau der gleiche Typ
oder der gleiche Typ; ggf. mit Subtypen
oder gemischte Typen (eher selten)
Abhängig vom geplanten Gebrauch kann eine Collection…
schnellen Zugriff auf die einzelnen Elemente unterstützen.
die Sortierung der Elemente unterstützen.
die Möglichkeit zum Zugriff auf bestimmte Elemente geben.
bei Bedarf wachsen.
usw.
Wenn primitive Werte an Stellen verwendet werden, die eigentlich Objekte verlangen (z. B. Collections), dann werden automatisch die jeweiligen passenden Wrapperklassen verwendet; d. h. die primitiven Datentypen werden in Objekte umgewandelt und entsprechend behandelt:
int -> java.lang.Integer float -> java.lang.Float double -> java.lang.Double char -> java.lang.Character boolean -> java.lang.Boolean byte -> java.lang.Byte short -> java.lang.Short long -> java.lang.Long
Das Hauptinterface ist java.util.Collection
es definiert grundlegende Methoden für Sammlungen von Objekten.
es definiert keine Restriktionen / Garantien bezüglich Duplikate / Ordnung / Sortierung, usw.
List (hat die Implementierungen ArrayList, LinkedList, …)
Objekte sind sortiert
kann Duplikate enthalten
direkter Zugriff auf Objekte über Index
Set (hat die Implementierung HashSet)
keine Einschränkung bzgl. der Sortierung
Objekt kann nur einmal enthalten sein
SortedSet (hat die Implementierung TreeSet)
Ein Set, aber geordnet bzgl. einer spezifischen Vergleichsstrategie.
Im Folgenden betrachten wir Collections die Element vom Typ „E“ verwalten; dieser Typ ist durch „passende“ Typen ersetzbar.
java.uti.ListDas Interface bietet folgende Methoden:
boolean add(E e): Anhängen des Elements e an die Liste
void add(int pos, E e): Einfügen des Elements e an Position pos; verschiebt alle Elemente ab Position pos um eine Position nach hinten
boolean addAll(Collection c): Anhängen aller Elemente der Collection c an die Liste
boolean addAll(int pos, Collection c): Einfügen aller Elemente der Collection c an Position pos (s.o.)
void clear(): Löscht alle Elemente der Liste
boolean contains(Object o): Liefert true, wenn sich Objekt o in der Liste befindet
boolean containsAll(Collection c): Liefert true, falls alle Objekte der Collection c in der Liste sind
E get(int pos): Liefert das Element an Position pos der Liste
int indexOf(Object o): Liefert die erste Position, an der sich o in der Liste befindet, sonst -1. Gegenstück: int lastIndexOf(Object o)
boolean isEmpty(): Liefert true wenn die Liste leer ist
E remove(int pos): Entfernt das Objekt an Position pos und liefert es zurück
boolean remove(Object O): Versucht Objekt o aus der Liste zu entfernen; true bei Erfolg
int size(): Liefert die Größe der Liste
Object[] toArray(): Liefert ein Array, das alle Elemente der Liste umfasst
Für Konstruktoren in den Erbenklassen gilt:
es gibt immer Parameterlose Konstruktoren (Konvention)
Konstruktoren mit Collection als Parameter kopieren alle Werte in die Liste
Spezialfälle (siehe entsprechende Dokumentation)
Konkrete Implementierungen (Auswahl):
java.util.LinkedList fügt folgende Methoden hinzu (Auswahl):
void addFirst(E)
void addLast(E)
E getFirst()
E getLast()
java.util.ArrayList speichert die Elemente in einem Array und fügt folgende Methoden hinzu (Auswahl):
void ensureCapacity(int minCapacity) - falls die Liste weniger Elemente als minCapacity fassen kann, wird das Array vergrößert
void trimToSize() - verkleinert das Array auf die Listengröße
ArrayList(int initialCapacity) Neuer Konstruktor, für die Spezifikation der Größe
java.util.SetEin Set repräsentiert eine mathematische Menge
D. h. ein gegebenes Objekt ist nur maximal einmal vorhanden und das Einfügen scheitert, wenn das Objekt schon vorhanden ist.
Umfasst die meisten der schon bekannten Methoden
boolean add(E e)
boolean addAll(Collection c)
void clear()
boolean contains(Object O)
boolean containsAll(Collection c)
boolean isEmpty()
boolean remove(Object O)
boolean removeAll(Collection c)
int size()
Object[] toArray()Konkrete Implementierungen (Auswahl):
java.util.HashSet: verwaltet die Daten in einer Hashtabelle (sehr effizienter Zugriff)
java.util.TreeSet: verwaltet die Daten in einem Baum mit Zugriffszeiten in O(log n)[1].
Im folgenden wird der Typ „K“ für den Typ des Schlüssels und der Typ "V" für den Typ des Wertes verwendet; diese Typen sind durch „passende“ Typen ersetzbar.
java.util.MapWenn Objekte nicht über einen numerischen Index, sondern über einen Schlüssel (einzigartiger, aber sonst zufälliger Wert) auffindbar sein sollen, z.B. eine Telefonnummer mit „Nachname + Vorname“.
Das Interface bietet folgende Methoden:
Object put(K key, V value) speichert "value" zum Auffinden mit "key"
Object get(Object key) findet das Objekt gespeichert unter "key"
boolean containsKey(Object key) beantwortet, ob ein Objekt unter "key" liegt
boolean containsValue(Object value) beantwortet, ob "value" in der HashMap ist
Object remove(Object key) löscht "key" und die assoziierten Objekte
Wir werden später klären warum nur die Parameter der Methode put einen generischen Typ (K für Key (Schlüssel) und V für Value (Wert)) haben.
Konkrete Implementierungen (Auswahl):
java.util.HashMap
Erlaubt Zugriff auf Elemente durch einen berechneten Schlüssel, z.B. „Nachname + Vorname“ Schlüssel wird in numerischen Index (Hashwert[2]) konvertiert und für effizienten Zugriff genutzt.
java.util.IteratorJava nutzt einen Iterator, um über Elemente in einer Collection zu laufen („zu iterieren“).
Normalerweise erhält man den Iterator durch den Aufruf von iterator() auf der Collection.
Das gilt für alle Subklassen des Collection Interface
Für eine HashMap nutzt man keys() und darauf iterator()
iterator() liefert eine Instanz von java.util.Iterator
Ein Iterator bietet die Operationen:
boolean hasNext() – gibt es noch weitere Elemente?
Object next() – liefert das nächste Element, falls eines existiert;sonst wird eine NoSuchElementException geworfen.
Prüfen Sie vorher die Existenz mit hasNext()!
void remove() – entfernt das zuletzt gelieferte Element; häufig nicht unterstützt. In diesem Fall wird eine UnsupportedOperationException geworfen.
Weiterhin gibt es eine besondere for-Schleife (foreach-loop), die die Iteration über eine Collection, die das Interface Iterable implementiert vereinfacht:
java.util.Iterable definiert dabei lediglich das Protokoll zur Erzeugung eines java.util.Iterators.
Die Implementation von Iterators ist ein Beispiel für die Umsetzung des Design Pattern (Entwurfsmuster) „Iterator“.
Es ist hier festzustellen, dass in Java die Methode hasNext() an die Stelle der Methode isDone() rückt. die Methode next() das Fortschalten des Iterators und die Rückgabe des nächsten Elements kombiniert. In anderen Sprachen bzw. im Textbuch sind diese beiden Operationen getrennt. Eine Design Pattern stellt auch immer nur eine Blaupause dar, die in der konkreten Umsetzung angepasst werden kann bzw. soll.
Iterables
Implementieren Sie das Interface java.lang.Iterable für Ihre Klasse Pair. D. h. schreiben Sie eine Methode java.util.Iterator iterator(), die einen Iterator für die Elemente des Paares zurückgibt.
Dazu ist es erforderlich, dass Sie eine Klasse PairIterator implementieren, die das Interface java.util.Iterator implementiert. Diese Klasse führt dann die eigentliche Iteration durch. Die Erzeugung der Instanz von PairIterator erfolgt in der Methode iterator().
1List<String> ls = new LinkedList<String>();2List<Object> lo = ls;3lo.add(new Object());4String s = ls.get(0);
Eine einfache Methode zum Ausgeben eines Stacks:
1static void printAll(Stack<Object> stack) {2for (int i = 0; i < stack.size(); i++) {3System.out.print(stack.get(i) + " ");4}5System.out.println();6}
Diese Methode definiert einen Parameter vom Typ Stack<Object>. Das bedeutet, dass nur Stack<Object>-Objekte übergeben werden können.
Die Implementierung funktioniert aber auch mit Listen von Subtypen von Object wie String oder Integer.
Ein Aufruf mit einem Stack<Integer>-Objekt führt zu einem Compilerfehler:
printAll(new Stack<Integer>())
| Error:
| incompatible types:
| Stack<java.lang.Integer>
| cannot be converted to
| Stack<java.lang.String>Eine Lösung ist die Verwendung von Wildcards:
1static void printAll(Stack<?> stack) {2for (int i = 0; i < stack.size(); i++) {3System.out.print(stack.get(i) + " ");4}5System.out.println();6}
Durch die Verwendung von Stack<?> kann die Methode mit allen Subtypen von Object aufgerufen werden.
1abstract class Shape {2abstract void draw(Canvas c);3}4class Circle extends Shape {5void draw(Canvas c) { /*...*/ }6}7class Rectangle extends Shape {8void draw(Canvas c) { /*...*/ }9}10class Canvas {11void draw(Shape s) {12s.draw(this);13} }
Aufgabe: Definition einer Methode drawAll(<list of shapes>) für Canvas, die eine Liste von Formen zeichnet?
drawAll(List<Shape> shapes) würde nur mit Listen von Shape-Objekten funktionieren.
drawAll(List<?> shapes) würde alle Listen von Shape-Objekten und allen Subtypen von Shape funktionieren, aber auch Listen von anderen Typen.
Wir müssen den Type der Liste auf Shape und Subtypen von Shape beschränken. Dies erreichen wir mit einem beschränkten Wildcard:
drawAll(List<? extends Shape> shapes) funktioniert mit Listen von Shape-Objekten und allen Subtypen von Shape.
? extends X bedeutet:
Wir kennen den exakten Typ nicht („?“)
Aber wir wissen, dass der Typ zu X konform sein muss
X ist die „obere Schranke“ der Wildcard
Wo ist das Problem bei folgender Methode?
1void addRectangle(List<? extends Shape> shapes) {2shapes.add(0, new Rectangle());3}
Das Problem ist, dass wir nicht wissen, welcher konkrete Typ von List übergeben wird. Es könnte auch eine List<Circle> sein, die keine Rechtecke aufnehmen kann.
Die Methode addRectangle würde also nicht mit einer List<Circle> funktionieren.
Die Lösung ist die Spezifikation einer unteren Schranke. Dies ist mittels der Verwendung von super möglich.
1void addRectangle(List<? super Rectangle> shapes) {2shapes.add(0, new Rectangle());3}
? super X bedeutet:
Wir kennen den exakten Typ nicht („?“)
Aber wir wissen, dass X von dem unbekannten Typ abgeleitet sein muss
X ist die „untere Schranke“ der Wildcard
Statische Typsysteme sind (noch immer) Gegenstand der Forschung
Java-ähnliche Typsysteme sind begrenzt, aber im Allgemeinen können Typsysteme sehr mächtig und ausdrucksstark sein - aber auch sehr kompliziert
Manche Programmierer sehen statische Typsysteme als eine Begrenzung ihrer Freiheit ("ich weiß, was ich tue")
Andere Programmierer denken, dass statische Typsysteme nicht nur viele Fehler erkennen, sondern auch eine gute Struktur im Code erzwingen ("erst denken, dann schreiben")
In der Praxis zeigt sich, dass fast alle großen Projekte auf statische Typsysteme setzen.
Wildcards
Fügen Sie Ihrer generischen Klasse Pair eine Methode addToMap(...) hinzu, die die Elemente des Pairs in einer java.util.Map speichert. D. h. der erste Wert eines Pairs wird als Schlüssel und der Zweite als Value verwendet.
Achten Sie darauf, dass die Methode auch Maps von Supertypen von U und V akzeptiert. D. h. es sollte folgendes Szenario unterstützt werden:
1Pair<Integer,Integer> p = new Pair<>(1, 2);2java.util.Map<Object,Integer> map = new java.util.HashMap<>();3p1.addToMap(map); // D.h. dem Key "1" ist nur der Wert "2" zugewiesen.
Schreiben Sie eine Methode die die Werte eine Pairs aktualisiert basierend auf den Werten eines anderen Paares. Achten Sie darauf, dass die Methode auch mit Subtypen von U und V arbeitet.
1Pair<Integer,Integer> p = new Pair<>(1, 2);2Pair<Object,Object> pObject = new Pair<>("a",new Object());3pObject.update(p1);