3 $ #2 ( 4)st.inf.tu-dresden.de/files/teaching/ss12/swt/Vorlesungen/22-st...6 #$ $ ' #$ Bestellung kunde: String anzahl: int liste java.util.ArrayList add(Object o) get(pos: int):

Softwaretechnologie, © Prof. Uwe AßmannTechnische Universität Dresden, Fakultät Informatik 1

"Der Aufrufer programmiert gegen die Schnittstelle,er befindet sich sozusagen im luftleeren Raum."

Siedersleben/Denert,Wie baut man Informationssysteme,Informatik-Spektrum, August 2000

"Der Aufrufer programmiert gegen die Schnittstelle,er befindet sich sozusagen im luftleeren Raum."

Siedersleben/Denert,Wie baut man Informationssysteme,Informatik-Spektrum, August 2000

22) Programmieren gegen Schnittstellen

► 1 Polymorphe Container durch Schnittstellen► 2 Entwurfsmuster Iterator (Stream)► 3 Auswahl von Implementierungen für

Datenstrukturen► 4 Persistente Datenhaltung

► Version 12-0.3, 13.04.12

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

2

Schnittstellen und Implementierungen im Collection-Framework

<<interface>>Collection

<<interface>>Map

<<interface>>SortedSet

<<interface>>SortedMap

LinkedList

ArrayList

HashSet

TreeSet

HashMap

TreeMap

<<interface>>Set

<<interface>>List

Vererbung (extends)

Implementierung (implements)

<<interface>>Queue

PriorityQueueVector

Stack

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

3

import java.util.ArrayList;...class Bestellung { private String kunde; private ArrayList liste; private int anzahl = 0;

public Bestellung(String kunde) { this.kunde = kunde; this.liste = new ArrayList(); } public void neuePosition (Bestellposition b) { liste.add(b); } public void loeschePosition (int pos) { liste.remove(pos); }...

Typanpassungen mit Schnittstellen: Geordnete Listen mit ArrayList (1)

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

4

Anwendungsbeispiel mit ArrayList (falsch!)

... public void sonderpreis (int pos, int preis) { liste.get(pos).einzelpreis(preis); } ...

► Compilermeldung:

„Method einzelpreis(int) not found in class java.lang.Object.“

liste.get(pos).einzelpreis(preis);

?ArrayList defi niert auf

BestellpositionObject

Spezialisierung von Object auf Bestellposition?

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

5

Typanpassungen auf Elementtypen

Bestellung– kunde: String

– anzahl: int liste

java.util.ArrayListadd(Object o)

get(pos: int): Object...

1Object

*

Bestell-position

*

Typanpassung (cast):• Operationen der Oberklasse passen immer

auch auf Objekte der Unterklasse• Operationen der Unterklasse auf Objekte einer Oberklasse

anzuwenden, erfordert explizite Typanpassung (dynamic cast):

( Typ ) Objekt

hier: (Bestellposition)liste.get(pos)

Zusicherung: Alle von einem Bestellung-Objektüber die liste-Assoziation erreichbaren Objekte

sind aus der Klasse Bestellposition.

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

6

Anwendungsbeispiel mit ArrayList (2)

public void sonderpreis (int pos, int preis) { ((Bestellposition)liste.get(pos)).einzelpreis(preis); } public int auftragssumme() { int s = 0; for(int i=0; i<liste.size(); i++) s += ((Bestellposition)liste.get(i)).positionspreis(); return s; } public void print () { System.out.println("Bestellung fuer Kunde "+kunde); for(int i=0; i<liste.size(); i++) System.out.println(liste.get(i)); System.out.println("Auftragssumme: "+auftragssumme()); System.out.println(); }}

Online:Bestellung1.java

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

7

Geordnete Collections II -java.util.LinkedList (Auszug)

public class LinkedList implements List { public boolean add (Object o); public boolean remove (Object o); public void clear(); public boolean isEmpty(); public boolean contains (Object o); public int size(); public Object get (int index); public Object set (int index, Object element) public Object remove (int index); public int indexOf (Object o); public void addFirst (Object o); public void addLast (Object o); ...}


Anwendungsbeispielmit LinkedList:


22.1 Polymorphe Container durch Schnittstellen

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

9

Programmieren gegen Schnittstellen-- Polymorphe Container

class Bestellung {

private String kunde; private List liste;

... // Konstruktor sh. nächste Folien

public void neuePosition (Bestellposition b) { liste.add(b); }

public void loeschePosition (int pos) { liste.remove(pos); }

public void sonderpreis (int pos, int preis) { ((Bestellposition)liste.get(pos)).einzelpreis(preis); }

List ist ein Interface,

keine Klasse !

!

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

10

• ArrayList:class Bestellung {

private String kunde; private List liste; public Bestellung(String kunde) { this.kunde = kunde; this.liste = new ArrayList(); } ...

• LinkedList: class Bestellung {

private String kunde; private List liste; public Bestellung(String kunde) { this.kunde = kunde; this.liste = new LinkedList(); } ...

Polymorphe Container:Wechsel der Datenstruktur

List ist ein Interface,

keine Klasse !

!

Code muß beiWechsel derDatenstrukturnur an einerStelle (Konstruktor)geändert werden !

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

11

Standardalgorithmen in der Algorithmenklasse java.util.Collections

► Algorithmenklassen (Hilfsklassen) enthalten Algorithmen, die auf einer Familie von anderen Klassen arbeiten

– Hier: java.util.Collections enthält Algorithmen auf beliebigen Klassen, die das Collection- bzw. List-Interface implementieren

– Bei manchen Operationen ist Ordnung auf Elementen vorausgesetzt.– Achtung: Statische Operationen!

public class Collections {

public static Object max (Collection coll);

public static Object min (Collection coll);

public static int binarySearch(List list, Object key);

public static void reverse (List list);

public static void sort (List list)

...

} Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

12

Prädikat-Schnittstellen (...able Schnittstellen)

► Prädikat-Schnittstellen drücken bestimmte Eigenschaft einer Klasse aus. Sie werden oft mit dem Suffix “able” benannt:

– Iterable– Clonable– Serializable

► Beispiel: geordnete Standarddatentypen (z.B. String oder List) implementieren die Prädikatschnittstelle Comparable:

public interface Comparable {

public int compareTo (Object o);

}

► Resultat ist kleiner/gleich/größer 0:genau dann wenn "this" kleiner/gleich/größer als Objekt o

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

13

Schnittstellen und Klassen (Erweiterung)

Schnittstelle(interface)

Abstrakte Klasse(Konkrete) Klasse

Klassenbegriff

Prädikat-Schnittstelle Algorithmenklasse


22.2 Entwurfsmuster Iterator (Stream)

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

15

Entwurfsmuster Iterator (Implementierungsmuster)► Name: Iterator (auch: Stream, Cursor, Enumeration)

► Problem: Sequentielles, polymorphes Durchlaufen der Elemente eines strukturieren Objekts oder einer Collection.

– Aufzählen der in einem “Behälter” befindlichen Elemente durch Herausziehen (pull) mit Hilfe einer Iteratormethode

– Keine Aussage über die Reihenfolge!

► Lösung:

elements(): Iterator

Container

Element

next()hasNext()

Iterator

ConcreteIterator

{abstract}

<<create>>

pull..

*

Iterator-Methode

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

16

Iterator-Beispiel in der JDK (ArrayList)

1Bestellung– kunde: String

– anzahl: int liste

Object

java.util.ArrayList

add(o: Object)get(pos: int): Object

iterator(): Iterator...

*

<<create>>

<<interface>> java.util.Iterator

hasNext()next()

ConcreteIterator

Aggregate

Element

Iterator

Klassenname nicht bekannt, weil privat

(z.B. ArrayListIterator)

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

17

Iterator-Implementierungsmuster

► Verwendungsbeispiel:

List list;.. Iterator i = list.iterator();while (i.hasNext()) {

doSomeThing(i.next());}

List list;.. Iterator i = list.iterator();while (i.hasNext()) {

doSomeThing(i.next());}

► Vorteile:– Iteratoren und Iteratormethoden erlauben, die Netz-Struktur einer

komplexten Datenstruktur nach außen hin zu verbergen (Geheimnisprinzip)

– Sie erlauben bedarfsgesteuerte Berechnungen (processing on demand, lazy processing), weil sie nicht alle Objekte der komplexen Datenstruktur herausgeben, sondern nur die, die wirklich benötigt werden

– Iteratoren können “unendliche” Datenstrukturen repräsentieren, z.B. die natürlichen Zahlen

► Verwendungsbeispiel:

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

18

Anwendungsbeispiel mit Iteratoren

import java.util.Iterator;...

class Bestellung {

private String kunde; private ArrayList liste;

... public int auftragssumme() { Iterator i = liste.iterator(); int s = 0; while (i.hasNext()) s += ((Bestellposition)i.next()).positionspreis(); return s; } ...}


Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

19

Iterator-Implementierungsmuster in modernen Sprachen

class bigObject { private List subObjects; public iterator Object deliverThem() { while (i in subObjects) {

yield i; } }}

class bigObject { private List subObjects; public iterator Object deliverThem() { while (i in subObjects) {

yield i; } }}

► In vielen Programmiersprachen (Sather, Scala) stehen Iteratormethoden (stream methods) als spezielle Prozeduren zur Verfügung, die die Unterobjekte eines Objekts liefern können

– Die yield-Anweisung gibt aus der Prozedur die Elemente zurück– Iterator-Prozedur kann mehrfach aufgerufen werden– Beim letzten Mal liefert sie null

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

20

For-Schleifen auf Iterable-Prädikatschnittstellen

class BillItem { int price; } class Bill { int sum = 0; private List billItems; public void sumUp() { for (BillItem item: billItems) { sum += item.price; } return sum; }}

class BillItem { int price; } class Bill { int sum = 0; private List billItems; public void sumUp() { for (BillItem item: billItems) { sum += item.price; } return sum; }}

► Erbt eine Klasse von Iterable, kann sie in einer vereinfachten for-Schleife benutzt werden

class BillItem { int price; } class Bill { int sum = 0; private List billItems; public void sumUp() { for (Iterator i = billItems.iterator(); i.hasNext(); ) { item = i.next(); sum += item.price; } return sum; }}

class BillItem { int price; } class Bill { int sum = 0; private List billItems; public void sumUp() { for (Iterator i = billItems.iterator(); i.hasNext(); ) { item = i.next(); sum += item.price; } return sum; }}


22.2.2 Senken (Sinks)

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

22

Entwurfsmuster Senke (Implementierungsmuster)► Name: Senke (auch: Ablage, sink, belt)

► Problem: Ablage eines beliebig großen Datenstromes.– push– ggf. mit Abfrage, ob noch freier Platz in der Ablage

vorhanden

► Lösung:

Client

push()hasFreeSpace()

Sink

ConcreteSink

{abstract}push..

Sink-Methode

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

23

Erweiterung: Begriffshierarchie der Methodenarten

ZustandsinvarianteMethoden

ZustandsveränderndeMethoden

Anfrage (query) CheckerZustands-modifikatoren

Netz-modifikatoren

Methode

Repräsentations-Wechsler

AllgemeineMethoden

Tester

ModifikatorenIteratormethoden

SenkenSoftwaretechnologie, © Prof. Uwe Aßmann

Technische Universität Dresden, Fakultät Informatik 24

22.2.3 Channels (Pipes)

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

25

Entwurfsmuster Channel (Pipe) (Implementierungsmuster)► Name: Channel (auch: pipe, buffer, Kanal)

► Zweck: asynchrone Kommunikation zwischen zwei Komponenten durch Pufferung eines beliebig großen Datenstromes mit Hilfe eines Puffers buffer

– Kombination von push- und pull-Methoden (Strom- und Ablagemethoden)– ggf. mit Abfrage, ob noch freier Platz in der Ablage vorhanden– ggf. mit Abfrage, ob noch Daten im Kanal vorhanden

Client

push()hasFreeSpace()

Channel

ConcreteChannel

push ofsink..

next()hasNext()

pull of stream..

- buffer

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

26

Channels in anderen Sprachen

► Channels (pipes) kommen in vielen Sprachen als Konstrukte vor■ Shell-Skripte (Operator für pipes: “|”)■ Communicating Sequential Processes (CSP, Hoare):

♦ Operator für push: “?”

♦ Operator für pull: “!”

■ Architectural Description Languages (ADL, Kurs CBSE)

► Sie sind ein elementares Muster für die Kommunikation von parallelen Prozessen (producer-consumer-Muster)


22.3 Auswahl von Implementierungenvon Datenstrukturen

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

28

Weitere Implementierungen in der Collection-Hierarchie


<<interface>>Set


<<interface>>List

<<interface>>Map


LinkedList

ArrayList

TreeSet

HashSet

TreeMap

HashMap

Vererbung (extends)


Vector Hashtable

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

29

Welche Listen-Implementierung soll man wählen?

► Innere Schleifen bilden die „heißen Punkte“ (hot spots) eines Programms

– Optimierung von inneren Schleifen durch Auswahl von Implementierungen mit geeignetem Zugriffsprofil

► Gemessener relativer Aufwand für Operationen auf Listen:(aus Eckel, Thinking in Java, 2nd ed., 2000)

– Stärken von ArrayList: wahlfreier Zugriff– Stärken von LinkedList: Iteration, Einfügen und Entfernen irgendwo in

der Liste– Vector generell die langsamste Lösung

Typ Lesen Iteration Einfügen Entfernen

array 1430 3850 -- --

ArrayList 3070 12200 500 46850

LinkedList 16320 9110 110 60

Vector 4890 16250 550 46850

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

30

Collection Framework (Überblick)(Mengen ohne Mehrfacheintrag)


<<interface>>Set


<<interface>>List

<<interface>>Map


LinkedList

ArrayList

TreeSet

HashSet

TreeMap

HashMap

Vererbung (extends)


Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

31

Ungeordnete Mengen: java.util.Set (Auszug)

// Query methods+ Object get(int index);

// Zustandsveränderer+ boolean add (Object o);

<<interface>>Set

// Query methods+ boolean isEmpty();+ boolean contains(Object o);+ boolean equals(Object o);+ int hashCode();+ Iterator iterator();

// Repräsentations-Trans-// formierer+ Object[] toArray();

// Zustandsveränderer+ boolean add (Object o);+ boolean remove (Object o);+ void clear();


Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

32

Anwendungsbeispiel für Set

Artikel– name: String

– preis: int

+ preis(): int

Warengruppe– name: String

– lagerplatz: String

*

1

+ add (a: Artikel)+ anzahl(): int

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

33

java.util.HashSet (Auszug)

(Anmerkung: Erläuterung von Hashfunktionenfolgt etwas später !)



<<interface>>Set// Query methods

+ boolean isEmpty();+ boolean contains(Object o);+ boolean equals(Object o);+ int hashCode();+ Iterator iterator();




// Konstruktor# HashSet(int initialCapacity,float loadFactor);+ Object get(int index);+ int hashCode()


<<interface>>HashSet

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

34

Anwendungsbeispiel mit HashSet

class Warengruppe { private String name; private String lagerplatz; private Set inhalt;

public Warengruppe (String name, String lagerplatz) {

this.name = name; this.lagerplatz = lagerplatz; this.inhalt = new HashSet(); }

public void add (Artikel a) { inhalt.add(a); }

public int anzahl() { return inhalt.size(); }

public String toString() { String s = "Warengruppe "+name+"\n"; Iterator it = inhalt.iterator(); while (it.hasNext()) { s += " "+(Artikel)it.next(); }; } }

Online:Warengruppe0.java

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

35

Duplikatsprüfung für Elemente in Mengen:Wann sind Objekte gleich? (1)

► Vergleich mit Operation == :

– Referenzgleichheit, d.h. physische Identität der Objekte

– Typischer Fehler: Stringvergleich mit "=="(ist nicht korrekt, geht aber meistens gut!)

► Vergleich mit o.equals():

– deklariert in java.lang.Object

– überdefiniert in vielen Bibliotheksklassen ● z.B. java.lang.String

– für selbstdefinierte Klassen ● Standardbedeutung Referenzgleichheit

● bei Bedarf selbst überdefinieren !

(Ggf. für kompatible Definition der Operation o.hashCode() aus java.lang.Object sorgen) Online:

Warengruppe1.java

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

36

Wann sind Objekte gleich? (2)Referenzgleichheit

public static void main (String[] args) { Warengruppe w1 = new Warengruppe("Moebel","L1"); w1.add(new Artikel("Tisch",200)); w1.add(new Artikel("Stuhl",100)); w1.add(new Artikel("Schrank",300)); w1.add(new Artikel("Tisch",200)); System.out.println(w1);}

Systemausgabe beim Benutzen der Standard-Gleichheit:

Warengruppe MoebelTisch(200) Tisch(200) Schrank(300) Stuhl(100)


Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

37

Wann sind Objekte gleich? (3)Referenzgleichheit

public static void main (String[] args) { Artikel tisch = new Artikel("Tisch",200); Artikel stuhl = new Artikel("Stuhl",100); Artikel schrank = new Artikel("Schrank",300); Warengruppe w2 = new Warengruppe("Moebel","L2"); w2.add(tisch); w2.add(stuhl); w2.add(schrank); w2.add(tisch); System.out.println(w1);}

Systemausgabe:

Warengruppe MoebelSchrank(300) Tisch(200) Stuhl(100)

Es wurde zweifach dasselbe Tisch-Objekt übergeben ! (Gleiches Verhalten bei Strukturgleichheit, s. Warengruppe1.java) P

rof.

U. A

ßm

an

n, S

oftw

are

tech

nol

og

i e, T

U D

resd

e n

38

java.util.SortedSet (Auszug)



<<interface>>Set// Query methods

+ boolean isEmpty();+ boolean contains(Object o);+ boolean equals(Object o);+ int hashCode();+ Iterator iterator();




+ Object first();+ Object last()


Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

39

java.util.TreeSet

► java.util.TreeSet implementiert ein geordnete Menge mit Hilfe eines Baumes und benötigt zum Sortieren dessen die Schnittstelle Comparable

► Modifi kation der Klasse Warengruppe:

► Aber Systemreaktion:Exception in thread "main" java.lang.ClassCastException: Artikel at java.util.TreeMap.compare(TreeMap.java, Compiled Code)

► in java.util.TreeSet:public class TreeSet … implements SortedSet … { … }

class Warengruppe {

private Set inhalt; public Warengruppe (…) { … this.inhalt = new TreeSet(); } …}

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

40

class Artikel implements Comparable { ... public int compareTo (Object o) { return name.compareTo(((Artikel)o).name); }}

Anwendungsbeispiel mit TreeSet

► Artikel muss zusätzlich von Schnittstelle Comparable erben

► Modifikation der Klasse „Artikel“:

Systemausgabe:

Warengruppe MoebelSchrank(300) Stuhl(100) Tisch(200)


Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

41

HashSet oder TreeSet?

► Gemessener relativer Aufwand für Operationen auf Mengen:(aus Eckel, Thinking in Java, 2nd ed., 2000)

► Stärken von HashSet:– in allen Fällen schneller !

► Stärken von TreeSet:– erlaubt Operationen für sortierte Mengen

Typ Einfügen Enthalten Iteration

HashSet 36,14 106,5 39,39

TreeSet 150,6 177,4 40,04

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

42

Collection Framework (Überblick)(Maps)


<<interface>>Set


<<interface>>List

<<interface>>Map


LinkedList

ArrayList

TreeSet

HashSet

TreeMap

HashMap

Vererbung (extends)


Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

43

java.util.Map (Auszug)

<<interface>>HashMap

// Anfragen (query methods)+ int size();+ boolean isEmpty();+ boolean containsKey(Object key);+ boolean containsValue(Object value);+ Object get (Object key);+ int hashCode();+ Iterator iterator();+ Set keySet();+ Set values(); // Zustandsveränderer+ void clear();+ Object put (Object key, Object value);+ boolean remove (Object o);

<<interface>>Map

► Eine Map ist ein „assoziativer Speicher“ (associative array), der Objekte als Werte (value) unter Schlüsseln (key) zugreifbar macht

– Ein Schlüssel liefert einen Wert (Funktion). – Map liefert funktionale Abhängigkeit zwischen Schlüssel und Wert

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

44

Anwendungsbeispiel: Verfeinerung von qualifizierten Relationen

Artikel– name: String

– preis: int

+ preis(): int

Katalog– name: String

1

+ put (code: String, a: Artikel)+ get (code: String): Artikel

+ anzahl(): int

code: String

*

HashMap ist einesehr günstige Umsetzungfür qualifizierte Assoziationen:Der Qualifikator bildet den Schlüssel;die Zielobjeke den WertHier:•Schlüssel: code:String•Wert: a:Artikel

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

45

Anwendungsbeispiel mit HashMap

class Katalog { private String name; private Map inhalt;

public Katalog (String name) { this.name = name; this.inhalt = new HashMap(); }

public void put (String code, Artikel a) { inhalt.put(code,a); }

public int anzahl() { return inhalt.size(); }

public Artikel get (String code) { return (Artikel)inhalt.get(code); } ...}

Online:Katalog.java

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

46

Testprogramm für Anwendungsbeispiel: Speicherung der Waren mit Schlüsseln

public static void main (String[] args) { Artikel tisch = new Artikel("Tisch",200); Artikel stuhl = new Artikel("Stuhl",100); Artikel schrank = new Artikel("Schrank",300); Artikel regal = new Artikel("Regal",200);

Katalog k = new Katalog("Katalog1"); k.put("M01",tisch); k.put("M02",stuhl); k.put("M03",schrank); System.out.println(k);

k.put("M03",regal); System.out.println(k);}

Katalog Katalog1 M03 -> Schrank(300) M02 -> Stuhl(100) M01 -> Tisch(200)

Katalog Katalog1 M03 -> Regal(200) M02 -> Stuhl(100) M01 -> Tisch(200)

Systemausgabe:

put(...) überschreibt vorhandenen Eintrag (Ergebnis = vorhandener Eintrag).

Ordnung auf den Schlüsseln: SortedMap (Implementierung z.B.TreeMap).

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

47

value: Object

Prinzip der HashtabelleEffekt von hashtab.put(key,value)

key.hashCode()

Object

hashCode(): int

key: Object

value: Object

0

capacity

hashtab

► Typischerweise wird der Schlüssel (key) transformiert:– Das Objekt liefert seinen Hashwert mit der Hash-Funktion hashCode()– Mit dem Hashwert wird in eine Hashtabelle eingestochen, d.h. der

Hashwert wird auf einen Zahlenbereich modulo der Kapazität der Hashtabelle abgebildet, d.h., der Hashwert wird auf die Hashtabelle “normiert”

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

48

value?: Object

Kollision beim Einstechen

0

capacity

key1: Object

value1: Object

key2: Object

value2: Object

key1.hashCode()= key2.hashCode()

Verfahren zur Kollisionsauflösung:– Überlauflisten– Überlauf in der Hashtabelle

► Die Hashfunktion ist mehrdeutig (nicht injektiv): – Bei nicht eindeutigen Schlüsseln, oder auch durch die Normierung,

werden Einträge doppelt “adressiert” (Kollision)

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

49

Vorgehensweise beim Datenstruktur-Entwurf

Identifikation der Anforderungen an die Datenstruktur:Funktionalität, häufig benutzte Operationen

Abstraktion auf die wesentlichen Eigenschaften

Suche nach vorgefertigten Lösungen (Nutzung der Collection-Bibliothek)

Ggf. Experimente (experimentelle Prototypen)

Anpassung anvorgefertigte Lösung

Entwicklung einerneuartigen Lösung

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

50

Suche nach vorgefertigten Lösungen (Collection-Klassen der Bibliothek)

Einfügen eines ElementsEntfernen eines ElementsAufzählen aller Elemente

"ist enthalten"-Abfragedynamisch erweiterbar

Collection

Einfügen eines Werts für einen Schlüssel

Entfernen eines Schlüssel/Wert-Paars

Abfrage eines Werts für einen Schlüssel

"ist enthalten"-Abfrage für Schlüssel

dynamisch erweiterbar

Map

Einfügereihenfolge relevant?

List

Abfrage an i-ter Position

Ersetzen an i-ter Position

Entfernen an i-ter Position

janein

Set

kleinstes/größtes Element

Elemente "über"/"unter" x

SortedSet

Sortierung relevant?

Sortierung der Schlüssel relevant?

SortedMap

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

51

Beispiel: Realisierung von Assoziationen

A B*

assoc

Anforderung Realisierung

1) Assoziation anlegen2) Assoziation entfernen3) Durchlaufen aller bestehenden

Assoziationen zu B-Objekten4) Manchmal: Abfrage, ob

Assoziation zu einem B-Objekt besteht

5) Keine Obergrenze derMultiplizität gegeben

Datenstruktur im A-Objekt für B-Referenzen

1) Einfügen (ohne Reihenfolge)2) Entfernen (ohne Reihenfolge)3) Aufzählen aller Elemente

4) "ist enthalten"-Abfrage

5) Maximalanzahl der Elementeunbekannt;dynamisch erweiterbar

Set

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

52

Realisierung von ungeordneten Assoziationen mit Set

A Bassoc

*

class A { private Set assoc; ...

public void addAssoc (B b) { assoc.add(b); }

public boolean testAssoc (B b) { return assoc.contains(b); }

public A { ... assoc = new HashSet();}

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

53

Beispiel: Raumverwaltung

static Besprechungsraum freienRaumSuchen (int groesse, Hour beginn, int dauer)

► Suche unter vorhandenen Räumen nach Raum mit mindestens der Kapazität groesse, aber möglichst klein.

– Datenstruktur für vorhandene Räume in Klasse Raumverwaltung» SortedSet (Elemente: Besprechungsraum)

► Überprüfung eines Raumes, ob er für die Zeit ab beginn für die Länge dauer bereits belegt ist.

– Operation in Klasse Besprechungsraum:boolean frei (Hour beginn, int dauer)

– Datenstruktur in Klasse Besprechungsraum für Zeiten (Stunden):» Set (Elemente: Hour)

► Zusatzanforderung (Variante): Überprüfung, welcher andere Termin eine bestimmte Stunde belegt.

– Datenstruktur in Klasse Besprechungsraum:» Map (Schlüssel: Hour, Wert: Teambesprechung)

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

54

Raumverwaltung: Freien Raum suchen

class Raumverwaltung {

// Vorhandene Raeume, aufsteigend nach Größe sortiert // statisches Klassenattribut und -methode private static SortedSet vorhandeneRaeume

= new TreeSet();

// Suche freien Raum aufsteigend nach Größe static Besprechungsraum freienRaumSuchen

(int groesse, Hour beginn, int dauer) { Besprechungsraum r = null; boolean gefunden = false; Iterator it = vorhandeneRaeume.iterator(); while (! gefunden && it.hasNext()) { r = (Besprechungsraum)it.next(); if (r.grossGenug(groesse)&& r.frei(beginn,dauer)) gefunden = true;

}; if (gefunden) return r;

else return null; } ...}


22.4 Persistente Datenhaltung(Files als Channels)

Art is long, and Time is fleeting.H. W. Longfellow

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

56

Temporäre und persistente Daten

► Daten sind– temporär, wenn sie mit Beendigung des Programms verloren gehen, das sie

verwaltet;

– persistent, wenn sie über die Beendigung des verwaltenden Programms hinaus erhalten bleiben.

► Objektorientierte Programme benötigen Mechanismen zur Realisierung der Persistenz von Objekten.

– Einsatz eines Datenbank-Systems● Objektorientiertes Datenbank-System

● Relationales Datenbank-SystemJava: Java Data Base Connectivity (JDBC)

● Zugriffsschicht auf DatenhaltungJava: Java Data Objects (JDO)

– Speicherung von Objektstrukturen in Dateien mit Senken und Iteratoren● Objekt-Serialisierung (Object Serialization)

● Die Dateien werden als Channels benutzt:

● Zuerst schreiben in eine Sink

● Dann lesen mit Iterator

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

57

Objekt-Serialisierung in Java

► Die Klassen java.io.ObjectOutputStream und java.io.ObjectInputStream stellen Methoden bereit, um ein Geflecht von Objekten linear darzustellen (zu serialisieren) bzw. aus dieser Darstellung zu rekonstruieren.

■ Ein OutputStream entspricht dem Entwurfsmuster Sink■ Ein InputStream entspricht dem Entwurfsmuster Iterator

► Eine Klasse, die Serialisierung zulassen will, muß die (leere!) Prädikat-Schnittstelle java.io.Serializable implementieren.

class ObjectOutputStream { public ObjectOutputStream (OutputStream out)

throws IOException;// push Method public void writeObject (Object obj)

throws IOException;}

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

58

Objekt-Serialisierung: Abspeichern

import java.io.*;

class XClass implements Serializable {private int x;public XClass (int x) {

this.x = x; }}

...XClass xobj;...FileOutputStream fs = new FileOutputStream("Xfile.dat");ObjectOutputStream os = new ObjectOutputStream(fs);

// internally realized as push for all child objectsos.writeObject(xobj);...

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

59

Objekt-Serialisierung: Einlesen

import java.io.*;

class XClass implements Serializable {private int x;public XClass (int x) {

this.x = x; }}

...XClass xobj;...FileInputStream fs = new FileInputStream("Xfile.dat");ObjectInputStream os = new ObjectInputStream(fs);// internally realised as pullxobj = (XClass) os.readObject();

Pro

f. U

. Aß

ma

nn,

Sof

twa

rete

chn

olo

gi e

, TU

Dre

sde n

60

The End

► Diese Folien sind eine überarbeitete Version der Vorlesungsfolien zur Vorlesung Softwaretechnologie von © Prof. H. Hussmann, 2002. used by permission.

Documents

3 $ #2 ( 4)st.inf.tu-dresden.de/files/teaching/ss12/swt/Vorlesungen/22-st...6 #$ $ ' #$ Bestellung kunde: String anzahl: int liste java.util.ArrayList add(Object o) get(pos: int):