// Generic CLR stacks are defined in the System assembly.
<pragma:references("system")>
<pragma:target("dll")>

// We are using pragmas as a temporal measure.
// In the final version, we'll do this using "projects".

using System, System.Collections.Generic;

namespace Freya.DataStructures.Trees;

public

    BinaryTree = class[X(IComparable)]
    public
        Visitor = method(Obj: X; Level: Integer);
    protected
        TreeNode = class;
        Root: TreeNode;
    public
        method Add(AValue: X);
            ensures Contains(AValue);
        method Contains(AValue: X): Boolean;
        iterator Preorder: X;
        method Visit(Action: Visitor);
    end;

    BinaryTree[X].TreeNode = class
    public
        constructor(AValue: X);

        property Value: X; readonly;
        property Left, Right: TreeNode;

        method Contains(AValue: X): TreeNode;
        method Visit(Action: Visitor; Level: Integer);
    end;

implementation for BinaryTree[X].TreeNode is

    constructor(AValue: X);
    begin
        Value := AValue;
    end;

    method Contains(AValue: X): TreeNode;
    begin
        var Rslt := AValue.CompareTo(Self.Value);
        if Rslt = 0 then
            Result := Self
        else
        begin
            Result := nil;
            if Rslt < 0 then
            begin
                if Left <> nil then
                    Result := Left.Contains(AValue);
            end
            else if Right <> nil then
                Result := Right.Contains(AValue);
        end;
    end;

    method Visit(Action: Visitor; Level: Integer);
    begin
        if Left <> nil then
            Left.Visit(Action, Level + 1);
        Action(Value, Level);
        if Right <> nil then
            Right.Visit(Action, Level + 1);
    end;

implementation for BinaryTree[X] is

    method Contains(AValue: X): Boolean;
    // Click here for the compiled IL code!
    begin
        Result := Root <> nil and Root.Contains(AValue) <> nil;
    end;

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

    method Visit(Action: Visitor);
    begin
        if Root <> nil then
            Root.Visit(Action, 0);
    end;

    iterator PreOrder: X;
    var
        St: Stack[TreeNode];
    begin
        if Root <> nil then
        begin
            St := new Stack[TreeNode];
            St.Push(Root);
            repeat
                var t := St.Pop;
                if t.Right <> nil then
                    St.Push(t.Right);
                if t.Left <> nil then
                    St.Push(t.Left);
                yield t.Value;
            until St.Count = 0;
        end;
    end;

end.