(**********************************************************************

    :Program.    Trees.def
    :Contents.   generic data type: binary trees
    :Author.     Nicolas Benezan [bne]
    :Address.    Postwiesenstr. 2, D7000 Stuttgart 60
    :Phone.      711/333679
    :Copyright.  Public Domain
    :Language.   Modula-2
    :Translator. M2Amiga A+L V3.2d
    :Imports.    TaskMemory [bne]
    :History.    V1.0 [bne] 25.Jun.1989
    :Update.     [bne] 15.Jul.1989 cosmetics, inline dokumentation
    :History.    V1.1 [bne] 13.Aug.1989 (bugs fixed, + InsertMode)

**********************************************************************)

DEFINITION MODULE Trees;

FROM SYSTEM     IMPORT ADDRESS, BYTE;

TYPE
  Tree;
  CompareProc=PROCEDURE(ADDRESS(*1st data*), ADDRESS(*2nd data*)): INTEGER;
  TreeProc=PROCEDURE(ADDRESS(* data *), ADDRESS(* Ref *));
  TreeNodePtr=POINTER TO TreeNode;
  TreeNode=RECORD
    l: TreeNodePtr;
    r: TreeNodePtr;
  (*data: AnyRecord *)
  END;

VAR
  TreesAllocProc: PROCEDURE(VAR ADDRESS, LONGINT);
  TreesDeallocProc: PROCEDURE(VAR ADDRESS);
  (* defaults: TaskMemory.Allocate, TaskMemory.Deallocate *)

PROCEDURE InitTree(VAR T: Tree;
                       AllowDupKeys: BOOLEAN;
                       Cmp: CompareProc): BOOLEAN;

(*:Semantic. Prepares a new Tree for further use.
  :Input.    T: uninitialised Tree
  :Output.   T: initialised Tree, if result is TRUE
  :Input.    AllowDupKeys: FALSE = duplicate keys cause errors
  :Input.    Cmp: procedure to compare two data records
  :Result.   TRUE if there was enough memory for the Tree
*)

PROCEDURE DiscardTree(VAR T: Tree);

(*:Semantic. Removes Tree and all its Nodes from memory.
  :Input.    T: initialised Tree
  :Output.   T: uninitialised Tree
*)

PROCEDURE Add(T: Tree;
              Node: ADDRESS): BOOLEAN;

(*:Semantic. Adds a new node to a Tree without moving or copying it.
  :Input.    T: properly initialised Tree
  :Input.    Node: Address of a structure which consists of a TreeNode
  :Input.          and further data
  :Result.   TRUE, if successful (in InsertMode "add" it never fails)
*)

PROCEDURE Put(T: Tree;
              Data: ARRAY OF BYTE): ADDRESS;

(*:Semantic. Copies data to a new place and Add()s it to the Tree.
  :Input.    T: properly initialised Tree
  :Input.    Data: any data record
  :Result.   address of where the data was copied to or NIL if failed
*)

PROCEDURE Get(T: Tree;
              Data: ADDRESS): ADDRESS;

(*:Semantic. Searches a node and returns the address of its data.
  :Input.    T: properly initialised Tree
  :Input.    Data: address of a dummy record containing only key data
  :Input.          needed by the compare procedure
  :Result.   address of the data (if found) or NIL
*)

PROCEDURE Do(T: Tree;
             Action: TreeProc;
             Ref: ADDRESS);

(*:Semantic. Performs <Action> with each node of <T> as parameter.
  :Input.    T: properly initialised Tree
  :Input.    Action: what to do with each data node
  :Input.    Ref: pointer to additional data
*)

PROCEDURE NodesInTree(T: Tree): LONGINT;

(*:Input.    T: properly initialised Tree
  :Result.   number of nodes in Tree
*)

END Trees.