, Polling,
2008© APSIS GmbH , Polling,
2008
Kapitel 9
Manchmal ist es ein Nachteil der obigen ISack-Schnittstelle, dass die Sackobjekte ein beliebiges Objekt als Element speichern können. In vielen Situationen wäre es wünschenswert, nur einen Typ von Objekten in einen Multibehälter aufnehmen zu können: Der Eintrag eines anderen Typs sollte als Fehler gemeldet werden. Beispielsweise soll ein Sack nur Farben und keine Getränke, auch keine Eimer- oder Button-Objekte aufnehmen können:
package lehrbuch.multi; public interface IFarbsack { // alle final-Parameter sind auch const public void entleeren(); // löscht alle Farben aus dem Farbsack public void eintragen(final Farbe element); public void entfernen(final Farbe element) throws NichtEnthaltenException; public boolean vorhanden(final Farbe element); public boolean istLeer(); // const }
Der Versuch, in einen Farbsack einen Wert oder ein Objekt von einem anderen Typ als Farbe einzutragen, scheitert an der Typprüfung des Compilers:
IFarbsack farbsack = new Farbsack(); farbsack.eintragen(Farbe.GRUEN); // erfolgreich farbsack.eintragen(Getraenk.WEIN); // erfolglos farbsack.eintragen(5); // erfolglos
Die implementierende Klasse Farbsack unterscheidet sich von der Klassse Sack nur darin, dass Object überall auf Farbe ausgetauscht wurde.
Der Nachteil dieser Lösung ist, dass für jeden Elementtyp eine extra Klasse (ggf. mit extra Schnittstelle) entwickelt werden muss. Diese Klassen sind sehr ähnlich, der einzige Unterschied zwischen ihnen ist der Typ des zu speichernden Objekts.
Um sich diese Vielzahl sehr ähnlicher Klassen zu ersparen, wurde das Konzept der generischen Klassen in der Java-Version 5 " eingeführt. Der Entwickler der Klasse lässt den zu speichernden Typ offen, er wird erst bei der Ausprägung der Klasse durch den Benutzer eingesetzt. Eine generische Klasse hat somit einen formalen (generischen) Typparameter, der vom Benutzer durch den aktuellen (generischen) Typparameter ersetzt wird. Diese werden in spitzen Klammern nach dem Klassennamen geschrieben:
package lehrbuch.multi; public interface ISack<Typ> { // alle final-Parameter sind auch const public void entleeren(); // löscht alle Objekte aus dem Sack public void eintragen(final Typ element); public void entfernen(final Typ element) throws NichtEnthaltenException; public boolean vorhanden(final Typ element); public boolean istLeer(); // const }
Diese Schnittstelle unterscheidet sich in den markierten Zeilen von der obigen im Parametertyp der Methoden: statt Object (wo alles paßt) steht hier der formale Typparameter Typ. Dies bedeutet, dass für eine Ausprägung dieser Klasse mit einem bestimmten aktuellen Typparameter (z.B. Farbe) die markierten Methoden nur mit Objekten dieses Typs aufgerufen werden dürfen:
ISack<Farbe> farbsack = new Sack<Farbe>(); farbsack.eintragen(Farbe.ROT); farbsack.eintragen(Getraenk.WASSER); // Typfehler ISack<Integer> ganzzahlsack = new Sack<Integer>(); ganzzahlsack.eintragen(new Integer(5)); ganzzahlsack.eintragen(new Float(5)); // Typfehler
Die ISack-Version ohne den generischen Parameter nennen wir polymorpher Sack . Er würde den Typfehler nicht auslösen.
Auch die Collection-Klassen und Schnittstellen in java.util sind ab der Java-Version 5 generisch:
package java.util; public interface Collection<E> { public void clear(); public boolean add(E o); public boolean remove(E o); public boolean contains(E o); … }
public class LinkedList<E> { …
Eine Besonderheit der generischen Sprachelementen ist, dass die Sprachversion 5 nur einen neuen Compiler braucht; der generierte Bytecode kann von alten Java-Interpretern ausgeführt werden.
Auch die generischen Multibehälter können nur Objekte aufnehmen – manche meinen ein Nachteil des Generizität-Konzepts von Java (im Gegensatz zu C++). Für primitive Typen müssten nach wie vor spezielle Multibehälter angefertigt werden:
public interface IZeichensack { // alle final-Parameter sind auch const public void entleeren(); // löscht alle Zeichen aus dem Zeichensack public void eintragen(final char zeichen); public void entfernen(final char zeichen) throws KeinEintragException; public boolean vorhanden(final char zeichen); public boolean istLeer(); } // const
Als Lösung für dieses Problem ist im Kapitel 7.5.1. beschriebenes Implizites Ein- und Aushüllen: Generische Klassen können doch primitive Werte aufnehmen:
ISack <Char> zeichensack = new ISack <Char>(); zeichensack.eintragen('a'); // implizit: eintragen(new Char('a')) char zeichen = zeichensack.lesen(); // implizit: (Char)(zeichensack.lesen()).valueOf()
Betrachten wir jetzt den Multibehälter mit der Schnittstelle multi.IFarbmenge (ab sofort wird der Einfachheit halber die Paketqualifikation lehrbuch vor deutschsprachigen Klassennamen weggelassen, d.h. die Klausel import lehrbuch.*; wird vorausgesetzt – außer, wenn dies zu Uneindeutigkeiten führt). Er funktioniert sehr ähnlich wie ein Behälter der Klasse Kreis, im Gegensatz dazu kann er aber Farben „sammeln“, d.h. gleichzeitig mehrere Farben speichern. Das Vorhandensein einzelner Farben kann mit Hilfe eines Informators abgefragt werden. Einzelne Farben können aus der Farbmenge mit einem Mutator entfernt werden.
Der Konstruktor der Klasse, die IFarbmenge implementiert, erzeugt eine leere Menge. Der Mutator entleeren bringt das Objekt in denselben Zustand. Die Klasse exportiert außerdem die Mutatoren eintragen und entfernen sowie den Informator vorhanden. Diese drei Methoden haben einen Leseparameter der Klasse Farbe.
Der obige Abschnitt beschreibt die Schnittstelle IFarbmenge verbal. Formal sieht sie folgendermaßen aus:
import lehrbuch.Farbe; package lehrbuch.multi; public interface IFarbmenge { // alle final-Parameter sind auch const public void entleeren(); // löscht alle Farben aus der Farbmenge public void eintragen(final Farbe farbe); // trägt farbe die Farbmenge ein public void entfernen(final Farbe farbe); // löscht Farbe aus der Farbmenge public boolean vorhanden(final Farbe farbe); } // const
Hier haben wir vermerkt, dass alle final-Parameter (d.h. Parameterreferenzen, die von der Methode nicht verändert werden) auch const sind (d.h. auch die Parameterobjekte werden von den Methoden nicht verändert). Wo die Methode auch das Zielobjekt (d.h. die Menge selbst, für die sie aufgerufen wurde) nicht verändert (Informator), haben wir im Kommentar extra mit const gekennzeichnet. An diese Konvention werden wir uns auch weiterhin halten.
Eine Klasse, die diese Schnittstelle implementiert (z.B. die Klasse multi.Farbmenge), hat – wie auch die Klasse Eimer – öffentliche, geschützte und private Komponenten. In der Schnittstelle erscheinen nur die öffentlichen Komponenten. Die öffentlichen und geschützten Komponenten erscheinen in der Dokumentation. Die privaten Komponenten sind für den Benutzer unzugänglich, d.h. für sein Programm nicht sichtbar; sie erscheinen nur im Klassentext.
Ein einfaches Beispiel für die Benutzung dieser Klasse:
import lehrbuch.multi.IFarbmenge; // Schnittstelle import lehrbuch.multi.Farbmenge; // Implementierung import lehrbuch.Farbe; public class ImmerGruen { public static void main(String[] kzp[]) { IFarbmenge menge = new Farbmenge(); menge.eintragen(Farbe.ROT); menge.eintragen(Farbe.ROT); // keine Veränderung menge.eintragen(Farbe.GRUEN); menge.entfernen(Farbe.ROT); menge.entfernen(Farbe.ROT); // keine Veränderung boolean gruenIstDa = menge.vorhanden(Farbe.GRUEN); } } // true
Es ist nicht unüblich, die Referenz von der Schnittstelle (hier: IFarbmenge) zu vereinbaren; dann hat der Programmierer die Freiheit, dieser Referenz Objekte verschiedener Implementierungen (hier: Farbmenge) im Sinne der Aufwärtskompatibilität zuzuweisen. Hierzu müssen aber beide (Schnittstelle und Implementierung) importiert werden. Der Compiler lehnt es dann allerdings ab, wenn eine Methode aus der Implementierung aufgerufen wird, die in der Schnittstelle nicht vereinbart wurde. In diesem Fall würde er den Aufruf
menge.kopieren(andereMenge); // kopieren aus Farbmenge
als Fehler melden, weil kopieren nicht in der Schnittstelle (9.12) vereinbart wurde – obwohl die Klasse Farbmenge diese Methode zur Verfügung stellt. Wenn aber die Referenz menge vom Typ Farbmenge (und nicht IFarbmenge, wie im obigen Programm) vereinbart wurde, ist der Aufruf von kopieren gültig.
Mit Hilfe der Klasse multi.Farbmenge kann man sich Multibehälter anlegen, in denen drei verschiedene Farben gleichzeitig gespeichert werden können. Es besteht jedoch keine Möglichkeit, die üblichen Mengenoperationen wie Vereinigung oder Schnitt zweier Farbmengen oder die Komplementmenge (s. Abbildung Abb. 9.3) zu errechnen. Eine geeignete Erweiterung der Schnittstelle macht dies möglich:
package lehrbuch.multi; public interface IErwFarbmenge extends IFarbmenge { public IErwFarbmenge und(final IErwFarbmenge that); // const // Schnitt public IErwFarbmenge oder(final IErwFarbmenge that); // const // Vereinigung public IErwFarbmenge nicht(); // const // Komplement public boolean istLeer(); // const public void kopieren(final IErwFarbmenge that) throws VollException; public boolean istGleich(final IErwFarbmenge that); } // const
Hier kann man abfragen, ob eine Farbmenge leer ist, man kann eine Kopie der Farbmenge anfertigen und auch feststellen, ob zwei Farbmengen dieselben Farben enthalten oder nicht (ob sie gleich sind). Die Parameter haben wir hier that genannt, als Gegenstück zum this (was das Zielobjekt, die andere beteiligte Menge bezeichnet).
Der Klasse multi.Farbmenge ähnlich ist die Klasse multi.Zeichenmenge. In ihren Objekten können aber nicht Farben, sondern Schriftzeichen vom Typ char gespeichert werden. Sie implementiert die folgende Schnittstelle:
package lehrbuch.multi; public interface IZeichenmenge { public void entleeren(); // löscht alle Zeichen aus der Zeichenmenge public void eintragen(final char zeichen); // trägt zeichen ein public void entfernen(final char zeichen); // löscht zeichen public boolean vorhanden(final char zeichen); public void allesAnzeigen(); } // const // zeigt die gespeicherten Zeichen an
Die Ähnlichkeit der Farbmenge mit der Zeichenmenge bringt uns auf die Idee, ihre Gemeinsamkeiten in eine Oberklasse zu verlagern. Die Schwierigkeit dabei ist, dass für einige Methoden (wie eintragen oder vorhanden) die Elementklasse als Parameter bekannt sein muss. Die Aufwärtskompatibilität ermöglicht jedoch, auch für die verschiedenen Elementklassen eine gemeinsame Oberklasse zu vereinbaren; hier werden die „Minimalanforderungen“ definiert, die eine Elementklasse erfüllen muss, um in einer Menge gespeichert werden zu können. Diese sind u. U. abstrakte Methoden der Elementklasse, die in der Mengenklasse benutzt werden. Weil hier nur abstrakte Methoden vereinbart werden, kann man die Elementklasse als Schnittstelle vereinbaren.
Multibehälter, deren Elementklasse bei der Ausprägung festgelegt wird und nur Objekte dieser Klasse aufnehmen können, nennen wir generische Behälter. Unterschiedliche Ausprägungen können natürlich Objekte unterschiedlicher Klassen aufnehmen.
In der Java-Version 5 wurden generische Klassen eingeführt, mit deren Hilfe auch generische Multibehälter (so auch generische Mengen) programmiert werden können. Die Idee ist ähnlich wie bei generischen Methoden (s. Kapitel 7.8.): Der formale Typparameter (in spitzen Klammern) kann in der Klassendefinition benutzt werden, wird jedoch erst bei der Ausprägung der Klasse durch den aktuellen Typparameter (den benötigten Typ) festgelegt.
Die einfachste generische Menge kann für eine beliebige Elementklasse ausgeprägt werden; ihre Elementoberklasse ist die Oberklasse aller Klassen, d.h. java.lang.Object. Sie implementiert die allgemeine Mengenschnittstelle:
public interface IMenge<Element> { public void entleeren(); // löscht alle Elemente aus der Menge public void eintragen(final Element element); public void entfernen(final Element element); public boolean vorhanden(final Element element); // const public boolean istLeer(); // const public void und(final IMenge<Element> that); // Schnitt public void oder(final IMenge<Element> that); // Vereinigung // public void entweder(final IMenge that); // nur für diskrete Mengen implementierbar, s. Kapitel 9.2.9. // public void nein(); // Komplement nur für diskrete Mengen implementierbar // public boolean istVoll(); // const // nur für diskrete Mengen implementierbar /* die Vergleichs- und Persistenzmethoden nehmen wir nicht in die Schnittstelle auf, damit sie nicht in jeder Implementierung enthalten sein müssen; der Kommentar empfiehlt, sie auch zu implementieren: */ // public void kopieren(final IMenge that) throws VollException; // public boolean istGleich(final IMenge that); // const // public void speichern(String dateiname) throws DateiException; // const // public void laden (final String dateiname) throws DateiException; }
Als generische Klasse kann eine Menge nur Referenzen einer bestimmten Elementklasse aufnehmen können. Die Elementklasse muss bei der Ausprägung der Menge durch den aktuellen Typparameter festgelegt werden. Der Versuch, die Methoden mit Objekten einer anderen Klasse als Parameter auszuführen, wird vom Compiler abgelehnt.
Eine Implementierung dieser Schnittstelle ist die generische Klasse lehrbuch.multi. Menge. Sie kann in einem Programm für einen beliebigen Referenztyp (Klasse) ausgeprägt werden:
IMenge<Integer> ganzzahlmenge = new Menge<Integer>;
IMenge<Eimer> eimermenge = new Menge<Eimer>;
Im Gegensatz zu generischen Methoden kann hier der aktuelle Typparameter nicht weggelassen werden. In ein so ausgeprägtes Mengenobjekt können nun Integer- bzw. Eimer-Objekte eingetragen werden:
Integer zahl = new Integer(5); ganzzahlmenge.eintragen(zahl); ganzzahlmenge.eintragen(new Integer(6)); // anonymes Objekt Eimer eimer = new Eimer(); eimer.fuellen(); eimermenge.eintragen(eimer); eimermenge.eintragen(new Eimer());
Der Compiler erkennt, wenn ein Objekt einer falschen Klasse in eine Menge eingetragen wird:
Ö ganzzahlmenge.eintragen(eimer); // der Compiler meldet Typfehler
Dies unterscheidet die generischen Multibehälter von den polymorphen Multibehältern, die Objekte unterschiedlicher Klassen aufnehmen können. Man sagt, die generischen Multibehälter sind homogen, die polymorphen sind heterogen.
Die Persistenzoperationen sind nur dann erfolgreich ausführbar, wenn die Klassen aller eingetragenen Elemente die Schnittstelle java.io.Serializable implementieren (s. Kapitel 11.1.).
Ein Multibehälter kann grundsätzlich auf zweierlei Weise programmiert werden: generisch und polymorph. In eine Ausprägung einer generischen Klasse können Objekte nur einer bestimmten Klasse (und deren Unterklassen) aufgenommen werden; in einen polymorphen Multibehälter können demgegenüber Objekte verschiedener Unterklassen einer bestimmten Klasse gespeichert werden. In diesem Lehrbuch folgen wir folgender Namenskonvention:
public class MengePol implements IMenge<Object> { public MengePol() { … } public MengePol(final MengePol menge) { … } public void eintragen(final Object element) { … } // beliebiges Objekt ist geeignet … // die Implementierung der weiteren Methoden aus IMenge }
Wie im Kapitel 9.2.5. schon diskutiert wurde, ist eine Schwäche von Java, dass generische Multibehälter mit Elementen der Klasse java.lang.Object hantieren, also auch der Parameter von eintragen dieser Klasse angehört. Wegen der impliziten Aufwärtskompatibilität kann hier jedoch ein beliebiges Objekt übergeben werden:
farbenschlange.eintragen(Farbe.ROT); // aufwärtskompatibel
Die Klasse des eingetragenen Elements wird erst zur Laufzeit geprüft. Noch weniger elegant ist, dass die Ergebnisklasse des Informators (z.B. lesen), der ein Element eines generischen Multibehälters liefert, auch nur java.lang.Object (bzw. die jeweilige Oberklasse der Elementklasse) ist. Da die Abwärtskompatibilität nur explizit erreicht werden kann, muss diese vom Benutzer erzwungen und das Ergebnis in seine eigene Elementklasse konvertiert werden:
Farbe farbe = (Farbe)farbenschlange.lesen();
Eine bewährte und zweckmäßige Vorgehensweise bei der Entwicklung eines solchen Programms ist die Strategie „von oben nach unten“ (top down). Dabei beginnen die Überlegungen an der Anwenderoberfläche:
1. Entwurf der Oberfläche
· Planung der Oberfläche aus Anwendersicht: Welche Menüpunkte, Masken, Meldungen, Fenster sollen erscheinen? Der Anwender soll die Interna des Programms nicht kennen (Objekte, Methoden, Bezeichner): Der Entwickler soll sich in seine Denkweise hineinversetzen. Im obigen Programm benötigen Sie zwei Menüpunkte und die Eingabemaske für die Patienten.
· Zuordnung der Programmelemente zu den Oberflächenobjekten: Rückrufprozeduren für die Menüpunkte, Objekte für die Masken usw. Im obigen Programm entsprechen diesen die zwei Rückrufprozeduren für die Menüpunkte und die Klasse Patient für die Eingabemaske.
· Auswahl geeigneter „Fertigprodukte“ für die Anwenderkommunikation: Die nötigen Klassen werden generiert und importiert. Im obigen Programm werden Programm und MenueArzt gebraucht.
2. Entwurf der Programmstruktur
· Planung des Informationsflusses zwischen den Methoden.
· Aufteilung der globalen und lokalen Variablen: Woran soll sich das Programm zwischen den Ereignissen (Menüauswahlen) erinnern? Das Gedächtnis der Klasse wird mit Hilfe von globalen Referenzen implementiert. Im obigen Programm ist es das Objekt liste.
· Alle andere Objekte sollen lokal in den Rückrufprozeduren sein.
· Auswahl geeigneter Datenbehälter: Die Art und Weise, wie aus dem Gedächtnis die Daten abgerufen werden sollen, entscheidet, von welcher Art die Datenbehälter sein sollen. Im obigen Programm handelt es sich um eine Warteschlange.
· Auch für die nötigen Datenbehälter (z.B. das globale Objekt) können oft (evtl. halb-) fertige Klassen gefunden werden. Nur wenn keine Klasse auffindbar ist, sollen neue programmiert werden.
Nach diesen Vorbereitungen müssen nur die gesammelten Programmbausteine (Kommunikationsklassen, Rückrufprozeduren, globale und lokale Variablen, Datenbehälterklassen) zusammengesteckt werden. Die einzelnen Namen (von Objekten, Klassen, Methoden) müssen dabei aus den richtigen Paketen geholt (z.B. mit import) und die Methoden mit den richtigen Parametern (Anzahl, Klasse) und Zielobjekten versehen werden.
interface Collection interface List extends Collection interface Set extends Collection interface SortedSet extends Set interface NavigableSet extends Set interface Queue extends Collection interface Dequeue extends Queue
abstract class AbstractCollection implements Collection abstract class AbstractSet extends AbstractCollection implements Set class HashSet extends AbstractSet implements Set class TreeSet extends AbstractSet implements SortedSet class EnumSet extends AbstractSet implements Set
abstract class AbstractList extends AbstractCollection implements List abstract class AbstractSequentialList extends AbstractList class LinkedList extends AbstractSequentialList implements List class ArrayList extends AbstractList implements List class Vector extends AbstractList implements List class Stack extends Vector
abstract class AbstractQueue extends AbstractCollection implements Queue
class PriorityQueue extends AbstractQueue implements Queue
Mit Hilfe von Klassen der Schnittstelle Observer können Objekte überwacht werden: Veränderungen an den überwachten Objekten bewirken dann den Aufruf der Methode update. Hierzu muss jedoch die Klasse des überwachten Objekts java.util.Observable erweitern.
In der Warteschlange und im Stapel ist immer nur das Randelement (das erste oder letzte) erreichbar. Positionierbare Listen „erinnern sich“ nicht nur an die eingetragenen Daten und ihre Reihenfolge, sondern auch an eine aktuelle Position in der Liste. An dieser Position kann dann ein neues Element eingefügt oder ein altes entfernt werden. In Multibehältern dieser Klassen kann man navigieren: an das erste oder an das letzte, an das vorherige oder an das nachfolgende Element positionieren, oder ein bestimmtes Element suchen:
public interface PosListe { // alle final-Parameter sind auch const public void entleeren (); // ensures istLeer(); public void eintragen (Object element) throws VollException; // requires !istVoll(); ensures !istLeer() & aktuellesElement() == element; // trägt Element nach dem Element an der aktuellen Position in die Liste ein public void erstesEintragen(final Object element) throws VollException; // requires !istVoll(); ensures !istLeer() & aktuellesElement() == element; // trägt Element an die erste Position in die Liste ein public Object aktuellesElement() throws LeerException; // requires !istLeer(); // liefert das Element an der aktuellen Position der Liste public void loeschen() throws LeerException; // requires !istLeer(); // löscht das aktuelle Element aus Liste public void anfang() throws LeerException; // positioniert auf das erste Element public void ende() throws LeerException; // positioniert auf das letzte Element der Liste public void vorwaerts() throws LeerException; // navigiert eine Position nach vorne public void rueckwaerts() throws LeerException; // navigiert eine Position zurück public void suchen(final Object element) throws NichtGefundenAusnahme; // ensures aktuellesElement == element; // positioniert auf das nächste Vorkommnis von element nach der aktuellen public boolean istLeer(); public boolean istVoll(); // ... Iterator, Persistenzoperationen, Kopieren und Gleichheit als Kommentar class NichtGefundenAusnahme extends Exception { } } // innere Ausnahme
Die problemspezifische Ausnahme NichtGefundenAusnahme wurde hier als innere Klasse vereinbart; sie muss mit catch (PosListe.NichtGefundenAusnahme ausnahme) aufgefangen werden. Auch die Implementierungen dieser Schnittstelle müssen throws PosListe.NichtGefundenAusnahme spezifizieren.
Übung: Rufen Sie die Methoden der generischen positionierbaren Liste kapitel9.PosListeGen für Farben menügesteuert auf. Testen Sie die Wirkung der Navigationsmethoden.
Positionierbare Listen werden oft als Implementierungswerkzeuge benutzt. So wie im Programm (4.1) mit Hilfe der Klasse Eimer die Klasse ZweiEimer implementiert wurde, ist die polymorphe Klasse PosListePol geeignet, z.B. die Schnittstelle Menge polymorph zu implementieren. Als private Komponente enthält die Klasse MengePol eine Referenz auf eine positionierbare Liste. Da die Funktionalität dieser beiden Klassen diesmal einander nicht so nahe steht wie bei den Eimern, muss jetzt die Implementierung mehr leisten. Beim eintragen und entfernen muss die gesamte Liste durchsucht werden: Wenn element beim eintragen gefunden wird, wird die Liste nicht verändert; ansonsten wird es eingetragen. Hierzu wird suchen der positionierbaren Liste aufgerufen:
public class MengePol implements Menge { private PosListePol liste; public MengePol() { // Konstruktor liste = new PosListePol(); } public MengePol(final MengePol quelle) throws VollException { liste = new PosListePol(quelle.liste); } // Kopierkonstruktor weitergereicht public void entleeren() { liste.entleeren(); } // weitergereicht public void eintragen(final Object element) { try { liste.anfang(); liste.suchen(element); } // gefunden, keine Veränderung catch (LeerException ausnahme) { eintr(element); } catch (PosListe.NichtGefundenAusnahme ausnahme) { eintr(element); } } private void eintr(final Object element) { try { liste.eintragen(element); } // throws VollException catch (VollException ausnahme) { throw new Error("Voll beim Eintragen"); } } /* kommt hoffentlich nicht vor: Die Schnittstelle Menge sieht den Fall nicht vor, dass beim Eintragen die Menge voll wird; er ist sehr unwahrscheinlich, dass der Speicher erschöpft ist, zumal jedes Element nur einmal aufgenommen wird */ public void entfernen(final Object element) { ... // ähnlich: wenn gefunden, loeschen; ansonsten keine Veränderung public boolean vorhanden(final Object element) { ... // ähnlich: wenn gefunden, true; ansonsten false public void iterator(String rueckruf) { // ruft rueckruf für alle Elemente auf liste.iterator(rueckruf); } ... istLeer, kopieren, istGleich, speichern und laden ähnlich einfach weiterreichen }
Übung: Implementieren Sie Stapel polymorph mit Hilfe der Klasse PosListePol.
Ein häufig benutzter Spezialfall der positionierbaren Liste ist eine sequenzielle Datei (deren Name nur entfernt an Dateien auf Datenträgern erinnern soll). Hierbei werden die Navigation, das Lesen und das Schreiben stark eingeschränkt:
Eine Datei behält also die Daten in der Reihenfolge des Eintrags. Das Eintragen muss abgeschlossen sein, bevor die Datei gelesen werden kann. Das Lesen erfolgt in der Reihenfolge des Eintrags. Möchte man zu einem schon gelesenen Element zurück, muss das Lesen von vorne angefangen werden:
|
W1 |
W2 |
... |
Wi |
Wi+1 |
... |
Wn |
Datei |
|
| | ® |
Position |
||||||
| |
Lesen |
|||||||
| |
Zurücksetzen |
Abb.: Sequenzielle Datei
Die Schnittstelle kapitel9.SeqDatei definiert die Methoden einer sequenziellen Datei:
public interface SeqDatei { // alle final-Parameter sind auch const public void neuBeschreiben(); // macht die Datei leer, bereit zum Beschreiben public void zuruecksetzen(); // macht die Datei bereit zum Lesen public void eintragen(final Object element) throws LesemodusFehler; /* trägt element an das Ende der Datei ein; nur im Schreibmodus; Ausnahme LesemodusFehler, wenn neuBeschreiben gar nicht oder nicht nach zuruecksetzen aufgerufen wurde */
public void naechstesElement() throws SchreibmodusFehler, DateiendeAusnahme; /* schreitet zum nächsten Element; SchreibmodusFehler, wenn zuruecksetzen gar nicht oder nicht nach neuBeschreiben aufgerufen wurde; DateiendeAusnahme, falls naechstesElement öfter als eintragen aufgerufen wurde */
public Object aktuellesElement() throws SchreibmodusFehler, DateiendeAusnahme; // const // liefert das Element an der aktuellen Position public boolean endeDerDatei() throws SchreibmodusFehler; // true wenn der Aufruf naechstesElement die DateiendeAusnahme auslösen würde // public void kopieren(final SeqDatei quelle) throws VollException; // public boolean istGleich(final SeqDatei quelle); // diesmal kein Iterator, keine Persistenzoperationen // exportierte Ausnahmen als innere Klassen: public class LesemodusFehler extends Error { } public class SchreibmodusFehler extends Error { } public class DateiendeAusnahme extends Exception { } }
Wie aus den Kommentaren in der Schnittstelle ersichtlich ist, kann eine Datei nur beschrieben werden, wenn sie mit neuBeschreiben zum Schreiben geöffnet wurde. Die mit eintragen übergebenen Elemente werden der Reihe nach in die Datei eingetragen. Anschließend kann die Datei mit zuruecksetzen zum Lesen geöffnet werden. Ein Aufruf der Funktion aktuellesElement liefert dann das älteste (als Erstes eingetragene) Element der Datei. Mit dem Aufruf naechstesElement kann man zum Nächsten weiterschreiten, falls es noch welche gibt. Der Ausnahme DateiendeAusnahme kann durch die Abfrage der Booleschen Funktion endeDerDatei vorgebeugt werden.
Übung; Implementieren Sie die Schnittstelle SeqDatei mit Hilfe der generischen Klasse PosListeGen.
Dateien werden typischerweise mit kopfgesteuerten Schleifen abgearbeitet. Ein Beispiel hierfür ist das Zusammenführen oder Mischen (merge) zweier sortierter Dateien.
public void zusammenfuehren( // vorsortierte Dateien werden zusammengeführt final SeqDatei eingabe1, final SeqDatei eingabe2, SeqDatei ausgabe) { try { Element puffer1 = new Element(), puffer2 = new Element(); // geordnet eingabe1.zuruecksetzen(); eingabe2.zuruecksetzen(); ausgabe.neuBeschreiben(); if (! eingabe1.endeDerDatei()) puffer1 = (Element)eingabe1.aktuellesElement(); // jeweils erstes Element einlesen if (! eingabe2.endeDerDatei()) puffer2 = (Element)eingabe2.aktuellesElement(); while (! eingabe1.endeDerDatei() && ! eingabe2.endeDerDatei()) { if (puffer1.istKleiner(puffer2)) { // istKleiner ist eine Methode von Element ausgabe.eintragen(puffer1); // den kleineren schreiben eingabe1.naechstesElement(); puffer1 = (Element)eingabe1.aktuellesElement(); } // und wieder einlesen else { ausgabe.eintragen(puffer2); eingabe2.naechstesElement(); puffer2 = (Element)eingabe2.aktuellesElement(); } }
// eingabe1 oder eingabe2 ist zu Ende; Rest kopieren: while (!eingabe1.endeDerDatei()) { ausgabe.eintragen(puffer1); // den kleineren schreiben eingabe1.naechstesElement(); puffer1 = (Element)eingabe1.aktuellesElement(); } // und wieder einlesen
while (!eingabe2.endeDerDatei()) { ausgabe.eintragen(puffer2); eingabe2.naechstesElement(); puffer2 = (Element)eingabe2.aktuellesElement(); } } catch (SeqDatei.DateiendeAusnahme a) { // dürfte nicht vorkommen System.err.println("Programmfehler: " + a); } }
Dieser Algorithmus wird nach dem Vorsortieren der Daten in sortierten Teilsequenzen benutzt. Zwei solche Sequenzen der Länge n werden mit Hilfe der Prozedur mischen in eine Sequenz der Länge 2n gemischt. Bei mehreren Sequenzen muss dies wiederholt werden, bis nur eine sortierte Sequenz vorliegt.
Unseren nächsten Multibehälter der Art Liste, in dem die Elemente nur in einer bestimmten Reihenfolge erreichbar sind, ist der Sortierkanal ; er gibt die gespeicherten Elemente in sortierter Reihenfolge aus: immer das kleinste gespeicherte Element.
Diese Klasse ist für Sortieraufgaben geeignet: Zuerst werden alle Elemente eingegeben, dann in sortierter Reihenfolge ausgelesen und aus dem Sortierkanal entfernt. Probleme treten dann auf, wenn mehr Elemente sortiert werden müssen als in den zur Verfügung stehenden Speicherplatz passen: Wenn beim Eintragen die Ausnahme VollException ausgelöst wird, muss das kleinste Element entfernt werden, um weiteren Platz zu schaffen. Wenn man Glück hat, kann man auf diese Weise mehr Elemente sortieren als der Speicher aufnimmt. Eine Garantie ist es jedoch nicht: Es kann vorkommen, dass ein neu eingelesenes Element kleiner ist als ein schon ausgegebenes. In diesem Fall werden vorsortierte Sequenzen erzeugt, die dann später durch Zusammenführen zu einer sortierten Folge zusammengeführt werden können. Die erwartete Durchschnittslänge einer durch den Sortierkanal erzeugten Sequenz ist die doppelte des verfügbaren Speicherplatzes. Durch ein konventionelles Verfahren – wie z.B. das bekannte Blasensort (bubble sort) – werden höchstens so lange Sequenzen produziert, wie sie in den Speicherplatz passen. (Ausführlicher wird das Thema in [SolAlg] behandelt.)
Abb: Sortierkanal
Eine Sortierkanalklasse kann nicht für eine beliebige Elementklasse ausgeprägt werden, sondern nur für geordnete Klassen , für die eine Methode istKleiner definiert ist. Dies wird sichergestellt, indem als Elementklasse nicht einfach Object, sondern die Schnittstelle Geordnet genommen wird:
public interface Geordnet { public boolean istKleiner(Geordnet objekt); } // vergleicht zwei Objekte // a.istKleiner(b) && b.istKleiner(c) impliziert a.istKleiner(c)
Der Benutzer des Sortierkanals muss zuerst diese Schnittstelle implementieren und die Methode istKleiner definieren, die seinen Objekten eine Ordnung vermittelt. Der Kommentar in der gekennzeichneten Zeile fordert die übliche Assoziativität einer Ordnungsoperation.
Anschließend kann er eine Implementierung der folgenden Schnittstelle ausprägen, um einen Sortierkanal für seine Elemente zu bekommen:
public interface Sortierkanal { public void entleeren (); public void eintragen (final Geordnet element) throws VollException; public void entfernen() throws LeerException; // des kleinsten Elements public Geordnet kleinstesLesen() throws LeerException; public boolean istVoll(); // weiteres Eintragen nicht möglich public boolean istLeer(); // Iterator, Persistenzoperationen, Kopieren und Gleichheit wie üblich als Kommentar
Diese Schnittstelle wird typischerweise generisch implementiert, wie z.B. die Klasse kapitel9.SortiertkanalGen. Eine polymorphe Implementierung ist selten sinnvoll, da die Methode istKleiner nur Objekte derselben Unterklasse vergleichen kann.
Die Methode istKleiner ist eine Rückruffunktion: Wenn der Mutator eintragen ein neues Objekt der Geordnet implementierenden Klasse in den Multibehälter einsortiert, muss er dieses mit den schon vorhandenen Objekten vergleichen, um seinen Platz zu finden. Für diesen Zweck ruft er dann die im Benutzerprogramm implementierte Funktion istKleiner zurück.
Für Aufzählungsklassen ist die Methode istKleiner einfach zu definieren:
class GeordneteFarbe extends Aufz implements Geordnet { public static final GeordneteFarbe ROT = new GeordneteFarbe(); ... // Aufzählungswerte und Konstruktoren wie üblich public boolean istKleiner(Geordnet farbe) { return super.istKleiner((Aufz)farbe); } } // istKleiner aus Aufz ...
SortierkanalGen farbkanal = new SortierkanalGen(GeordneteFarbe.ROT); GeordneteFarbe farbe = GeordneteFarbe.ROT; farbkanal.eintragen(farbe); ... // weitere Farben eintragen GeordneteFarbe kleinstes = (GeordneteFarbe)farbkanal.kleinstesLesen();
Für andere Klassen, z.B. für Eimer, muss vom Benutzer definiert werden, wie von zwei Eimern der kleinere ausgewählt werden kann:
class GeordneterEimer extends Eimer implements Geordnet { public boolean istKleiner(Geordnet eimer) { boolean ergebnis; ... // Algorithmus, der bestimmt, wie zwei Eimer miteinander verglichen werden // (z.B. nach Inhalt oder Position) return ergebnis; } }
GeordneterEimer eimer = new GeordneterEimer();
SortierkanalGen eimerKanal = new SortierkanalGen(eimer);
In den Multibehälter eimerKanal können nun Eimer mit Hilfe des Mutatoraufrufs
eimer.fuellen();
eimerKanal.eintragen(eimer);
eingetragen werden. Die Aufrufe
eimer = (GeordneterEimer)eimerKanal.kleinstesLesen();
eimer.anzeigen();
zeigen den kleinsten eingetragenen und noch nicht entfernten Eimer an.
Die bisherigen Multibehälter können Datenelemente in einer bestimmten Reihenfolge aufnehmen; die Ausgabereihenfolge der eingetragenen Elemente hängt von der Art des Behälters ab, und der Benutzer hat keinen Einfluss darauf. Im Gegensatz dazu kann bei Assoziativspeichern die Ausgabereihenfolge durch die Angabe eines Schlüssels (key) gesteuert werden.
Ein Assoziativspeicher ist also ein Multibehälter, der mit jedem Datenelement auch einen dazugehörigen – damit assoziierten – Schlüssel (ein zweites, meistens kleineres Datenelement) speichert. Beim Lesen (oder wie es in diesem Zusammenhang heißt, Suchen) des Elements muss dann dieser Schlüssel angegeben werden. Ein einfaches Beispiel hierfür ist ein Telefonbuch: Mit der Angabe des Namens eines Telefonbesitzers als Schlüssel kann seine Telefonnummer gefunden werden.
Abb: Assoziativspeicher
Die Schnittstelle eines allgemeinen Assoziativspeichers kann wie üblich formuliert werden:
public interface AssoSpeicher { public void entleeren(); public void eintragen(final Object schluessel, final Object element) throws VollException; public Object finden(final Object schluessel) throws NichtVorhandenAusnahme; // const public boolean vorhanden(final Object schluessel); // const public boolean istLeer(); // const public boolean istVoll(); // const public class NichtVorhandenAusnahme extends Exception { } } // Iterator, Persistenzoperationen, Kopieren und Gleichheit wie üblich als Kommentar
Die Besonderheit dieser Schnittstelle ist, dass für die generische Implementierung zwei Registrierungsobjekte der beiden Elementklassen nötig sind:
AssoSpeicherGen telefonbuch = new AssoSpeicherGen(telefonnummer, teilnehmer);
Die Funktionalität des Assoziativspeichers muss definieren, ob Eintragungen mit gleichen Schlüsseln möglich sind oder nicht. Die obige Definition geht davon aus, dass eintragen mit einem schon vorhandenem Schlüssel den alten Eintrag (evtl. nach einer Meldung) überschreibt. Eine alternative (vielleicht bessere) Lösung ist, wenn eintragen die VorhandenAusnahme auslöst, wenn er mit einem schon vorhandenem Schlüssel aufgerufen wird – dann findet die Eintragung nicht statt.
Wenn der Assoziativspeicher unterschiedliche Einträge mit gleichem Schlüssel speichern kann, spricht man von einer Assoziativtabelle oder Schlüsseltransformationstabelle (hash table). In diesem Fall exportiert die Klasse neben finden eine zweite Funktion
public interface AssoTab extends AssoSpeicher { public Object naechstesFinden() throws NichtVorhandenAusnahme; }
Der Informator finden liefert dann jeweils das zuerst eingetragene Element; die weiteren können mit naechstesFinden gefunden werden. naechstesFinden wird ohne schluessel-Parameter aufgerufen; er liefert entsprechend des letzten Aufrufs von finden. Der Informator naechstesFinden erinnert sich damit an den letzten Aufruf.
Es ist technisch etwas unsauber, finden und naechstesFinden als Funktion zu programmieren, zumal sie nicht const-Methoden sind: Sie merken sich das zuletzt gefundene Element und speichern diese interne Information im Objekt. Nichtsdestotrotz ändern sie am Zustand des Objekts aus Benutzersicht nichts, daher sind sie – logisch gesehen – Informatoren.
Prinzipiell ist der Schlüssel unabhängig vom Element – wichtig ist es nur, dass der Benutzer das Element vergessen kann und sich nur den Schlüssel merkt, um es später mit seiner Hilfe wieder zu finden. Der Benutzer kann aber den Schlüssel auch aus den Daten des Elements errechnen. Hierzu liefert die Standardklasse Object eine Methode hashCode, die für ein beliebiges Objekt eine seinen Inhalt identifizierende Ganzzahl vom Typ int liefert. Sie kann als Schlüssel verwendet werden.
Das Paket java.util exportiert die Klasse Hashtable, deren Methoden clear, isEmpty, put, containsKey und get in ihrer Funktionalität entleeren, istLeer, eintragen, vorhanden und finden entsprechen. Die Methoden contains und containsValue suchen jedoch nicht nach dem Schlüssel, sondern nach dem Element. Die Klasse exportiert auch die Methode rehash, die den Inhalt des Assoziativspeicher umorganisiert, um die Eintragungen effektiver zu finden. Dies ist insbesondere dann nötig, wenn mit remove viele Elemente entfernt wurden.
Assoziativspeicher können – im Gegensatz zu den Sortierkanälen – auch polymorph implementiert werden.
Übung: Schreiben Sie einen Stapeltesttreiber für den Assoziativspeicher. Im Gegensatz zu einem Dialogtesttreiber ist dies ein konstantes Programm: Es läuft jedes Mal gleich ab. Sein Sinn ist, dass es für verschiedene Implementierungen der zu testenden Klasse (z.B. nach einer Fehlerkorrektur) ihre jeweilige Funktionalität überprüfen kann. Die Testdaten werden hier nicht interaktiv eingegeben, sondern sind im Programm festgelegt.
Prägen Sie nun den Assoziativspeicher mit den Klassen lehrbuch.Char und Buchstabe aus, wobei diese letztere eine Aufzählungsklasse mit den Buchstaben von A bis Z sein soll. Sie bildet den Schlüssel: Jedem seiner Werte wird der entsprechende Buchstabe der Klasse lehrbuch.Char zugeordnet. Ihr Programm soll 20 Eintragungen (in gemischter Reihenfolge) in den Assoziativspeicher vornehmen. Überprüfen Sie anschließend mit Ausgabe über System.out.println, ob alle 20 ordnungsgemäß eingetragen werden.
Eine Variation des Assoziativspeichers ist die direkte Datei. Der Schlüssel wird hier nicht vom Benutzer angegeben, sondern wird beim Eintragen von der Klasse erzeugt und dem Benutzer zurückgegeben. Mit Hilfe dieses Schlüssels kann er dann sein Element wieder finden. Die Daten werden, wie bei einer sequenziellen Datei, in der Reihenfolge der Eintragung, d.h. sequenziell gespeichert (typischerweise ist der Schlüssel eine Folgenummer). Neben der direkten Positionierung mit dem Schlüssel besteht die Möglichkeit, die Daten sequenziell zurückzulesen:
public interface DirDatei { // alle final-Parameter sind auch const public void neuBeschreiben(); // macht die Datei leer, bereit zum Beschreiben public void zuruecksetzen(); // macht die Datei bereit zum Lesen public void eintragen(final Object element) throws LesemodusFehler; /* trägt element an das Ende der Datei ein; nur im Schreibmodus; schluessel kann abgefragt werden; Ausnahme LesemodusFehler, wenn neuBeschreiben gar nicht oder nicht nach zuruecksetzen aufgerufen wurde */
public int schluessel(); // gibt den Schlüssel der aktuellen Position zurück public void positionieren(int schluessel) throws DateiendeAusnahme, SchreibmodusFehler; public void naechstesElement() throws SchreibmodusFehler, DateiendeAusnahme; /* schreitet zum nächsten Element; SchreibmodusFehler, wenn zuruecksetzen gar nicht oder nicht nach neuBeschreiben aufgerufen wurde; DateiendeAusnahme, falls naechstesElement öfter als eintragen aufgerufen wurde */ public Object aktuellesElement() throws SchreibmodusFehler, DateiendeAusnahme; // const // liefert das Element an der aktuellen Position; nur im Lesemodus public boolean endeDerDatei() throws SchreibmodusFehler; // true wenn naechstesElement die DateiendeAusnahme auslöst; nur im Lesemodus // public void kopieren(final DirDatei quelle) throws VollException; // public boolean istGleich(final DirDatei quelle); // diesmal kein Iterator, keine Persistenzoperationen public class LesemodusFehler extends Exception { } public class SchreibmodusFehler extends Exception { } public class DateiendeAusnahme extends Exception { } }
Im Gegensatz zum Assoziativspeicher wird also die direkte Datei nur mit einer Elementklasse Element ausgeprägt. An Stelle der Schlüsselklasse wird hier einfach der Typ int verwendet.
Ähnlich wie SeqDatei, kann auch DirDatei unterschiedliche Implementierungen haben, von denen einige persistent sind, andere nicht. Die Klasse kapitel9.DirDateiImpl ist ein Beispiel für das Erste.
© APSIS GmbH , Polling,
2008