-- Generic tree handling package.

    WITH text_io ; USE text_io ; -- make standard I/O available

    GENERIC

       TYPE elem IS PRIVATE ;
       WITH FUNCTION ">" ( x, y : elem ) RETURN BOOLEAN ;
       WITH PROCEDURE put ( x : elem ) ;

    PACKAGE tree_handler IS

-- Package Types :

    TYPE node ; -- full spec given later

    TYPE tree IS ACCESS node ; -- pointer type to node records

    TYPE node IS RECORD -- now give node record definition
       value : elem ;
       left  : tree ;
       right : tree ;
    END RECORD ;

-- Package Procedures :

-- insert => Put an element onto the tree.
    PROCEDURE insert ( t : IN OUT tree ; e : elem ) ;

-- put => Output the tree to the terminal.
    PROCEDURE put ( t : tree ) ;

    END tree_handler ; -------------------------------------------------

    PACKAGE BODY tree_handler IS

--    insert => Insert an element into a tree.
       PROCEDURE insert ( t : IN OUT tree ; e : elem ) IS

       BEGIN -- insert

--    if tree is empty then insert element here
-- debug
    PUT ( ">" ) ; PUT ( e ) ; PUT ( "<" ) ;

       IF t = NULL THEN
          t := NEW node'( e, NULL, NULL ) ; -- doesn't work
--        t := NEW node'( value => e, left => NULL, right => NULL ) ;
-- debug
--  t := NEW node ;
--  t.ALL := ( e,  NULL, NULL ) ; -- doesn't work either
--  t.value := e ;
--  t.right := NULL ;
--  t.left := NULL ;

    PUT ( ">" ) ; PUT ( t.value ) ; PUT ( "<" ) ; NEW_LINE ; -- debug

--    if element is greater than current one search right branch
       ELSIF e > t.value THEN
    PUT ( ">" ) ; PUT ( t.value ) ; PUT ( "<" ) ; NEW_LINE ; -- debug
          insert ( t.right, e ) ;

--    otherwise search left branch
       ELSE
    PUT ( ">" ) ; PUT ( t.value ) ; PUT ( "<" ) ; NEW_LINE ; -- debug
          insert ( t.left, e ) ;
       END IF ;

       END insert ; ----------------------------------------------------

--    put => Output tree contents in increasing order.
       PROCEDURE put ( t : tree ) IS

       BEGIN -- put

--    do nothing if tree is empty
       IF t /= NULL THEN

          put ( t.left ) ;  -- output left branch
          put ( t.value ) ; -- output current value
          NEW_LINE ;
          put ( t.right ) ; -- output right branch
       END IF ;

       END put ; -------------------------------------------------------

    END tree_handler ; -------------------------------------------------