with Ada.Text_IO;

package body Red_Black_Trees is
   function Create(Item: Item_Type) return Tree_Type_Access is
      Node : Tree_Type_Access;
   begin
      Node := new Tree_Type'(Item, Black, Null, Null, Null);
      return Node;
   end Create;

--  --     procedure Rotate_Left(Root : in out Tree_Type_Access; X : in out Tree_Type_Access) is
--  --        Y : Tree_Type_Access;
--  --     begin
--  --        Y := X.Right;
--  --        X.Right := Y.Left;
--  --
--  --        if X.Right /= Null then
--  --           X.Right.Parent := X;
--  --        end if;
--  --
--  --        Y.Parent := X.Parent;
--  --
--  --        if X.Parent = Null then
--  --           Root := Y;
--  --        else if X = X.Parent.Left then
--  --              X.Parent.Left := Y;
--  --           else
--  --              X.Parent.Right := Y;
--  --           end if;
--  --        end if;
--  --
--  --        Y.Left := X;
--  --        X.Parent := Y;
--  --     end Rotate_Left;
--  --
--  --     procedure Rotate_Right(Root : in out Tree_Type_Access; Y : in out Tree_Type_Access) is
--  --        X : Tree_Type_Access;
--  --     begin
--  --        X := Y.Left;
--  --        Y.Left := X.Right;
--  --        if X.Right /= Null then
--  --           X.Right.Parent := Y;
--  --        end if;
--  --
--  --        X.Parent := Y.Parent;
--  --        if X.Parent = Null then
--  --           Root := X;
--  --        else if Y = Y.Parent.Left then
--  --              Y.Parent.Left := X;
--  --           else
--  --              Y.Parent.Right := X;
--  --           end if;
--  --        end if;
--  --        X.Right := Y;
--  --        Y.Parent := X;
--  --     end Rotate_Right;
--
--     procedure Swap_Color(C1: in out Color_Type; C2: in out Color_Type) is
--        Tmp_Col : Color_Type := C1;
--     begin
--        C1 := C2;
--        C2 := Tmp_Col;
--     end Swap_Color;
--
--     procedure Balance(Root: in out Tree_Type_Access; Z : in out Tree_Type_Access) is
--        Y : Tree_Type_Access;
--     begin
--        Ada.Text_IO.Put_Line("In Balance");
--
--        while Z /= Root and then Z.Parent.Col = Red loop
--           if Z.Parent = Z.Parent.Parent.Left then
--              Y := Z.Parent.Parent.Right;
--           else
--              Y := Z.Parent.Parent.Left;
--           end if;
--
--           if Y.Col = Red then
--              Y.Col := Black;
--              Z.Parent.Col := Black;
--              Z.Parent.Parent.Col := Red;
--              Z := Z.Parent.Parent;
--           else
--              if Z.Parent = Z.Parent.Parent.Left and then Z = Z.Parent.Left then
--                 Swap_Color(Z.Parent.Col, Z.Parent.Parent.Col);
--                 Rotate_Right(Root, Z.Parent.Parent);
--              end if;
--
--              if Z.Parent = Z.Parent.Parent.Left and then Z = Z.Parent.Right then
--                 Swap_Color(Z.Col, Z.Parent.Parent.Col);
--                 Rotate_Left(Root, Z.Parent);
--                 Rotate_Right(Root, Z.Parent.Parent);
--              end if;
--
--              if Z.Parent = Z.Parent.Parent.Right and then Z = Z.Parent.Right then
--                 Swap_Color(Z.Parent.Col, Z.Parent.Parent.Col);
--                 Rotate_Left(Root, Z.Parent.Parent);
--              end if;
--
--              if Z.Parent = Z.Parent.Parent.Right and then Z = Z.Parent.Left then
--                 Swap_Color(Z.Col, Z.Parent.Parent.Col);
--                 Rotate_Right(Root, Z.Parent);
--                 Rotate_Left(Root, Z.Parent.Parent);
--              end if;
--           end if;
--           Root.Col := Black;
--        end loop;
--
--
--     end Balance;
--
--     function Uncle(Node: Tree_Type_Access) return Tree_Type_Access is
--     begin
--        if Node.Parent = Null or else Node.Parent.Parent = Null then
--           return Null;
--        end if;
--        if Node.Parent = Node.Parent.Left then
--           return Node.Parent.Parent.Right;
--        else
--           return Node.Parent.Parent.Left;
--        end if;
--     end Uncle;
--
--     function Sibling(Node: Tree_Type_Access) return Tree_Type_Access is
--     begin
--        if Node.Parent = Null then
--           return Null;
--        end if;
--        if Node.Parent = Node.Parent.Left then
--           return Node.Parent.Right;
--        else
--           return Node.Parent.Left;
--        end if;
--     end Sibling;
--
--     procedure Move_Down(Node: Tree_Type_Access; Node_Parent: Tree_Type_Access) is
--     begin
--        if Node.Parent /= Null then
--           if Node.Parent = Node.Parent.Left then
--              Node.Parent.Left := Node_Parent;
--           else
--              Node.Parent.Right := Node_Parent;
--           end if;
--        end if;
--        Node_Parent.Parent := Node.Parent;
--        Node.Parent := Node_Parent;
--     end Move_Down;
--
--     procedure Rotate_Left(Node: Tree_Type_Access; X: Tree_Type_Access) is
--        Node_Parent : Tree_Type_Access;
--     begin
--        Node_Parent := X.Right;
--
--        if X = Node.
--     end Rotate_Left;
--
--     procedure Insert(Tree: in out Tree_Type_Access; Item: Item_Type) is
--     begin
--        null;
--     end Insert;
--
--  --        Z : Tree_Type_Access;
--  --        X, Y : Tree_Type_Access;
--  --
--  --     begin
--  --        Z := new Tree_Type; --'(Item, Black, Null, Null, Null);
--  --        Z.all.Item := Item;
--  --
--  --        Y := Null;
--  --        X := Tree;
--  --        while X /= Null loop
--  --           Y := X;
--  --           if Z.Item < X.Item then
--  --              X := X.Left;
--  --           else
--  --              X := X.Right;
--  --           end if;
--  --        end loop;
--  --
--  --        Z.Parent := Y;
--  --        if not (Z.Item < Y.Item) then
--  --           Y.Right := Z;
--  --        else
--  --           Y.Left := Z;
--  --        end if;
--  --        Z.Col := Red;
--  --
--  --        Balance(Tree, Z);
--  --        --if Z.Item <
--  --
--  --     end Insert;


   function Parent(Node: Tree_Type_Access) return Tree_Type_Access is
   begin
      return Node.Parent;
   end Parent;

   function Grandparent(Node: Tree_Type_Access) return Tree_Type_Access is
      P : Tree_Type_Access := Parent(Node);
   begin
      if P = Null then
         return Null;
      end if;
      return Parent(P);
   end Grandparent;

   function Sibling(Node: Tree_Type_Access) return Tree_Type_Access is
      P : Tree_Type_Access := Parent(Node);
   begin
      if P = Null then
         return Null;
      end if;
      if Node = P.Left then
         return P.Right;
      else
         return P.Left;
      end if;
   end Sibling;

   function Uncle(Node: Tree_Type_Access) return Tree_Type_Access is
      P : Tree_Type_Access := Parent(Node);
      G : Tree_Type_Access := Grandparent(Node);
   begin
      if G = Null then
         return Null;
      end if;
      return Sibling(P);
   end Uncle;

   procedure Rotate_Left(Node: Tree_Type_Access) is
      Node_New : Tree_Type_Access := Node.Right;
      P : Tree_Type_Access := Parent(N);
   begin
      Node.Right := Node_New.Left;
      Node_New.Left := Node;
   end Uncle;

end Red_Black_Trees;