(**************************************************************************** :Program. ComplexLists.mod :Contents. list-module with complex extensions and many support-routines :Author. Richard Günther [gvm] :Address. HeilbronnerStr.267, 72760 Reutlingen :Phone. 07121/66432 :Copyright. Freeware :Language. Oberon2 :Translator. AmigaOberon v3.00d :Imports. none :History. V1.0 [gvm] 15-Dec-92 first implementation :History. V1.1 [gvm] 01-Jan-93 added Sublists and Check :History. V1.2 [gvm] 17-Jan-93 added Sorted and MultiUser :History. V1.2a[gvm] 20-Jan-93 tried to use Assembler code (not ready yet) :History. V1.3 [gvm] 05-Jun-93 added SaveLoad and Duplicate/Copy :History. V1.4 [gvm] 16-Jun-93 MultiUser rewritten, fixed bugs :History. V1.5 [gvm] 04-Sep-93 changed Sort-algorithm to QuickSort :History. V1.5b[gvm] 05-Sep-93 Sort rewritten, fixed bugs :History. V1.5c[gvm] 04-Oct-93 using new IdentifiedTypes-module :Bugs. not 90% compatible with OberonLists, not 100% tested ****************************************************************************) COPYRIGHT: Dieses Modul darf ohne Einschränkungen in nicht kommerziellen (Shareware ist kommerziell) Programmen verwendet werden. Für anderweitige Verwendung ist meine schriftliche Zustimmung nötig, setzen Sie sich bitte mit mir in Verbindung. Dieses Modul darf nur in seinem vollen Umfang (Dokumentation, Quellcode) und nur zum Selbstkostenpreis (maximal 5 Deutsche Mark) vertrieben werden. Ich übernehme keine Garantie für die Fehlerfreiheit dieses Moduls. Die ver- wendung der Routinen ist auf eigene Gefahr, für eventuelle Schäden an Daten oder Programmen wird keine Haftung übernommen! INHALT: ComplexLists ist ein Listenmodul, das neben den zu AmigaOberon's Listenmodul weitgehend kompatiblen Routinen umfangreiche Unter- stützung von Listenbäumen, sortierten Listen, Listendateien und Schutzmechanismen für den Zugriff von mehreren Tasks aus enthält. Die Verwendung des GarbageCollectors ist zwingend notwendig. KOMPATIBLITÄT ZU Oberon3.0s LinkedLists: Im Folgenden werden die Routinen aufgelistet, für die eine Entsprechende Routine in LinkedLists zur Verfügung steht, die nicht dem Syntax von ComplexLists entsprechen: - next,prev,head und tail werden in LinkedLists direkt aus den Strukturen gelesen und sind nicht durch Methoden realisiert. Verwenden Sie bitte in ComplexLists die entsprechenden Methoden Next(), Prev(), Head() und Tail(). - nbElements() existiert in ComplexLists nicht. Stattdessen wird in ComplexLists die Anzahl der Elemente über den Zugriff auf das Feld numElements in der Listen-Struktur erfahren. - isEmpty() existiert unter dem Namen Empty() - Do erwartet einen zusätzlichen Parameter action (s.u.), durch ihn wird auch DoBackward überflüssig. - Remove gibt es nicht in der Form list.Remove(e:BT.ANY) ComplexLists ist keine Erweiterung von BasicTypes.COLLECTION! Dies war nicht möglich, da die Listenstruktur eine Erweiterung von Node ist. STRUKTUR-BESCHREIBUNGEN: Node-Struktur: Node = POINTER TO RECORD (IdentifiedTypes.IDENT) root: List; END; Das Element root ist das einzige, auf das zugegriffen werden darf, allerdings auch nur lesend! Es enthält die Liste, in der die Node steht oder NIL, falls sie in keiner Liste ist. List-Struktur: List = POINTER TO RECORD (Node) numElements: LONGINT; flags: SET; semaphore: Exec.SignalSemaphore; END; Auf alle Elemente darf nur lesend zugegriffen werden! - numElements enthält die Anzahl der Elemente, die in der Liste sind oder 0, wenn die Liste leer ist. - flags enthält den Listenstatus, d.h. ob die Liste sortiert ist und in welcher Richtung, ob eine Semaphore initialisiert ist und ob die Liste öffentlich ist. Für nähere Informationen lesen Sie bitte den Quelltext. - semaphore enthält die Semaphore, die Sie benötigen, wenn Sie mit Exec auf die Liste zugreifen wollen und diese nicht öffentlich ist. Näheres siehe RKM, semaphore ist kein Pointer! In der Semaphore-Struktur existiert ein Element, das den Zugriff auf die Liste ermöglicht: ListSemaphore = UNTRACED POINTER TO STRUCT (Exec.SignalSemaphore) list: List END; Zugriff über: semaphore(ListSemaphore).list PROZEDUR-BESCHREIBUNGEN: Prozeduren zur elementaren Listenverarbeitung: PROCEDURE Create(): List; Diese Prozedur erzeugt eine neue, initialisierte Liste. Achtung! Diese Prozedur kann NIL zurückgeben, wenn nicht genug Speicher für eine neue Liste vorhanden ist. PROCEDURE (list:List) Init; Initialisiert die Liste. Es werden dabei alle Elemente der Liste entfernt und eventuelle Flags gelöscht. Eine installierte Semaphore wird ebenfalls entfernt. PROCEDURE (list:List) Empty(): BOOLEAN; Gibt TRUE zurück, wenn die Liste leer ist. Der Aufruf kann ersetzt werden durch "IF list.numElements=0 THEN ...". PROCEDURE (list:List) Head(): Node; Gibt das erste Element der Liste zurück. Achtung! Diese Prozedur kann NIL zurückgeben, wenn die Liste leer ist. PROCEDURE (list:List) Tail(): Node; Gibt das letzte Element der Liste zurück. Achtung! Diese Prozedur kann NIL zurückgeben, wenn die Liste leer ist. PROCEDURE (node:Node) Next(): Node; Nächstes Listenelement erfragen. Achtung! Diese Prozedur kann NIL zurückgeben, wenn node das letzte Element der Liste war. PROCEDURE (node:Node) ExistsNext(): BOOLEAN; Gibt TRUE zurück, wenn ein nächstes Element existiert. PROCEDURE (node:Node) Prev(): Node; Vorheriges Listenelement erfragen. Achtung! Diese Prozedur kann NIL zurückgeben, wenn node das erste Element der Liste war. PROCEDURE (node:Node) ExistsPrev(): BOOLEAN; Gibt TRUE zurück, wenn ein vorheriges Element existiert. PROCEDURE (node:Node) IsElementOf(list: List): BOOLEAN; Gibt TRUE zurück, wenn node ein Element von list ist. Der Aufruf läßt sich auch durch "IF node.root=list THEN ..." ersetzen. PROCEDURE (node:Node) Go(offset: LONGINT): Node; Geht vom Element node aus offset Elemente richtung Listenkopf (offset>0), bzw. richtung Listenende (offset<0). Wenn der offset über das Listenende/den Listenanfang hinausgeht, wird das erste bzw. letzte Element zurückgegeben. PROCEDURE (list:List) Goto(position: LONGINT): Node; Gibt das position-ste Element der Liste zurück. Achtung! Diese Prozedur kann NIL zurückgeben, wenn das position-ste Element nicht existiert. PROCEDURE (node:Node) Position(): LONGINT; Gibt die Nummer des Elements in der Liste zurück, wobei vom Kopf aus gezählt wird und das erste Element die Nummer 1 hat. PROCEDURE (node:Node) Remove; Entfernt das Element aus der Liste. PROCEDURE (node:Node) AddBefore(n: Node); Fügt das Element n vor node in die Liste, in der node steht ein. PROCEDURE (node:Node) AddBehind(n: Node); Fügt das Element n hinter node in die Liste, in der node steht ein. PROCEDURE (node:Node) MoveBefore(n: Node); Fügt das Element n vor node in die Liste, in der node steht ein. Falls n schon in einer Liste war, wird es zuvor aus ihr entfernt. PROCEDURE (node:Node) MoveBehind(n: Node); Fügt das Element n hinter node in die Liste, in der node steht ein. Falls n schon in einer Liste war, wird es zuvor aus ihr entfernt. PROCEDURE (node:Node) Swap(n: Node); Vertauscht die Positionen von node und n. PROCEDURE (list:List) RemHead(): Node; Entfernt das erste Element der Liste und gibt es zurück. Achtung! Diese Prozedur kann NIL zurückgeben, wenn die Liste leer ist. PROCEDURE (list:List) RemTail(): Node; Entfernt das letzte Element der Liste und gibt es zurück. Achtung! Diese Prozedur kann NIL zurückgeben, wenn die Liste leer ist. PROCEDURE (list:List) Add(n: Node); Fügt das Element n in die Liste list ein. PROCEDURE (list:List) AddHead(n: Node); Hängt das Element n an den Anfang der Liste list an. PROCEDURE (list:List) AddTail(n: Node); Hängt das Element n an das Ende der Liste list an. PROCEDURE (list:List) Move(n: Node); Fügt das Element n in die Liste list ein. Falls n schon in einer Liste war, wird es zuvor aus ihr entfernt. PROCEDURE (list:List) MoveHead(n: Node); Hängt das Element n an den Anfang der Liste list an. Falls n schon in einer Liste war, wird es zuvor aus ihr entfernt. PROCEDURE (list:List) MoveTail(n: Node); Hängt das Element n an das Ende der Liste list an. Falls n schon in einer Liste war, wird es zuvor aus ihr entfernt. Komplexere Listenprozeduren: PROCEDURE (list: List) Test*(): LONGINT; Testet die Integrität der Liste. Die Nummer des fehlerhaften Elements wird zurückgegeben, wenn alles OK war, dann -1. PROCEDURE (list: List) Do*(action: SET; proc: DoProc; arg: BT.ANY): BOOLEAN; Mit Hilfe dieser Prozedur kann die gesamte Listenstruktur einer Liste bearbeitet werden. Im Feld action gibt man an, ob Unterlisten bearbeitet werden sollen ({recursive}) und ob vorwärts ({}) oder rückwärts vorge- gangen werden soll ({backward}). Falls Unterlisten bearbeitet werden, werden die Listenköpfe ausgelassen, wenn Sie nicht {doListsFirst} (erst die Listenköpfe) oder {doListsSecond} (Listenköpfe nach ihren Elementen) angeben. Bei Angabe von beiden Flags wird der Listenkopf vor und nach den Elementen der Unterliste bearbeitet. Bei proc gibt man eine Prozedur der Form PROCEDURE(list: List; node: Node; arg: BT.ANY): BOOLEAN; an, die als Parameter die gerade in Bearbeitung befindliche Liste, die zu bearbeitende node und die an Do übergebene Argumentstruktur erhält. Die Prozedur sollte TRUE zurückgeben, wenn mit der Bearbeitung fortgefahren werden soll und FALSE, wenn die Bearbeitung der Liste abge- brochen werden soll. Do gibt TRUE zurück, wenn die Bearbeitung vollständig durchgeführt wurde und FALSE, falls sie unterbrochen wurde. Prozeduren zur Unterstützung sortierter Listen: PROCEDURE (list: List) SetSortParameters(criteria: SET; proc: SortProc); Diese Methode legt für die Liste den zu verwendenden Sortieralgorithmus und die Parameter für die Sortierreihenfolge fest. Bei criteria geben Sie bitte ComplexLists.ascending an, um die Liste in aufsteigender Reihenfolge (Head-Element ist kleinstes Element) zu sortieren, geben sie dieses Flag nicht an, so wird die Liste in ab- steigender Reihenfolge sortiert. Geben Sie ComplexLists.listsTop an, um die Unterlisten am Kopf der Liste zu sammeln, wenn Sie dieses Flag nicht angeben, sammeln sich die Listenköpfe der Unterlisten am Ende der Liste. Bei proc tragen Sie bitte die von Ihnen bevorzugte Sortierprozedur ein. Tragen Sie hier NIL ein, wenn Sie die alte Einstellung behalten wollen. Wenn Sie die Sortierreihenfolge verändert haben, wird die Liste auto- matisch neu sortiert. Diese Methode müssen Sie nicht unbedingt aufrufen, die Voreinstellungen sind ComplexLists.QuickSort als Sortierroutine und aufsteigende Sortierung mit Unterlisten am Kopf der Liste. PROCEDURE (node:Node) Compare(n: Node): INTEGER; Diese Methode muß (sollte) für jeden neuen Datentyp überschrieben werden. Sie muß Werte kleiner Null zurückgeben, wenn node kleiner als n ist, Null, wenn node gleich n ist und Werte größer Null, falls node größer n ist. PROCEDURE (list: List) Sort; Diese Prozedur sortiert die Liste nach dem bei SetSortParameters angegebenem Verfahren (voreingestellt ist QuickSort). Sie benötigt dafür für jeden Datentyp eine korrekt implementierte Compare-Methode. PROCEDURE (list:List) AddSorted(node: Node); Fügt node in die sortierte Liste list ein. Anstatt dieser Prozedur sollte immer Add verwendet werden. Add ruft, wenn die Liste sortiert ist, AddSorted auf. Prozeduren zur Unterstützung von Unterlisten bzw. Listenbäumen: PROCEDURE (list:List) Root(): List; Gibt die oberste Liste des Listenbaums zurück. PROCEDURE (node:Node) IsInListTreeOf(list: List): BOOLEAN; Gibt TRUE zurück, wenn node Element von list oder einer ihrer Unterlisten ist. PROCEDURE (list:List) Expand; Löst die Liste list auf und fügt ihre Elemente in die nächst höhere Liste ein. Dieser Versuch kann fehlschlagen, wenn es keine höhere Liste gibt, dies wird über einen Requester gemeldet. PROCEDURE (list:List) Merge(l: List); Hängt die Liste l an die Liste list an. Prozeduren zum Laden und Speichern von Listen und ihren Elementen: Prozeduren und Methoden für diese Fähigkeit werden vom Modul IdentifiedTypes zur Verfügung gestellt. Daher ist es wichtig, daß jede Erweiterung von Node bei diesem Modul angemeldet wird (näheres dazu in der Dokumentation zu diesem Modul). Hier sind nur die für die Typen Node und List benötigten Methoden (Read, Write und Copy) definiert, die Typen werden angemeldet. Die Write-, Read- (und Copy-) Methoden sollten für jeden Datentyp definiert werden. Beispiel und nähere Erläuterungen finden Sie in der Dokumentation zu IdentifiedTypes. Prozeduren zum Schutz von Listen bei Zugriffen von mehreren Tasks aus: Die Schutzmechanismen beruhen auf den von Exec zur Verfügung gestellten Semaphoren, daher ist es sinnvoll, wenn Sie sich über deren Funktions- weise informieren (z.B. im RKM Libraries). Exec bietet nur kooperative Schutzmechanismen, sodaß Sie, falls Sie Semaphoren verwenden, unbedingt von den Exec-Funktionen gebrauch machen sollten. PROCEDURE MakeSemaphore(list: List; name: ARRAY OF CHAR); Erzeugt für die Liste eine Semaphore. In name können Sie optional den Namen angeben, den die Liste erhalten sollen, wenn Sie sie in die globale Exec-Semaphore-Liste einfügen wollen. Wenn Sie dies nicht wollen, übergeben Sie hier einfach "". Sie können die Prozedur mehrfach aufrufen, z.B. um die Liste global sichtbar zu machen oder um den Namen zu ändern. PROCEDURE DeleteSemaphore(list: List); Entfernt die Semaphore wieder. Diese Prozeduren sind nicht bzw. nur ungenügend getestet! Bei eventuellen Problemen bitte ich Sie, mir diese mitzuteilen. Viel Spaß mit dem Modul, für eventuelle Probleme und Anregungen stehe ich gerne zur Verfügung.