with Ada.Calendar;
with Ada.Integer_Text_IO;
with Ada.Text_IO;
use Ada.Calendar;
use Ada.Integer_Text_IO;
use Ada.Text_IO;

procedure Heapsort is
   Max_Values: constant Natural := 1000;
   type Integer_Array is array (Natural range 0..Max_Values) of Integer;
   Values: Integer_Array;
   Count: Natural;
   Elapsed: Duration;

   procedure Sift_Down(Start_Node: Natural; End_Node: Natural) is
      Root: Natural := Start_Node;
      Child: Natural;
      Temp: Integer;
   begin
      while 2 * Root + 1 < End_Node loop
         Child := 2 * Root + 1;
         if Child + 1 < End_Node and then Values(Child) < Values(Child + 1) then
            Child := Child + 1;
         end if;
         exit when Values(Root) >= Values(Child);
         Temp := Values(Root);
         Values(Root) := Values(Child);
         Values(Child) := Temp;
         Root := Child;
      end loop;
   end Sift_Down;
   procedure Load_File(FileSpec: String) is
      Input_File: File_Type;
   begin
      Count := 0;
      put("READING INPUT FILE...");
      Open(Input_File, In_File, FileSpec);
      while not End_Of_File(Input_File) loop
         Get(Input_File, Values(Count));
         Count := Count + 1;
         exit when Count > Max_Values;
      end loop;
      Close(Input_File);
      Put_Line("DONE.");
   end Load_File;
   procedure Save_File(FileSpec: String) is
      Output_File: File_Type;
   begin
      put("WRITING OUTPUT FILE...");
      Create(Output_File, Out_File, FileSpec);
      for Index in 0..Count-1 loop
         put(Output_File, Values(Index));
         New_Line(Output_File);
      end loop;
      Close(Output_File);
      Put_Line("DONE.");
   end Save_File;
   procedure Perform_Sort is
      Start_Time: Time;
      End_Time: Time;
      Temp: Integer;
   begin
      put("SORTING ELEMENTS...");
      Start_Time := Clock;
      if Count > 1 then
         for Start_Index in reverse 0..Count/2-1 loop
            Sift_Down(Start_Index, Count);
         end loop;
         for End_Index in reverse 1..Count-1 loop
            Temp := Values(0);
            Values(0) := Values(End_Index);
            Values(End_Index) := Temp;
            Sift_Down(0, End_Index);
         end loop;
      end if;
      End_Time := Clock;
      Put_Line("DONE.");
      Elapsed := End_Time - Start_Time;
   end Perform_Sort;

begin
   Put_Line("***HEAPSORT ADA***");
   Load_File("D:\Sorting\Sorting_Input.txt");
   Perform_Sort;
   Save_File("D:\Sorting\Output_ADA.txt");
   Put_Line("***RUN COMPLETE***");
   Put_Line("HEAPSORT TOOK " & Duration'Image(Elapsed) & " SECONDS.");
end Heapsort;