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

procedure TD2 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
        for i in a'range loop
            put(a(i), 3);
        end loop;
        new_line;
    end;
    
    procedure test(b : Boolean; s : String; nberreur : in out integer) is
    begin
      put(s); put(" : ");
      if b then
          put("ok !");
      else
          nberreur := nberreur + 1;
          put("failed !");
      end if;
      New_Line;
    end;
 
    subtype random_range is integer range 0..max_val;
    package random_int is new Ada.Numerics.Discrete_Random(random_range);
    use random_int;    

    procedure genere(a : in out T_Array) is
      Gen : Generator;
    begin
        Reset(Gen);
        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;
    
    -- tri par insertion tp2ex2a
    procedure tri_insertion1(a : in out T_Array) is
        v : Integer;
        pos : Natural;
    begin
        for i in 1..a'last - 1 loop
            -- valeur ˆ classer
            v := a(i + 1);
            -- au mieux nous sommes sur la bonne position
            pos := 1;
            -- recherche de la position d'insertion
            for j in reverse 1..i loop
                if v > a(j) then
                    pos := j + 1;
                    exit;
                end if;
            end loop;
            -- decalage des valeurs pos..i -> pos+1..i+1
            for j in reverse pos..i loop
                a(j + 1) := a(j);
            end loop;
            a(pos) := v;
        end loop;
    end;
    
    -- tri par insertion tp2ex2b
    procedure tri_insertion2(a : in out T_Array) is
        v : Integer;
        pos : Natural;
        nbcomp : natural := 0;
    begin
        for i in 1..a'last - 1 loop
            -- valeur ˆ classer
            v := a(i + 1);
            -- au pire nous insŽrons ˆ la premire position
            pos := 1;
            -- recherche de la position d'insertion et dŽcalage sinon
            for j in reverse 1..i loop
                nbcomp := nbcomp + 1;
                if v > a(j) then
                  pos := j + 1;
                  exit;
                else
                  a(j + 1) := a(j);
                end if;
            end loop;
            a(pos) := v;
        end loop;
        put("Nbcomp : "); put(nbcomp, 0); New_line;
    end;
    
    -- tri par insertion tp2ex2c
    -- recherche dichotomique de la position d'insertion
    procedure tri_insertion3(a : in out T_Array) is
        v : Integer;
        pos, g, d, n : Natural;
        nbcomp : natural := 0;
    begin
        for i in 1..a'last - 1 loop
            -- valeur ˆ classer
            v := a(i + 1);
            -- au pire nous insŽrons ˆ la premire position
            pos := 1;
            -- recherche de la position si non triŽ de 1..i+1
            nbcomp := nbcomp + 1;
            if v < a(i) then
                g := 1;
                d := i;
                while d - g > 1 loop
                    nbcomp := nbcomp + 1;
                    n := (g + d) / 2;
                    if a(n) < v then
                        g := n;
                    else
                        d := n;
                    end if;
                end loop;
                nbcomp := nbcomp + 1;
                if v < a(g) then
                    pos := g;
                else
                    pos := g+1;
                end if;
                -- decalage des valeurs pos..i -> pos+1..i+1
                for j in reverse pos..i loop
                    a(j + 1) := a(j);
                end loop;
                a(pos) := v;
            end if;
        end loop;
        put("Nbcomp : "); put(nbcomp, 0); New_line;
    end;
    
    
            
    t, t1, t2, t3, t4, t5 : t_array;
    pos : natural;
    nberreur : integer := 0;
    nbtest : natural := 1000;
begin
    for i in 1..nbtest loop
        genere(t);
        put(t);
    
        t1 := t;
        tri_insertion1(t1);
        put(t1);
        test(sorted(t1), "tri_insertion1", nberreur);

        t2 := t;
        tri_insertion2(t2);
        put(t2);
        test(sorted(t2), "tri_insertion2", nberreur);
        
        t3 := t;
        tri_insertion3(t3);
        put(t3);
        test(sorted(t3), "tri_insertion3", nberreur);
        new_line;
    end loop;
    
    put("Nb erreur : "); put(nberreur);
end TD2;
-- 63 39 35 14 30  4 95 72 78  2
--  2  4 14 30 35 39 63 72 78 95
--tri1 : ok !
--  2  4 14 30 35 39 63 72 78 95
--tri2 : ok !
--  2  4 14 30 35 39 63 72 78 95
--tri3 : ok !
--strIsIn("ab", "aab", pos) = 2 : ok !
--strIsIn("a", "aab", pos) = 1 : ok !
--strIsIn("abc", "aab", pos) = 0 : ok !
--strIsIn("ce", "Ce qu'on laisse sur la table fait plus de bien que ce qu'on y prend.", pos) = 52 : ok !
--strIsIn("table", "Ce qu'on laisse sur la table fait plus de bien que ce qu'on y prend.", pos) = 1 : ok !