Generische Typen in Java

Martin Wirsing

in Zusammenarbeit mit
Moritz Hammer und Axel Rauschmayer

SS 06
Informatik II, SS 06 2

Ziele

ƒ Exkurs: Wrapper-Klassen für Grundatentypen kennen lernen

ƒ Verstehen von parametrischer Typ-Polymorphie in Java
ƒ Die Kollektionshierarchie kennen lernen

M. Wirsing: Generische Typen in Java

Informatik II, SS 06 3

Exkurs: Grunddatentypen und ihre Klassen

ƒ Zu jedem Grunddatentyp gibt es eine korrespondierende Klasse:
Wrapper-Klasse Primitiver Typ
Integer int
Double double
Boolean boolean
Character char
ƒ Autoboxing:
Java unterstützt die automatische Konversion zwischen prim. Typ und Klasse.
Beispiel:
Integer j1 = new Integer(1906);
int i = 1906;
[Link]([Link](j1)); //true
Integer j = i;
[Link](j == j1); //false
int k = j;
int k1 = j1;
[Link](k == k1); //true
ƒ Achtung:
Durch Klassen werden neue Objekte erzeugt
=> hoher Speicherplatzverbrauch
„==„ auf Klassen vergleicht Objekt-Referenzen; besser „equals“ verwenden!
M. Wirsing: Generische Typen in Java
 Informatik II, SS 06 4

Realisierung von Typ-Polymorphie in alten Java-Versionen

ƒ Bis Java 1.4 wurde Typ-Polymorphie durch Vererbung von der Klasse Object
realisiert.
ƒ Beispiel: Eine Container-Klasse zur Aufnahme von Objekten verschiedener Typen

public class OldBox { public class TestOldBox {

private Object contents; public static void main(String[] args){

OldBox b1 = new OldBox("Apple");
public OldBox(Object cont) {
String s = (String) [Link]();
contents = cont;}
[Link](s);
public Object getContents() {
return contents;} OldBox b = new OldBox(new Integer(3));
int i = (Integer) [Link]();
public void setContents
[Link](s);
(Object o) {
}
contents = o;}
} Typüberprüfung
} zur Laufzeit

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 5

(Einfache) Realisierung mit generischen Typen

ƒ Ab Java 1.5 kann Typ-Polymorphie parametrisch durch (formale) Typparameter

realisiert werden (parametrische Polymorphie – eine Art universelle Polymorphie).
ƒ Beispiel: Eine Klasse zur Aufnahme von genau einem Objekt
Typvariable
public class Box <T> { public static void main(String[] args){
Box<String> b =
private T contents; new Box<String>("Apple");
String s = [Link]();
public Box(T cont) { [Link](s);
contents = cont;}
Box<Integer> b1 =
public T getContents() { new Box<Integer>(new Integer(3));
return contents;} int i = [Link]();
[Link](i);
public void setContents(T o) { }
contents = o;} } Aktueller Typparameter:
Typüberprüfung zur
Übersetzungszeit!
M. Wirsing: Generische Typen in Java
 Informatik II, SS 06 6

Geschichtliches: Generische Typen in Java

ƒ 1997: Martin Odersky, Philip Wadler: Pizza.
In: Principles of Programming Languages Conference, POPL 97.
„Eine funktionale Spracherweiterung von Java mit generischen Typen“
ƒ 1998: Gilad Bracha, Martin Odersky, David Stoutamire, and Philip Wadler. Making the
future safe for the past: Adding Genericity to the Java Programming Language,
OOPSLA 98, Vancouver, October 1998.
„Beschreibt Generic Java (GJ) als Weiterentwicklung von Pizza“
ƒ September 2004: Tiger Release Java 1.5 mit generischen Typen basierend auf GJ.

Wadler, Odersky, Bracha, Stoutamire Und von hinten: Making Java easier to type,
M. Wirsing: Generische Typen in Java
and easier to type
 Informatik II, SS 06 7

Generische Typen: Syntax

ƒ Deklaration einer generischen Klasse:
class <<Klassenname>> < <<Liste von Typvariablen>> >
ƒ Instantiierung eines generischen Typs:
<<Klassenname>> < <<Liste von Typausdrücken>> >
ƒ Beispiele für Instantiierungen von Box<T>:
Box<String>
Box<Integer>
Box<Box<String>> //Geschachtelter Typausdruck
Box<int> //unzulässig,Grunddatentypen nicht erlaubt als Typparameter
Box<String, String> //unzulässig, zu viele Parameter

ƒ Beispiel Box: Erweitere z.B. TestBox1 um:

Box<Box<String>> bb = new Box<Box<String>>(b);
Box<String> b1 = [Link]();
String s1 = [Link]();
[Link](s1);

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 8

Einfache generische Methoden

ƒ Deklaration einer generischen Methode:
< <<Liste von Typvariablen>> > <<Ergebnistyp>> <<Name>> ( <<Parameterliste>> )
ƒ Methodenaufruf einer generischen Methode (wie bisher):
<<Name>> ( <<Liste von aktuellen Parametern>> )

ƒ Beispiel: Eine Methode, die zufällig ein Ergebnis wählt

public class Random {
public static <T> T zufall(T m, T n) {
return [Link]() > 0.5 ? m : n;
}
}

ƒ Beispiel Methodenaufrufe:
String s = [Link]("Essen", "Schlafen");
int i = [Link](100, 50);

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 9

Übersetzung von generischen Typen

Zwei Möglichkeiten zur Übersetzung von generischen Datentypen:
ƒ Heterogene Übersetzung.
Für jede Instantiierung (etwa Box<String>, Box<Integer>, Box<Point>) wird individueller
Code erzeugt, also drei Klassen.
ƒ Homogene Übersetzung.
Für jede parametrisierte Klasse (etwa Box<T>) wird genau eine Klasse erzeugt, die die
generischen Typinformationen löscht („type erasure“) und die Typparameter durch die Klasse
Object ersetzt. Für jeden konkreten Typ werden zusätzlich Typanpassungen in die
Anweisungen eingebaut.

Java nutzt die homogene Übersetzung, (C++ die heterogene):

¾ Weniger erzeugter Code, Möglichkeit der Übersetzung nach “Old” Java ohne generische Typen,
¾ Aber geringere Ausdrucksmächtigkeit der Typüberprüfung (zur Compilezeit)

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 10

Übersetzung von generischen Typen

Beispiel: Box<T> wird übersetzt in (die von OldBox bekannte Version) :
public class Box {
private Object contents;

public Box(Object cont) {

contents = cont;
}

public Object getContents() {

return contents;
}
. . .

public static void main(String[] args){

Box b = new Box("Apple"); ! Das ist eine (gute) Approximation.
String s = (String) [Link](); In Wirklichkeit wird aber direkt in
[Link](s);
Bytecode übersetzt!
}
}
M. Wirsing: Generische Typen in Java
 Informatik II, SS 06 11

Zusammenhang mit nichtgenerischen Typen

Generische Klassen können auch ohne Typparameter verwendet werden; damit können sie mit „altem“
Programmcode zusammen arbeiten.
ƒ Ein parametrisierter Typ ohne Typangabe heißt Raw-Type. Raw-Types bieten die gleiche
Funktionalität wie parametrisierte Typen,
ƒ Allerdings werden die Parametertypen nicht zur Compilezeit überprüft, was zu Problemen führen
kann.
ƒ Beispiel: Der Raw-Type von Box<T> ist Box.
Box<String> sBox = new Box<String>(„apple“);
Box oBox = new Box(); //Jede Parametertypinformation fehlt
oBox = sBox;
[Link]( new Integer(3) ); // Warnung vor Unsafe type operation
//Eclipse schlägt Restrukturierung („Refactoring“) mit
//„infer generic type arguments“ vor.
//Denn:
[Link]( [Link]() ); // führt zu ClassCastException

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 12

Vererbung und Generische Typen

ƒ Von generischen Klassen lassen sich in gewohnter Weise Unterklassen ableiten.
ƒ Diese Unterklassen können, aber müssen nicht selbst generische Klassen sein.
ƒ Beispiel: Generische Klasse als Erbe:
public class Pair<E, S> extends Box<E> {
private S secondContent;

public Pair(E first, S second) {

super(first); [Link] = second; }

public S getSecondContent() { . . . }
public void setSecondContent(S second) {. . .}
}
ƒ Beispiel Nichtgenerische Klasse als Erbe:
class StringBox extends Box<String> {
public StringBox(String s) {super(s);}
}

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 13

Vererbung und Generische Typen

ƒ Aber: Vererbung bei Parametertypen induziert NICHT
Vererbung der generischen Typen!

ƒ Beispiel: Ist eine Box von Strings auch eine Box von Objects?
Box <String> ls = new Box<String>(…);
Es wird versucht,
Box <Object> lo;
einem String ein
lo = ls; //Typfehler!
Object zuzuweisen!
[Link](new Object());
String s = [Link](); //würde zu ClassCastException führen

ƒ Regel:
Ist Foo Subtyp (Subklasse oder Subinterface) von Bar und G ist eine generische
Deklaration,
so ist G<Foo> kein Untertyp von G<Bar> !

Aus dem Java Tutorial (G. Bracha): „This is probably the hardest thing you need to
learn about
M. Wirsing: Generische Typen ingenerics,
Java because it goes against our deeply held intuitions.“
 Informatik II, SS 06 14

Einschränkung von Typvariablen

Mit
<<Typvariable>> extends <<Typausdruck>>
ist es möglich nur solche Typparameter zuzulassen, die Erben von <<Typausdruck>> sind.

Beispiel: FruitBox enthält nur Früchte (Erben von Fruit)

public class Apple extends Fruit{}
public class Steak {}
public class FruitBox <T extends Fruit>{
<< analog Box<T> >>
public static void main(String[] args) {
Apple a1 = new Apple();
Steak s1 = new Steak();

FruitBox<Apple> aBox = new FruitBox<Apple>(a1); //ok

FruitBox<Steak> sBox =
new FruitBox<Steak>(s1);//Compilezeitfehler:Bound Mismatch
}
}
M. Wirsing: Generische Typen in Java
 Informatik II, SS 06 15

Generische Klassen in UML

Eine generische Klasse
C<T> bzw. C<T extends D>
Repräsentieren wir in UML durch einen kleinen Kasten in der rechten oberen Ecke der
Klasse C, in dem die Typvariable (mit Angabe der Beschränkung) steht.

T T < D
C C
bzw.

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 16

Platzhalter (Wildcards)
ƒ Problem:
Beim Drucken von FruitBox stoßen wir auf ein Problem:
public static void fruitBoxPrint( FruitBox<Fruit> f) {
[Link](f); }
druckt nur Objekte der Klasse FruitBox<Fruit>,
da z.B. FruitBox<Apple> keine Unterklasse von FruitBox<Fruit> ist.
ƒ Lösung: Der Platzhalter (Wildcard, Joker) “?” erlaubt mit
<<Klassenname>> <?>
die Verwendung beliebiger (korrekter aktueller) Typen für “?”
ƒ Beispiel: Der Platzhalter “?” erlaubt das Drucken beliebiger Früchteschachteln
public static void fruitBoxPrint( FruitBox<?> f){
[Link](f);}
public static void main(String[] args) {
FruitBox<Apple> aBox = new FruitBox<Apple>(new Apple);
fruitBoxPrint(aBox);

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 17

Beschränkte Platzhalter (Bounded Wildcards)

ƒ Der beschränkte Platzhalter (Wildcard, Joker)
<<Klassenname>> <? extends <<Typausdruck>> >
beschränkt die Verwendung auf Subtypen von <<Typausdruck>>

ƒ Beispiel: Drucken von Früchteschachteln mit Box<T>

public static void fruitBoxPrint1(Box<? extends Fruit> f){
[Link](f);}
public static void main(String[] args) {
Box<Apple> aBox = new Box<Apple>(new Apple);
fruitBoxPrint1(aBox);

ƒ Analog: Der beschränkte Platzhalter (Wildcard, Joker)

<<Klassenname>> <? super <<Typausdruck>> >
beschränkt die Verwendung auf Obertypen von <<Typausdruck>>

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 18

Generische Methoden vs. Platzhalter

ƒ Wann benutzt man generische Methoden, wann Platzhalter?
ƒ mit Platzhalter:
public static void fruitBoxPrint1(Box<? extends Fruit> f){
[Link](f);}
ƒ als generische Methode:
public static <T extends Fruit> void fruitBoxPrint2(Box<T> f){
[Link](f);}

ƒ Benutzung von Platzhaltern, wenn:

ƒ der Typparameter T wird nur einmal benutzt wird,
ƒ der Typ des Rückgabewertes nicht von T abhängt,
ƒ kein anderes Argument der Methode von T abhängig ist,
ƒ Das Typ-Argument für Typ-Polymorphie verwendet wird,
d.h. dass verschiedene Argumenttypen erlaubt sind.

ƒ Platzhalter für Typ-Polymorphie – mit Subtyping.

ƒ Generische Methoden verwenden, um Abhängigkeiten zwischen Argumenttypen und/oder
Rückgabetypen einer Methode herzustellen.
M. Wirsing: Generische Typen in Java
 Informatik II, SS 06 19

Wann braucht man generische Methoden

ƒ Bei Abhängigkeiten zwischen Argument- und Resultattyp
Beispiel :
public static <T> T trace(T t){
[Link](t);
return t;
}

ƒ Bei Abhängigkeiten zwischen zwei oder mehr Argumenttypen

Beispiel :
public static <T> void toBox(T t, Box<T> b){
[Link](t);
}

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 20

Eine erste Zusammenfassung

ƒ Zu jedem Grunddatentyp gibt es eine korrespondierende Wrapper Klasse
ƒ Java unterstützt die automatische Konversion zwischen prim. Typ und Klasse.

ƒ Ab Java 1.5 kann Typ-Polymorphie parametrisch durch (formale) Typparameter realisiert

werden (parametrische Polymorphie).
ƒ Generische Klassen und generische Methoden haben Typvariablen als Parameter.
Ihre Instantiierungsmöglichkeiten können durch Subtyp-Anforderungen
eingeschränkt sein.
ƒ Vererbung von aktuellen Parametern induziert NICHT die Vererbung der
generischen Typen.
ƒ Generische Klassen werden “homogen” übersetzt:
Für jede parametrisierte Klasse (etwa Box<T>) wird genau eine Klasse erzeugt,
die die generischen Typinformationen löscht („type erasure“) und die Typparameter
durch die Klasse Object ersetzt. Für jeden konkreten Typ werden zusätzlich
Typanpassungen in die Anweisungen eingebaut.

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 21

Das Collection Framework

ƒ Das Collection Framework ist ein System von generischen Schnittstellen und Klassen
zur Darstellung mengenartiger Datentypen.
Ein Collection Objekt fasst
Eine Menge ist eine Collection, für endlich viele Elemente
deren Elemente KEINE Duplikate E
<<interface>> gleichen Typs zu
zugelassen sind. Collection einer Gruppe zusammen.

E E
<<interface>> <<interface>>
Set List

E E E E
HashSet <<interface>> ArrayList LinkedList
SortedSet
Eine Liste ist eine geordnete
E Collection, in der Elemente
Aufsteigend geordnete TreeSet auch mehrfach vorkommen
Listen ohne Duplikate
können.

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 22

Das Collection Framework

ƒ Das Collection Framework ist ein System von generischen Schnittstellen und Klassen
zur Darstellung mengenartiger Datentypen.

E
<<interface>>
Collection

E E
<<interface>> <<interface>>
Set List

E E E E
HashSet <<interface>> ArrayList LinkedList
SortedSet

E Implementiert List Implementiert List

TreeSet mit Hilfe von Reihungen durch (doppelt)
Implementiert Set verkettete Listen.
durch Hashtabellen Implementiert SortedSet
durch geordnete Bäume
M. Wirsing: Generische Typen in Java
 Informatik II, SS 06 23

Die Schnittstelle Collection

Das
interface Collection<E> extends Iterable
bietet u.a. folgende Methoden an:
ƒ boolean add( E o )
Fügt dem Container ein Element hinzu und gibt true zurück, falls sich das Element einfügen lässt.
Gibt false zurück, wenn schon ein Objekt gleichen Werts vorhanden ist und doppelte Werte nicht
erlaubt sind.
ƒ boolean addAll( Collection<? extends E> c )
Fügt alle Elemente der Collection c dem Container hinzu.
ƒ boolean contains( Object o )
Liefert true, falls der Container ein inhaltlich gleiches Element enthält.
ƒ boolean containsAll( Collection<?> c )
Liefert true, falls der Container alle Elemente der Collection c enthält.
ƒ boolean isEmpty() Liefert true, falls der Container keine Elemente enthält.
ƒ Iterator<E> iterator() Liefert ein Iterator-Objekt über alle Elemente des Containers.
ƒ boolean remove( Object o )
Entfernt das angegebene Objekt aus dem Container, falls es vorhanden ist.
M. Wirsing: Generische Typen in Java
 Informatik II, SS 06 24

Die Schnittstelle List und eine Implementierung

ƒ Das Schnittstelle
interface List<E> extends Collection<E>
spezifiziert, dass die geerbten Methoden add und addall Elemente am Ende der Liste einfügen
und dass remove das erste Element entfernt.
Weitere Operationen sind u.a.:
ƒ void add( int index, E element )
Fügt ein Objekt an der angegebenen Stelle in die Liste ein.
ƒ E get( int index ) liefert das Element an der angegebenen Stelle der Liste

ƒ Die Klassen
class ArrayList<E>
class LinkedList<E> (siehe spätere Vorlesung)
implementieren List<E> .

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 25

Eine Anwendung von List

…
import [Link].*;
public class CollectionInfo {

/** Methode zur Ausgabe von Infos über eine Integer Collection */
public static void printInfo(Collection<Integer> c) {
[Link]("Die Menge enthält " + [Link]() + " Elemente.");
[Link]("Ist 0 in der Menge? " + [Link](new Integer(0)));
[Link]("Ist 17 in der Menge? " + [Link](17));

[Link]("Alle Elemente: ");

for(Integer x : c)[Link](x);
}
/**bildet Liste aus den Eingaben der Kommandozeile und druckt dafür Infos*/
public static void main(String[] args) {
List<Integer> l = new ArrayList<Integer>();
for(String k : args)
[Link]([Link](k));
printInfo(l); // Infos ueber die Liste der Eingaben
}
}
M. Wirsing: Generische Typen in Java
 Informatik II, SS 06 26

Die Schnittstelle Set und eine schnelle Implementierung

ƒ Das Schnittstelle
interface Set<E> extends Collection<E>
spezifiziert, dass die geerbten Methoden add und addall keine Elemente zusätzlich aufnehmen,
die schon vorhanden sind.
Für Set-Objekte u,v entspricht
ƒ [Link](v) der Mengenvereinigung,
ƒ [Link](v) dem Mengendurchschnitt, Konstante Zeitkompl. für
add, remove, contains
ƒ [Link](v) der Mengendifferenz u\v .

ƒ Die Klasse
class HashSet<E>
implementiert u.a. Set<E> mit einer schnellen Hash-basierten Datenstruktur.
ƒ Konstruktoren sind:
ƒ HashSet()
Erzeugt ein neues HashSet-Objekt mit 16 freien Plätzen und einem Füllfaktor von 0,75.
ƒ HashSet( Collection<? extends E> c )
Erzeugt ein neues HashSet aus der Menge c gegebener Elemente.

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 27

Eine Anwendung von Set

Um Mengen (ohne Duplikate) zu betrachten, kann man die HashSet-Implementierung von
Set verwenden:
...
Set<Integer> s = new HashSet<Integer>();
for(String k : args)
[Link]([Link](k));
printInfo(s); // Infos ueber die Menge ohne Duplikate

M. Wirsing: Generische Typen in Java

 Informatik II, SS 06 28

Nochmals Vererbung und Generische Typen

ƒ Vererbung bei Parametertypen induziert NICHT
Vererbung der generischen Typen!

ƒ Beispiel: Ist eine Liste von Strings auch eine Liste von Objects?

List <String> ls= new ArrayList<String>();

List <Object> lo; Es wird versucht,
lo = ls; einem String ein
[Link](new Object()); Object zuzuweisen!
String s = [Link](0);

ƒ Nochmals Regel:
Ist Foo Subtyp (Subklasse oder Subinterface) von Bar und G ist eine generische
Deklaration,
so ist G<Foo> kein Untertyp von G<Bar> !
M. Wirsing: Generische Typen in Java
Informatik II, SS 06 29

Zusammenfassung
ƒ Das Collection Framework ist ein System von generischen
Schnittstellen
und Klassen zur Darstellung mengenartiger Datentypen.
ƒ Collection ist die Basisschnittstelle, sie wird von der Listenschnittstelle
List und der Mengenschnittstelle Set erweitert.
ƒ Listen-Implementierungen sind ArrayList und LinkedList;
Mengen-Implementierungen sind HashSet und TreeSet.

M. Wirsing: Generische Typen in Java