with Ada.Text_IO, Ada.Integer_Text_IO, Ada.Numerics.Discrete_Random;
use Ada.Text_IO, Ada.Integer_Text_IO;

procedure Lab4Tree is

  type Node is
    record
      Data : Integer := 0;
      Parent: access Node := Null;
      Left : access Node := Null;
      Right : access Node := Null;
    end record;

  type Node_Ptr is access all Node;

  procedure PrintNode(Tree : Node_Ptr; Indent : String) is
  begin
    Put(Indent);
    Put(Tree.Data, 4);
    New_Line;
    if Tree.Left /= Null then
      PrintNode(Tree.Left, Indent & " ");
    end if;
    if Tree.Right /= Null then
      PrintNode(Tree.Right, Indent & " ");
    end if;
  end PrintNode;

  procedure Print(Tree : Node_Ptr) is
    Tmp : Node_Ptr := Tree;
  begin
    if Tree = Null then
      Put_Line("Empty tree");
    else
      PrintNode(Tmp, "");
    end if;
  end Print;

  procedure Insert(Tree : in out Node_Ptr; Data : Integer) is
    N : Node_Ptr := new Node;
  begin
    if Tree = Null then
      N.Parent := Null;
      N.Data := Data;
      N.Left := Null;
      N.Right := Null;
      Tree := N;
    else
      if Data < Tree.Data then
        if Tree.Left = Null then
          Tree.Left := N;
          N.Parent := Tree;
          N.Data := Data;
          N.Left := Null;
          N.Right := Null;
        else
          Insert(Tree.Left, Data);
        end if;
      else
        if Tree.Right = Null then
          Tree.Right := N;
          N.Parent := Tree;
          N.Data := Data;
          N.Left := Null;
          N.Right := Null;
        else
          Insert(Tree.Right, Data);
        end if;
      end if;
    end if;
  end Insert;

  procedure Generate_Random_Tree(Tree: out Node_Ptr; N, M: Integer) is
    subtype Elem_Range is Integer range 0 .. M;
    package Random_Range is new Ada.Numerics.Discrete_Random(Elem_Range);
    use Random_Range;
    Gen : Generator;
  begin
    Reset(Gen);
    for I in Integer range 1 .. N loop
      Insert(Tree, Random(Gen) mod M);
    end loop;
  end Generate_Random_Tree;

  function Search(Tree: in out Node_Ptr; Data: Integer) return Node_Ptr is
  begin
    if Tree.Data = Data or else Tree = Null then
      return Tree;
    elsif Data > Tree.Data then
      return Search(Tree.Right, Data);
    else
      return Search(Tree.Left, Data);
    end if;
  end Search;

  procedure Delete_Node(Node_To_Delete: in out Node_Ptr; Replacement:  Node_Ptr) is
  begin
    if Node_To_Delete.Parent = Null then
      Node_To_Delete := Replacement;
    elsif Node_To_Delete.Data > Node_To_Delete.Parent.Data then
      Node_To_Delete.Parent.Right := Replacement;
    else
      Node_To_Delete.Parent.Left := Replacement;
    end if;
  end Delete_Node;

  function Find_Right_Parent(Node: in out Node_Ptr) return Node_Ptr is
    Right_Parent: Node_Ptr := Null;
  begin
    if Node.Parent /= Null then
      if Node.Parent.Left = Node then
        Right_Parent := Node.Parent;
      else
        Right_Parent := Find_Right_Parent(Node.Parent);
      end if;
    end if;
    return Right_Parent;
  end Find_Right_Parent;

  function Find_Successor(Node: in out Node_Ptr) return Node_Ptr is
    Tmp: Node_Ptr := Null;
    Successor: Node_Ptr := Null;
  begin
    if Node.Right /= Null then
      Tmp := Node.Right;
      while Tmp /= Null loop
        Successor := Tmp;
        Tmp := Tmp.Left;
      end loop;
    else
      Successor := Find_Right_Parent(Node);
    end if;
    return Successor;
  end Find_Successor;

  procedure Delete(Tree: in out Node_Ptr; Data: Integer) is
    Successor : Node_Ptr := Null;
  begin
    if Tree = Null then
      return;
    elsif Data > Tree.Data then
      Delete(Tree.Right, Data);
    elsif Data < Tree.Data then
      Delete(Tree.Left, Data);
    else
      if Tree.Left = Null and Tree.Right = Null then
        Delete_Node(Tree, Null);
      elsif Tree.Left = Null and Tree.Right /= Null then
        Delete_Node(Tree, Tree.Right);
        Tree.Right.Parent := Tree.Parent;
      elsif Tree.Left /= Null and Tree.Right = Null then
        Delete_Node(Tree, Tree.Left);
        Tree.Left.Parent := Tree.Parent;
      else
        Successor := Find_Successor(Tree);
        Delete(Successor, Successor.Data);
        Successor.Parent := Tree.Parent;
        Successor.Left := Tree.Left;
        Successor.Right := Tree.Right;
        Delete_Node(Tree, Successor);
      end if;
    end if;
  end Delete;

  TreeInstance : Node_Ptr := Null;

begin
  Insert(TreeInstance, 8);
  Insert(TreeInstance, 3);
  Insert(TreeInstance, 10);
  Insert(TreeInstance, 1);
  Insert(TreeInstance, 6);
  Insert(TreeInstance, 4);
  Insert(TreeInstance, 7);
  Insert(TreeInstance, 14);
  Insert(TreeInstance, 13);
  Print(TreeInstance);
  Put_Line("------");
  Delete(TreeInstance, 13);
  Print(TreeInstance);
end Lab4Tree;