---------------------------------------bst ads------------------------------------------------

generic

   type Element_Type is private;       -- The type of element in the list
   type Key_Type is limited private;   -- The type of key in the element
   with function Key_Of (Element: Element_Type) return Key_Type;
   with function "=" (Left, Right: Key_Type) return Boolean;
   with function "<" (Left, Right: Key_Type) return Boolean;

package Binary_Search_Tree is

   type Tree_Type is limited private;

   type Traversal_Order is (Inorder, Preorder, Postorder);

   No_Key : exception;

   procedure Insert (Tree : in out Tree_Type;
                     Item : in     Element_Type);

   function Retrieve (Tree: Tree_Type;
                       Key: Key_Type) return Element_Type;

   generic

      with procedure Process (Element : in out Element_Type);

   procedure Traverse (Tree  : in out Tree_Type;
                       Order : in Traversal_Order);

private

   type Node_Type;                       -- Incomplete type declaration

   type Tree_Type is access Node_Type;   -- Access to a node
   subtype Node_Ptr is Tree_Type;        -- A synonym for our access type

   type Node_Type is                     -- Complete type declaration
      record
         Info  : Element_Type;    -- One element
         Left  : Node_Ptr;        -- Link to left child
         Right : Node_Ptr;        -- Link to right child
      end record;

end Binary_Search_Tree;


----------------------------------bst adb---------------------------------------------


with Ada.Text_IO;
use Ada.Text_IO;
package body Binary_Search_Tree is


   procedure Insert (Tree: in out Tree_Type; Item: in Element_Type) is
   begin
      if Tree = null then
         Tree := new Node_Type'(Info=>Item, Left=>null, Right=>null);
      elsif Key_Of (Item) = Key_Of (Tree.Info) then
         Put("That number is already in the tree!");
      elsif Key_of (Item) < Key_Of (Tree.Info) then
         Insert (Tree => Tree.Left, Item => Item);
      else
         Insert (Tree => Tree.Right, Item => Item);
      end if;
   end Insert;



   function Retrieve (Tree: Tree_Type;
                      Key :  Key_Type) return Element_Type is
   begin
      if Tree = null then
         Put("No value found!");
         raise No_Key;
      elsif Key = Key_Of (Tree.Info) then
         return (Tree.Info);
      elsif Key < Key_Of (Tree.Info) then
         return (Retrieve (Tree => Tree.Left, Key => Key));
      else
         return (Retrieve (Tree => Tree.Right, Key => Key));
      end if;
   end Retrieve;



   procedure Traverse (Tree  : in out Tree_Type;
                       Order : in Traversal_Order) is


      procedure Checked_Process (Element: in out Element_Type) is
         New_Element: Element_Type := Element;
      begin
         Process (New_Element);
         if Key_Of (Element) /= Key_Of (New_Element) then
            Put("No value found!");
            raise No_Key;
         else
            Element := New_Element;
         end if;
      end Checked_Process;


      procedure Inorder (Tree : in Tree_Type) is
      begin
         if Tree /= null then
            --Put_Line(Retrieve(Tree, Integer));
            Inorder (Tree => Tree.Left);    -- Traverse Left subtree
            Checked_Process (Tree.Info);
            Inorder (Tree => Tree.Right);   -- Traverse Right subtree
         end if;
      end Inorder;

      procedure Preorder (Tree : in Tree_Type) is
      begin
         if Tree /= null then
            Inorder (Tree => Tree.Left);    -- Traverse Left subtree
            Checked_Process (Tree.Info);
            Inorder (Tree => Tree.Right);   -- Traverse Right subtree
         end if;
      end Preorder;

      procedure Postorder (Tree : in Tree_Type) is


      begin
         if Tree /= null then
            Inorder (Tree => Tree.Right);  -- Traverse Left subtree
            Inorder (Tree => Tree.Right); -- Traverse Right subtree
            Checked_Process (Tree.Info);
         end if;
      end Postorder;

   begin -- Traverse
      case Order is
         when Inorder   => Inorder (Tree);
         when Preorder  => Preorder (Tree);
         when Postorder => Postorder (Tree);
      end case;
   end Traverse;

end Binary_Search_Tree;

--------------------------------------------------main adb-------------------------------------------

with Binary_Search_Tree;


-- this package contains our basic IO functions such as Put, Get and New_Line
with Ada.Text_IO;
use Ada.Text_IO;
with Ada.Integer_text_io;
use Ada.Integer_text_io;
with Ada.Exceptions;
use Ada.Exceptions;


procedure Main is
  -- signals that we are ready to begin coding.
  -- we use the space between the procedure declaration and the begin keyword
  -- to specify any local variables we will need for the procedure as they
  -- are not allowed to be declarated after the keyword begin


   function My_Key_Of (A: Integer) return Integer
   is begin
      return A;
   end My_Key_Of;

   procedure My_Process (B: in out Integer)
   is begin
      put(Integer'Image(B));
   end My_Process;

   MAX_Switch : Integer:=1;

   procedure My_Process_MAX (C: in out Integer)
   is begin
      if MAX_Switch = 1 then
         put(Integer'Image(C));
         MAX_Switch:=0;
      end if;
   end My_Process_MAX;

   MIN_Switch : Integer:=1;

   procedure My_Process_MIN (D: in out Integer)
   is begin
      if MIN_Switch = 1 then
         put(Integer'Image(D));
         MIN_Switch:=0;
      end if;
   end My_Process_MIN;


package My_Tree is new Binary_Search_Tree(Integer, Integer, My_Key_of, Standard."=", Standard."<");

 i: Integer;
 mytree : My_Tree.Tree_Type;
 order : My_Tree.Traversal_Order;

   procedure My_Traverse is new My_Tree.Traverse (My_Process);
   procedure My_Traverse_MAX is new My_Tree.Traverse (My_Process_MAX);
   procedure My_Traverse_MIN is new My_Tree.Traverse (My_Process_MIN);
--procedure mytraverse is new My_Tree.Traverse(mytree, order);




begin

   Put("Please enter a single digit number, ranging from 1-9, and press enter. Entering 0 will stop the input.");

loop

      Get(i);
      exit  when i = 0;
      if i > 10 then
         Put("Please, PLEASE make sure your number is a single digit.");
      elsif i < 0 then
         Put("Please, PLEASE make sure your number is a positive digit.");
      else
         My_Tree.Insert(mytree, i);
         Ada.Text_IO.New_Line;
      end if;


end loop;

   --My_Tree.Inorder(mytree);
   My_Traverse(mytree, My_Tree.Inorder);
            Ada.Text_IO.New_Line;
   My_Traverse_MIN(mytree, My_Tree.Preorder);
            Ada.Text_IO.New_Line;

   My_Traverse_MAX(mytree, My_Tree.Postorder);
   --My_Traverse(mytree, My_Tree.Preorder);






   Ada.Text_IO.New_Line;



-- end our Main procedure
end Main;