/*----------------------------------------------------------*/
/*                                                          */
/*         AUTHOR : Eric VIOLARD                            */
/*         E-MAIL : violard@icps.u-strasbg.fr               */
/*         ORGANISM : Université Louis Pasteur (Strasbourg) */
/*         CREATION : 28/12/02                              */
/*                                                          */
/* ---------------------------------------------------------*/
  
/*    
      Programme qui résoud le problème du drapeau hollandais.

*/

#include <stdlib.h>
#include <stdio.h>

#define N 10 /* taille du tableau */

/* les 3 valeurs possibles des élements du tableau : */

#define bleu  0
#define blanc 1
#define rouge 2


void swap(int t[], int i, int j)
     /* une (fameuse !) fonction qui échange les valeurs de 2 éléments d'un tableau (par effet de bord) */
{
  char tmp; /* pour sauvegarder une des valeurs */

  tmp=t[i];
  t[i]=t[j];
  t[j]=tmp;
}


void init_drapeau(int t[])
     /* initialisation du drapeau (les éléments ne prennent que 3 valeurs possibles) (par effet de bord) */
{
  int i;

  srand(time(NULL));
  for(i=0;i<N;i++)
    t[i]=rand()%3;
}

void ecriture_drapeau(int t[])
     /* initialisation du drapeau (les éléments ne prennent que 3 valeurs possibles) */
{
  int i;

  for(i=0;i<N;i++)
    switch(t[i]) 
      { 
      case bleu  : printf("bleu ");break;
      case blanc : printf("blanc ");break;
      case rouge : printf("rouge ");break;
      default : break;
      }
  printf("\n");
}


void tri(int t[])
     /* tri du tableau (par effet de bord) */
{
  int i_blanc=-1; /* indice du premier élément blanc (-1 si pas d'élément blanc) */ 
  int i_rouge=-1;/* indice du premier élément rouge (-1 si pas d'élément rouge) */ 
 
  int i;


  for(i=0;i<N;i++) /* un seul parcours du tableau */
    {
      /* à chaque étape, le morceau de tableau de l'indice 0 à l'indice i-1 est trié, 
         et on ajoute en bonne place une nouvelle valeur, celle de t[i] */
 
      if(t[i]==bleu) /* s'il c'est un bleu */
        {
	  if(i_blanc>=0) /* et s'il y a déja un blanc dans le morceau trié, alors on échange avec le premier blanc */ 
	    { swap(t,i_blanc,i); i_blanc++; } /* l'indice du premier blanc doit être incrémenté */
          else /* s'il n'y a pas de blanc et s'il y a un rouge, alors on échange avec le premier rouge */ 
            if(i_rouge>=0) { swap(t,i_rouge,i); i_rouge++; };/* l'indice du premier rouge doit être incrémenté */
          /* sinon on laisse la valeur en place */
	};
      if(t[i]==blanc)  /* s'il c'est un blanc */
        {         
          if(i_rouge>=0) /* et s'il y a déja un rouge, on échange avec le premier rouge */
            { swap(t,i_rouge,i);  if(i_blanc<0) i_blanc=i_rouge; i_rouge++; } 
            /* l'indice du premier rouge doit être incrémenté et si c'est le premier blanc, on doit mémoriser son indice */
          else 
          /* sinon on laisse la valeur en place */
             if(i_blanc<0) /* si c'est le premier blanc */
               i_blanc=i; /* alors on doit mémoriser son indice */
        };
      if(t[i]==rouge)  /* s'il c'est un rouge */
        {   /* on laisse la valeur en place */     
            if(i_rouge<0) i_rouge=i;  /* si c'est le premier rouge, on doit le mémoriser */       
        }
   }
}


main() /* petit programme de test */
{
  int drapeau[N];
  
  init_drapeau(drapeau);
  ecriture_drapeau(drapeau);
  tri(drapeau);
  ecriture_drapeau(drapeau);
  
}