/**
 * Graphical illustration of various sorting
 * algorithms
 *
 * Written by vvb@mech.math.msu.su
 */

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
import java.net.*;
import java.io.*;
import java.util.*;

class Action {
    static final byte COMPARE = 0;
    static final byte SWAP = 1;
    byte type;
    int ind0;
    int ind1;

    public Action(int t, int i, int j) {
        type = (byte) t;
        ind0 = i;
        ind1 = j;
    }
}

public class GSort extends Applet  implements Runnable {
    // Array size
    static final int NMAX = 100;
    int a[] = new int[NMAX];
    int b[] = new int[NMAX];
    String sortName = "";
    boolean sorting = false;
    boolean pause = false;
    int numComparings = 0;
    int numSwappings = 0;
    ArrayDeque<Action> actions = new ArrayDeque<Action>();
    boolean finished = false;
    boolean terminate = false;

    Thread sortingThread = null;
    static final int DT = 20;   // 0.02 sec

    // Layout constants
    static final int SKIP = 2;
    static final int MARGIN = 4;
    static final int BAR_WIDTH = 6;
    static final int BAR_HEIGHT = 400;
    static final int DRAW_AREA_WIDTH = 2*MARGIN +
                     (BAR_WIDTH + SKIP)*NMAX - SKIP;
    static final int DRAW_AREA_HEIGHT = 2*MARGIN + BAR_HEIGHT;

    static final int BUTTON_HEIGHT = 30;
    static final int VSKIP = 10;
    static final int HSKIP = SKIP;
    static final int BUTTON_WIDTH = 114;
    static final int LABEL_WIDTH = BUTTON_WIDTH;
    static final int TEXT_WIDTH = 400;

    // Buttons
    Button initButton;
    Button terminateButton;
    Button bubbleSortButton;
    Button directSortButton;
    Button shellSortButton;
    Button quickSortButton;
    Button heapSortButton;
    Button mergeSortButton;

    TextField sortAlgorithm;
    TextField numComparingsField;
    TextField numSwapsField;

    Canvas drawArea;
    //... Graphics drawAreaGraphics;

    public void init() {
        setLayout(null);
        setBackground(Color.lightGray);

        int x = MARGIN;
        int y = MARGIN;

        initButton = new Button("Random");
        add(initButton);
        initButton.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        x += BUTTON_WIDTH + HSKIP;

        bubbleSortButton = new Button("Bubble Sort");
        add(bubbleSortButton);
        bubbleSortButton.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        x += BUTTON_WIDTH + HSKIP;

        directSortButton = new Button("Direct Sort");
        add(directSortButton);
        directSortButton.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        x += BUTTON_WIDTH + HSKIP;

        shellSortButton = new Button("Shell Sort");
        add(shellSortButton);
        shellSortButton.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        x += BUTTON_WIDTH + HSKIP;

        quickSortButton = new Button("Quick Sort");
        add(quickSortButton);
        quickSortButton.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        x += BUTTON_WIDTH + HSKIP;

        heapSortButton = new Button("Heap Sort");
        add(heapSortButton);
        heapSortButton.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        x += BUTTON_WIDTH + HSKIP;

        mergeSortButton = new Button("In-place Merge");
        add(mergeSortButton);
        mergeSortButton.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        // x += BUTTON_WIDTH + HSKIP;

        x = MARGIN;
        y += BUTTON_HEIGHT + VSKIP;

        sortAlgorithm = new TextField();
        //??? float align = sortAlgorithm.getAlignmentX();
        add(sortAlgorithm);
        sortAlgorithm.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        x += BUTTON_WIDTH + HSKIP;

        terminateButton = new Button("Pause");
        add(terminateButton);
        terminateButton.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        terminateButton.setEnabled(false);
        x += BUTTON_WIDTH + HSKIP;

        Label l = new Label("Comparings:");
        add(l);
        l.setBounds(x, y, LABEL_WIDTH, BUTTON_HEIGHT);
        x += LABEL_WIDTH + HSKIP;

        numComparingsField = new TextField();
        add(numComparingsField);
        numComparingsField.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        x += BUTTON_WIDTH + HSKIP;

        l = new Label("Swappings:");
        add(l);
        l.setBounds(x, y, LABEL_WIDTH, BUTTON_HEIGHT);
        x += LABEL_WIDTH + HSKIP;

        numSwapsField = new TextField();
        add(numSwapsField);
        numSwapsField.setBounds(x, y, BUTTON_WIDTH, BUTTON_HEIGHT);
        // x += BUTTON_WIDTH + HSKIP;

        x = MARGIN;
        y += BUTTON_HEIGHT + VSKIP;

        drawArea = new Canvas() {
            public void paint(Graphics g) {
                g.setColor(Color.white);
                g.fillRect(0, 0, DRAW_AREA_WIDTH, DRAW_AREA_HEIGHT);

                g.setColor(Color.red);
                int x0 = MARGIN;
                int y0 = MARGIN;
                for (int i = 0; i < NMAX; ++i) {
                    g.fillRect(
                        x0 + i * (BAR_WIDTH + SKIP),
                        y0 + (BAR_HEIGHT - a[i]),
                        BAR_WIDTH, a[i]
                    );
                }
            }

            public void update(Graphics g) {
                paint(g);
            }
        };
        add(drawArea);
        drawArea.setBounds(x, y, DRAW_AREA_WIDTH, DRAW_AREA_HEIGHT);
        //... drawAreaGraphics = drawArea.getGraphics();

        ActionListener al = new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                Object source = e.getSource();
                if (source == initButton) {
                    onInit();
                } else if (source == terminateButton) {
                    onTerminate();
                } else if (source == bubbleSortButton) {
                    onBubbleSort();
                } else if (source == directSortButton) {
                    onDirectSort();
                } else if (source == shellSortButton) {
                    onShellSort();
                } else if (source == quickSortButton) {
                    onQuickSort();
                } else if (source == heapSortButton) {
                    onHeapSort();
                } else if (source == mergeSortButton) {
                    onMergeSort();
                }
            }
        };
        initButton.addActionListener(al);
        terminateButton.addActionListener(al);
        bubbleSortButton.addActionListener(al);
        directSortButton.addActionListener(al);
        shellSortButton.addActionListener(al);
        quickSortButton.addActionListener(al);
        heapSortButton.addActionListener(al);
        mergeSortButton.addActionListener(al);

        onInit();

        initButton.requestFocus();
    }

    void swap(int array[], int i, int j) {
        int tmp = array[i];
        array[i] = array[j]; array[j] = tmp;
        if (array == b) {
            // System.out.println("Swap " + i + " " + j);
            actions.addLast(
                new Action(Action.SWAP, i, j)
            );
            // ++numSwappings;
        }
    }

    int compare(int i, int j) {
        actions.addLast(
            new Action(Action.COMPARE, i, j)
        );
        // System.out.println("Compare " + i  + " " + j);
        // ++numComparings;
        return (b[i] - b[j]);
    }

    int compare(int array[], int i, int j) {
        actions.addLast(
            new Action(Action.COMPARE, i, j)
        );
        // System.out.println("Compare " + i  + " " + j);
        // ++numComparings;
        return (array[i] - array[j]);
    }



    public void animate() {
        if (sorting && actions.size() > 0) {
            Action act = actions.peekFirst();
            if (act == null)
                return;

            int i = act.ind0;
            int j = act.ind1;
            if (act.type == Action.SWAP) {
                swap(a, i, j);
                drawElement(i, Color.red);
                drawElement(j, Color.red);
                actions.removeFirst();
                ++numSwappings;
            } else if (act.type == Action.COMPARE) {
                if (i >= 0) {
                    drawElement(i, Color.green);
                    drawElement(j, Color.green);
                    act.ind0 = (-act.ind0) - 1;
                    ++numComparings;
                } else {
                    drawElement(-(i+1), Color.red);
                    drawElement(j, Color.red);
                    actions.removeFirst();
                }
            }

            // redraw();
            if (actions.size() <= 0) {
                sorting = false;
                // showStat();
                drawArea.repaint();
            }
            showStat();
        } else if (actions.size() <= 0) {
            sorting = false;
        }
    }

    void showStat() {
        numComparingsField.setText("" + numComparings);
        numSwapsField.setText("" + numSwappings);
        // sortAlgorithm.setText("" + sortName);
    }

    void drawElement(int i, Color color) {
        Graphics drawAreaGraphics = drawArea.getGraphics();
        if (drawAreaGraphics == null)
            return;
        int x0 = MARGIN;
        int y0 = MARGIN;
        int x = x0 + i * (BAR_WIDTH + SKIP);

        drawAreaGraphics.setColor(Color.white);
        drawAreaGraphics.fillRect(
            x, y0,
            BAR_WIDTH, BAR_HEIGHT - a[i]
        );

        drawAreaGraphics.setColor(color);
        drawAreaGraphics.fillRect(
            x, y0 + (BAR_HEIGHT - a[i]),
            BAR_WIDTH, a[i]
        );
    }

    public static void main(String[] args) {
        Frame f = new Frame("Sorting Algorithms");

        WindowAdapter wa = new WindowAdapter() {
            public void windowClosing(WindowEvent e) {
                System.exit(0);
            }
        };
        f.addWindowListener(wa);

        f.setFont(new Font("Helvetica", Font.PLAIN, 14));

        // Add menu bar
        final MenuBar mb = new MenuBar();
        f.setMenuBar(mb);
        final Menu fileMenu = new Menu("File");
        final MenuItem quitItem = new MenuItem("Quit");
        fileMenu.add(quitItem);
        mb.add(fileMenu);

        ActionListener al = new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                // System.out.println("Action " + e);
                if (e.getActionCommand().equals("Quit")) {
                    System.exit(0);
                }
            }
        };
        fileMenu.addActionListener(al);

        GSort gs = new GSort();
        f.add("Center", gs);

        // f.pack();
        int w = 2*MARGIN + 7*(BUTTON_WIDTH + HSKIP) - HSKIP;
        if (w < DRAW_AREA_WIDTH + 2*MARGIN)
            w = DRAW_AREA_WIDTH + 2*MARGIN;

        f.setSize(
            w + 16,                     // + 16 ???
            2*MARGIN + 2*(BUTTON_HEIGHT + VSKIP) +
            70 +                        // For menu bar
            DRAW_AREA_HEIGHT
        );
        f.setVisible(true);

        gs.init();
        gs.start();
    }

    void onInit() {
        initialize();
        drawArea.repaint();
    }

    void initialize() {
        if (sortingThread != null && sorting) {
            terminate = true;
            try {
                sortingThread.join(500);    // Wait 0.5 sec
            } catch (InterruptedException e) {

            }
        }
        sorting = false;

        for (int i = 0; i < NMAX; ++i) {
            double r = Math.random();
            a[i] = (int)(r * (double) BAR_HEIGHT + 0.49);
            if (a[i] < 2)
                a[i] = 2;
        }
        numComparings = 0;
        numSwappings = 0;

        actions.clear();
    }

    void onTerminate() {
        if (sortingThread != null && sorting) {
            /*...
            terminate = true;
            try {
                sortingThread.join(500);    // Wait 0.5 sec
            } catch (InterruptedException e) {

            }
            ...*/
            if (!pause) {
                pause = true;
                terminateButton.setLabel("Continue");
            } else {
                pause = false;
                terminateButton.setLabel("Pause");
            }
        }
        showStat();
        //... sorting = false;
        drawArea.repaint();
    }

    void onBubbleSort() {
        onTerminate();
        actions.clear();

        sortName = "Bubble Sort";
        sortAlgorithm.setText("" + sortName);

        numComparings = 0;
        numSwappings = 0;
        showStat();
        for (int i = 0; i < NMAX; ++i)
            b[i] = a[i];

        sorting = true;
        boolean inversion = true;
        while (inversion) {
            inversion = false;
            for (int i = 0; i < NMAX-1; ++i) {
                if (compare(i, i+1) > 0) {
                    swap(b, i, i+1);
                    inversion = true;
                }
            }
        }
        drawArea.repaint();
        startSortingThread();
    }

    void onDirectSort() {
        onTerminate();
        actions.clear();

        // System.out.println("onDirectSort");
        sortName = "Select Min";
        sortAlgorithm.setText("" + sortName);

        numComparings = 0;
        numSwappings = 0;
        showStat();
        for (int i = 0; i < NMAX; ++i)
            b[i] = a[i];

        sorting = true;
        for (int i = 0; i < NMAX-1; ++i) {
            int imin = i;
            for (int j = i+1; j < NMAX; ++j) {
                if (compare(j, imin) < 0) {
                    imin = j;
                }
            }
            if (imin != i) {
                swap(b, i, imin);
            }
        }

        drawArea.repaint();
        startSortingThread();
    }

    void onShellSort() {
        onTerminate();
        actions.clear();

        sortName = "Shell Sort";
        sortAlgorithm.setText("" + sortName);

        numComparings = 0;
        numSwappings = 0;
        showStat();
        for (int i = 0; i < NMAX; ++i)
            b[i] = a[i];

        sorting = true;
        int gap = 1;
        while ((gap + 1)*2 - 1 < NMAX) {
            gap = (gap + 1)*2 - 1;
        }

        boolean inversion = true;
        while (inversion || gap > 1) {
            inversion = false;
            for (int i = 0; i < NMAX-gap; ++i) {
                if (compare(i, i+gap) > 0) {
                    swap(b, i, i+gap);
                    inversion = true;
                }
            }
            if (!inversion && gap > 1) {
                gap = (gap + 1)/2 - 1;
                inversion = true;
            }
        }

        drawArea.repaint();
        startSortingThread();
    }

    void onQuickSort() {
        onTerminate();
        actions.clear();

        sorting = true;
        sortName = "Quick Sort";
        sortAlgorithm.setText("" + sortName);

        numComparings = 0;
        numSwappings = 0;
        showStat();
        for (int i = 0; i < NMAX; ++i)
            b[i] = a[i];

        qSort(0, NMAX);

        drawArea.repaint();
        startSortingThread();
    }

    void qSort(int s, int n) {
        if (n <= 1)
            return;
        while (n > 0) {
            int m = s + n/2;
            m = partition(s, n, m);
            int n0 = m - s;
            int n1 = n - 1 - n0;
            if (n0 <= n1) {
                qSort(s, n0);
                s = m+1;
                n = n1;
            } else {
                qSort(m+1, n1);
                n = n0;
            }
        }
    }

    int partition(int s, int n, int m) {
        int mNew;
        if (m != s) {
            swap(b, s, m);
        }
        int n0 = 0;
        int n1 = 0;
        while (n0 + n1 < n-1) {
            int i = s+1+n0;
            if (compare(i, s) <= 0) {
                ++n0;
            } else if (compare(s + (n-1) - n1, s) > 0) {
                ++n1;
            } else {
                int j = s + (n-1) - n1;
                assert(b[i] > b[s] && b[j] <= b[s]);
                swap(b, i, j);
                ++n0;
                ++n1;
            }
        }
        if (n0 > 0) {
            int i = s+n0;
            swap(b, s, i);
            mNew = i;
        }
        else  {
            mNew = s;
        }
        return mNew;
    }

    void onHeapSort() {
        onTerminate();
        actions.clear();

        sortName = "Heap Sort";
        sortAlgorithm.setText("" + sortName);

        numComparings = 0;
        numSwappings = 0;
        showStat();
        for (int i = 0; i < NMAX; ++i)
            b[i] = a[i];

        sorting = true;

        //===========
        int n = NMAX;
        int k = n / 2 + 1;
        while (k >= 0) {
            sieve(k, n);
            --k;
        }
        k = n;

        while (k > 1) {
            --k;
            swap(b, 0, k);
            sieve(0, k);
        }
        //===========

        drawArea.repaint();
        startSortingThread();
    }

    void sieve(int i, int n) {
        int s0 = 2*i;
        int s1 = s0 + 1;
        int s = s0;
        if (s1 < n && compare(s1, s0) > 0)
            s = s1;
        while (s < n && compare(i, s) < 0) {
            swap(b, i, s);
            i = s;
            s0 = 2*i;
            s1 = s0 + 1;
            s = s0;
            if (s1 < n && compare(s1, s0) > 0)
                s = s1;
        }
    }

    void onMergeSort() {
        onTerminate();
        actions.clear();

        sortName = "In-place Merge";
        sortAlgorithm.setText("" + sortName);

        numComparings = 0;
        numSwappings = 0;
        showStat();
        for (int i = 0; i < NMAX; ++i)
            b[i] = a[i];

        sorting = true;

        //===========
        int n = NMAX;
        if (n <= 1)
            return;
        if (n == 2) {
            //... if (b[0] > b[1])
            if (compare(0, 1) > 0)
                swap(b, 0, 1);
            return;
        }

        int len = 1;

        while (len < n) {
            int i = 0;
            while (i < n-len) {
                int len2 = len;
                if (i + len + len2 > n)
                    len2 = n - (i + len);
                // Merge a pair of sub-arrays
                mergeBlocks(
                    b, i, len, len2
                );
                // Go to the next pair
                i += (len + len2);
            }

            len *= 2;
        }
        //===========

        drawArea.repaint();
        startSortingThread();
    }

    // The sub-array a consists of 2 consecutive blocks
    // of lengths len0 and len1 that are already sorted.
    // Merge them in place using the recursive procedure.
    void mergeBlocks(
        int a[], int beg,
        int len0, int len1
    ) {
        if (len0 <= 0 || len1 <= 0)
            return;
        int n = len0 + len1;

        if (len0 == 1) {
            /*...
            int i = 0;
            //... while (i < n-1 && a[beg+i] > a[beg+i+1]) {
            while (
                i < n-1 &&
                compare(a, beg+i, beg+i+1) > 0
            ) {
                swap(a, beg+i, beg+i+1);
                ++i;
            }
            ...*/

            int k = findUpper(a, beg+1, len1, beg);
            int i = 0;
            while (i < k) {
                // assert(a[beg+i] > a[beg+i+1]);
                swap(a, beg+i, beg+i+1);
                ++i;
            }
            // assert(i >= n-1 || a[beg+i] <= a[beg+i+1]);
            return;
        }

        if (len1 == 1) {
            /*...
            int i = n-1;
            //... while (i > 0 && a[beg+i] < a[beg+i-1]) {
            while (
                i > 0 &&
                compare(a, beg+i, beg+i-1) < 0
            ) {
                swap(a, beg+i, beg+i-1);
                --i;
            }
            ...*/

            int k = findLower(a, beg, len0, beg+n-1);
            int i = n-1;
            while (i > k+1) {
                // assert(a[beg+i-1] > a[beg+i]);
                swap(a, beg+i-1, beg+i);
                --i;
            }
            // assert(i <= 0 || a[i-1] <= a[i]);
            return;
        }

        // assert(len0 > 1 && len1 > 1);
        int c0, c1;
        if (len0 >= len1) {
            c0 = len0/2;
            c1 = findUpper(
                a, beg+len0,
                len1, // a[beg+c0]
                beg+c0
            );
            // assert(len0+c1 >= n || a[beg+len0+c1] >= a[beg+c0]);

            swapBlocks(
                a, beg+c0,
                len0-c0, c1
            );
        } else {
            c1 = len1/2;
            c0 = findLower(
                    a, beg,
                    len0, // a[beg+len0+c1]
                    beg+len0+c1
                ) + 1;
            // assert(c0 >= len0 || a[beg+c0] >= a[beg+len0+c1]);
            swapBlocks(
                a, beg+c0,
                len0-c0, c1
            );
        }
        mergeBlocks(
            a, beg,
            c0, c1
        );
        mergeBlocks(
            a, beg+c0+c1,
            len0-c0, len1-c1
        );
    }

    void swapBlocks(
        int a[], int beg,
        int len0, int len1
    ) {
        if (len0 <= 0 || len1 <= 0)
            return;
        if (len0 == len1) {
            for (int i = 0; i < len0; ++i)
                swap(a, beg+i, beg+i+len0);
            return;
        }
        reverseBlock(a, beg, len0);
        reverseBlock(a, beg+len0, len1);
        reverseBlock(a, beg, len0+len1);
    }

    void reverseBlock(int a[], int beg, int n) {
        if (n <= 1)
            return;
        int i = 0; int j = n-1;
        while (i < j) {
            swap(a, i+beg, j+beg);
            ++i; --j;
        }
    }

    // The sub-array a[beg] of length n is sorted.
    // Find the element with minimal index i such that
    // a[beg+i] >= x
    int findUpper(
        int a[], int beg,
        int n,
        //... int x
        int xIdx        // x == a[xIdx]
    ) {
        //... if (n <= 0 || x <= a[beg])
        if (n <= 0 || compare(a, xIdx, beg)  <= 0)
            return 0;
        //... if (x > a[beg+n-1])
        if (compare(a, xIdx, beg+n-1) > 0)
            return n;
        // assert(n > 0 && a[beg] < x && x <= a[beg+n-1]);
        int b = 0; int e = n-1;
        while (e-b > 1) {
            // assert(a[beg+b] < x && x <= a[beg+e]);
            int c = (b+e)/2;
            //... if (a[beg+c] < x)
            if (compare(a, beg+c, xIdx) < 0)
                b = c;
            else
                e = c;
        }
        // assert(a[beg+e-1] < x && x <= a[beg+e]);
        return e;
    }

    // The sub-array a[beg] of length n is sorted.
    // Find the element with maximal index i such that
    // a[beg+i] <= x
    int findLower(
        int a[], int beg,
        int n,
        int xIdx    // x == a[xIdx]
    ) {
        //... if (n <= 0 || x < a[beg])
        if (n <= 0 || compare(a, xIdx, beg) < 0)
            return (-1);
        //... if (a[beg+n-1] <= x)
        if (compare(a, beg+n-1, xIdx) <= 0)
            return n-1;
        // assert(n > 0 && a[beg] <= x && x < a[beg+n-1]);
        int b = 0; int e = n-1;
        while (e-b > 1) {
            // assert(a[beg+b] <= x && x < a[beg+e]);
            int c = (b+e)/2;
            //... if (a[beg+c] <= x)
            if (compare(a, beg+c, xIdx) <= 0)
                b = c;
            else
                e = c;
        }
        // assert(a[beg+b] <= x && x < a[beg+b+1]);
        return b;
    }

    public void startSortingThread() {
        if (sortingThread != null)
            return;
        sortingThread = new Thread(this, "SortingThread");
        sortingThread.start();
    }

    public void run() {
        pause = false;
        terminateButton.setLabel("Pause");
        terminateButton.setEnabled(true);

        while (sorting && !terminate && sortingThread != null) {
            if (!pause)
                animate();
            try {
                sortingThread.sleep(DT);
            } catch (InterruptedException e) {

            }
        }

        terminate = false;
        sortingThread = null;
        // stepButton.enable(true);
        // startButton.enable(true);
        // stopButton.enable(false);
        // eraseButton.enable(true);

        pause = false;
        terminateButton.setEnabled(false);
    }
}