{##########################################################################
 # 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 }
.

.