Bei den Mengen fällt auf, daß das Eintragen eines schon vorhandenen Elements keine Veränderung des Zustandes bewirkt. Ein Multibehälter vom Typ TZeichenmenge kann ein Zeichen nur einmal aufnehmen. Dies ist eine Eigenschaft von Mengen. Ein Sack dagegen kann einen Wert mehrmals aufnehmen. Der abstrakte Datentyp TZeichensack ist ein solcher Sacktyp:
generic -- Ausschnitt aus der Datei GSack.ads type TElement is private; package GSack is type TSack is limited private; procedure Entleeren (Sack: out TSack); -- Konstruktor, löscht den gesamten Inhalt procedure Fuellen (Sack: in out TSack; Zeichen: in Character ); -- raises: ESack_voll: exception; procedure Entfernen (Sack: in out TSack; Zeichen: in Character); -- raises: EKein_Eintrag: exception; -- löscht aus Sack nur eine Eintragung, falls vorhanden procedure Alle_entfernen (Sack: in out TSack; Zeichen: in Character); -- löscht alle Zeichen aus Sack function Vorhanden (Sack: TSack; Zeichen: Character) return Boolean; function Leer (Sack: TSack) return Boolean; procedure Kopieren (Ziel: out TSack; Quelle: in TZeichensack); function "=" (Links, Rechts: TSack) return Boolean; procedure Speichern (Sack: in TSack; Dateiname: in String); -- Persistenzoperationen procedure Laden (Sack: out TSack; Dateiname: in String); -- raises: EDatei: exception; -- der Inhalt der Datei paßt nicht in Sack, oder keine Datei mit Dateiname procedure Alles_anzeigen (Sack: in TSack); -- zeigt alle vorhandenen Zeichen am Bildschirm an private ... end GSack;
Übung: Erweitern Sie die Schnittstelle der Paketschablone GSack zu einer Paketschablone GSack_Algebra, indem Sie Operationen hinzufügen, mit denen die Summe und die Differenz zweier Säcke errechnet werden kann. Prägen Sie Ihre Erweiterung für Farben in einem Testprogramm aus. Sie können Ihr Programm allerdings noch nicht binden, da Sie das Paket noch nicht implementiert haben.
Ein Sack mit diskretem Elementtyp kann als Reihung implementiert werden. Im Gegensatz zur Menge muß hier jedoch Information nicht nur über das Vorhandensein oder Fehlen einzelner Elemente gespeichert werden, sondern auch über ihre Anzahl. Von daher ist es notwendig, für den Basistyp der Reihung statt Boolean einen Ganzzahltyp zu nehmen. Wir brauchen dazu die auch für Ganzzahltypen definierten Attributsfunktionen Succ und Pred, mit denen wir einen Ganzzahlwert erhöhen oder erniedrigen können:
type TSack is array (TElement) of Natural; -- Anzahl der eingetragenen Elemente für jeden Wert procedure Fuellen (Sack: in out TSack; Element: in TElement) is begin Sack (Element) := Natural'Succ (Sack (Element)); -- inkrementieren exception when Constraint_Error => raise ESack_voll; -- wenn mehr als Natural'Last end Fuellen; procedure Entfernen (Sack: in out TSack; Element: in TElement) is begin Sack (Element) := Natural'Pred (Sack (Element)); -- dekrementieren exception when Constraint_Error => raise EKein_Eintrag; -- wenn Sack (Element) = 0 end Entfernen;
Bei dieser Implementierung kann aber - wie auch oben bei den Mengen - nicht garantiert werden, daß der Sack am Anfang (zum Zeitpunkt des Anlegens) leer ist, d.h. die Anzahl aller Elemente 0 ist. Zu diesem Zweck muß der Benutzer nach dem Anlegen eines Sackes sein Konstruktor aufrufen:
procedure Entleeren (Sack: out TSack) is -- Konstruktor begin Sack := TSack'(others => Natural’First); end Entleeren;
Dem Benutzer soll dann in der Dokumentation des Pakets deutlich gemacht werden, daß er bei jedem Anlegen eines Sack-Objekts den Konstruktor Entleeren aufrufen muß.
Die Implementierung der weiteren Sack-Operationen mit dieser Methode wird dem Leser überlassen.
Eine einfache Überlegung zeigt aber, daß der Rechner bei dieser Implementierung schnell an seine Grenzen kommt. Braucht nämlich der Benutzer einen Ganzzahl-Sack, legt er sich die Ausprägung in der Form
package MGanz_Sack is new GSack (Integer); -- einige Compiler können keine so große Reihungen angelegen Sack: MGanz_Sack.TSack;
an. Wieviel Platz belegt das Datenobjekt Sack im Speicher des Rechners? Für jeden Wert des Basistyps (in dem Fall Integer) eine positive Zahl. Wenn Standard den Datentyp Integer mit 4 Bytes implementiert, sind das 232 Integer-Objekte, d.h. insgesamt 4 . 232 Bytes. Eine sehr ineffiziente Speichernutzung, wenn man nur einige der vielen möglichen Ganzzahlwerte im Sack speichern möchte.
Der Benutzer sollte also nicht nur über die Funktionalität des Moduls in seiner Schnittstelle informiert werden, sondern auch über die Art und Weise, wie das Modul die Ressourcen nutzt. Der Zugriff auf Reihungen ist sehr schnell, verbraucht aber viel Platz. Von daher sind folgende Kommentare in der Schnittstelle angebracht:
generic type TElement is (<>); -- ausprägbar nur für nicht sehr große diskrete Typen package GSack is -- schnelle aber große Implementierung -- Speicherverbrauch: (TElement'Last - First) * Positive'Size Bytes pro Objekt -- Zugriffsgeschwindigkeit: 1 Schritt pro Operation ...
Aus diesen Kommentaren erfährt der Benutzer, daß diese Implementierung von GSack für Ganzzahlsäcke ungünstig ist. Es sollte auch eine andere vorliegen, die sparsamer mit dem Speicher umgeht, z.B. mit Hilfe einer positionierbaren Liste. Es ist also durchaus möglich, für einen abstrakten Datentyp mehrere Implementierungen zur Verfügung zu stellen, unter denen der Benutzer den für seine Zwecke günstigsten auswählen kann.
Rückmeldungen bitte an den Autor solymosi@tfh-berlin.de
Leitseite des Autors