
    \chapter{Die TooL Beh"alterklassenbibliothek}\label{TBehBib}Im folgenden
wird die Beh"alterklassenbibliothek von TooL beschrieben, indem zun"achst
noch einmal die Zielrichtung des Entwurfs formuliert wird. Abschnitt
\ref{Klassch} beschreibt das 
Klassifizierungsschema. In weiteren Abschnitten wird dann die Klassifizierung
der allgemeinen Beh"altereigenschaften vorgestellt (Abschnitt \ref{AllEig}).
Anschlie"send folgt ein "Uberblick "uber die 
spezielleren Beh"alterkategorien (Abschnitt \ref{BehKat}). Der Abschnitt
\ref{Impl} stellt interessante Implementierungen unter anderem im
Hinblick auf die Verwendung der "Ahnlichkeitsrelation vor. Die in TooL
besondere Problematik der Verwendung von Typparametern zur Beschreibung des
Elementtyps der Beh"alter wird in Abschnitt \ref{GenBehKlas}
diskutiert. Abschnitt \ref{Iterationsabstraktion} geht auf die zur
Iterationsabstraktion verwendeten Konzepte ein.
Schlie"slich erfolgt die Formulierung eines Zwischenergebnisses im Hinblick
auf die gestellte Zielsetzung (Abschnitt \ref{BehFazit}). Weitere Abschnitte
besch"aftigen sich mit der Adaption von Entwurfsmustern und den verwendeten
Entwurfshilfmitteln (\ref{Entwrfsmstr} und \ref{Klssnbrwsr}).

Die Implementierung der Beh"alterklassenbibliothek soll zur Beantwortung der
folgenden Fragestellungen beitragen:
\begin{enumerate}
\item{Ist es m"og\-lich, in einer Sprache, die zur streng typisierten
Schnittstellenvererbung zwingt, eine Be\-h"al\-ter\-klas\-sen\-bib\-li\-o\-thek
zu entwerfen? 
Oder anders formuliert: lassen sich die Methodensignaturen 
so sauber klassifizieren, da"s diese Methoden auch in den komplizierteren
Objekten benutzbar bleiben und damit die einfache Sicht auf komplizierte
Objekte garantiert werden kann? }  
\item{L"a"st sich gleichzeitig das Ziel hoher Wiederverwendbarkeit und
Kombinierbarkeit von implementiertem Teilprotokoll erreichen?}
\item{Wird durch die Integration der "Ahnlichkeitsrelation in das Typsystem von
TooL und damit der M"oglichkeit zur typsicheren kontravarianten Spezialisierung
die Wiederverwendbarkeit erh"oht?}
\end{enumerate}
Als Vorlage f"ur den Entwurf dient die Beh"alterklassenbibliothek von Eiffel
\cite{Mey94a}. Diese fein strukturierte Bibliothek liefert vielf"altige
Ans"atze zur Klassifizierung von Beh"alterprotokoll. 
    \section{Klassifizierungsschema}\label{Klassch}Das im folgenden
vorgestellte Klassifizierungsschema kann als Leitfaden f"ur die Entwicklung,
Erweiterung oder Ver"anderung der Hierarchie angesehen werden oder als
Orientierungshilfe innerhalb des Vererbungsgraphen dienen. Es beruht auf
der Beobachtung, da"s sich die Beh"alterklassen durch Eigenschaften beschreiben
lassen. Diesen Eigenschaften bzw. Kombinationen solcher Eigenschaften l"a"st
sich jeweils ein 
bestimmtes Teilprotokoll zuordnen. Das Schema teilt nun das Protokoll eines
Beh"alters in ein allgemeines und in ein spezielleres Protokoll auf. Das
allgemeine Protokoll l"a"st sich allgemeinen, die Beh"alterkonzepte
beschreibenden Eigenschaften zuordnen. Es enth"alt nur solche Methoden, die bereits
auf diesem abstrakten Beschreibungsniveau sinnvoll beschrieben werden
k"onnen. Das speziellere Protokoll kann erst zugeordnet werden, wenn bereits
die Entscheidung f"ur eine bestimmte Beh"alterkategorie durch Kombination
einiger 
allgemeiner Eigenschaften gefallen ist. Ist eine solche Kategorie begr"undet,
so 
l"a"st sich durch erneute Aufteilung nach spezielleren Eigenschaften der
Beh"alterkategorie das spezielle Protokoll zuordnen. Konkrete Beh"alter ergeben
sich dann aus der Kombination der speziellen Beh"altereigenschaften bzw. des
mit ihnen verhafteten Protokolls. Die einzelnen Schritte des
Klassifizierungsprozesses sind damit: 
\begin{enumerate}
\item{Klassifizierung der allgemeinen Eigenschaften von Beh"altern in einem
weitgehend baumf"ormig strukturierten Teil des Vererbungsgraphen}\label{Pro1} 
\item{Zusammenf"uhrung allgemeiner Eigenschaften zu allgemeinen
Beh"alterkategorien}\label{Pro2}
\item{Erneute Aufteilung zur Beschreibung speziellerer Eigenschaften der
Beh"alterkategorie}\label{Pro3}
\item{Kombination spezieller Eigenschaften zu entsprechenden
Beh"altervarianten}\label{Pro4}
\end{enumerate}
Die Klassifizierung der allgemeinen Eigenschaften in einer Baumstruktur, wie
unter \ref{Pro1}. er\-w"ahnt, er\-gibt sich aus der M"oglichkeit, die Eigenschaften
dieser Ebene zu gruppieren und f"ur jede dieser Gruppen einen Teilbaum von
Eigenschaften zu bilden. Die Erl"auterung der Gruppierung folgt in Abschnitt
\ref{AllEig}. Abbildung \ref{SchemaBild} soll das Schema graphisch
darstellen.

%%%%%%%%%Bild: Klassifizierungsschema
\renewcommand{\epsfsize}[2]{0.789#1}
\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsfysize=6cm
\epsffile{../Bilder/bjoern/Bib.Schema.ps}
\end{center}
\caption{Klassifizierungsschema}\label{SchemaBild}
\end{figure}

Die Zeichnung auf der linken Seite der Abbildung ist eine Strukturskizze des
Vererbungsgraphen. Im oberen Abschnitt ist die Baumstruktur
zur Klassifizierung der 
allgemeinen Beh"altereigenschaften angedeutet. Als Bezugspunkt wurde die
Beh"alterkategorie {\em Liste} gew"ahlt. Die 
Wurzel der Listenhierarchie fa"st einige allgemeine Beh"altereigenschaften
zusammen. Durch diese Zusammenfassung erh"alt die Wurzelklasse bereits ein sehr
einfaches Listenprotokoll, welches im Prinzip schon f"ur die Bedienung
ausreichen kann. 
Die Aufteilung der spezielleren Listenprotokolle erfolgt dann wieder
eigenschaftsbezogen. Insbesondere in diesem Abschnitt der Klassifizierung
bedeutet die Abgrenzung einer Eigenschaft nicht notwendigerweise die Definition
weiterer Methoden. Es kann sich auch um eine Implementierungseigenschaft
handeln, welche nur die bereits vorhandenen geerbten Methoden auf eine
bestimmte 
Art und Weise implementiert. Diese kann dann mit den anderen, weitere
F"ahigkeiten vererbenden Eigenschaftsklassen kombiniert werden, soda"s sich
immer komplexere implementierte Listen aufbauen lassen, bis schlie"slich die
gew"unschte Listenvariante zur Verf"ugung steht.

Die Abgrenzung des die allgemeinen Beh"altereigenschaften klassifizierenden
Teilgraphens von den Beh"alterkategorien ist nicht so streng, wie es die
Zeichnung zu vermitteln scheint. Eine spezielle Eigenschaft eines Beh"alters
kann 
durchaus nur die Manifestierung einer allgemeinen Beh"altereigenschaft sein,
die aber nicht auf alle Mitglieder der Beh"alterkategorie zutrifft. Diese
allgemeine Eigenschaft kann dann nicht eine Eigenschaft der Wurzel der
Beh"alterkategorie werden, da sonst das dieser Eigenschaft zugeordnete
Protokoll f"ur ein solches Mitglied unbrauchbar wird, was gerade vermieden
werden sollte. Es wird ein spezielle Klasse zur Umsetzung dieser
Eigenschaft f"ur die aktuelle Beh"alterkategorie ben"otigt, in welcher dann
aufgrund der Entscheidung f"ur eine bestimmte Beh"alterart eventuell auch noch
weitere Methoden definierbar werden.

Die z.B. von \cite[S.36ff]{DissIngrid} getroffene und in Abschnitt
\ref{VererbungsFormen} 
beschriebene Unterscheidung von Konzept- und Implementierungsvererbung l"a"st
sich auf das Klassifizierungsschema und damit auf die Vererbungshierarchie
folgenderma"sen "ubertragen. Die Schritte \ref{Pro1}--\ref{Pro3} des
Klassifizierungsprozesses legen eher die Konzeptvererbung nahe. Hier werden
keine Beh"alterstrukturen festgelegt, sondern nur Protokollvarianten
unterschieden und angeordnet. Erst Schritt \ref{Pro3} f"uhrt mit den
Implementierungseigenschaften oder Implementierungsvarianten einer
Beh"alterkategorie solche Strukturdefinitionen ein, soda"s schlie"slich in
Schritt \ref{Pro4} bei der Kombination der speziellen Eigenschaften der
Beh"alterkategorie und hier insbesondere bei der Kombination mit den
Implementierungseigenschaften, die Implementierungsvererbung verst"arkt zum
Einsatz kommt. In Abschnitt \ref{Listen} wird dies exemplarisch anhand der
Listen noch einmal aufgegriffen (siehe auch Abbildung \ref{ListVarFig}).
    \section{Allgemeine Beh"altereigenschaften}\label{AllEig}F"ur die
allgemeinen Beh"altereigenschaften lassen sich, wie auch in der
Containerhierarchie von Eiffel geschehen, drei Hauptkategorien bilden. Sie
unterscheiden die wichtigsten Protokollgruppen f"ur die Benutzung eines
Beh"alters. Es sind:
\begin{enumerate}
\item{Eigenschaften der Aufnahmef"ahigkeit.}\label{AufnFormI}
\item{Eigenschaften, die Formen des Elementzugriffs
beschreiben.}\label{ZugrFormI} 
\item{Eigenschaften, die Formen des Traversierens
beschreiben.}\label{TravFormI} 
\end{enumerate}
Innerhalb dieser 
Eigenschaftsgruppen l"a"st sich eine Strukturierung oft durch Beantwortung
einfacher Fragen erreichen, die dann zur Unterscheidung von Eigenschaften
f"uhrt. So be\-sch"af\-tigt man sich in der unter \ref{AufnFormI}. genannten
Gruppe z.B. 
mit den Fragen: Wieviele Elemente sind enthalten? Gibt es eine
Kapazit"atsgrenze? Die zweite Gruppe stellt die Frage: Wie wird ein Element
identifiziert? Und unter \ref{TravFormI}. steht die Frage nach der Art des
Traversierens im Vordergrund. "Uber diese Kategorien hinaus gibt es weitere
wichtige Eigenschaften wie die Sortierbarkeit des Beh"alters oder die
'Sortiertheit'. Letztere soll die Eigenschaft beschreiben, da"s die Elemente
des Beh"alters immer sortiert gehalten werden.

Die Aufteilung des Protokolls
kann in TooL aber nicht wie in Eiffel vorgenommen werden, da TooL keine
M"oglichkeit bietet, Methoden umzubenennen und somit den Programmierer zur
Schnittstellenvererbung zwingt. Dies erfordert innerhalb der
Eigenschaftsgruppen und insbesondere in der zweiten Gruppe eine andere
Organisation der Eigenschaftshierarchie.

%%%%%%%%%Bild: Allgemein Eigenschaften :Gruppen
\renewcommand{\epsfsize}[2]{0.789#1} 
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfysize=7cm
\epsffile{../Bilder/bjoern/Bib.Allg1.ps}
\end{center}
\caption{Allgemeine Eigenschaftsgruppen}\label{AllgBehEigGr}
\end{figure}

Abbildung \ref{AllgBehEigGr} bietet
eine "Ubersicht auf die derzeit unterschiedenen Eigenschaftsgruppen und zeigt
gleichzeitig den Wurzelbereich des Vererbungsgraphen der
Beh"alterklassenbibliothek. Die gestrichelte Umrandung der Klassen soll
verdeutlichen, da"s es sich um abstrakte Klassen handelt. Die Verbindungspfeile
symbolisieren die Vererbungsbeziehung\footnote{Die Pfeile folgen den vererbten
Eigenschaften. Sie zeigen also von der Oberklasse zur Subklasse.}.

Als allgemeine Eigenschaft der Beh"alterklassen k"onnte man auch die Tatsache
betrachten, da"s alle Beh"alterklassen einen Typparameter zur Beschreibung des
Elementtyps erhalten (Abbildung \ref{EigUnProFig}). Es
handelt sich also um generische Klassen, die sich durch verschiedene
Elementtypen instantiieren lassen. F"ur den Elementtyp 
wird in der derzeitigen Version der Klassenbibliothek eine
"Ahnlichkeitsbeziehung zum Objekttyp der Klasse {\sf Equality} verlangt. Anders
formuliert bedeutet dies, da"s jedes Elementobjekt eines Beh"alters die Methode
{\sf ''=''} zum Vergleich auf Gleichheit mit einem anderen Elementobjekt
verstehen mu"s. 
Die spezielle Typisierungsproblematik dieses Parameters wird im
Abschnitt \ref{GenBehKlas} gesondert betrachtet. Au"serdem wird dort eine
Alternative 
f"ur die "Ahnlichkeitsbeziehung zum Objekttyp {\sf Equality} diskutiert.

Das allgemeinste, insofern 
eigenschaftsunabh"angige Protokoll findet sich in der Wurzelklasse {\sf
Container} der Beh"alterhierarchie und soll Gegenstand des n"achsten Abschnitts
sein.    
        \subsection{Eigenschaftsunabh"angiges
Protokoll}\label{EigUnPro}Mit eigenschaftsunabh"angigem Protokoll sind
diejenigen Methoden gemeint, welche jeder Container spezifizieren soll.
Konzeptionell lie"sen sich diese Methoden teilweise auch in den
Eigenschaftsgruppen unterbringen, soda"s die Klasse {\sf Container} entfallen
k"onnte. Sie lassen sich jedoch auch gut in den anderen Gruppen nutzen, etwa
zur Formulierung von Vor- und Nachbedingungen oder f"ur die Implementierung
anderer Methoden. Wenn diese Methoden also dennoch der Klasse {\sf Container}
zugewiesen werden, so geschieht dies, weil dadurch fr"uhzeitige
Querverbindungen im Vererbungsgraphen vermieden werden. Dadurch wird die
"Ubersichtlichkeit erh"oht.

Die wichtigsten in Klasse {\sf Container}
definierten Methoden sind in Abbildung \ref{EigUnProFig} zu sehen.

%%%%%%%%%Bild: Eigenschaftsunabhaengiges Protokoll
\begin{figure}[htb]
\begin{xple}
\k{class} Container(E $<\!\!\!*\!\!:$ Equality)
\k{super} Equality
\k{metaclass} AbstractClass
\k{public} \k{methods} \ldots
includes(e :E) :Bool \k{deferred}
isEmpty :Bool \k{\{}elements.isAtEnd\k{\}}
elements :FiniteReadStream(E) \k{deferred}
do(statement :\k{Fun}(:E):\k{Void}) :\k{Void} \k{deferred}
\ldots
;
\end{xple}
\caption{Eigenschaftsunabh"angiges Protokoll}\label{EigUnProFig}
\end{figure}

Die Methode {\sf includes} soll die Mitgliedschaft eines Elementes im Beh"alter
feststellen. Eine solche Aussage sollte unabh"angig von
Traversierungseigenschaften, der Frage wieviele Elemente enthalten sind, oder
ob das Element etwa doppelt enthalten ist, m"oglich sein.

Etwas problematisch ist die Vererbung an die Eigenschaftsgruppe der
Aufnahmef"ahigkeit und dort insbesondere an die Eigenschaft {\sf
Infinite}. Genaueres dazu im diese Gruppe behandelnden, folgenden Abschnitt.

Die interessanteste der abgebildeten Methoden ist sicherlich {\sf elements}.
Durch diese Methode wird von jedem Beh"alter verlangt, da"s er seine Elemente
aufz"ahlen kann. Sie 
liefert einen {\sf ReadStream} zur"uck, "uber den dann die M"oglichkeit
besteht, 
die Elemente des Beh"alters eines nach dem anderen abzurufen. Die {\sf Streams}
stellen einen von den Beh"alterklassen unabh"angigen Teil des Vererbungsgraphen
von TooL und bieten verschiedene Varianten der Iterationsabstraktion. Eine
genauere Beschreibung folgt noch im Abschnitt \ref{Iterationsabstraktion}. F"ur
die Beh"alterklassen ist aber schon hier interessant zu erw"ahnen, da"s der
R"uckgabetyp {\sf ReadStream} der {\sf elements}-Methode von Subklassen
spezialisiert werden kann. Die {\sf Stream}-Hierarchie ist so gestaltet, da"s
f"ur die Nachfolger von {\sf ReadStream} die Subtypbeziehung erhalten bleibt.
Daher kann der R"uckgabetyp der Methode {\sf elements} beim "Uberschreiben der
Methode durch einen spezielleren {\sf Stream} ersetzt werden.

Die F"ahigkeit
des Beh"alters, seine Elemente aufzuz"ahlen, k"onnte hier bereits zur einfachen
Implementierung der anderen Methoden verwendet werden. Dies geschieht aber
nicht, wiederum aus R"ucksicht gegen"uber der Klasse {\sf Infinite} (n"aheres
im n"achsten Abschnitt). Die gesonderte Aufnahme der "uber die Elemente des
Beh"alters iterierenden Methode {\sf do}, welche
potentiell auch in der {\sf Stream}-Hierarchie zu finden w"are, wurde
vorgenommen, 
um die Beh"alter anzuhalten, eine einfachere, die komplexe Implementierung der
{\sf Streams} vermeidende, effizientere Version dieser wichtigen Methode zur
Verf"ugung zu stellen.
	\subsection{Eigenschaften der Aufnahmef"ahigkeit}\label{AufFah}Die
Eigenschaften der Aufnahmef"ahigkeit beantworten die Fragen: Wieviele Elemente
enth"alt der Beh"alter? Gibt es einen Kapazit"atsgrenze? Ist diese Grenze
verschiebbar? Die Wurzelklasse des Teilgraphen wie er in Abbildung
\ref{AufnFahFig} zu sehen ist, definiert eine Aussage als unabh"angig von den
anderen Aufnahmef"ahigkeitseigenschaften. Dies ist die Aussage, da"s alle
Beh"alter potentiell gef"ullt seien k"onnten, und schl"agt sich nieder in der
Spezifikation der Methode {\sf isFull} in dieser Klasse. Anhand dieser Methode
lassen sich die anderen Eigenschaften der Aufnahmef"ahigkeit gut unterscheiden,
denn sie enthalten jeweils eine andere Implementierung dieser Methode. Die
beiden Nachfolger von {\sf Boxed} beantworten die Frage nach der Anzahl der
Elemente.

%%%%%%%%%Bild: Allgemeine Eigenschaften Aufnahmefaehigkeit
\renewcommand{\epsfsize}[2]{0.789#1}
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfysize=8cm
\epsffile{../Bilder/bjoern/Bib.Aufn.ps}
\end{center}
\caption{Eigenschaften der Aufnahmef"ahigkeit}\label{AufnFahFig}
\end{figure}

Da ist zun"achst die Klasse {\sf Infinite}, welche f"ur die
Eigenschaft eines Beh"alters immer unendlich viele Elemente zu enthalten
steht. Dies 
ist f"ur den klassischen Beh"alterbegriff eine ungew"ohnliche Annahme. Es ist
aber dennoch m"oglich, sich entsprechende Beh"alter vorzustellen. Da w"are zum
Beispiel ein Beh"alter der Zufallszahlen enth"alt, oder einer, der alle
Primzahlen beinhaltet. Es ist also m"oglich f"ur Beh"alter die ihre Elemente
funktional berechnen k"onnen. Mit dieser Betrachtungsweise ist ein
unendlicher Beh"alter immer gef"ullt und die Methode {\sf isFull} ist daher
entsprechend durch {\sf true} implementiert. Es k"onnen keine Elemente
eingef"ugt werden.

Die aus {\sf Container} ererbten Methoden sind teilweise
problematisch. Insbesondere die Frage des Enthaltenseins eines Elementes
scheint f"ur eine unendlich Menge nicht vern"unftig zu sein, da hier falls das
Element nicht vorhanden ist potentiell die Gefahr besteht, da"s die Berechnung
nicht terminiert. Es lassen sich aber in den 
angegebenen Beispielf"allen Implementierungen angeben: Die Eigenschaft Primzahl
kann direkt nachgewiesen werden und ein Beh"alter von Zufallszahlen enth"alt
alle Zahlen des Generierungsbereichs. Die Definition eines die Elemente
aufz"ahlenden {\sf Streams} (f"ur die Implementierung der Methode {\sf
elements}) macht insoweit keine Probleme, als die hier in Gestalt der Klasse
{\sf ReadStream} verlangte Form der {\sf Streams} nur eine die Elemente Schritt
f"ur Schritt abrufende Funktionalit"at zur Verf"ugung stellt. Die die
komplexere Funktionalit"at fordernde Signatur der {\sf elements}-Methode mit
{\sf FiniteReadStream} als R"uckgabetyp, wird daher erst in {\sf Accessible}
der Wurzel der Zugriffsformgruppe spezifiziert. Die Kombination mit dem
Protokoll dieser Gruppe (insbesondere Einf"uge- und L"oschmethoden) wird bei
der hier verwendeten Interpretation von {\sf Infinite} als unpassend
betrachtet. 
Kombinierbar bleibt ein unendlicher Beh"alter allerdings mit dem
Traversierungsprotokoll, was dort allerdings auch zur Komplizierung der
Struktur beigetragen hat. Es bleibt anzumerken, da"s sich die gefundenen
Beispiele f"ur unendliche Beh"alter auch auf {\sf Streams} abbilden lassen. Die
Beseitigung dieser Eigenschaft scheint daher m"oglich. 

Die gegenteilige Antwort auf die Frage nach den Elementen ist dann, da"s der
Beh"alter zu jedem Betrachtungszeitpunkt endlich viele Elemente
enth"alt. Dieser Aussage entspricht die Klasse {\sf Finite}. Die Eigenschaft,
endlich viele 
Elemente zu enthalten, erm"oglicht die Einf"uhrung der Methode {\sf size}, wie
dies auch in Abbildung \ref{AufnFahFig} angedeutet ist.

Bei der Subklasse {\sf Counted} handelt es sich um den Repr"asentanten einer
Im\-ple\-men\-tie\-rungs\-ei\-gen\-schaft (siehe Abschnitt \ref{Klassch}). Sie
steht 
f"ur eine h"aufige Implementierungsform der Methode {\sf size}, welche die
Methode durch Verwaltung der Anzahl der aktuell enthaltenen Elemente mit Hilfe
einer Z"ahlvariablen realisiert. Die Klasse f"uhrt also diese nicht
"offentliche Variable ein und implementiert die geerbte Methode {\sf
size}. Beh"alter mit der Eigenschaft {\sf Finite} k"onnen dann bei Bedarf diese
Klasse dazu erben. 

Die beiden weiteren Nachfolger der Klasse {\sf Finite} beantworten die Frage
nach dem Vorhandensein einer Kapazit"atsgrenze. Die Klasse {\sf Unbounded}
steht dabei f"ur das Fehlen einer solchen Grenze. In diesem Fall kann immer ein
Element eingef"ugt werden. Ein solcher Beh"alter ist niemals gef"ullt  und die
Methode {\sf isFull} antwortet daher immer mit {\sf false}.
Die Klasse {\sf Bounded} steht f"ur das Vorhandensein einer solchen
Kapazit"atsgrenze. Dann ist verst"andlich, da"s man auch diese Grenze in
Erfahrung bringen m"ochte, was die Einf"uhrung der Methode {\sf capacity}
begr"undet. Die Aussage "uber die das Erreichen der Kapazit"atsgrenze kann nun
durch Vergleich von Kapazit"atsgrenze und Elementanzahl getroffen werden. Und
so geschieht es auch bei der Implementierung der Methode {\sf isFull}.

Die letzte zu beantwortende Frage dieser Eigenschaftsgruppe betrifft die
Verschiebbarkeit der Kapazit"atsgrenze. Die beiden Nachfolger von {\sf Bounded}
repr"asentieren die beiden m"oglichen Varianten. Die Klasse {\sf Fixed} f"ur
die nicht verschiebbare Grenze implementiert nun auch die Methode {\sf size},
und zwar "uber die Methode {\sf capacity}. Dies hat zur Folge, da"s die Methode
{\sf isFull} auch f"ur einen Beh"alter mit der Eigenschaft {\sf Fixed} immer
mit {\sf true} antwortet. Dabei wird davon ausgegangen, da"s
ein Beh"alter fester Gr"o"se nicht mehr unterscheidet, ob seine 'Slots' noch
den Initialisierungswert enthalten, oder ob bereits weitere Zuweisungen auf sie
erfolgt sind. Andere Varianten sind nat"urlich denkbar und k"onnen durch
"Uberschreiben durchgesetzt werden.

Der folgende Abschnitt er"offnet mit der Beschreibung der
Zugriffsformeigenschaften die zweite Hauptgruppe der allgemeinen
Beh"altereigenschaften. Hier wird unter anderem das wichtige Einf"uge- und
L"oschprotokoll klassifiziert. 
        \subsection{Zugriffsformen}\label{ZugrForm}Die Eigenschaftsgruppe
der Zugriffsformen beantwortet die Frage nach der
I\-den\-ti\-fi\-zie\-rungs\-m"og\-lich\-keit, die der Beh"alter f"ur seine
Elemente anbietet. Es werden drei Varianten unterschieden:
\begin{enumerate}
\item{Assoziativ: Das Element identifiziert sich selbst. Zugriff durch
"Ubergabe des Elementes, z.B. bei Mengen}
\item{Identifikation durch 'Auszeichnung': Der Beh"alter stellt immer ein
'aktives' Element bereit, z.B. bei Listen.}
\item{Identifikation durch Schl"ussel: Den Elementen ist ein Zugriffsschl"ussel
zugeordnet, z.B. in Verzeichnissen (Dictionary).} 
\end{enumerate}
Abbildung \ref{ZugrFormFig} stellt den die Klassifizierung realisierenden
Teilgraphen dar.
Die erste und einfachste Form des Zugriffs ist, da"s Element selbst zur
Identifizierung zu verwenden. Will der Benutzer beh"alterspezifische
Informationen "uber ein 
bestimmtes Element erhalten, oder will er eine Aktion bez"uglich dieses
Elementes einleiten, so mu"s er der entsprechenden Methode das Element
"ubergeben.

%%%%%%%%%Bild: Allgemeine Eigenschaften Aufnahmefaehigkeit
\renewcommand{\epsfsize}[2]{0.789#1}
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfysize=8cm
\epsffile{../Bilder/bjoern/Bib.Zugr.ps}
\end{center}
\caption{Klassifizierung der Zugriffsformen}\label{ZugrFormFig}
\end{figure}

Die  der Eigenschaft zugeordnete Klasse hei"st {\sf Associative}.
Ein Beh"alter, der nur diese Zugriffsart kennt, kann kein Element
mehrfach enthalten. Denn er k"onnte unabh"angig davon, ob er nun ein dem
"ubergebenen Objekt gleichartiges oder eine identisches Element enth"alt,
immer nur dieses Element ansprechen. Das Einf"ugen eines weiteren, zu einem
enthaltenen identischen oder gleichartigen Elements k"onnte dann auch
bestenfalls zum "Uberschreiben des Elementes f"uhren. Mehrfache Vorkommen eines
Elementes k"onnten nicht unterschieden werden.
Ein solcher rein assoziativer Beh"alter ben"otigt eine M"oglichkeit, das in ihm
identifizierte Objekt 
zur"uckzugeben. Wenn es durch ein nicht identisches Element identifiziert
wurde, kann es erw"unscht sein, da"s im Beh"alter enthaltene Objekt
zur"uckzuerhalten. 
Daher findet sich in {\sf Associative} die Spezifikation einer Zugriffsmethode
{\sf get}, die sowohl als Parametertyp als auch als R"uckgabetyp den
Elementtyp definiert. Die Methode {\sf set} in {\sf Associative} steht f"ur das
assoziative Einf"ugen ohne die M"oglichkeit, mehrere identische oder gleiche
Elemente zu verwalten. Typische Subklassen dieser Eigenschaft sind z.B. {\sf
Set} und {\sf Hashtable}.

Durch die zweite Zugriffsform, welche von der Klasse {\sf Active}
repr"asentiert 
wird, bietet der Beh"alter immer ein Element als 'aktives' Element an. Das
hei"st, er spezifiziert eine spezielle Methode, hier {\sf item} genannt, "uber
welche dieses Element abgerufen werden kann. Weiterhin stellt er auf dieses
Element bezogene 
Aktionen zur Verf"ugung wie z.B. die Methode {\sf deleteItem}. Durch die
Auszeichnung werden nun auch im Beh"alter enthaltene identische oder
gleichartige Elemente unterscheidbar. Die Einf"ugemethode {\sf set} hat zwar
die Signatur der Methode in {\sf Associative}, repr"asentiert aber f"ur das
konzeptionell andere Einf"ugen mit potentiellem Einflu"s auf die aktive
Position bzw. das Einf"ugen mehrerer identischer oder gleichartiger Elemente.
Als Subklassen kommen f"ur diese Eigenschaft zum Beispiel Listen, Stapel oder
Warteschlangen in Betracht.

Die dritte Variante der Zugriffsformen "uber Schl"ussel findet ihrer
Entsprechung in der Klasse {\sf Keyed}. Diese Klasse erh"alt  einen weiteren
Typparameter f"ur den Schl"usseltyp. Auch f"ur diesen wird mindestens eine
"Ahnlichkeit zur Klasse {\sf Equality} verlangt, um die Vergleichbarkeit der
Schl"ussel sicherzustellen.  F"ur diesen Parameter lassen
sich die "Uberlegungen zu Alternativen f"ur die vom Elementtyp verlangte
"Ahnlichkeitsbeziehung aus Abschnitt \ref{GenBehKlas} 
"ubernehmen. Durch die Identifikation von Elementen "uber Schl"ussel sind auch
in solchen Beh"altern gleichartige oder identische Elemente unterscheidbar.
Die Einf"ugemethode {\sf set} ben"otigt nun einen zus"atzlichen
Schl"usselparameter um die Zuordnung von Element und Schl"ussel herzustellen.
Des weiteren wird nat"urlich die das Element identifizierende Methode ''$[]$''
mit Parameter vom Schl"usseltyp und R"uckgabetyp vom Elementtyp sowie 
die syntaktisch verwandte Methode ''$[]:=$'' zum "Uberschreiben einer
Schl"usselzuordung angeboten\footnote{Diese speziellen Methoden sind
syntaktische Varianten der ebenfalls vorhandenen Methoden {\sf get} und {\sf
set}. Sie erlauben die Angabe des Schl"ussels in der gewohnten
'Array-Schreibweise' 
zwischen den beiden eckigen Klammern}. Typische Subklasse dieser Eigenschaft
ist z.B. ein {\sf Dictionary}.  

Die letzte Klasse dieser Eigenschaftsgruppe {\sf Indexed} stellt eine
Spezialisierung der Zugriffsform "uber Schl"ussel dar. Der Schl"usseltyp wird
auf ganzzahlige Werte beschr"ankt. Dies erfolgt einfach durch Instantiierung
des 
Schl"usseltyps der Oberklasse {\sf Keyed} mit {\sf Int}. Die Klasse Indexed
ben"otigt erneut nur den Elementtypparameter.
Die nun auf den Schl"usseln definierte Ordnungsrelation l"a"st in dieser Klasse
einige Implementierungen zu, so z.B. f"ur die Methode {\sf elements} aus {\sf
Container}, welche die Verbindung zu den {\sf Streams} herstellte. Bei dieser
Methode l"a"st sich die Ordnung auf den Schl"usseln auch zur Spezialisierung
des R"uckgabetyps auf positionierbare {\sf Streams} nutzen. Typische Nachfolger
dieser Klasse sind {\sf Arrays}.

Zur"uck zur Zugriffsform mittels Identifikation durch das
Element selbst, wie sie durch {\sf Associative} repr"asentiert wird. Sie nimmt
insofern eine Sonderrolle ein, als da"s Teile des ihr zuzuordnenden Protokolls
auch mit den anderen Formen harmonieren. Dieses Protokoll wird daher schon
in Vorg"angern von {\sf Associative} eingef"uhrt. So findet sich die Methode
{\sf includes}, eine  assoziative Methode, bereits in der Klasse {\sf
Container}, und 
in der Klasse {\sf Accessible} wird bereits das assoziative L"oschen durch die
Methode {\sf delete} angeboten. Diese Identifikationsform ist deshalb letztlich
in allen Beh"altern anzutreffen, und {\sf Associative} repr"asentiert nur noch
diejenigen Beh"alter, die keine andere, erg"anzende Form des Zugriffs
anbieten. 

        \subsection{Traversierungsformen}\label{TravForm} Die Eigenschaft
der Traversierbarkeit bedeutet f"ur einen Beh"alter, da"s er eine Strukturidee
f"ur die Anordnung seiner Elemente explizt macht. Er bietet daher an seiner
Schnittstelle Methoden an, die es erm"oglichen, sich innerhalb dieser Struktur
von einem Element zum anderen zu bewegen. Dies 
ist im Unterschied zu der Iterationsabstraktion der {\sf Streams} zu sehen,
welche jeder Beh"alter "uber die in der Klasse {\sf Container} definierte
Methode {\sf elements} zur Verf"ugung stellen mu"s, auch wenn er sonst keine
Reihenfolge auf seinen Elementen sichtbar werden l"a"st. Die Klasse {\sf
Traversable} definiert zun"achst das von der weiteren Differenzierung
unabh"angige Basisprotokoll, welches sich einfach durch die Tatsache ergibt,
da"s die Elemente in einer bestimmten Reihenfolge durchlaufen werden sollen,
und da"s immer eine aktuelle Position w"ahrend dieses Prozesses existiert.

%%%%%%%%%Bild:Traversierungsformen
\renewcommand{\epsfsize}[2]{0.789#1}
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfysize=8cm
\epsffile{../Bilder/bjoern/Bib.Trav.ps}
\end{center}
\caption{Eigenschaftsgruppe Traversierungsformen}\label{TravFormFig}
\end{figure}

Daraus ergeben sich die Methoden zum Aufsuchen der Startposition ({\sf start})
und zur "Uberpr"ufung, ob diese Position eingenommen wurde ({\sf isAtStart}).
Weiterhin wird die Identifikation einer g"ultigen Position und der Zugriff auf
ein Element an einer solchen Position "uber die Methoden {\sf isOff} und {\sf
item} angeboten. Abbildung \ref{TravFormFig} gibt einen "Uberblick "uber die
weitere Struktur der Eigenschaftsgruppe.

Die beiden Subklassen {\sf Linear} und {\sf Hierarchical} unterscheiden, wie
die Namen schon sagen, die Eigenschaft, ob dem Traversieren eine lineare oder
eine hierarchische Strukturvorstellung zugrunde liegen soll.
Lineares Traversieren findet sich typischerweise bei Listen, hierarchisches
Traversieren ist f"ur bestimmte B"aume vorstellbar.

Die Klasse 
{\sf Linear} spezifiziert nun die Standardmethode {\sf next} zur Einnahme der
Folgeposition. Au"serdem findet sich dort mit Methode {\sf index}
die M"oglichkeit, die Position innerhalb der Reihenfolge der Elemente zu
bestimmen und "uber {\sf gotoIndex} auch eine solche, soweit sie vorhanden ist,
anzusteuern. Damit ist auch f"ur einen Beh"alter mit dieser Eigenschaft eine
freie Positionierbarkeit m"oglich allerdings durch entsprechend teure
Operationen, eine tats"achlich einseitig lineare Speicherungsstruktur der
Elemente vorausgesetzt.

Das hierarchische Traversierungsprotokoll der Klasse
{\sf Hierarchical} bietet entsprechend der zugrunde liegenden
Strukturvorstellung Methoden zum Auf- und Absteigen in der Hierarchie ({\sf
up}, {\sf down}) und 
zur "Uberpr"ufung des Vorhandenseins bzw. der G"ultigkeit von Nachfolgern (z.B.
Methode {\sf is$\!$ValidSucc}). Dabei wird hier von vornherein vom
Vorhandensein beliebig vieler (auch unterschiedlich vieler) Nachfolger
innerhalb der Hierarchie 
ausgegangen. So definiert dann auch die Methode {\sf successorCount} die Anzahl
der zu einem bestimmten Zeitpunkt prinzipiell m"oglichen Nachfolger, die dann
aber noch unerreichbar seien k"onnen.

Die Klasse {\sf Bilinear} erg"anzt das einfach lineare Traversieren zum
bidirektional linearen Traversieren durch Einf"uhrung der Methode {\sf back},
durch welche die Vorg"angerposition der aktuellen Position betreten wird. Das
Vorhandensein der (bei entsprechender Beh"alterstruktur eventuell direkt
implementierten) Methode, erm"oglicht schon in dieser Klasse die Optimierung
der 
geerbten Methode {\sf gotoIndex} zumindest f"ur die Positionen zwischen
Startposition und aktueller Position.

In {\sf FiniteLinear} wird in Abweichung von der Baumstruktur die Eigenschaft
des linear traversierbaren Beh"alters mit der Eigenschaft {\sf Finite} aus der
Gruppe der Auf\-nah\-me\-f"a\-hig\-keits\-ei\-gen\-schaf\-ten\footnote{siehe Abschnitt
\ref{AufFah}} kombiniert. Die Unterscheidung zwischen linearem und endlich
linearem Traversieren wurde vorgenommen, um die Kombinierbarkeit des linearen
Traversierens mit den 'unendlichen' Beh"altern zu erm"oglichen. Methoden, bei
denen die Gefahr einer Endlosschleife besteht wie z.B. die Methode {\sf
search}, welche die dem "ubergebenen Element entsprechende Position aufsucht,
oder die die Endlichkeit zwingend voraussetzen wie die Methode {\sf end},
welche die letzte Position der definierten Reihenfolge aufsucht, wurden in die
Klasse {\sf FiniteLinear} ausgelagert.

Die Klasse {\sf FiniteBilinear} schlie"slich kombiniert lediglich noch die
endlich 
lineare Eigenschaft mit der des bidirektionalen linearen Traversierens. Hier
ist dann noch einmal eine Verbesserung der Methode {\sf gotoIndex} m"oglich.
Nun unter Ber"ucksichtigung des maximalen Index, der durch die von {\sf Finite}
geerbte Methode {\sf size} bekannt wird.
        \subsection{'Sortiertheit'}\label{Sort} Die Eigenschaft der
Sortiertheit soll f"ur einen Beh"alter bedeuten, da"s er seine Elemente immer
sortiert zu halten hat. Diese Forderung ist nat"urlich nur f"ur solche
Beh"alter sinnvoll, die auch eine Reihenfolge f"ur ihre Elemente
definieren. Insofern sind die Eigenschaften dieser Gruppe nicht mit jedem 
Beh"alter kompatibel.

%%%%%%%%%Bild: Die Klasse Ordered
\begin{figure}[htb]
\begin{xple}
\k{class} Ordered
\k{super} Equality
\k{metaclass} AbstractClass
\k{public} \k{methods}
order(x :Self) :Int \k{deferred}   
''$=$''(x :Self) :Bool \k{\{}order.(x) $==$ 0\k{\}}
''$<$''(x :Self) :Bool \k{\{}order.(x) $<$  0\k{\}}
''$>$''(x :Self) :Bool \k{\{}order.(x) $>$  0\k{\}}
\ldots
;
\end{xple}
\caption{Ordnungsrelation f"ur Objekte}\label{KlasOrd}
\end{figure}

F"ur den Elementtyp eines sortierten Beh"alters wird eine
"Ahnlichkeitsbeziehung zum durch die Klasse {\sf Sorted} definierten Objekttyp
gefordert. 
Diese Klasse spezifiziert die
Ordnungsrelation definierende Methoden zum Objektvergleich (z.B. {\sf ''$<$''}
und {\sf ''$>$''}).
Die so "uber den Elementtyp auch f"ur den Beh"alter erreichbaren Methoden
k"onnen dann zur Implementierung der Sortierungserhaltung genutzt werden.
Die Struktur der Eigenschaftsgruppe wird anhand der Abbildung \ref{SortEigFig}
erkennbar. 
In der Wurzelklasse {\sf Sorted} werden Methoden zur Erkundung der
Sortierungsrichtung beschrieben({\sf isSortedAscending}, {\sf
isSortedDescending}). 

%%%%%%%%%Bild: Sortierheitseigenschaften
\renewcommand{\epsfsize}[2]{0.789#1}
\begin{figure}[hbt]
\begin{center}
\leavevmode
\epsfysize=8cm
\epsffile{../Bilder/bjoern/Bib.Sort.ps}
\end{center}
\caption{Sortierte Beh"alter}\label{SortEigFig}
\end{figure}

Der Nachfolger {\sf SortedFinite} kombiniert die
Eigenschaft des Sortiertseins mit der Endlichkeit. Dadurch werden die Methoden
zur Berechnung des Minimums und des Maximums sinnvoll. Die drei Nachfolger
dieser Klasse beschreiben verschiedene Varianten des Sortiertseins welche auch
kombinierbar sind.

Die Subklasse {\sf MergeableSorted} f"uhrt eine Methode zum Mischen zweier
sortierter Beh"alter ein. Dieses die Sortierung erhaltende Mischen wird hier
als die eigentliche Form des Mischens angesehen. Ein Zusammenf"ugen nach
dem Rei"sverschlu"sverfahren etwa f"ur Listen m"u"ste anders benannt werden.

Ein weiterer Nachfolger von {\sf SortedFinite} ist {\sf ReversableSorted}.
Diese Klasse spezifiziert eine Methode zum Umschalten zwischen aufsteigender
und absteigender Sortierung. Gleichzeitig implementiert sie die "uber die
Sortierungsrichtung Auskunft gebenden geerbten Methoden mit Hilfe einer
privaten Variablen, welche sich die aktuelle Sortierungsrichtung merkt.

Der dritte Nachfolger {\sf SortedLinear} kombiniert endlich lineares
Traversieren mit der Sortiertheitseigenschaft. Durch die M"oglichkeit zum
Traversieren wird bereits hier eine Reihenfolge der Elemente sichtbar. Dadurch
sind die Methoden zur Berechnung von Minimum und Maximum implementierbar.
Des weiteren wird eine Methode zur Medianberechnung angeboten.

Die letzte Klasse dieser Gruppe kombiniert die Eigenschaft der Umkehrbarkeit
der Sortierrichtung mit dem endlich bilinearen Traversieren und steht somit
f"ur die Aussage, da"s alle endlich bilinear traversierbaren Beh"alter auch die
Umkehrung der Sortierrichtung unterst"utzen k"onnen.
        \subsection{Sortierbarkeit}\label{SortBar}Die Eigenschaft der
Sortierbarkeit soll in Abgrenzung zu einem immer sortierten Beh"alter lediglich
bedeuten, da"s eine Sortiermethode angeboten wird. Dies soll auch dann m"oglich
sein, wenn auf den Elementen des Beh"alters von vornherein keine
Ordnungsrelation definiert ist. Ein Beh"alter, f"ur dessen Elemente lediglich
eine Gleichheitsrelation verlangt wird, kann auch mit Elementen belegt werden,
f"ur die eine Ordnungsrelation denkbar w"are. Bei einer solchen Belegung soll
es m"oglich sein, den Beh"alter zwischenzeitlich zu sortieren. In der
Wurzelklasse {\sf Sortable} wird daher eine Sortiermethode spezifiziert, der
man eine die Ordnungsrelation zwischen den Beh"alterelementen definierende
Funktion "ubergeben kann. Die Angabe einer solchen Funktion ist, insbesondere
wenn dem Beh"alter bei der Erzeugung ein geordneter Elementtyp "ubergeben
wurde, durch einfache Abbildung auf die ordnenden Methoden der Elemente zu
leisten.

%%%%%%%%%Bild: Sortierbarkeit und sortierungerhaltendes Mischen
\renewcommand{\epsfsize}[2]{0.789#1}
\begin{figure}[htb]
\begin{center}
\leavevmode
\epsfysize=4,5cm
\epsffile{../Bilder/bjoern/Bib.Sortbl.ps}
\end{center}
\caption{Sortierbarkeit und sortierungserhaltendes Mischen}\label{SortBarFig}
\end{figure}

Durch die Unabh"angigkeit der Sortierbarkeit vom Elementtyp des
Beh"alters kann die Sortiermethode bereits fr"uhzeitig von Beh"altern geerbt
werden, 
die eine Reihenfolge auf ihren Elementen sichtbar werden lassen. Diese
Reihenfolge kann dann von der Sortiermethode ver"andert werden. Es ist dann
nicht mehr n"otig, zur Umsetzung dieser Eigenschaft in einer Beh"alterkategorie
spezielle sortierbare Beh"alterklassen zu definieren, die nur sortierbare
Elemente aufnehmen. 

F"ur die Subklasse {\sf MergeableSortable} treffen in Bezug auf das
sortierungsstabile Mischen die gleichen "Uberlegungen zu, wie die f"ur ihre
Vorga"angerin angestellten "Uberlegungen bez"uglich der Sortiermethode.
Derartiges Mischen macht nur Sinn, wenn der Beh"alter auch sortierbar ist, also
eine Sortiermethode anbietet, um zun"achst "uberhaupt einmal eine Sortierung zu
erhalten. Dies erkl"art die Plazierung als Erbe von {\sf Sortable}. Die
angebotene Mischmethode hat dann auch die gleichen Parameter wie die geerbte
Sortiermethode. Prinzipiell lassen sich beide Methoden durch die "uber den
Funktionsparameter m"ogliche algorithmische Steuerung des Misch-
bzw.Sortiervorganges auch zu beliebigen anderen Manipulationen der Reihenfolge 
nutzen, z.B. zur Erzeugung einer Sequenz von abwechselnd aus den
Beh"altern entnommenen Elementen.

Die Beh"alterklassenbibliothek verwendet die Eigenschaften der Sortierbarkeit
und der 'Sortiertheit' als sich gegenseitig ausschlie"sende Eigenschaften. Dies
geschieht aufgrund der "Uberlegung, 
da"s das (Um)Sortieren der Elemente eines bereits sortierten Beh"alters in eine
der Ordnung dieser Elemente zuwiderlaufende Reihenfolge nicht sinnvoll ist. Bei
entsprechender Anpassung der Implementierung besonders der Einf"ugemethoden ist
eine Kombination der beiden Eigenschaften allerdings m"oglich.
