unit Freya.DataStructures.Trees;
public

    BinaryTree = class[X: IComparable]
    // El tipo paramétrico debe soportar la interfaz IComparable
    protected
        // Esta clase anidada terminará de declararse más adelante
        TreeNode = class[X: IComparable];
        Root: TreeNode of X;
    public
        procedure Add(Value: X);
            ensures Contains(Value);
        function Contains(AValue: X): Boolean;
        iterator Preorder: X;
    end;

    // Una clase anidada.
    // Puede declararse fuera de la clase principal...
    // ... para evitar la indentación excesiva.
    BinaryTree.TreeNode = class[X: IComparable]
    protected
        function Contains(AValue: X): BinaryTree.TreeNode[X];
    public
        constructor TreeNode(AValue: X);
        Value: X;
        Left, Right: BinaryTree.TreeNode of X;
        iterator Preorder: X;
    end;

private  // BinaryTree.TreeNode[X]

    // No es necesario repetir el parámetro genérico formal, como en:
    // constructor BinaryTree.TreeNode[X](AValue: X);
    // function BinaryTree.TreeNode[X].Contains(AValue: X): TTreeNode[X];

    constructor BinaryTree.TreeNode(AValue: X);
    // BinaryTree.TreeNode es el nombre de la clase anidada,
    // en vez de un par clase.constructor.
    // Los constructores de Freya son anónimos
    begin
        Value := AValue;
    end;

    function BinaryTree.TreeNode.Contains(AValue: X): TreeNode[X];
    begin
        if AValue = Value then
            Result := Self
        else
        begin
            Result := nil;
            if AValue < Value then
            begin
                if Left <> nil then
                    Result := Left.Contains(AValue);
            end
            else if Right <> nil then
                Result := Right.Contains(AValue);
        end;
    end;

    iterator BinaryTree.TreeNode.Preorder: X;
    begin
        Result := Value;
        Yield;
        if Left <> nil then
            for Result in Left.Preorder do Yield;
        if Right <> nil then
            for Result in Right.Preorder do Yield;
    end;

private  // BinaryTree[X]

    function BinaryTree.Contains(AValue: X): Boolean;
    begin
        Result := (Root <> nil) and (Root.Contains(AValue) <> nil);
    end;

    procedure BinaryTree.Add(AValue: X);
    var
        Parent, Current: TreeNode[X];
    begin
        Parent := nil;
        Current := Root;
        while (Current <> nil) and (Current.Value <> AValue) do
        begin
            Parent := Current;
            if AValue < Current.Value then
                Current := Current.Left
            else
                Current := Current.Right;
        end;
        if Current = nil then
        begin
            Current := new TreeNode[X](AValue);
            if Parent = nil then
                Root := Current
            else if AValue < Parent.Value then
                Parent.Left := Current
            else
                Parent.Right := Current;
        end;
    end;

    iterator BinaryTree.Preorder: X;
    begin
        if Root <> nil then
            for Result in Root.Preorder do
                Yield;
    end;

end.