-----------------------------------------------------------------------------
-- Nom fichier      : Tri_Tableau.ads                                      --
-- Auteur           : R. Chelouah                                          --
-- Date             : 26/03/2002                                           --
--                                                                         --
-- But              :  Trier un tableau                                    --
--                                                                         --
-- Date de modif.   :                                                      --
-- Raison           :                                                      --
-- Modules appeles  :  Ada.Numerics.Float_Random                           --
--                     Generateur de nombres aleatoires entre 0.0 et 1.0   --
-- Mat. particulier :                                                      --
--                                                                         --
-- Compilation      :  GNAT                                                --
-- Edition de liens :  GNAT                                                --
-- Mode d'execution :  Console                                             --
-----------------------------------------------------------------------------
   with Ada.Text_IO;               use Ada.Text_IO;               -- Module d'entree/sortie de texte
   with Ada.Integer_Text_IO;       use Ada.Integer_Text_IO;       -- Module d'entree/sortie d'entiers
   with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; -- Module generateur aleatoire
   with Spider;                    use Spider;                    -- Bibliotheque graphique 2D
   with Spider.Draw;               use spider.Draw;               -- pour la gestion des couleurs


-- Procedure principale
    procedure Tri_Tableau is
   
    -- Type T_Menu (type enumeration)
      type T_Menu is (Propagation, Selection, Insertion, Quitter);
       package ES_Menu is new enumeration_IO(T_Menu);
      use ES_Menu;
    
     -- valeur max des nombres generes,
      Valeur_Max : constant := 200.0;

    -- dimensions de la fenetre de visualisation
    -- pour eviter une valeur qui va sortir de l'ecran
      XLeng, YLeng : constant := Natural(Valeur_Max*2.0); 

     -- Type T_Vecteur d'entiers compris entre 1 et integer(Valeur_Max)= 100
      type T_Vecteur is array (Natural range <> ) of Natural range 0..Natural(Valeur_Max);
 
      
   -- Specifications des fonctions et des procedures utilisees
   -- ********************************************************
       procedure Presentation;
       function  Menu return T_Menu;
       function  Saisir(Str : String) return Positive;
       procedure Afficher_Menu;
       procedure Permuter(V1, V2 : in out Natural);
       procedure Propagation(Vecteur    : in out T_Vecteur);
       procedure Selection(Vecteur      : in out T_Vecteur);
       procedure Insertion(Vecteur      : in out T_Vecteur);
       procedure Afficher_Vecteur(Str       : String;
                                  Vecteur   : in T_Vecteur);
       procedure Visualiser_Vecteur(Vecteur : in T_Vecteur);
       procedure Remplir_Vecteur(Genrateur  : in Generator;
                                 ValeurMax  : in Float;
                                 Vecteur    : out T_Vecteur);
   -- ********************************************************
   
   
      -----------------------------------------------------------------------------
      -- Nom         : Presentation                                                                             
      -- But         :  
      -- Parametres  :                      
      -----------------------------------------------------------------------------
      procedure Presentation is
      begin
	       Put_line("  *****************************************************************");
          Put_Line("  * Programme qui permet de trier un tableau rempli aleatoirement *");
          Put_Line("  *                                                               *");
          Put_line("  *****************************************************************");
      end Presentation;
   
      ----------------------------------------------------------------------------
      -- Nom         : Afficher_Menu                                                                             
      -- But         : Afficher le menu ci-dessous
      -- 	New_Line;
      -- 	Put_Line(" ***** Quelle operation desirez vous effectuer *******");
      -- 	Put_Line("                                                      ");
      -- 	Put_Line("    PROPAGATION ---------------------------------: 1  ");
      -- 	Put_Line("    SELECTION   ---------------------------------: 2  ");
      -- 	Put_Line("    INSERTION   ---------------------------------: 3  ");
      -- 	Put_Line("    QUITTER     ---------------------------------: 4  ");
      -- 	Put_Line("                                                      ");
      -- 	Put_Line(" *****************************************************"); 
      --  New_line;
      -----------------------------------------------------------------------------      
      procedure Afficher_Menu is 
      begin       
	      New_Line;
	      Put_Line("    ******* Quelle operation desirez vous effectuer *******");
	      New_Line;
         for Menu in T_Menu loop
                 Put("       ");
                 Put(Menu, T_Menu'Width);
                 Put(" ------------------------------:  ");
                 Put(T_Menu'Pos(Menu)+1, 0);
                 New_Line;
         end loop;
         New_Line;
	      Put_Line("    ********************************************************"); 
         New_line;
           
      end Afficher_Menu;

     ----------------------------------------------------------------------------
     -- Nom         : Menu                                                                             
     -- But         :  
     -- Parametres  : 
     -- Exception   :                     
     -----------------------------------------------------------------------------
     function Menu return T_Menu is
       subtype T_Choix is Positive range T_Menu'Pos(T_Menu'First)+1..T_Menu'Pos(T_Menu'Last)+1;
       Choix : T_Choix;
     begin -- Menu
        Afficher_Menu;
	     Put(" Saisir votre Choix : ");
	     loop
    	     begin
		        Get(Choix);
		        New_Line(2);
		        Skip_Line;
		        return T_Menu'Val(Choix-1);		
	           exception
		        when Data_Error | Constraint_Error=>
                   Skip_line; New_line;
				       Put_Line(" Saisie incorrecte");
					    Put(" Veuillez entrez une nouvelle valeur: ");
	         end;
         end loop;
      end Menu;
     
   ----------------------------------------------------------------------------
   -- Nom         : Saisir                                                                             
   -- But         :  
   -- Parametres  : 
   -- Exception   :                     
   -----------------------------------------------------------------------------
   function Saisir(Str : String) return Positive is
      Longueur : Positive;
   begin
      loop
         begin
            Put(Str);
            Get(Longueur);
            Skip_Line;
            return Longueur;
              exception
                 when Data_Error|Constraint_Error =>
                     Skip_Line;
                     Put_Line(" Erreur de saisie, refaire ... ");
          end;
       end loop;
   end;
   
      ----------------------------------------------------------------------------
      -- Nom         : Remplir_Vecteur                                                                            
      -- But         :  
      -- Parametres  : 
      -- Exception   :                     
      -----------------------------------------------------------------------------
      procedure Remplir_Vecteur(Genrateur  : in Generator;
                                 ValeurMax  : in Float;
                                 Vecteur    : out T_Vecteur) is
      begin  
         for I in Vecteur'range loop
            Vecteur(I):= Natural(Random(Genrateur)*ValeurMax);
         end loop;
      end Remplir_Vecteur;
   
   ----------------------------------------------------------------------------
   -- Nom         : Permuter                                                                             
   -- But         :  
   -- Parametres  : 
   -- Exception   :                     
   -----------------------------------------------------------------------------
     procedure Permuter(V1, V2 : in out Natural) is
        Temp : Natural;
     begin
          Temp := V1;
          V1   := V2;
          V2   := Temp;
     end Permuter;

   ----------------------------------------------------------------------------
   -- Nom         : Propagation                                                                             
   -- But         :  
   -- Parametres  : 
   -- Exception   :                     
   -----------------------------------------------------------------------------
       procedure Propagation(Vecteur : in out T_Vecteur) is
      begin 
         Visualiser_Vecteur(Vecteur);                -- appel de la procedure de visualisation vecteur initial
         for M in Vecteur'First.. Vecteur'Last-1 loop
            for J in Vecteur'First.. Vecteur'Last-M loop
               If Vecteur(J)>Vecteur(J+1) then
                  Permuter(Vecteur(J),Vecteur(J+1)); -- permuter vect(J) et Vect(J+1)
               end if; 
               Visualiser_Vecteur(Vecteur);          -- appel de la procedure de visualisation a chaque etape meme sîl n'y pas de permutation
            end loop;
         end loop;
      end Propagation;
   
   ----------------------------------------------------------------------------
   -- Nom         : Selection                                                                             
   -- But         :  
   -- Parametres  : 
   -- Exception   :                     
   -----------------------------------------------------------------------------
       procedure Selection(Vecteur : in out T_Vecteur) is
         Imax : Natural;
      begin  
         for M in Vecteur'First.. Vecteur'Last-1 loop
            Imax := M;
            for J in M+1.. Vecteur'Last loop
               If Vecteur(J)>Vecteur(imax) then
                  Imax:= J;
               end if;                
            end loop;
            Permuter(Vecteur(M), Vecteur(imax)); -- permuter vect(Imax) et Vect(M)
            Visualiser_Vecteur(Vecteur);         -- appel de la procedure de visualisation
         end loop;
      end Selection;
   
   ----------------------------------------------------------------------------
   -- Nom         : Insertion                                                                             
   -- But         :  
   -- Parametres  : 
   -- Exception   :                     
   -----------------------------------------------------------------------------
       procedure Insertion(Vecteur : in out T_Vecteur) is
         Value : Natural;
         J : Integer;
      begin  
         for I in Vecteur'First + 1 .. Vecteur'Last loop 
            Value := Vecteur(I);
            J  := I - 1;
            while J in Vecteur'range loop
               exit when Vecteur (J) <= Value;
               Vecteur (J + 1) := Vecteur (J);
               J := J - 1;
            end loop;
                --  Il y a toujours deux raisons à la sortie de la boucle
                --  1) Value est plus petit que tous les éléments parcourus
                --     remarquons que dans ce cas J vaut V'First-1
                --  2) J est la première valeur pour laquelle V (J) <= Value
                --  Dans les deux cas la place de Value est en V (J + 1), d'où
            Vecteur (J+1) := Value;                
            Visualiser_Vecteur(Vecteur); -- appel de la procedure de visualisation
         end loop;
      end Insertion;
   
   ----------------------------------------------------------------------------
   -- Nom         : Afficher_Vecteur                                                                             
   -- But         :  
   -- Parametres  : 
   -- Exception   :                     
   -----------------------------------------------------------------------------
      procedure Afficher_Vecteur(Str : String; Vecteur : in T_Vecteur) is
      begin 
         New_Line;
         Put_Line(Str);
         Put_Line(" ------------------------- ");
         Put(" [");
         for I in Vecteur'range loop
            Put(Vecteur(I),4);
         end loop;
         Put("]");
         New_Line(1);
         delay 0.5;    -- temporisation de 0.5 sec (type reel) 
      end Afficher_Vecteur;
   
   ----------------------------------------------------------------------------
   -- Nom         : Visualiser_Vecteur                                                                             
   -- But         :  
   -- Parametres  : 
   -- Exception   :                     
   -----------------------------------------------------------------------------
      procedure Visualiser_Vecteur(Vecteur : in T_Vecteur) is
      begin  
		
         delay 0.3;                                      -- temporisation de 0.3 sec (type reel) 
         Clear_Window;                                   -- effacer l'écran
			
			-- choisir la couleur rouge et tracer d'axe horizontal                         
         Set_Color_Pen(Red);
         Line_To(0,YLeng/2,XLeng,YLeng/2);
            
			Set_Color_Pen(Blue);	-- choisir la couleur bleue 
			
			-- tracer les barres verticales 
         for I in Vecteur'range loop
            Move_To(I*XLeng/(Vecteur'length+1),YLeng/2);  -- deplacement horizontal
            Line(0,-Vecteur(I));                          -- le tracé du segment dans l'histogramme
         end loop;   
      end Visualiser_Vecteur;
  
  
   --------------------------------------------------------------
   --  Declaration de variables
   --------------------------------------------------------------
   
   -- variables : dimensions du tableau, generateur aleatoire
      Gen        : Generator ;
   
   -- variable mon choix
      Mon_Choix : T_Menu;
    
   -- Corps de la procedure principale
   begin -- Tri_Tableau;
      Presentation;                                                  -- presentation de l'application pour l'utilisateur
      Reset(Gen,0);                                                  -- appel de la procedure pour initialiser le generateur avec la valeur 0
      loop                                                           -- boucle de repetition general sans quitter l'application
         begin 
         
            Mon_Choix := Menu;                                       -- j'appelle la fonction menu qui renvoie le choix fait..
            
            exit when Mon_Choix = Quitter;                           -- Si mon choix = Q alors je quitte l'application

   Calcul : declare                                                  -- declarer un bloc pour tableau dynamique
   
               Vect : T_Vecteur(1..Saisir(" Donner la dimension du vecteur : ")) ;
               
            begin  
            
               Remplir_Vecteur(Gen, Valeur_Max, Vect);               -- appel de la procedure Remplir_Vecteur
               
               Afficher_Vecteur(" Voici le vecteur initial ",Vect);  -- appel de la procedure Afficher_Vecteur (non trié)
               
               Spider.Init_Size_Window(" Visualisation : " & T_Menu'Image(Mon_Choix), XLeng, YLeng);
               
               case Mon_Choix is		                                 -- selon mon choix, j'appelle une methode de tri
                  
                  when T_Menu'(Propagation) => 
                                     Propagation(Vect);
                           
                  when T_Menu'(Selection) => 
                                     Selection(Vect);
                           
                  when T_Menu'(Insertion) => 
                                     Insertion(Vect);
                                     
                  when T_Menu'(Quitter) => exit;                     -- obligatoire sinon erreur de compilation
                  
               end case;
               
               Afficher_Vecteur(" Voici le vecteur final ", Vect);   -- appel de la procedure Afficher_Vecteur (trié)
               New_Line(1);
               
               Put(" Taper la touche Ret pour continuer... ");
               Skip_Line;
               New_Line(1);
               
               Spider.close_Window;
               
            end calcul;
         
         
             exception                                             -- il est toujour utile d'avoir un bloc de traitement
                                                                   -- d'exception a la fin du programme principal 
                 when others =>  Skip_Line;                        -- quand il y une une exception dans une procedure
                      Put_Line(" Erreur inconnu, refaire... ");    --  1 afficher dans quelle bloc cette exception est levee
                      New_Line;                                    --  2 propager l'exception vers le programme principal
                                                                   --  3 faire un traitement global des exceptions dans le prog principal                                                
         end;      -- Bloc de loop
         
      end loop;     -- boucle de repetition
      
   end Tri_Tableau;  --  fin finale
