DEFINITION Lists;

IMPORT
  BT := BasicTypes;

TYPE
  NodePtr = POINTER TO Node;
  Node = RECORD (BT.ANYDesc) 
    next : NodePtr;
    prev : NodePtr;
  END;
  ListPtr = POINTER TO List;
  List = RECORD (BT.COLLECTIONDesc) 
    head : NodePtr;
    tail : NodePtr;
    PROCEDURE (list:ListPtr) Add(x: BT.ANY);
    PROCEDURE (list:ListPtr) Remove(x: BT.ANY);
    PROCEDURE (list:ListPtr) nbElements(): LONGINT;
    PROCEDURE (list:ListPtr) isEmpty(): BOOLEAN;
    PROCEDURE (list:ListPtr) Do(p: BT.DoProc; par: BT.ANY);
  END;
  DoProc = PROCEDURE(n: NodePtr);

PROCEDURE Init(VAR list: List);
PROCEDURE AddHead(VAR list: List; n: NodePtr);
PROCEDURE AddTail(VAR list: List; n: NodePtr);
PROCEDURE Remove(VAR list: List; n: NodePtr);
PROCEDURE RemHead(VAR list: List): NodePtr;
PROCEDURE RemTail(VAR list: List): NodePtr;
PROCEDURE AddBefore(VAR list: List; n, x: NodePtr);
PROCEDURE AddBehind(VAR list: List; n, x: NodePtr);
PROCEDURE Empty(VAR list: List): BOOLEAN;
PROCEDURE CountElements(VAR list: List): LONGINT;
PROCEDURE DoForward(VAR list: List; proc: DoProc);
PROCEDURE DoBackward(VAR list: List; proc: DoProc);
PROCEDURE Next(VAR n: NodePtr): BOOLEAN;
PROCEDURE Previous(VAR n: NodePtr): BOOLEAN;
PROCEDURE Succ(VAR n: NodePtr);
PROCEDURE Pred(VAR n: NodePtr);
PROCEDURE Head(VAR list: List): NodePtr;
PROCEDURE Tail(VAR list: List): NodePtr;

END Lists.