public class TriTableau{

    private int contenu[]; 
    private int taille;
    
    /** Constructeur de tableau aléatoire, dont les éléments seront compris entre 1 et 100
     * @param t la taille du tableau */ 
    public TriTableau(int t){ 
       taille=t;
       contenu=new int[taille];
       for(int i=0;i<taille;i++)
       	contenu[i]=(int)(Math.random()*100+1); 
       }
    /** Constructeur de tableau aléatoire, dont les éléments seront compris entre 1 et le deuxième paramètre
     * @param t la taille du tableau 
     * @param max, chaque élément du tableau sera un nombre aléatoire entre 1 et max */ 
    public TriTableau(int t,int max){ 
       taille=t;
       contenu=new int[taille];
       for(int i=0;i<taille;i++)
       	contenu[i]=(int)(Math.random()*max+1); 
       }
    /** Constructeur de tableau pour récupérer les arguments du main
     * @param tableauChaine, tableau de chaines de caractères */             
    public TriTableau(String tableauChaine[]){
        taille=tableauChaine.length;
        contenu=new int[taille];
        for(int i=0;i<taille;i++)
	contenu[i]=Integer.parseInt(tableauChaine[i]);
    }
    
    /** Accesseur pour récupérer la taille*/                 
    public int getTaille(){ 
        return(taille);
    }
     public int[] getContenu(){ 
        return contenu;
    }
     /** Modifieur de contenu
     * @param contenu, nouveau tableau d'entiers */                              
    public void setTableau(int contenu[]){
        // met a jour le tableau d'entiers et donc la taille
        taille=contenu.length;
        this.contenu=contenu;
    }

    /**
     * Modifie la valeur d'un element
     * @param index de la valeur a modifier
     * @param nouvelle valeur
     */
    public void setValeur(int index, int value)
    {
	this.contenu[index]=value;
    }

   /**
     * retourne la valeur d'un element
     * @param index de la valeur a retourner
     */
    public int getValeur(int index)
    {
	return this.contenu[index];
    }

    /** Fonction d'affichage*/                     
    public String toString(){
        String s="[";
        for(int i=0;i<taille-1;i++) 
	s=s+contenu[i]+",";
        s=s+contenu[taille-1]+"]";
        return(s);
    }

    /** Fonction d'échange des éléments d'indice i et j du tableau
     * @param i premier indice
     * @param j deuxième indice */ 
    public void echange(int i, int j){ 
        int x=contenu[i]; 
        contenu[i]=contenu[j];
        contenu[j]=x; 
    } 
    
/*****************************************************************************
**                            ALGORITHMES DE TRI                            **
*****************************************************************************/  
    
    public void triInsertion(){
        int j;
        for(int i=1;i<taille;i++){ //ici on commence à 1 
             for(j=0;contenu[j]<contenu[i];j++);//le corps de la boucle est vide
             int tampon = contenu[i];
             for(int k=i;k>j;k--)
                 contenu[k]=contenu[k-1];
             contenu[j]=tampon;
        }
     }  
    public int indiceDuMinimum(int i){
       int indiceMinimum=i;
       int j=i+1;
       while(j<taille){
           if(contenu[j]<contenu[indiceMinimum])
               indiceMinimum=j;
           j++;
        }
        return(indiceMinimum);
     }

     public void triSelection(){
         for(int i=0;i<taille;i++)
            echange(i,indiceDuMinimum(i));
     } 
     
     public void triBulle(){
          boolean fini=false;
          for(int i=1;i<taille;i++){ 
              if (fini == true) return; // on sort de  la boucle 
               else fini=true; 
              for(int j=0;j<taille-i;j++)
                   if(contenu[j]>contenu[j+1]){
                        echange(j,j+1);
                        fini=false;
                   }
           } 
     }


      public void drapeau2(){
            int i=-1;
            int j=taille;
            while(i+1<j){ 
                if(contenu[i+1]==1) 
                   i++;
               else{ 
                   j--;
                   echange(i+1,j);
              }
            }
       }
       
       public void drapeau3(){
	int i=-1;
	int j=taille;
	int k=taille;
	while(i+1<j){ 
 	   switch(contenu[i+1]){
		case 1:
			i++;
			break;
		case 2:
	 		echange(i+1,j-1);
      	 	j--;
			break;
		case 3:
	 		echange(j-1,k-1);
			echange(i+1,k-1);
      	 	j--;
			k--;
			break;
	  }
	}		
  }


 
/*****************************************************************************
**                      TRI PAR INSERTION DECROISSANT                       **
*****************************************************************************/  
    public void triInsertionDecroissant(){
        int j;
        for(int i=1;i<taille;i++){ //ici on commence à 1 
             for(j=0;contenu[j]>contenu[i];j++);//le corps de la boucle est vide
             int tampon = contenu[i];
             for(int k=i;k>j;k--)
                 contenu[k]=contenu[k-1];
             contenu[j]=tampon;
        }
     }  

/*****************************************************************************
**                            TRI SANS NOM                                  **
*****************************************************************************/  
    
    public int elementMin()
    {
	int min=contenu[0];
	for (int i=1; i< taille;i++)
	    {
		if (contenu[i]<min)
		    {
			min=contenu[i];
		    }
	    }
	return min;
    }

    public int elementMax()
    {
	int max=contenu[0];
	for (int i=1; i< taille;i++)
	    {
		if (contenu[i]>max)
		    {
			max=contenu[i];
		    }
	    }
	return max;
    }


    public TriTableau compresse(int min, int max)
    {
	//on cree le tableau intermediaire
	TriTableau t = new TriTableau(max-min+1);
	//	int[] tablo = new int[max-min+1];
	//il faut le remplir de 0
	for (int i=0;i<t.taille;i++){t.setValeur(i,0);}
	//et on le remplit finalement
	for (int i=0;i<taille;i++)
	    {
		t.setValeur(contenu[i]-min, t.getValeur(contenu[i]-min)+1);
	    }
	return t;
    }

    public TriTableau decompresse(int ta, int min)
    {
	TriTableau t = new TriTableau(ta);

	//notre index dans le tableau final
	int index = 0;
	//on parcourt le tableau intermediaire
	for (int i=0; i<taille;i++)
	    {
		for (int j=0;j<contenu[i];j++)
		    {
			t.setValeur(index,min+i);
			index++;
		    }
	    }
	return t;
    }


    public static void main(String args[]) { 
        TriTableau t=new TriTableau(10,15);
        System.out.println( "Un  tableau : " + t);
        t.triInsertion();
        System.out.println( "le même tableau trié par le  tri insertion " + t);
        t=new TriTableau(10,10);
        System.out.println( "Un  autre tableau : " + t);
        t.triSelection();
        System.out.println( "le même tableau trié par le tri selection " + t);
        t=new TriTableau(10,10);
        System.out.println( "Un autre tableau : " + t);
        t.triBulle();
        System.out.println( "le même tableau trié par le  tri à bulles " + t);
        t=new TriTableau(10,2);
        System.out.println( "Un  tableau à 2 valeurs " + t);
        t.drapeau2();
        System.out.println( "le même tableau trié par l'algorithme du drapeau à 2 couleurs " + t);
        t=new TriTableau(10,3);
        System.out.println( "Un  tableau à 3 valeurs " + t);
        t.drapeau3();
        System.out.println( "le même tableau trié par l'algorithme du drapeau à 3 couleurs " + t);


	//POUR LE TP5
	t=new TriTableau(10,6);
	System.out.println( "Un  tableau à 6 valeurs " + t);
	t.triInsertionDecroissant();
	System.out.println( "le même tableau trié par le  tri insertion decroissant " + t);
  

	t=new TriTableau(10,10);
	System.out.println( "Un nouveau tableau " + t);
	int min = t.elementMin();
	int max = t.elementMax();
	TriTableau tabloCompresse = t.compresse(min, max);
	System.out.println( "Le tableau compresse est " + tabloCompresse);
	TriTableau tabloDecompresse = tabloCompresse.decompresse(t.taille, min);
	System.out.println( "Le tableau trie  est " + tabloDecompresse);
    }
}