% This code written by Phil Edmonds, July 29, 1996.
%
% It is slightly poor in style because it has very few comments.
%
%

% class for a node of a binary search tree
% Written by Phil Edmonds, July 29, 1996.
%
unit
class BSTnode
    import Types in "Types.t"
    export Init, Key, Data, Left, Right, Insert

    var Key : Types.key
    var Data : Types.data

    var Left : ^BSTnode
    var Right : ^BSTnode

    proc Init (k : Types.key, d : Types.data)
        Key := k
        Data := d
        Left := nil
        Right := nil
    end Init

    % a node knows how to insert a newnode into one of its subtrees

    proc Insert (k : Types.key, d : Types.data)
        
        % does it go on the left?
        if k < Key then
          
            if Left = nil then % create and insert on left
                new Left
                Left -> Init (k, d)
            else  % otherwise insert it into the left child
                Left -> Insert (k,d)
            end if

        % does it go on the right?
        elsif k > Key then

            if Right = nil then  % create and insert on right
                new Right
                Right -> Init (k, d)
            else % otherwise insert it into the right child
                Right -> Insert (k,d)
            end if

        end if
    end Insert

end BSTnode

%------cut here----------------

%
% A binary search tree module that uses the binary tree node class (BSTnode)
% Could be a class as well
% Written by Phil Edmonds, July 29, 1996.
%
unit
module BST
    import
        Types in "Types.t",
        BSTnode in "BST-node.t"
    export Init, Insert, InOrderPrint

    var root : ^BSTnode

    proc Init
        root := nil
    end Init

    %--------------------------
    % INSERT

    proc Insert (key : Types.key, data : Types.data)
        if root = nil then
            new root
            root -> Init (key, data)
        else
            root -> Insert (key, data)
        end if
    end Insert

    %-----------------------------
    % IN ORDER PRINT

    % recursive in-order traversal
    proc recInOrder (node : ^BSTnode)
        if node not= nil then
            recInOrder (node -> Left)
            put node -> Key, ": ", node -> Data
            recInOrder (node -> Right)
        end if
    end recInOrder

    proc InOrderPrint
        recInOrder (root)
    end InOrderPrint

end BST

%------------------cut here--------------------



unit
module Types
    export key,data
    
    type key : int
    type data : string
end Types