import java.util.*;

/**
 * Démonstration des algorithmes de tri (version graphique)
 */
class TrisGraphiques {

    static final int LARGEUR = 801;
    static final int HAUTEUR = 600;
    static final int EPAISSEUR = 10;
    static final String COLOR_NORMAL = "black";
    static final String COLOR_HIGHLIGHT = "orangered";

    static long tempo = 50;     // millisecondes

    static final Random random = new Random();
    static DrawingWindow w;

    static void initTab(int[] tab, int max) {
        for (int i = 0; i < tab.length; i++)
            tab[i] = random.nextInt(max);
    }

    static void afficheVal(int[] tab, int i, String color) {
        if (i >= 0 && i < tab.length) {
            int x1 = EPAISSEUR * i + 1;
            int x2 = EPAISSEUR * (i + 1) - 1;
            int y = w.height - 1 - tab[i];
            w.setColor("white");
            w.fillRect(x1, 0, x2, y - 1);
            w.setColor(color);
            w.fillRect(x1, y, x2, w.height - 1);
        }
    }

    static int[] prevVals = {-1, -1};
    static void afficheVals(int[] tab, int i, int j) {
        afficheVal(tab, i, COLOR_HIGHLIGHT);
        afficheVal(tab, j, COLOR_HIGHLIGHT);

        if (prevVals[0] != i && prevVals[0] != j)
            afficheVal(tab, prevVals[0], COLOR_NORMAL);
        if (prevVals[1] != i && prevVals[1] != j)
            afficheVal(tab, prevVals[1], COLOR_NORMAL);

        prevVals[0] = i;
        prevVals[1] = j;

        // w.sync();
        DrawingWindow.msleep(tempo);
    }

    static void afficheTab(int[] tab) {
        for (int i = 0; i < tab.length; i++)
            afficheVal(tab, i, COLOR_NORMAL);
        w.sync();
    }

    static void triInsert(int[] tab) {
        int valeur;
        int limite;
        int place;
        for (limite = 1; limite < tab.length; limite++) {
            valeur = tab[limite];
            place = limite;
            while (place > 0 && tab[place - 1] > valeur) {
                tab[place] = tab[place - 1];
                afficheVals(tab, place, limite);
                place = place - 1;
            }
            tab[place] = valeur;
            afficheVals(tab, place, limite);
        }
    }

    static void triSelect(int[] tab) {
        int iMin;
        int min;
        int limite;
        int i;
        for (limite = 0; limite < tab.length - 1; limite++) {
            iMin = limite;
            for (i = limite + 1; i < tab.length; i++) {
                if (tab[i] < tab[iMin]) {
                    iMin = i;
                    afficheVals(tab, limite, iMin);
                }
            }
            min = tab[iMin];
            tab[iMin] = tab[limite];
            tab[limite] = min;
            afficheVals(tab, limite, iMin);
        }
    }

    static void echangerValeurs(int[] tab, int i, int j) {
        int tmp = tab[i];
        tab[i] = tab[j];
        tab[j] = tmp;
        afficheVals(tab, i, j);
    }

    static void triBulles(int[] tab) {
        int i;
        int limite;
        boolean echange;
        limite = 0;
        echange = true;
        while (echange && limite < tab.length - 1) {
            echange = false;
            for (i = tab.length - 1; i > limite; i--) {
                if (tab[i] < tab[i - 1]) {
                    echangerValeurs(tab, i, i - 1);
                    echange = true;
                }
            }
            limite = limite + 1;
        }
    }

    static void triBulles2(int[] tab) {
        int i;
        int limiteGauche;
        int limiteDroite;
        boolean echange;
        boolean sensDirect;     // direction du parcours
        limiteGauche = 0;
        limiteDroite = tab.length - 1;
        echange = true;
        sensDirect = true;
        while (echange && limiteGauche < limiteDroite) {
            echange = false;
            if (sensDirect) {
                // parcours normal: droite -> gauche
                for (i = limiteDroite; i > limiteGauche; i--) {
                    if (tab[i] < tab[i - 1]) {
                        echangerValeurs(tab, i, i - 1);
                        echange = true;
                    }
                }
                limiteGauche = limiteGauche + 1;
            } else {
                // parcours inverse : gauche -> droite
                for (i = limiteGauche; i < limiteDroite; i++) {
                    if (tab[i] > tab[i + 1]) {
                        echangerValeurs(tab, i, i + 1);
                        echange = true;
                    }
                }
                limiteDroite = limiteDroite - 1;
            }
            sensDirect = !sensDirect;
        }
    }

    public static void main(String[] args) {
        if (args.length != 1) {
            System.err.println("Usage: java Tris algorithme");
            System.err.println("Algorithmes:\n" +
                               "  insert   tri par insertion\n" +
                               "  select   tri par sélection/permutation\n" +
                               "  bulles   tri à bulles\n" +
                               "  bulles2  double tri à bulles");
            System.exit(1);
        }

        String algo = args[0];
        w = new DrawingWindow("TrisGraphiques " + algo, LARGEUR, HAUTEUR);

        int taille = w.width / EPAISSEUR;

        int[] tab = new int[taille];
        initTab(tab, w.height);

        afficheTab(tab);

        String descr = "?";
        if (algo.equals("insert")) {
            descr = "tri par insertion";
            triInsert(tab);
        } else if (algo.equals("select")) {
            descr = "tri par sélection/permutation";
            triSelect(tab);
        } else if (algo.equals("bulles")) {
            descr = "tri à bulles";
            triBulles(tab);
        } else if (algo.equals("bulles2")) {
            descr = "double tri à bulles";
            triBulles2(tab);
        } else {
            System.err.println("Algorithme invalide : " + algo);
            System.exit(2);
        }

        afficheTab(tab);
    }
}