Sortierkanäle

Der Multibehälter der Art Liste, in dem die Elemente nur in einer bestimmten Reihenfolge erreichbar sind, wird nicht für alle, sondern nur für geordnete Datentypen ausgeprägt. Wir nennen so diejenigen, für deren Werte die Relation "kleiner" (meistens der Operator "<", vielleicht in Form einer Funktion) definiert wurde.

Diese Liste heißt Sortierkanal; er gibt die gespeicherten Elemente in sortierter Reihenfolge aus: immer das kleinste gespeicherte Element.

Dieses Paket 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 die Ausnahme ESpeicher_voll ausgelöst wird, muß das kleinste Element entfernt werden, um weiteren Platz zu schaffen. Wenn man Glück hat, kann man auf diese Weise also mehr Elemente sortieren als der Speicher aufnimmt. Eine Garantie ist es jedoch nicht: Es kann vorkommen, daß ein neu eingelesenes Element kleiner ist als ein schon ausgegebenes. In diesem Fall werden vorsortierte Sequenzen erzeugt, die dann später durch Mischen 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 werden höchstens so lange Sequenzen produziert, die in den Speicherplatz passen.

Sortierkanal

Eine Sortierkanalschablone kann nicht ohne weiteres für einen beliebigen Datentyp ausgeprägt werden. Für geordnete Datentypen, für die der Operator "<" zur Verfügung steht, ist es eindeutig, wie die eingetragenen Elemente einsortiert werden können. Für andere Datentypen muß jedoch dem Algorithmus mitgeteilt werden, wie er zwei Werte miteinander vergleichen kann. Dies geschieht durch eine Rückruffunktion:

generic
	type TElement is private;
	with function "<" (Rechts, Links: TElement) return Boolean; -- Rückruffunktion
package GSortier_Kanal is
	type TSortier_Kanal is limited private; -- wird leer angelegt
	procedure Entleeren (Kanal: out TSortier_Kanal);
	procedure Eintragen (Kanal: in out TSortier_Kanal; Element: in TElement); -- raises:
	ESpeicher_voll: exception;
	function Kleinstes_lesen (Kanal: TSortier_Kanal) return TElement; -- raises:
	EKanal_leer: exception;
	procedure Entfernen (Kanal: in out TSortier_Kanal); -- raises EKanal_leer; -- des kleinsten Elements
	function Leer (Kanal: TSortier_Kanal) return Boolean;
	function Voll (Kanal: TSortier_Kanal) return Boolean; -- weiteres Eintragen nicht möglich
	... -- Iterator, Persistenzoperationen, Kopieren und Gleichheit wie üblich

Diese Paketschablone braucht für die Ausprägung zwei Parameter: den Basistyp TElement und eine relationale Funktion für den Vergleich zweier Objekte vom Basistyp.

In der Tat ist dies eine Rückruffunktion: Wenn der Mutator Eintragen einen neuen Wert vom Typ TElement in den Multibehälter einsortiert, muß er diesen mit den schon vorhanden vergleichen, um seinen Platz zu finden. Für diesen Zweck ruft er dann die im Benutzerprogramm implementierte Funktion zurück. Diese Funktion kann im Falle eines geordneten Datentyps, z.B. Character, einfach den Operator "<" für Character aus Standard aufrufen. Die Ausprägung sieht dann folgendermaßen aus:

package MZeichen_Sort is new GSortier_Kanal (TElement => Character, "<" => "<");
	-- der formale und der aktuelle Parameter haben denselben Namen

Für andere Datentypen, z.B. für MEimer.TEimer, muß vom Benutzer definiert werden, wie von zwei Eimern der kleinere ausgewählt werden kann:

function Eimer_Vergleich (Erstes, Zweites: MEimer.TEimer) return Boolean is
	... -- Algorithmus, der bestimmt, wie zwei Eimer miteinander verglichen werden (z.B. nach Inhalt oder Position)
package MEimer_Sort is new GSortier_Kanal (TElement => MEimer.TEimer, "<" => Eimer_Vergleich);
Eimer_Kanal: MEimer_Sort.TSortier_Kanal;
Eimer: MEimer.TEimer;

In den Multibehälter Eimer_Kanal können nun Eimer z.B. menügesteuert mit Hilfe des Mutatoraufrufs

MEimer.Fuellen (Eimer => Eimer); -- der formale und der aktuelle Parameter haben hier auch denselben Namen
MEimer_Sort.Eintragen (Kanal => Eimer_Kanal, Element => Eimer);

eingetragen werden. Die Aufrufe

MEimer.Fuellen (Eimer => Eimer,
	Getraenk => MEimer.Inhalt (Eimer => MEimer_Sort.Kleinstes_lesen (Kanal => Eimer_Kanal)));
MEimer.MEimer_EA.Anzeigen (Eimer => Eimer);

zeigen den kleinsten eingetragenen und noch nicht entfernten Eimer am Bildschirm an.

Der Rumpf des Sortierkanals befindet sich in der Datei GuSortkn.ads

Rückmeldungen bitte an den Autor solymosi@tfh-berlin.de

Leitseite des Autors