[SOLVED] CS Java compiler Programmierung

Programmierung
Generics
Michael Goedicke
[email protected] auf der Basis von Folien von V Gruhn

Listen, Baume etc sind eigentlich allgemeine Strukturen
Die unterschiedlichen bisher betrachteten Implementierungen einer Liste sahen entweder einen festen Typ vor (z.B. Dokument, Student etc) als Element oder allgemein Object vor. Mit Object als Element ist es ohne weiteres moglich, Listen von unterschiedlichen Typen aufzubauen:
LinkedList dokumente = new LinkedList(); dokumente.add(new Dokument()); dokumente.add(new Dokument()); dokumente.add(new String(Hallo Welt));
Zur Erinnerung: Jede Klasse erbt automatisch von Object. Die Methode durchsuchen() wurde zur Laufzeit(!) eine
ClassCastException werfen, sobald sie versucht, ein Objekt in
den Typ Dokument zu casten, das diesen Typ nicht hat.
Ein Dilemma: Wir wollen dem Compiler den Typ der Elemente in der
Liste mitteilen und gleichzeitig die Implementierung der Liste nicht auf Elemente bestimmter Typen beschranken, damit wir sie immer wiederverwenden konnen.
M. Goedicke Programmierung WiSe 2020/2021
2

Die verkette Liste: generische Strukturen sehen Platzhalter vor, die spater gefullt werden konnen
Die Platzhalten mussen jedoch immer mit Elementen gleichen Typs versorgt werden!
M. Goedicke Programmierung WiSe 2020/2021
3

Die generische verkettete Liste: wie kann erreicht
werden, dass der Platzhalter festgelegt werden
kann
Seit Version 5 bietet Java eine komfortable Moglichkeit, einerseits wiederverwendbare und andererseits typensichere Datenstrukturen zu konstruieren: Generics.
Wir erweitern unser Interface Liste dazu um einen formalen Typparameter, sozusagen ein Stellvertreter fur den spater wirklich verwendeten Typ. Dieser muss in der Deklaration des Interfaces bzw. der Klasse angegeben werden und steht in < >. Damit ersetzen wir alle Vorkommen von Object.
Konvention ist, Typparameter als einfache Grobuchstaben anzugeben, hierT.
Achtung: funktioniert auch fur Interfaces!
public interface List {
public void add(T value);
public void add(int index, T value); public void clear();
public T get(int index);
public int indexOf(T value);
public boolean isEmpty();
public void remove(int index); public int size();
}
Typparameter T festgelegt in in der Deklaration unseres Interfaces.
Alle Vorkommen von Object werden gegen T ausgetauscht
M. Goedicke Programmierung WiSe 2020/2021
4

Die generische verkettete Liste, die Grundstruktur
Unsere Implementierungen von Node und LinkedList mussen entsprechend angepasst werden:
public class LinkedList implements List { private Node head;

}
public class Node { private T value; private Node next;
}
Platzhalter
M. Goedicke Programmierung WiSe 2020/2021
5

Die generische verkettete Liste
Mit diesen Anpassungen konnen wir dem Compiler mitteilen, welchen Typ die Liste in unserer Klasse Ordner enthalt:
public class Ordner {
private String beschriftung; private List dokumente; public Ordner(String beschriftung) {
this.beschriftung = beschriftung;
this.dokumente = new LinkedList (); }
}
Generics!
Positiver Nebeneffekt: Der Code wird lesbarer, da sofort ersichtlich ist, was sich eigentlich in der Liste befindet / befinden darf.
Anmerkung: Primitive Datentypen konnen hier nicht verwendet werden, ausschlielich Referenztypen. Folgende Anweisung ist also ungultig und fuhrt zu einem Kompilierfehler:
private List zahlen; Jedoch geht: Integer statt int
M. Goedicke Programmierung WiSe 2020/2021
6

Die generische verkettete Liste
Auf den Typecast in der Methode durchsuchen() konnen wir nun verzichten, da der Compiler wei, dass nur Objekte vom Typ
Dokument in der Liste sein konnen:
public Dokument durchsuchen(String titel) { for (Dokument dok: this.dokumente) {
if (dok.getTitel().equals(titel)) { return dokument;
} }
return null; }
Zum Vergleich die alte Version, ohne Generics:
public Dokument durchsuchen(String titel) { for (Object object: dokumente) {
Dokument dokument = (Dokument) object; if (dokument.getTitel().equals(titel)) {
return dokument; }
}
return null; }
M. Goedicke Programmierung WiSe 2020/2021
7

Die generische verkettete Liste
Generics sind ein wesentlicher Bestandteil der Java Klassenbibliothek, viele der vordefinierten Klassen und Interfaces machen davon starken Gebrauch.
Zwei Beispiele sind die Interfaces Comparable und Comparator, die wir beim Sortieren von Objekten kennengelernt haben:
public class OrdnerComparator implements Comparator {
@Override
public int compare(Ordner o1, Ordner o2) { // TODO Ordner vergleichen
return result;
} }
M. Goedicke Programmierung WiSe 2020/2021
8

Die generische verkettete Liste: Spezifikation von geforderten Typ-Parameter-Eigenschaften
Haufig werden Eigenschaften fur die Typ-Parameter gefordert.
Zwei Beispiele sind die Interfaces Comparable und Comparator,
werden fur das Suchen und Sortieren benotigt :
public class List > {

T current = head

current.compareTo()
}
M. Goedicke Programmierung WiSe 2020/2021
9

Eine (kleine) Anzahl von Moglichkeiten und
Einschrankungen fur generische Klassen gibt es in
Java
Wildcard upperbound: class Structure{}
> Mogliche aktuelle Parameter mussen Unterklassen von SomeClassOrInterface sein
Wildcard lowerbound: class Structure{}
> Mogliche aktuelle Parameter mussen Oberklassen von SomeClassOrInterface sein.
Eine Reihe von Einschrankungen gelten:
Siehe http://docs.oracle.com/javase/tutorial/java/generics/restrictions.html Primitive Typen (int,) konnen nicht als Typen fungieren stattdessen
(Integer,)
Keine Arrays von Parameter-Typen
M. Goedicke Programmierung WiSe 2020/2021
10

Die verkettete Liste: Klassenbibliothek
Die Java Runtime Environment (JRE) enthalt eine Klassenbibliothek, die viele Klassen und Interfaces bereitstellt:
Die Programmierbibliothek enthalt Klassen fur die Entwicklung von Benutzeroberflachen, Datenbank- und Netzwerkverbindungen, verteilten Anwendungen, usw.
Im Paket java.util befinden sich u. a. dynamische Datenstrukturen. Insbesondere stellt die Klassenbibliothek eine (doppelt) verkettete Liste
bereit.
M. Goedicke Programmierung WiSe 2020/2021
11

Die verkettete Liste: Klassenbibliothek
interface
Iterable
im Paket java.lang
interface
Collection
interface
Queue
interface
List
interface
Deque
AbstractList
AbstractSequentialList
ArrayList
Vector
LinkedList
doppelt verkettete Liste
M. Goedicke Programmierung WiSe 2020/2021
12

Die verkettete Liste: Klassenbibliothek
Wenn eine Klasse das Iterable-Interface implementiert, dann konnen die Instanzen dieser Klassen in einer foreach-Schleife verwendet werden und wir verstehen nun, wie das Iterable-Interface typsicher eingesetzt werden kann.
List liste = new LinkedList ();
for (int i = 0; i < 10; i++) { liste.add(i);}for (Integer i : liste) {Jeder primitive Datentyp hat in Java auch einen entsprechenden Referenztypen fur int ist dies die Klasse Integer. Die Umwandlung kann automatisch erfolgen, dies nennt man Autoboxing. }System.out.println(i);List liste = new LinkedList(); for (int i = 0; i < 10; i++) {liste.add(i); }Iterator iterator = liste.iterator(); while (iterator.hasNext()){System.out.println(iterator.next()); }interfaceIterable iterator():Iterator interfaceIterator hasNext():boolean next():Object remove():voidM. Goedicke Programmierung WiSe 2020/202113 Die verkettete Liste: Klassenbibliothek Das Collection-Interface definiert die Grundfunktionalitat der meisten Datenstrukturen im Paket java.util. Das List-Interface definiert die speziellen Eigenschaften einer Liste. Ein anderer Datentyp ist z.B. java.util.Set.Darstellung fur Generics in UML interfaceCollectionE+add(E):boolean +addAll(Collection):boolean +clear():void +contains(Object):boolean +containsAll(Collection):boolean +isEmpty():boolean +remove(Object):boolean +removeAll(Collection) +size():int… interfaceListE+add(E):boolean +add(int, E):boolean +get(int):E +indexOf(Object):int +remove(Object):boolean +set(int, E):E… M. Goedicke Programmierung WiSe 2020/202114 Die verkettete Liste: Klassenbibliothek Das Queue-Interface und das Deque-Interface definieren Eigenschaften einer Queue (s. spater), die als Sonderfall einer verketteten Liste betrachtet werden kann. Die Klassen AbstractList und AbstractSequentialList implementieren v.a. solche Methoden, die einen Spezialfall einer anderen Methode darstellen. Beispielsweise wird die Methode add(Object) durch einen Aufruf von add(size(), Object) implementiert. ArrayListE+ArrayList() +ArrayList(int) … Die Klasse ArrayList implementiert das List-Interface mit Hilfe eines Arrays. Wenn man den Konstruktor ArrayList(int) verwendet, dann kann man die initiale Groe des Arrays festlegen (die sich mit der Zeit aber andern kann).M. Goedicke Programmierung WiSe 2020/202115 Die verkettete Liste: Klassenbibliothek Die Klasse LinkedList realisiert das List-Interface durch eine doppelt verkettete Liste. Die beiden Listentypen unterscheiden sich in zentralen Aspekten: Der Zugriff auf die Elemente ist bei einer ArrayList schneller als beieiner LinkedList . Dagegen sind Einfuge- und Loschoperationen bei einer ArrayListaufwendiger als bei einer LinkedList.36 1 2 3 4 5 1 2 M. Goedicke Programmierung WiSe 2020/202116 Die verkettete Liste: Klassenbibliothek Wenn man die Klassen des Pakets java.util verwenden mochte, dann muss man sie importieren:import java.util.List; import java.util.LinkedList;public class Test { …}import java.util.*; public class Test {… } Die Klasse java.util.Collections enthalt Klassenmethoden, die zusatzliche Operationen auf Listen realisieren: binare Suche, Sortieren, Bestimmung von Minimum und Maximum, usw. Die meisten Operationen setzen allerdings voraus, dass die Elemente der Liste das Comparable-Interface implementieren.M. Goedicke Programmierung WiSe 2020/202117 Die verkettete Liste: Klassenbibliothek main()-Methode List liste = new LinkedList (); for (int i = 10; i > 0; i) {
liste.add(i);
}
for (Integer i : liste) { System.out.print([ + i + ]->);
}
System.out.println(); Collections.sort(liste); for (Integer i : liste) {
System.out.print([ + i + ]->); }
Die Wrapper-Klasse Integer des primitiven Datentyps int implementiert das Comparable-Interface.
Konsole
[10]->[9]->[8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]-> [1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->[10]->
M. Goedicke Programmierung WiSe 2020/2021
18

Die verkettete Liste: Klassenbibliothek
Wenn man eine Liste mit Hilfe einer Schleife durchlauft, dann fuhren Einfuge- und Loschoperationen im Schleifenrumpf manchmal zu unerwarteten Ergebnissen:
main()-Methode
List liste = new ArrayList (); for (int i = 1; i <= 10; i++) {liste.add(i);}for (int i = 0; i < liste.size(); i++) { System.out.print([ + liste.get(i) + ]->); liste.remove(0);
}
Konsole
[1]->[3]->[5]->[7]->[9]->
M. Goedicke Programmierung WiSe 2020/2021
19

Die verkettete Liste: Klassenbibliothek
List liste = new ArrayList (); for (int i = 0; i <= liste.size(); i++) {liste.add(i);}Endlosschleife Wenn man eine Liste mit Hilfe eines Iterators durchlauft, dann fuhren Anderungen an der Liste zu einem Laufzeitfehler allerdings nicht zu einem Kompilierfehler!List liste = new ArrayList (); liste.add(1);
for (Integer i: liste) {
liste.add(1);
}
Laufzeitfehler: ConcurrentModificationException
M. Goedicke Programmierung WiSe 2020/2021
20

Map
Das Interface Map dient zur Speicherung von Schlussel-Wert- Paaren. Hierbei werden eindeutig Schlusselobjekte vom Typ K (key) auf Wertobjekte vom Typ V (value) abgebildet.
Das Interface bietet unter anderem Operationen zum Einfugen, Auslesen und Loschen von Schlussel-Wert-Paaren.
Die Schlusselobjekte mussen eindeutig sein. Duplikate von Schlusselobjekten sind nicht erlaubt.
Das Interface ist in dem Paket java.util.Map enthalten. Es gibt mehrere Implementierungen des Interfaces. Neben anderen sind diese:
HashMap (java.util.HashMap) TreeMap (java.util.TreeMap)
M. Goedicke Programmierung WiSe 2020/2021
21

Map
HashMap
BieteteinenschnellenZugriffaufdieObjekteanhandeines
Hashwertes
Die Klasse der Schlusselobjekte sollte die Methoden hashCode() und equals(), welche von Objekt geerbt werden, sinnvoll uberschreiben.
Es gibt keine Garantie uber die Reihenfolge in welcher die Schlussel-Werte Paare in der HashMap abgelegt werden. Diese kann sich wahrend der Laufzeit andern.
M. Goedicke Programmierung WiSe 2020/2021
22

Map
TreeMap
DerZugriffaufdieSchlussel-WertPaareistlangsameralsbei
der HashMap.
Bietet aber eine eindeutige Sortierung der Schlusselwerte.
Die Schlusselobjekte mussen entweder das Interface Comparable implementieren oder der TreeMap muss ein Comparator ubergeben werden.
M. Goedicke Programmierung WiSe 2020/2021
23

Map Hashwert
Die Hashfunktion muss einen int-Wert zuruckgeben. Viele Java- Klassen enthalten bereits eine eigene Hashfuktion z.B. String.
Fur eigene Klassen sollte die Methode hashCode() uberschrieben werden. In der Regel wird der Hashwert als Funktion uber die Klassenattribute gebildet. Dies kann zum Beispiel mit der Methode: Objects.hash(Object values) erreicht werden.
M. Goedicke Programmierung WiSe 2020/2021
24

Map Auszug von Methoden der Map
V put (K key, V value)
Fugt value in Map unter Schlussel key ein
Gibt den Wert des unter key gespeicherten Objektes zuruck
V remove (Object key)
Entfernt Objekt, das unter key abgelegt ist
Gibt den Wert zum geloschten Schlussel zuruck
V get(Object key)
Gibt Wert-Objekt zum dazugehorigen key zuruck
int size()
Anzahl der Schlussel-Wert-Paare in Map
Set keySet()
Gibt Menge aller Schlussel zuruck (Schlussel einzigartig, daher
Set)
Collection values()
Gibt Menge aller Werte zuruck (inkl. Duplikate, daher Collection statt Set)
M. Goedicke Programmierung WiSe 2020/2021
25

Map Auszug von Methoden der Map
M. Goedicke Programmierung WiSe 2020/2021
26