Amiga ISO Collection/AmigaUtilCD2.iso/Programming/Misc/OB3.2D2.DMS/in.adf/Module/linkedlists.mod

Text File | 1994-08-05 | 4.6 KB | 204 lines

(*-------------------------------------------------------------------------*)
(*                                                                         *)
(*  Amiga Oberon Library Module: LinkedList           Date: 02-Nov-92      *)
(*                                                                         *)
(*   © 1992 by Fridtjof Siebert                                            *)
(*                                                                         *)
(*-------------------------------------------------------------------------*)

MODULE LinkedLists;

IMPORT
(* $IFNOT NoCheck *)
       Requests,
(* $END *)
       BT * := BasicTypes;


TYPE
  Node * = POINTER TO NodeDesc;
  List * = POINTER TO ListDesc;

  NodeDesc * = RECORD (BT.ANYDesc)
    next-,prev-: Node;
    list: List;
  END;

  ListDesc* = RECORD (BT.COLLECTIONDesc);
    head-: Node;
    tail-: Node;
    remallowed: INTEGER;
    numElements: LONGINT;
  END;


PROCEDURE Create * (): List;
VAR
  list: List;
BEGIN
  NEW(list);
  RETURN list;
END Create;


PROCEDURE (list: List) Init*;
BEGIN
  list.head := NIL;
  list.tail := NIL;
  list.remallowed := 0;
  list.numElements := 0;
END Init;


PROCEDURE (list: List) AddHead*(n: Node);
BEGIN
(* $IFNOT NoCheck THEN *)
  IF n.list#NIL THEN Requests.Fail("LinkedLists: Element added to two lists!") END;
(* $END *)
  n.list := list;
  n.next := list.head;
  n.prev := NIL;
  IF n.next=NIL THEN list.tail   := n;
                ELSE n.next.prev := n END;
  list.head := n;
  INC(list.numElements);
END AddHead;


PROCEDURE (list: List) AddTail*(n: Node);
BEGIN
(* $IFNOT NoCheck THEN *)
  IF n.list#NIL THEN Requests.Fail("LinkedLists: Element added to two lists!") END;
(* $END *)
  n.list := list;
  n.prev := list.tail;
  n.next := NIL;
  IF n.prev=NIL THEN list.head   := n;
                ELSE n.prev.next := n END;
  list.tail := n;
  INC(list.numElements);
END AddTail;


PROCEDURE (n: Node) Remove*;
BEGIN
(* $IFNOT NoCheck THEN *)
  IF (n.list=NIL) THEN Requests.Fail("LinkedLists: Remove called with Element not added to a list!") END;
  IF (n.list.remallowed#0) THEN Requests.Fail("LinkedLists: Remove called within Do or DoBackward") END;
(* $END *)
  IF n.next#NIL THEN n.next.prev := n.prev ELSE n.list.tail := n.prev END;
  IF n.prev#NIL THEN n.prev.next := n.next ELSE n.list.head := n.next END;
  DEC(n.list.numElements);
  n.list := NIL;
END Remove;


PROCEDURE (list: List) RemHead*(): Node;
VAR n: Node;
BEGIN
  n := list.head;
  IF n#NIL THEN n.Remove END;
  RETURN n;
END RemHead;


PROCEDURE (list: List) RemTail*(): Node;
VAR n: Node;
BEGIN
  n := list.tail;
  IF n#NIL THEN n.Remove END;
  RETURN n;
END RemTail;


PROCEDURE (x: Node) AddBefore*(n: Node);
(* fügt n vor x in die Liste ein *)

BEGIN
(* $IFNOT NoCheck THEN *)
  IF x.list=NIL THEN Requests.Fail("LinkedLists: AddBefore() called with Element not added to a list!") END;
  IF n.list#NIL THEN Requests.Fail("LinkedLists: Element added to two lists!") END;
(* $END *)
  n.prev := x.prev;
  n.next := x;
  x.prev := n;
  IF n.prev=NIL THEN x.list.head := n
                ELSE n.prev.next := n END;
  INC(x.list.numElements);
  n.list := x.list;
END AddBefore;


PROCEDURE (x: Node) AddBehind*(n: Node);
(* fügt n hinter x in die Liste ein *)

BEGIN
(* $IFNOT NoCheck THEN *)
  IF x.list=NIL THEN Requests.Fail("LinkedLists: AddBehind() called with Element not added to a list!") END;
  IF n.list#NIL THEN Requests.Fail("LinkedLists: Element added to two lists!") END;
(* $END *)
  n.next := x.next;
  n.prev := x;
  x.next := n;
  IF n.next=NIL THEN x.list.tail := n
                ELSE n.next.prev := n END;
  INC(x.list.numElements);
  n.list := x.list;
END AddBehind;


PROCEDURE (list: List) Add * (x: BT.ANY);
(* add x to c.
 * depending on the implementation it is added at some point to the
 * collection.
 *)

BEGIN
  list.AddTail(x(Node));
END Add;


PROCEDURE (list: List) Remove * (x: BT.ANY);
(* removes x from c.
 *)

BEGIN
  x(Node).Remove;
END Remove;


PROCEDURE (list: List) nbElements * (): LONGINT;
(* returns the number of elements within c.
 *)
BEGIN
  RETURN list.numElements;
END nbElements;


PROCEDURE (list: List) Do * (p: BT.DoProc; par: BT.ANY);
(* calls p(x,par) for every element x stored within c.
 * par passes some additional information to p. par is not touched by Do.
 *)

VAR n: Node;
BEGIN
  INC(list.remallowed);
  n := list.head; WHILE n#NIL DO p(n,par); n := n.next END;
  DEC(list.remallowed);
END Do;


PROCEDURE (list: List) DoBackward*(p: BT.DoProc; par: BT.ANY);
VAR n: Node;
BEGIN
  INC(list.remallowed);
  n := list.tail; WHILE n#NIL DO p(n,par); n := n.prev END;
  DEC(list.remallowed);
END DoBackward;


END LinkedLists.