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

public class TriFusionGraphique {

  static class Pion {
    int val;
    double px;
    double py; };

  static int [] tc;
  static Pion [] tp;
  static int tECi;
  static int tECf;
  static int tRf = -1;

  static void affichage() {
    EcranGraphique.clear();
    for ( int i = 0 ; i < tp.length ; i++ ) {
      if ( ( i >= tECi ) && ( i <= tECf ) )
        EcranGraphique.setColor(200,0,0);
        else
        EcranGraphique.setColor(0,0,0);
      EcranGraphique.drawRect((int) Math.round(tp[i].px),(int) Math.round(tp[i].py),39,39);
//      EcranGraphique.drawText((int) Math.round(tp[i].px+10+((i<10)?5:0)),(int) Math.round(tp[i].py+60),EcranGraphique.COLABA8x13,"%d",i);
      EcranGraphique.drawText((int) Math.round(tp[i].px+10+((tp[i].val<10)?5:0)),(int) Math.round(tp[i].py+25),EcranGraphique.COLABA8x13,"%d",tp[i].val); }
    EcranGraphique.flush();
    EcranGraphique.wait(10);
  }

  static void separation(int lim) {
    for ( int j = 0 ; j < 30 ; j++ ) { 
      for ( int i = lim+1 ; i < tp.length ; i++ ) {
        tp[i].px += 1.0; }
      affichage();
      EcranGraphique.wait(10); }
  }

  static void decalageBas(double px,int i,int iSrc) {
    double dx = (tp[iSrc].px-(px+i*40))/25.0;
    for ( int j = 0 ; j < 25 ; j++ ) {
      tp[iSrc].px -= dx;
      tp[iSrc].py += 4.0;
      affichage();
      EcranGraphique.wait(10); }
  }

  static void decalageHaut(double px,int iSrc) {
    for ( int j = 0 ; j < 25 ; j++ ) {
      tp[iSrc].py -= 4.0;
      affichage();
      EcranGraphique.wait(10); }
  }

  static void permutation(int indi,int indf) {
    double pxi = tp[indi].px;
    double pyi = tp[indi].py;
    double pxf = tp[indf].px;
    double pyf = tp[indf].py;
    int vi = tp[indi].val;
    int vf = tp[indf].val;
    double cx = (tp[indi].px+tp[indf].px)/2.0;
    double cy = (tp[indi].py+tp[indf].py)/2.0;
    double dx = Math.abs(tp[indi].px-cx);
    for ( int j = 0 ; j <= 45 ; j++ ) { 
      double angle = (Math.PI*j)/45.0;
      tp[indf].px =(int) (cx+dx*Math.cos(angle));
      tp[indf].py =(int) (cy+50.0*Math.sin(angle));
      tp[indi].px =(int) (cx+dx*Math.cos(Math.PI+angle));
      tp[indi].py =(int) (cy+50.0*Math.sin(Math.PI+angle));
      affichage();
      EcranGraphique.wait(10); }
    tp[indi].px = pxi;
    tp[indi].py = pyi;
    tp[indi].val = vf;
    tp[indf].px = pxf;
    tp[indf].py = pyf;
    tp[indf].val = vi;
    affichage();
    EcranGraphique.wait(10);
  }
  
/* Fonction de fusion en un tableau trie         */
/* de deux sous-tableaux contigus                */
/* d'un tableau d'entiers                        */
/* Sous-tableau 1: t1 valeurs depuis l'indice i1 */
/* Sous-tableau 2: t2 valeurs au dela            */

  static void fusion(int [] t,int i1,int t1,int t2) {
    int deb = i1;
    int i2 = i1+t1;
    int l = t1+t2;
    int l1 = i1+t1;
    int l2 = l1+t2;
    int [] tf = new int[l];
    Pion [] tpf = new Pion[l];
    double px = tp[deb].px;
    for ( int i = 0 ; i < l ; i++ ) {
      if ( i1 == l1 ) {
        tf[i] = t[i2];
        tpf[i] = tp[i2];
        decalageBas(px,i,i2);
        i2++; }
        else {
        if ( i2 == l2 ) {
          tf[i] = t[i1];
          tpf[i] = tp[i1];
          decalageBas(px,i,i1);
          i1++; }
          else {
          if ( t[i1] < t[i2] ) {
            tf[i] = t[i1];
            tpf[i] = tp[i1];
            decalageBas(px,i,i1);
            i1++; }
            else {
            tf[i] = t[i2];
            tpf[i] = tp[i2];
            decalageBas(px,i,i2);
            i2++; } } } }
    for ( int i = 0 ; i < l ; i++ ) {
      tp[deb+i] = tpf[i]; }
    for ( int i = 0 ; i < l ; i++ ) {
      decalageHaut(px,deb+i);
      t[deb+i] = tf[i]; }
  }

/* Fonction de tri par fusion  d'un tableau      */
/* d'entiers des indices indi a indf compris     */

  static void triFusion(int [] t,int indi,int indf,Pion [] tp) {
    tECi = indi;
    tECf = indf;
    int iMedian;
    int aux;
    switch ( indf-indi ) {
      case 0 :
        break;
      case 1 : {
        if ( t[indf] < t[indi] ) {
          permutation(indi,indf);
          aux = t[indi];
          t[indi] = t[indf];
          t[indf] = aux; } }
        break;
      default : {
        iMedian = (indi+indf)/2;
        separation(iMedian);
        affichage();
        triFusion(t,indi,iMedian,tp);
        triFusion(t,iMedian+1,indf,tp);
        tECi = indi;
        tECf = indf;
        fusion(t,indi,iMedian-indi+1,indf-iMedian); } }
  }

/* Fonction de tri par fusion de l'ensemble      */
/* d'un tableau d'entiers                        */

  static void triFusion(int [] t) {
    triFusion(t,0,t.length-1,tp);
  }
  
/* Programme principal                           */

  public static void main(String [] args) {
    int [] t = Bibliotheque.initRand(14,99);
    tc = Bibliotheque.clone(t);
    tp = new Pion[t.length];
    for ( int i = 0 ; i < t.length ; i++ ) {
      tp[i] = new Pion();
      tp[i].val = t[i];
      tp[i].px = 10+i*40.0;
      tp[i].py = 60.0; }
    EcranGraphique.init(50,50,840,320,800,240,"Tri par fusion");
    EcranGraphique.setClearColor(255,255,255);
    affichage();
    triFusion(t);
    Bibliotheque.affichageTableau(t);
  }
}