% File "ftree.tu".
%
%
% FamilyTree records all the births in a structured format for a family
% of animals.  A family of animals is defined as the set of animals who
% all have the same ancestor, who has no ancestor himself.  I.e., this
% ancestor is the root of a tree of children.
%
%+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

unit
class FamilyTree

    import Animal in "animal.tu"

    export Init, AddMember, Prnt

    %========== INSTANCE VARIABLES ==============================
    %============================================================

    const MaxKids := 20


    type TreeNode :
        record
            member : ^Animal
            num_children : int
            child : array 1 .. MaxKids of ^TreeNode
        end record

    var ancestor : ^TreeNode


    %=========== PRIVATE FUNCTIONS ==============================
    %============================================================

    function newTreeNode (a : ^Animal) : ^TreeNode
        var tnode : ^TreeNode
        new tnode
        tnode -> member := a
        tnode -> num_children := 0
        result tnode
    end newTreeNode

    proc recInsertNode (root : ^TreeNode, parent : ^Animal,
            child : ^TreeNode)

        var n := root -> num_children

        if root = nil then
            return

        elsif root -> member = parent then

            % we've found the parent!
            root -> child (n + 1) := child
            root -> num_children := n + 1

        else

            % look for parent in each sub-tree
            for c : 1 .. n
                recInsertNode (root -> child (c), parent, child)
            end for
        end if
    end recInsertNode


    proc recTreePrint (stream : int, root : ^TreeNode, tab : string)

        if root = nil then
            return
        else
            put : stream, tab ..
            root -> member -> Prnt (stream)
            put : stream, ""
            var n := root -> num_children
            for c : 1 .. n
                var child := root -> child (c)
                recTreePrint (stream, child, tab + "  ")
            end for
        end if
    end recTreePrint

    %========== INITIALIZER =====================================
    %============================================================

    % initialize the three instance variables
    %------------------------------------------------------------
    proc Init (member : ^Animal)
        ancestor := newTreeNode (member)
    end Init




    %========== PUBLIC FUNCTIONS ================================
    %============================================================


    proc AddMember (parent1 : ^Animal, member : ^Animal,
            parent2 : ^Animal)

        var child : ^TreeNode
        child := newTreeNode (member)

        recInsertNode (ancestor, parent1, child)

    end AddMember


    % print the tree
    %------------------------------------------------------------
    proc Prnt (stream : int)

        recTreePrint (stream, ancestor, "")

    end Prnt

end FamilyTree