with Ada.Text_IO, ada.integer_text_io, Ada.Numerics.Discrete_Random;
use  Ada.Text_IO, ada.integer_text_io;

procedure Proposition_correction is
    max_val : constant := 99;
    n : constant := 10;

    type T_Array is array (1..n) of integer;

    procedure swap(a,b : in out integer) is
        v : integer;
    begin
        v := a;
        a := b;
        b := v;
    end;

    procedure Put(a : in T_Array) is
    begin
       Put("T_Array(");
       Put(A(A'First), 0);
       for i in (a'First+1)..A'Last loop
          Put(", ");
          Put(a(i), 0);
       end loop;
       Put(')');
    end;

    subtype random_range is integer range 0..max_val;
    package random_int is new Ada.Numerics.Discrete_Random(random_range);
    use random_int;
    Gen : Generator;

    procedure Fill_array(a : in out T_Array) is
    begin
        for i in a'Range loop
            a(i) := Random(Gen);
        end loop;
    end;

    function sorted(a : in T_Array)  return Boolean is
    begin
        for i in a'first..a'last-1 loop
            if a(i) > a(i + 1) then
                return false;
            end if;
        end loop;
        return true;
    end;

    -- partition simple qui ne tient pas compte des valeurs = pivot
    -- (donc version qui ne respecte pas l'énoncé)
    procedure Partition_v1(T : in out T_Array; A, B : in Integer; P, K : out Integer) is
       Pivot : Integer := T(A);
       CurrentIndex : Integer := A;
    begin
       Swap(T(A), T(B));
       for I in A..(B - 1) loop
          if T(I) <= Pivot then
             Swap(T(I), T(Currentindex));
             Currentindex := CurrentIndex + 1;
          end if;
       end loop;
       Swap(T(B), T(CurrentIndex));
       K := CurrentIndex + 1;
       P := CurrentIndex - 1;
       for I in reverse A..(CurrentIndex - 1) loop
          P := I;
          if T(I) /= Pivot then
             exit;
          end if;
       end loop;
    end Partition_v1;

    -- Partition avec algo du drapeau Irlandais.
    procedure Partition_V2(T : in out T_Array; A, B : in Integer; P, K : out Integer) is
       I : Integer;
       Pivot : Integer;
    begin
       I := A;
       P := A;
       K := B;
       Pivot := T(A);

       while I <= K loop
          if T(I) = Pivot then
             I := I + 1;
          elsif T(I) < Pivot then
             Swap(T(I), T(P));
             I := I + 1;
             P := P + 1;
          else
             while T(K) > Pivot and I < K loop
                K := K - 1;
             end loop;
             Swap(T(I), T(K));
             K := K - 1;
          end if;
       end loop;
       P := P - 1;
       K := K + 1;
    end Partition_V2;


    procedure Quicksort(T : in out T_Array) is
       procedure Quicksort_Rec(T : in out T_Array; A, B : in Integer) is
          K, P : Integer;
       begin
          if B <= A then
             return;
          end if;
          --Partition_v1(T, A, B, P, K);
          Partition_v2(T, A, B, P, K);
          Quicksort_Rec(T, A, P);
          Quicksort_Rec(T, K, B);
       end Quicksort_Rec;
    begin
       Quicksort_Rec(T, T'First, T'Last);
    end Quicksort;

    type T_ArrayNC is array (Integer range <>) of Integer;
    procedure Put(a : in T_ArrayNC) is
    begin
       Put("T_ArrayNC(");
       Put(A(A'First), 0);
       for i in (a'First+1)..A'Last loop
          Put(", ");
          Put(a(i), 0);
       end loop;
       Put(')');
    end;

    procedure Ex2_Q1(T : in T_ArrayNC) is
       Cpt : Integer := 1;
    begin
       for I in (T'First + 1)..T'Last loop
          if T(I - 1) <= T(I) then
             Cpt := Cpt + 1;
          else
             Put(Cpt, 0); Put(' ');
             Cpt := 1;
          end if;
       end loop;
       Put(Cpt, 0);
    end Ex2_q1;

    procedure Ex2_Q2(T : in T_ArrayNC) is
       procedure Ex2_Q2_Rec(T : in T_ArrayNC; I, Cpt : in Integer) is
       begin
          if I > T'Last then
             Put(Cpt, 0);
             return;
          end if;
          if T(I - 1) < T(I) then
             Ex2_Q2_Rec(T, I + 1, Cpt + 1);
          else
             Put(Cpt, 0); Put(' ');
             Ex2_Q2_Rec(T, I + 1, 1);
          end if;

       end Ex2_Q2_Rec;
    begin
       Ex2_Q2_Rec(T, T'First + 1, 1);
    end Ex2_Q2;

    procedure Ex2_Q3(T : in T_ArrayNC) is
       Cpt : Integer;
       Lasti : Integer;
       Nexti : Integer;
       LastVal : Integer;
    begin
       Lasti := T'First;
       loop
          Nexti := 0;
          Cpt := 1;
          LastVal := T(Lasti);
          for I in (Lasti + 1)..T'Last loop
             if LastVal <= T(I) then
                Cpt := Cpt + 1;
                LastVal := T(I);
             else
                if Nexti = 0 then
                   Nexti := I;
                end if;
             end if;
          end loop;
          Put(Cpt, 0); Put(' ');
          exit when Nexti = 0;
          Lasti := Nexti;
       end loop;
    end Ex2_q3;


    A : T_Array;
    B : T_Array := (5,3,1,5,7,4,9,5,10,8);
    Nbtest : constant Integer := 5;
begin
   Put("Quicksort("); Put(B); Put(") = ");
   Quicksort(B);
   Put(B);
   Put(" -- isSorted(A) = "); Put(Boolean'Image(Sorted(B)));
   New_Line;

   Reset(Gen);
   for I in 1..Nbtest loop
      Fill_Array(A);
      Put("Quicksort("); Put(A); Put(") = ");
      Quicksort(A);
      Put(A);
      Put(" -- isSorted(A) = "); Put(Boolean'Image(Sorted(A)));
      New_Line;
   end loop;

   Put("Ex2_Q1((3,6,2,4,7,8,4,5,6,1,2)) = ");
   Ex2_Q1((3,6,2,4,7,8,4,5,6,1,2)); New_Line;
   Put("Ex2_Q2((3,6,2,4,7,8,4,5,6,1,2)) = ");
   Ex2_Q2((3,6,2,4,7,8,4,5,6,1,2)); New_Line;
   Put("Ex2_Q3((3,6,2,4,7,8)) = ");
   Ex2_Q3((3,6,2,4,7,8));New_Line;
end Proposition_Correction;