OOP mit Java: Dynamische Datenstrukturen und Containerklassen

Konzepte	es sind nur wenige konzeptionell unterschiedliche ADTs notwendig
	Listen, Mengen, Verzeichnisse, Multimengen, Relationen, Graphen

Implementierungen	es gibt viele sehr ausgefeilte Algorithmen und Datenstrukturen zur effizienten Implementierung dieser Konzepte
	verkettete Listen, Bäume, Felder, hash-Tabellen, ...
	--> Literatur über Algorithmen und Datenstrukturen

	wenige gemeinsame Schnittstellen für alle Implementierungen: Verständlichkeit

Umsetzung	in Hierarchien von Klassen-- und Schnittstellenvererbungen

1.Schritt	Gemeinsamkeiten für alle Container festlegen

Beispiel	public interface ContainerPredicates<E> { public boolean isEmpty(); public boolean isIn(E e); public int noOfElements(); // ... }

	Allgemein nützliche Schnittstellen definieren --> Beispiel: totale Ordnung

2.Schritt	vollständige Schnittstelle für ein Container-Konzept festlegen

Beispiel	für Listen
	public interface List<E> extends ContainerPredicates<E> // , OtherInterfaces<E> { public E hd(); public List<E> tl(); public E get(int i); public List<E> cons(E e); public List<E> append(E e); // ... }

Beispiel	für Mengen
	public interface Set<E> extends ContainerPredicates<E> // , OtherInterfaces<E> { public void insert(E e); public void remove(E e); // ... }

3.Schritt	Allgemeingültige Eigenschaften eines Container-Konzepts in einer abstrakten Klasse implementieren

Beispiel	für Listen
	public abstract class ListImpl<E> implements List<E> { public boolean isEmpty() { return noOfElements() == 0; } public E hd() { return get(0); } // ... }

4.Schritt	vollständige konkrete Implementierungen entwickeln.

Beispiel	unter Verwendung einer Klasse für verkettete Listen. --> LinkedList
	Benutzung der verketteten Liste erlaubt das Beerben der abstrakten Klasse
	public class ListAsLinkedList<E> extends ListImpl<E> { protected LinkedList l; //-------------------- public ListAsLinkedList() { l = LinkedList.mkEmptyList(); } //-------------------- // isEmpty() und hd() // sind schon implementiert // eine Redefinition kann // zur Effizienzsteigerung noetig werden // hier z.B. fuer isEmpty() public int noOfElements() { return l.len(); } public boolean isIn(E e) { return l.isIn(e); } public List<E> append(E e) { l.append(e); return this; } public E get(int i) { return (E)(l.at(i)); } // ... }

2. Beispiel	mit der Klasse `Vector` aus dem JDK
	import java.util.Vector; public class ListAsVector<E> extends ListImpl<E> { protected Vector<E> v; //-------------------- public ListAsVector() { v = new Vector<E>(); } //-------------------- // isEmpty() und hd() // sind schon implementiert // eine Redefinition kann // zur Effizienzsteigerung noetig werden // hier z.B. fuer isEmpty() public int noOfElements() { return v.size(); } public boolean isIn(E e) { return v.contains(e); } public List<E> append(E e) { v.addElement(e); return this; } public E get(int i) { return v.elementAt(i); } // ... }

	In allen Anwendungen können für Listen ausschließlich Variablen vom Typ List verwendet werden, d.h. Variablen von der abstrakten Klasse, die das Konzept festlegt.

	Alle Listen können gleichartig verarbeitet werden.
	Eigene Routinen, die mit Listen arbeiten, können jede Art von Listen, auch gemischt verarbeiten.

	Nur die Konstruktoren brauchen explizit die konkreten Klassen

	Konstruktoren nicht über eine ganze Anwendung verstreuen, sondern in sogenannten Fabrikmethoden bündeln --> Entwurfsmuster

Methoden	sind nicht als Parameter erlaubt. forall Routinen mit Funktionen als Parameter zur Verarbeitung aller Elemente sind damit nicht möglich.

Ausweg	eine abstrakte Klasse mit einer Methode als Kommando definieren
	diese Klasse beerben und mit eigenen Methoden konkretisieren

dynamisches Binden	durch Vererbung und dynamisches Binden werden Methoden als Parameter simuliert

Beispiel
Command	eine abstrakte Kommando-Klasse
	abstract public class Command { abstract public void process(Object o); }

PrintCommand	eine konkrete Klasse für eine Ausgabe
	public class PrintCommand extends Command { public void process(Object o) { System.out.println(o.toString()); } }

Anwendung	eine einfache Array-Klasse mit einer Methode zur Verarbeitung aller Elemente
Array	public class Array { Object [] a; // ... vieles mehr //-------------------- public void forall(Command c) { for (int i = 0; i < a.length; ++i ) { c.process(a[i]); } } //-------------------- public void print() { forall(new PrintCommand()); } }

	die print-Methode verwendet die forall-Kontrollstruktur wieder.

	die print-Methode ist unabhängig von der konkreten Ausprägung der forall-Kontrollstruktur

	die print-Methode kann in eine abstrakte Oberklasse von Array ausgelagert werden und von vielen Klassen genutzt werden.

Beispiel
Container	eine abstrakte Oberklasse mit implementierter print-Methode
	abstract public class Container { //-------------------- abstract public void forall(Command c); //-------------------- public void print() { forall(new PrintCommand()); } }

Array1	eine abgeleitete Klasse, die nur die forall-Kontrollstruktur definiert
	public class Array1 extends Container { Object [] a; // ... vieles mehr //-------------------- public void forall(Command c) { for (int i = 0; i < a.length; ++i ) { c.process(a[i]); } } //-------------------- // print ist schon vorhanden }

	viele Methoden können so in gemeinsamen Oberklassen nur einmal implementiert und für die unterschiedlichsten Datenstrukturen wiederverwendet werden

	für jedes Kommando, auch für Kommandos, die nur einmal verwendet werden, muss eine neue Kommando-Klasse erstellt werden

	Namensraum der Klassen wird unnötig überfüllt.
	Abhilfe: geschachtelte und anonyme Klassen

	Kommandos können einen lokalen Zustand besitzen, dieser wird durch einen Konstruktor mit Parametern initialisiert

Beispiel	import java.io.PrintStream; public class PrintStreamCommand extends Command { PrintStream ps; public PrintStreamCommand() { this.ps = System.out; } public PrintStreamCommand(PrintStream ps) { this.ps = ps; } public void process(Object o) { ps.println(o.toString()); } }

Anwendung	import java.io.PrintStream; abstract public class Container1 extends Container { //-------------------- public void print(PrintStream ps) { forall(new PrintStreamCommand(ps)); } }

2. Beispiel	Akkumulieren eines Resultats
	Beispiel: Berechnung der Summe aller Elemente
	public class SumCommand extends Command { int sum; public SumCommand() { sum = 0; } public void process(Object o) { sum += ((Integer)o).intValue(); } public int getSum() { return sum; } }

Anwendung	abstract public class Container2 extends Container1 { //-------------------- public int sum() { SumCommand c = new SumCommand(); forall(c); return c.getSum(); } }

	die Technik, Methoden in Objekten zu speichern, und diese möglicherweise auch erst später aufzurufen, wird intensiv für die Ereignisbehandlung eingesetzt.

Beispiel	Nullstellenberechnung für reellwertige Funktionen

Beispiel	Modell View Controller Beispiele

Dynamische Datenstrukturen und Containerklassen

Containerklassen

Verarbeitung aller Elemente eines Containers