Weiter: 12.2 Mehrfache Implementationen Hinauf: 12 Objektorientierte Konzepte Zurück: 12 Objektorientierte Konzepte

12.1 Heterogene Listen

Zunächst geben wir ein Beispiel für eine doppelt verkettete Liste.

package Doubly_Linked is$$
$$
type Node_Type is tagged limited private;$$
type Node_Ptr is access all Node_Type'CLASS;$$
$$
procedure Add(Item: Node_Ptr; Head: in out Node_Ptr);$$
procedure Remove(Item: Node_Ptr; Head: in out Node_Ptr);$$
$$
function Next(Item: Node_Ptr) return Node_Ptr;$$
function Prev(Item: Node_Ptr) return Node_Ptr;$$
$$
private$$
type Node_Type is tagged limited$$
record$$
Prev: Node_Ptr := null;$$
Next: Node_Ptr := null;$$
end record;$$
end Doubly_Linked;$$

Diese Spezifikation einer doppelt verketteten Liste kann später durch Typerweiterung mit zusätzlichen Komponenten und Operationen versehen werden.

Wir werden nun dieses Paket benutzen, um eine Assoziationstabelle zu realisieren. Das generische Paket Association hat als Parameter einen Key_Type, einen darauf definierten Gleichheitsoperator und eine darauf definierte Hash-Funktion.

with Doubly_Linked;$$
generic$$
type Key_Type is limited private;$$
with function "$=$"(Left, Right: Key_Type) return Boolean is $>$;$$
with function Hash(Key: Key_Type) return Integer is $>$;$$
package Association is$$
$$
type Element_Type is new Doubly_Linked.Node_Type with$$
record$$
Key: Key_Type;$$
end record;$$
type Element_Ptr is new Doubly_Linked.Node_Ptr;$$
$$
function Key(E: Element_Ptr) return Key_Type;$$
$$
type Association_Table(Size: Positive) is limited private;$$
$$
procedure Enter($$
Table: in out Association_Table;$$
Element: in Element_Ptr);$$
$$
function Lookup($$
Table: in Association_Table;$$
Key: in Key_Type)$$
return Element_Ptr;$$
$$
-andereOperationen$$
$$
private$$
type Element_Ptr_Array is array (Integer range $>$) of Element_Ptr;$$
type Association_Table(Size: Positive) is$$
record$$
Buckets: Element_Ptr_Array(1..Size);$$
end record;$$
end Association;$$

Eine Association_Table ist also eine Hash-Tabelle, wobei jeder Eintrag in der Tabelle eine doppelt verkettete Liste von Elementen besitzt. Die Elemente können irgend welche Typen sein, die von Element_Type abgeleitet sind. Der Listenkopf ist vom Typ Element_Ptr, der wiederum von Node_Ptr abgeleitet ist (ein nicht getaggter, abgeleiteter Typ). Alle primitiven Operationen von Node_Ptr wie zum Beispiel Add oder Remove werden also von Element_Ptr geerbt.

Wir werden nun diese Hash-Tabelle benutzen, um eine Symboltabelle für einen Compiler einer einfachen Sprache zu definieren. Die Sprache soll Typen, Objekte und Funktionen kennen und die Symboltabelle soll dafür jeweils unterschiedliche Einträge haben.

with Association;$$
package Symbol_Table_Pkg is$$
$$
type Identifier is access string;$$
$$
function Equal(Left,Right: identifier) return Boolean;$$
function Hash(Key: Identifier) return Integer;$$
$$
-Instantiierung$$
package Symbol_Association is$$
new Association(Identifier, Equal, Hash);$$
subtype Symbol_Table is$$
Symbol_Association.Association_Table;$$
$$
type Type_Symbol is new Symbol_Association.Element_Type with$$
record$$
Category: Type_Category;$$
Size: Natural;$$
end record;$$
type Type_Ptr is access Type_Symbol;$$
$$
type Object_Symbol is new Symbol_Association.Element_Type with$$
record$$
Object_Type: Type_Ptr;$$
Stack_Offset: Integer;$$
end record;$$
$$
type Function_Symbol is new Symbol_Association.Element_Type with$$
record$$
Return_Type: Type_Ptr;$$
Formals: Symbol_Table(5); -einekleineHash-Tabelle$$
Locals: Symbol_Table(19); -eineetwasgroessereHash-Tabelle$$
Function_Body: Statement_List;$$
end record;$$
$$
end Symbol_Table_Pkg;$$

Weiter: 12.2 Mehrfache Implementationen Hinauf: 12 Objektorientierte Konzepte Zurück: 12 Objektorientierte Konzepte