with Ada.Text_Io; use Ada.Text_Io;
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Calendar; use Ada.Calendar;
with Tas_Gen;
with Arbre_Bin_Recherche_Cle_G;

procedure Performance is
   
   ---------------------------------------------------------------
   -- Instanciation
   -- Tas
   procedure Liberer_Entier(N : in out Integer) is begin null;
   end Liberer_Entier;

   function Cle(N : in Integer) return Integer is begin return N;
   end Cle;

   package Tas_Entiers is new Tas_Gen(Integer, Integer, Cle, "<", Liberer_Entier, Integer'Image);
   use Tas_Entiers;
   
   -- Arbre binaire
   package Arbre_Entiers is new Arbre_Bin_Recherche_Cle_G(Integer, Integer, Cle, "<", "=", Liberer_Entier, Integer'Image);
   use Arbre_Entiers;
   
   ---------------------------------------------------------------
   
   
   ---------------------------------------------------------------
   -- Constante de taille des tas
   C_TAS : constant Natural := 200000;
   
   -- Tableau
   type Resultat is array (Natural range <> ) of integer;
   
   -- Pointeurs sur procedure
   type P_procedure is access procedure (F : in String);
   ---------------------------------------------------------------
   
   
   ---------------------------------------------------------------
   -- Procedure de tri par tas
   procedure Tri_Par_Tas(F : in string) is
      File : File_Type;
      Ligne : String(1..80);
      I, Len : Integer := 1;
      T : Un_Tas(C_TAS);
      Res : Resultat(1..C_TAS) := (others => -1);
   begin
      Open(File, In_File, F);
      
      -- Lecture du fichier dans un tas
      while not End_Of_File(File) loop
	 Get_line(File, Ligne, Len);
	 I := Integer'value(Ligne(1..Len)); 
	 Ajouter(I, T);
      end loop;
      --Put_Line(Tas_To_String(T));
      Close(File);
      
      -- Tri
      I := 1;
      declare begin loop
	 Enlever_Racine(T, Len);
	 while Res(I) /= -1 loop I := I+1; end loop;
	 Res(I) := Len;
      end loop; exception when Tas_Vide => goto pass;
      end;
  <<Pass>>
      
      -- Sauvegarde du tri
      create(File, Out_File, "./output/tas.out.txt");
      
      for Len in 1..I-1 loop
	 Put(File, Integer'image(Res(Len)));
	 New_Line(File);
      end loop;
      
      Close(File);
   end Tri_Par_Tas;
   ---------------------------------------------------------------
   --                 * *    
   --           *    *  *
   --      *  *    *     *  *
   --     *     *    *  *    *
   -- * *   *    *    *    *   *
   -- *     *  *    * * .#  *   *
   -- *   *     * #.  .# *   *
   --  *     "#.  #: #" * *    *
   -- *   * * "#. ##"       *
   --   *       "###
   --             "##
   --              ##.
   --              .##:
   --              :###
   --              ;###
   --            ,####.
   --/\/\/\/\/\/.######.\/\/\/\/\ 
   ---------------------------------------------------------------
   -- Procedure tri par arbre
   procedure Tri_Par_arbre(F : in string) is
      File : File_Type;
      Ligne : String(1..80);
      I, Len, Max : Integer := 1;
      A : Arbre;
      Res : Resultat(1..C_TAS) := (others => -1);
   begin
      Open(File, In_File, F);
      
      -- Lecture du fichier dans un arbre
      while not End_Of_File(File) loop
	 Get_line(File, Ligne, Len);
	 I := Integer'value(Ligne(1..Len)); 
	 Inserer(I, A);
      end loop;
      --Put_Line(Arbre_To_String(A));
      Close(File);
      
      -- Tri
      I := 1;
      while not Est_Vide(A) loop
	 Max := MaxA(A);
	 Res(I) := Max;
	 Supprimer(Max, A);
	 I := I + 1;
      end loop;
      
      -- Sauvegarde du tri
      create(File, Out_File, "./output/arbre.out.txt");
      
      for Len in 1..I-1 loop
	 Put(File, Integer'image(Res(Len)));
	 New_Line(File);
      end loop;
      
      Close(File);
   end Tri_Par_Arbre;
   ---------------------------------------------------------------
   
   
   ---------------------------------------------------------------
   -- Quicksort
   procedure Quicksort (A : in out Resultat) is
      procedure Swap(Left, Right : Natural) is
	 Temp : Integer := A (Left);
      begin
	 A (Left) := A (Right);
	 A (Right) := Temp;
      end Swap;
      
   begin
      if A'Length > 1 then
	 declare
	    Pivot_Value : Integer := A (A'First);
	    Right : Natural := A'Last;
	    Left : Natural := A'First;
	 begin
	    loop
	       while Left < Right and not (Pivot_Value < A (Left)) loop
		  Left := Natural'Succ (Left);
	       end loop;
	       while Pivot_Value < A (Right) loop
		  Right := Natural'Pred (Right);
	       end loop;
	       exit when Right <= Left;
	       Swap (Left, Right);
	       Left := Natural'Succ (Left);
	       Right := Natural'Pred (Right);
	    end loop;
	    if Right = A'Last then
	       Right := Natural'Pred (Right);
	       Swap (A'First, A'Last);
	    end if;
	    if Left = A'First then
	       Left := Natural'Succ (Left);
	    end if;
	    Quicksort (A (A'First .. Right));
	    Quicksort (A (Left .. A'Last));
	 end;
      end if;
   end Quicksort;
      
   
   -- Procedure de tri de tableau
   procedure Tri_simple(F : in string) is
      File : File_Type;
      Ligne : String(1..80);
      I, Len, Fin : Integer := 1;
      Res : Resultat(1..C_TAS) := (others => -1);
   begin
      Open(File, In_File, F);
      Fin := 0;
      
      -- Lecture du fichier dans un arbre
      while not End_Of_File(File) loop
	 Get_line(File, Ligne, Len);
	 I := Integer'value(Ligne(1..Len));
	 Fin := Fin + 1;
	 Res(Fin) := I;
      end loop;
      Close(File);
      
      -- Tri
      declare
	 A, B : Resultat(1..Fin) := Res(1..Fin);
      begin
	 Quicksort(A);
	 
	 for I in A'Range loop
	    B(B'Last - I + 1) := A(I);
	 end loop;
	 
	 -- Sauvegarde du tri
	 create(File, Out_File, "./output/QS.out.txt");
	 
	 for Len in 1..Fin loop
	    Put(File, Integer'image(B(Len)));
	    New_Line(File);
	 end loop;
	 
      end;
      Close(File);
   end Tri_simple;
   ---------------------------------------------------------------
   
   
   ---------------------------------------------------------------
   procedure Chrono(P : in P_Procedure; Arg : in String) is 
      -- Varaibles temps
      T1, T2 : Time;   
   begin 
      T1 := Clock;
      P(Arg);
      T2 := Clock;
      
      Put_Line("Temps d'éxécution : " & Duration'Image(T2 - T1));
      New_Line;
   end Chrono;
   ---------------------------------------------------------------
   
   
      
   ---------------------------------------------------------------
   -- Begin
   DataSet : Unbounded_String := To_Unbounded_String("data_150000.txt.dbn");
   P1, P2, P3 : P_Procedure;
begin
   -- Pointeurs sur procedures
   P1 := Tri_Par_Tas'Access;
   P2 := Tri_Par_Arbre'Access;
   P3 := Tri_Simple'Access;
   
   -- Tests de performances
   Put_Line("Test de performance sur tas : ");
   Chrono(P1, "./data/" & To_String(DataSet));
   
   Put_Line("Test de performance sur arbre : ");
   Chrono(P2, "./data/" & To_String(DataSet));
   
   Put_Line("Test de performance sur liste : ");
   Chrono(P3, "./data/" & To_String(DataSet));
end Performance;
