{##########################################################################
# UNBALANCED BINARY SEARCH TREE MODULE
#
# This module will take elements and insert them into a binary tree
# maintaining 'order' via the COMPARE function in UBSMOD.TYP. The tree
# remains unbalanced, however, so searching is dependent on input (the
# more random the input, the quicker the routine.
#
# NOTES:
#      1) Be sure to copy UBSMOD.TYP that contains the type definitions
#         of this module. Changing the 'element' type will require mod-
#         ification of the COMPARE and PRINT func/proc in the above file.
#      2) Your driver program should include the $I UBSMOD.EXT that defines
#         all of the external funct/procs, and $I UBSTYP.
#      3) Final linkage includes your DRIVER and UBSMOD.
#      4) There is a small UBSTST.PAS file that is a short test program
#         that you may use to test your change of the 'element' et.al.
#
# by DAVE HEYLIGER - AMUS STAFF
#
# last update: 09-12-85
############################################################################}

MODULE UBSMOD;

{+-- This module implements the following set operations using an unbalanced
|    binary search tree:
|
|           ubsmakenull -  initializes set to empty set
|
|           ubsinsert   - inserts element into set
|
|           ubssearch   - searches and if found retrieves element
|
|           ubsdump     - dumps the tree using an inorder traversal
+-----------------------------------------------------------------------}

{$I ubsmod.typ}

procedure ubsmakenull(var t: ubs);
{+-- on entry - true
|   on exit  - t represents an empty set
+----------------------------------------}
begin { ubsmakenull }
t := nil;
end; { ubsmakenull }


procedure ubsinsert(x: ubselement; var t: ubs);
{+-- on entry - t has been initialized previously,
|               if any node n compare(x,n)=0 then x replaces n.
|               compare determines '=','<','>' for ubselements.
|    on exit  - x is inserted into t
+-----------------------------------------------------------------}
begin { ubsinsert }
if t = nil
  then  begin { base case }
        new(t);
        t^.element := x;
        t^.left := nil; { no left subtree }
        t^.right := nil { no right subtree }
        end { base case }
  else if compare(x,t^.element) = -1 then ubsinsert(x,t^.left)
  else if compare(x,t^.element) = 0 then t^.element := x
  else ubsinsert(x,t^.right);
end; { ubsinsert }


function ubssearch(x: ubselement; var r: ubselement; t: ubs):boolean;
{+-- on entry - t has been initialized previously;
|    on exit  - returns true iff there is an element r in the tree such that
|               compare(x,r) = 0; in that case r is returned in r.
|               returns false otherwise.
+---------------------------------------------------------------------------}
begin { ubssearch }
if t = nil
 then ubssearch := false { not found }
 else if compare(x,t^.element) = -1
         then ubssearch := ubssearch(x,r,t^.left)
         else if compare(x,t^.element) = 0
                 then begin { found }
                      r := t^.element; { returns element }
                      ubssearch := true; { x found }
                      end { found }
                 else ubssearch := ubssearch(x,r,t^.right);
end; { ubssearch }


procedure ubsdump(t: ubs; var out: text);
{+-- on entry - t has been initialized previously
|    on exit  - tree contents is dumped on file out in a reasonable form;
|               inorder traversal is used
+------------------------------------------------------------------------}
begin { ubsdump }
if t <> nil
  then begin { non empty tree }
       ubsdump(t^.left,out);
       print(out,t^.element);
       ubsdump(t^.right,out);
       end; { non empty tree }
end; { ubsdump }