% A binary tree class

unit
class BinaryTree
    export Init, InsertInPlace, PrintIt, CountLeaves

    type nodeType :
        record
            key : string
            left, right : ^nodeType
        end record


    var root : ^nodeType %    root of the tree


    %------------------------------------------------------------

    %--------------------
    % Initialize the tree
    %--------------------
    proc Init
        root := nil
    end Init

    %-----------------------------------
    % Insert a new element into the tree
    %-----------------------------------
    %  key is the string to insert
    %  place is an integer > 0 that represents the 'node number'
    %         in which the key should be inserted.  Nodes are numbered
    %         as if the tree was complete, one level at a time, left
    %         to right.  If the path to the node number does not yet exist,
    %         this procedure will insert at the first nil
    %         pointer it finds.


    proc InsertInPlace (place : int, key : string)
        var new_node : ^nodeType
        new new_node
        new_node -> key := key
        new_node -> left := nil
        new_node -> right := nil

        if root = nil then
            root := new_node
        else

            % converts place to a binary string
            % then can follow 'bits' to node.  "0" is left, "1" is right
            var dirs : string := intstr (place, 1, 2)
            var curr : ^nodeType := root
            var i : int := 2
            loop
                exit when i > length (dirs)

                if dirs (i) = "0" then
                    % go left
                    if curr -> left = nil then
                        curr -> left := new_node
                        exit
                    end if
                    curr := curr -> left
                elsif dirs (i) = "1" then
                    % go right
                    if curr -> right = nil then
                        curr -> right := new_node
                        exit
                    end if
                    curr := curr -> right
                end if
                i := i + 1
            end loop
        end if
    end InsertInPlace

    %--------------------------------------------------
    % Print all values in the tree.  Do it recursively.
    %  (not exported)
    %--------------------------------------------------
    %  curr is the current node
    %  tab is the current tabbing string (also contains formatting)
    %  dir is the direction we just came from (0 = left, 1 = right)

    proc recPrintIt (curr : ^nodeType, tab : string, dir : int)
        if curr not= nil then
            var link : string

            case dir of
                label 0 :
                    link := "|"
                label :
                    link := " "
            end case

            recPrintIt (curr -> right, tab + link + "  ", 1)

            case dir of
                label 0 :
                    link := "`"
                label 1 :
                    link := ","
                label :
                    link := " "
            end case

            put tab, link, "--", curr -> key

            case dir of
                label 1 :
                    link := "|"
                label :
                    link := " "
            end case
            recPrintIt (curr -> left, tab + link + "  ", 0)

        end if
    end recPrintIt


    %-----------------------------
    % Print all values in the tree
    %-----------------------------

    proc PrintIt
        recPrintIt (root, "", - 1)
    end PrintIt



    %--------------------------------------
    % Counts the number of leaves in a tree
    %--------------------------------------

    function CountLeaves : int

        %%%% YOUR CODE HERE %%%%%
        result 0    %%%% REMOVE THIS LINE, OF COURSE

    end CountLeaves


end BinaryTree