/* Tri par insertion d'un tableau d'entiers      */

public class TriInsertionGraphiqueEnConsole {

  static final int px = 40;
  static final int py = 170;

  static void affichage(int [] t,int px,int py) {
    EcranGraphique.drawLine(px-10,py-25,px+t.length*40-10,py-25);
    EcranGraphique.drawLine(px-10,py+10,px+t.length*40-10,py+10);
    for ( int i = 0 ; i <= t.length ; i++ )
      EcranGraphique.drawLine(px-10+i*40,py-25,px-10+i*40,py+10);
    for ( int i = 0 ; i < t.length ; i++ ) {
      EcranGraphique.drawText(px+40*i,py,EcranGraphique.COLABA8x13,"%d",t[i]); }
  }

  static void affichage(int [] t,int px,int py,int lim) {
    EcranGraphique.setColor(0,0,0);
    EcranGraphique.drawLine(px-10,py-25,px+t.length*40-10,py-25);
    EcranGraphique.drawLine(px-10,py+10,px+t.length*40-10,py+10);
    for ( int i = 0 ; i <= t.length ; i++ )
      EcranGraphique.drawLine(px-10+i*40,py-25,px-10+i*40,py+10);
    for ( int i = 0 ; i < t.length ; i++ ) {
      if ( i < lim )
        EcranGraphique.setColor(0,192,0);
        else
        if ( i == lim )
          EcranGraphique.setColor(0,0,192);
          else
          EcranGraphique.setColor(0,0,0);
      EcranGraphique.drawText(px+40*i,py,EcranGraphique.COLABA8x13,"%d",t[i]); }
  }

  static void affichageRecherchePositionInsertion(int [] t,int ind,int i,int lim) {
    EcranGraphique.clear();
    affichage(t,40,120,lim);
    { int px = 50+ind*40-i;
      EcranGraphique.setColor(0,0,0);
      EcranGraphique.drawLine(px,140,px,180);
      EcranGraphique.drawLine(px-5,145,px,140);
      EcranGraphique.drawLine(px+5,145,px,140);
      EcranGraphique.setColor(0,0,192); }
    EcranGraphique.flush();
    EcranGraphique.wait(10);
  }

  static void affichageRecherchePositionInsertion(int [] t,int ind,int lim) {
    EcranGraphique.clear();
    affichage(t,40,120,lim);
    { int px = 50+ind*40;
      EcranGraphique.setColor(0,0,192);
      EcranGraphique.drawLine(px,140,px,180);
      EcranGraphique.drawLine(px-5,145,px,140);
      EcranGraphique.drawLine(px+5,145,px,140);
      EcranGraphique.setColor(0,0,192); }
    EcranGraphique.flush();
    EcranGraphique.wait(1000);
  }

  static void animationRecherchePositionInsertion(int [] t,int pos,int lim) {
    for ( int i = 0 ; i <= 40 ; i += 2 ) {
      affichageRecherchePositionInsertion(t,pos,i,lim); }
  }

  static void affichageDescente(int [] t,int px,int py,int dec,int lim) {
    EcranGraphique.setColor(0,0,0);
    EcranGraphique.drawLine(px-10,py-25,px+t.length*40-10,py-25);
    EcranGraphique.drawLine(px-10,py+10,px+t.length*40-10,py+10);
    for ( int i = 0 ; i <= t.length ; i++ )
      EcranGraphique.drawLine(px-10+i*40,py-25,px-10+i*40,py+10);
    for ( int i = 0 ; i < t.length ; i++ ) {
      if ( i < lim )
        EcranGraphique.setColor(0,192,0);
        else
        if ( i == lim )
          EcranGraphique.setColor(0,0,192);
          else
          EcranGraphique.setColor(0,0,0);
      EcranGraphique.drawText(px+40*i,py+((i==lim)?dec:0),EcranGraphique.COLABA8x13,"%d",t[i]); }
  }

  static void animationDescente(int [] t,int lim) {
    for ( int i = 0 ; i <= 60 ; i += 2 ) {
      EcranGraphique.clear();
      affichageDescente(t,40,120,i,lim);
      EcranGraphique.flush();
      EcranGraphique.wait(10); }
  }

  static void affichageRemontee(int [] t,int px,int py,int inc,int lim,int pos,int v,int max) {
    EcranGraphique.setColor(0,0,0);
    EcranGraphique.drawLine(px-10,py-25,px+t.length*40-10,py-25);
    EcranGraphique.drawLine(px-10,py+10,px+t.length*40-10,py+10);
    for ( int i = 0 ; i <= t.length ; i++ )
      EcranGraphique.drawLine(px-10+i*40,py-25,px-10+i*40,py+10);
    for ( int i = 0 ; i < t.length ; i++ ) {
      if ( i <= lim )
        EcranGraphique.setColor(0,192,0);
        else
        EcranGraphique.setColor(0,0,0);
      if ( i != pos )
        EcranGraphique.drawText(px+40*i,py,EcranGraphique.COLABA8x13,"%d",t[i]);
        else {
        double angle = Math.PI/2.0+(Math.PI/2.0*inc)/max;
        int x =(int) (px+40*lim+(lim-pos)*40*Math.cos(angle));
        int y =(int) (py+60*Math.sin(angle));
        EcranGraphique.drawText(x,y,EcranGraphique.COLABA8x13,"%d",v); } }
  }

  static void animationRemontee(int [] t,int lim,int pos,int v) {
    int max = (lim-pos)*20;
    for ( int i = 0 ; i <= max ; i += 1 ) {
      EcranGraphique.clear();
      affichageRemontee(t,40,120,i,lim,pos,v,max);
      EcranGraphique.flush();
      EcranGraphique.wait(10); }
  }

  static void affichageDecalage(int [] t,int px,int py,int pos,int dec,int lim,int v) {
    EcranGraphique.setColor(0,0,0);
    EcranGraphique.drawLine(px-10,py-25,px+t.length*40-10,py-25);
    EcranGraphique.drawLine(px-10,py+10,px+t.length*40-10,py+10);
    for ( int i = 0 ; i <= t.length ; i++ )
      EcranGraphique.drawLine(px-10+i*40,py-25,px-10+i*40,py+10);
    for ( int i = 0 ; i < t.length ; i++ ) {
      if ( i < lim )
        EcranGraphique.setColor(0,192,0);
        else
        if ( i == lim )
          EcranGraphique.setColor(0,0,192);
          else
          EcranGraphique.setColor(0,0,0);
      if ( i == pos )
        EcranGraphique.drawText(px+40*i+dec,py,EcranGraphique.COLABA8x13,"%d",t[i]);
        else
        if ( i == lim )
          EcranGraphique.drawText(px+40*i,py+60,EcranGraphique.COLABA8x13,"%d",v);
          else
          if ( ( i > pos ) && ( i < lim ) )
            EcranGraphique.drawText(px+40*(i+1),py,EcranGraphique.COLABA8x13,"%d",t[i+1]);
            else
            EcranGraphique.drawText(px+40*i,py,EcranGraphique.COLABA8x13,"%d",t[i]); }
  }

  static void animationDecalage(int [] t,int pos,int lim,int v) {
    for ( int i = 0 ; i <= 40 ; i += 2 ) {
      EcranGraphique.clear();
      affichageDecalage(t,40,120,pos,i,lim,v);
      EcranGraphique.flush();
      EcranGraphique.wait(10); }
  }

/* Fonction de recherche de la position          */
/* d'un entier v dans un tableau d'entiers       */
/* restreint aux indices 0 a l-1 inclus          */

  static int positionInsertion(int v,int l,int [] t) {
    int p = l;
    do {
      if ( p != l )
        animationRecherchePositionInsertion(t,p,l);
      p--; }
    while ( ( p >= 0 ) && ( v < t[p] ) );
    p++;
    affichageRecherchePositionInsertion(t,p,l);
    return p;
  }

/* Fonction de decalage de une cellule           */
/* vers la droite du contenu des cellules        */
/* de l'indice indi a l'indice indf              */
/* d'un tableau d'entiers                        */

  static void decalage(int indi,int indf,int [] t,int v) {
    for ( int i = indf ; i >= indi ; i-- ) {
      animationDecalage(t,i,indf+1,v);
      t[i+1] = t[i]; }
  }

/* Fonction de tri par insertion d'un tableau    */
/* d'entiers                                     */

  static void triInsertion(int [] t) {
    int p;
    int v;
    for ( int i = 1 ; i < t.length ; i++ ) {
      EcranGraphique.clear();
      affichage(t,40,120,i);
      EcranGraphique.flush();
      EcranGraphique.wait(1000);
      p = positionInsertion(t[i],i,t);
      if ( p != i ) {
        v = t[i];
        animationDescente(t,i);
        decalage(p,i-1,t,v);
        t[p] = v;
        animationRemontee(t,i,p,v); } }
    EcranGraphique.clear();
    affichage(t,40,120,t.length);
    EcranGraphique.flush();
    EcranGraphique.wait(1000);
  }

/* Programme principal                           */

  public static void main(String [] args) {
    Console.setTitle("TriInsertionGraphique");
    int [] t = Bibliotheque.initRand(15,99);
    int [] tc = Bibliotheque.clone(t);
    EcranGraphique.init(50,50,700,320,660,240,"Tri par insertion");
    EcranGraphique.setClearColor(255,255,255);
    triInsertion(t);
  }
}