% Phil wrote the following sample code that implements all the operations
% that involve the nodes in the node class or subclasses.  
% It also solves the problems of circular references.  We did not expect all
% students to attempt this sort of solution.  It is provided for your
% interest.
% Note that the lists are not implemented as expected in the assignment.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution to A4:  Rhino Tree,  CSC148H, Summer96
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Code for the node classes
%
%       Written by Phil Edmonds, July 1996
%
%     - each class should be saved in the designated file
%     - all operations are implemented in the nodes, in true OO design
%     - used interface/body for LetterNode and NumberNode to get
%       around the circular reference problem
%     - the lists of members have been simplified to unsorted arrays
%     - the tree module (or class) would be just a bunch of one-liners that
%       call PrintPrefix or Insert on the root.
%     - of course, this code should have many more comments

% The generic node class
% Node in "node.t"
%--------------------------------
unit
class Node

    export Init, PrintPrefix, Insert

    type keyType : string (1)

    const MAX := 26

    var Key : keyType % this is redundant info
    var Level : int
    var Size : int % number of children of the node
    var Links : array 1 .. MAX of ^Node

    % Initialize
    %----------------
    deferred procedure Init (k : keyType, l : int)


    % return a pointer to the requested child
    %----------------
    deferred function Child (k : keyType) : ^Node


    % create a new child
    % ------------------
    deferred function NewChild (k : keyType) : ^Node


    % recursive Insert (calls NewChild to create a new child if nec.)
    %----------------
    proc Insert (pcode : string (6), name : string)
        var child : ^Node
        child := Child (pcode (1))

        %create and attach new child if one doesn't exist
        if child = nil then
            child := NewChild (pcode (1))
        end if

        % insert in the child
        child -> Insert (pcode (2 .. *), name)
    end Insert


    % Print recursively
    %----------------
    proc PrintPrefix (prefix : string (6))
        var child : ^Node

        % still have prefix so must follow path
        if prefix not= "" then
            child := Child (prefix (1))
            if child not= nil then
                child -> PrintPrefix (prefix (2 .. *))
            end if

            % no prefix, so print all children
        else
            for i : 1 .. Size
                child := Links (i)
                if child not= nil then
                    child -> PrintPrefix ("")
                end if
            end for
        end if
    end PrintPrefix

end Node



% Now, the tricky bits.
% A LetterNode must create new DigitNodes, and vice versa.  NewChild
% does the work, but to avoid circular references, the classes are
% split into an (empty) interface, and a body.  We always refer to the
% classes using the interface, which autimatically looks to the body
% to see what to do.
% 
% LetterNode in "let-node.t"  (interface)
%-------------------------------
unit
class LetterNode
    inherit Node in "node.t"
    implement by LetterNodeBody in "let-node.tb"
end LetterNode

% LetterNodeBody in "let-node.tb"  (body)
%---------------------------------
unit
class LetterNodeBody
    implement LetterNode in "let-node.t"
    import NumberNode in "num-node.t", LeafNode in "leaf-node.t"

    const first_key := "0"

    body procedure Init (k : keyType, l : int)
        Size := 10
        Level := l
        Key := k
        for i : 1 .. Size
            Links (i) := nil
        end for
    end Init

    body function Child (k : keyType) : ^Node
        var i : int := ord (k) - ord (first_key) + 1
        result Links (i)
    end Child

    body function NewChild (k : keyType) : ^Node
        var child : ^NumberNode

        if Level = 5 then
            new LeafNode, child
        else % otherwise it's a NumberNode
            new child
        end if

        % initialize it
        child -> Init (k, Level + 1)

        % set the ponter for the new child
        var i : int := ord (k) - ord (first_key) + 1
        Links (i) := child

        result child
    end NewChild

end LetterNodeBody


% NumberNode in num-node.t (interface)
%--------------------------------------
unit
class NumberNode
    inherit Node in "node.t"
    implement by NumberNode in "num-node.tb"
   
end NumberNode

% NumberNodeBody in num-node.tb (body)
%--------------------------------------
unit
class NumberNodeBody
    implement NumberNode in "num-node.t"
    import LetterNode in "let-node.t"

    const first_key := "A"

    body procedure Init (k : keyType, l : int)
        Size := 26
        Level := l
        Key := k
        for i : 1 .. Size
            Links (i) := nil
        end for
    end Init

    body function Child (k : keyType) : ^Node
        var i : int := ord (k) - ord (first_key) + 1
        result Links (i)
    end Child

    body function NewChild (k : keyType) : ^Node
        var child : ^LetterNode
        new child
        child -> Init (k, Level + 1)

        % set the ponter for the new child
        var i : int := ord (k) - ord (first_key) + 1
        Links (i) := child
        
        result child
    end NewChild

end NumberNodeBody


% Finally, we have the leaf node (which doesn't need to be split).
% The neat thing is that Insert and PrintPrefix are used to insert and
% print the list of members.
%


% LeafNode in "leaf-node.t"
%-----------------------------
unit
class LeafNode
    inherit NumberNode in "num-node.t"

    const MAX_PEOPLE := 10
    var people : array 1 .. MAX_PEOPLE of string
    var count := 0

    body proc Init(k : keyType, l : int)
        Size := 0
        Key := k
        Level := l
    end Init

    body proc Insert (pcode : string(6), name : string)
        if count < MAX_PEOPLE then
            count += 1
            people (count) := name
        end if
    end Insert

    body proc PrintPrefix(prefix : string(6))
        for i : 1 .. count
            put people (i)
        end for
    end PrintPrefix

end LeafNode