
import javafx.application.Application;
import javafx.application.Platform;
import javafx.stage.Stage;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.layout.BorderPane;
import javafx.scene.layout.HBox;
import javafx.geometry.Pos;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.paint.Color;


/**
 * A program that can show a demonstration of Quicksort in action.
 * The items to be sorted are the hues of a set of vertical bars.
 * When sorted, the bars form a spectrum from red to violet.
 * Initially, the bars are sorted.  There is a Start button.  When
 * the user clicks this button, the order of the bars is randomized
 * and then Quicksort is applied.  During the sort, a black bar
 * marks the location of an "empty" space in the array.  
 * The user can abort the sort by clicking the button again.
 * 
 * The main point of this program is to demonstrate threads, with
 * very simple inter-thread communication. The recursive Quicksort
 * algorithm is run in a separate thread. All shanges to the canvas
 * by that thread are made using Platform.runLater().  The abort 
 * operation is implemented by setting the value of a volatile variable 
 * that is checked periodically by the thread.  When the user aborts
 * the sort before it finishes, the value of the variable changes;
 * the thread sees the change and exits.
 */
public class QuicksortThreadDemo extends Application {

    public static void main(String[] args) {
        launch(args);
    }
    //-----------------------------------------------------------------

    private final static int ARRAY_SIZE = 100;  // The number of colored bars;
                                                // canvas width will be 6*ARRAY_SIZE.

    private int[] hue = new int[ARRAY_SIZE];  // The array that will be sorted.
    private Color[] palette = new Color[ARRAY_SIZE]; // Colors in spectral order.
    private Canvas canvas;      // The panel that displays the colored bars.
    private GraphicsContext g;  // A graphics context for drawing on the canvas.
    private Button startButton; // The button that starts and stops the demo.

    private Runner runner; // The thread that runs the recursion.
    private volatile boolean running;   // Set to true while recursion is running;
                                        // this is set to false as a signal to the
                                        // thread to abort.


    /**
     * Set up the GUI and event-handling.  Also fills the palette array
     * with colors in spectral order.
     */
    public void start(Stage stage) {
        for (int i = 0; i < ARRAY_SIZE; i++) {
            palette[i] = Color.hsb((310.0*i)/ARRAY_SIZE, 1, 1);
        }
        canvas = new Canvas(6+6*ARRAY_SIZE, 206);
        g = canvas.getGraphicsContext2D();
        drawSorted();  // initial drawing of canvas, with sorted colors.
        startButton = new Button("Start!");
        startButton.setOnAction( e -> doStartOrStop() );
        HBox bottom = new HBox(startButton);
        bottom.setStyle("-fx-padding: 6px");
        bottom.setAlignment(Pos.CENTER);
        BorderPane root = new BorderPane(canvas);
        root.setBottom(bottom);
        Scene scene = new Scene(root);
        stage.setScene(scene);
        stage.setTitle("Demo: Quicksort in a Thread");
        stage.setResizable(false);
        stage.show();
    }


    /**
     * When the user aborts the recursion before it finishes, an exception of
     * this type is thrown to end the recursion cleanly.
     */
    private class ThreadTerminationException extends RuntimeException {
    }

    
    /**
     * Redraws the entire canvas, with colors in sorted order.  This method
     * is ALWAYS called on the application thread.  It is called in the
     * start() method to draw the initial contents of the canvas, and it
     * is called when the animation thread exits, to make sure that
     * the colors are shown in sorted order at that time.
     */
    private void drawSorted() {
        g.setFill(Color.GRAY);
        g.fillRect(0,0,canvas.getWidth(),canvas.getHeight());
        double barWidth = (double)(canvas.getWidth() - 6) / palette.length;
        double h = canvas.getHeight() - 6;
        for (int i = 0; i < palette.length; i++) {
            int x1 = 3 + (int)(i*barWidth + 0.49);
            int x2 = 3 + (int)((i+1)*barWidth + 0.49);
            int w = x2 - x1;
            g.setFill( palette[i] );
            g.fillRect(x1,3,w,h);
        }
    }
    
    
    /**
     * Change one of the values in the hue array, and redraw the corresponding
     * vertical line on the canvas in the new color.  This method is ALWAYS
     * called on the animation thread, not the application thread.  It uses
     * Platform.runLater() to draw the line that needs to change color on the canvas.
     * @param index  the index of the element in the hue array that is changed
     * @param colorNumber  the new value for the element in the hue array.
     *             If the value is -1, the new color is black; otherwise,
     *             colorNumber is an index into the palette array.
     */
    private void setHue( int index, int colorNumber ) {
        hue[index] = colorNumber;
        Platform.runLater( () -> {
            double barWidth = (double)(canvas.getWidth() - 6) / palette.length;
            double h = canvas.getHeight() - 6;
            int x1 = 3 + (int)(index*barWidth + 0.49);
            int x2 = 3 + (int)((index+1)*barWidth + 0.49);
            int w = x2 - x1;
            if (colorNumber == -1)
                g.setFill(Color.BLACK);
            else
                g.setFill(palette[colorNumber]);
            g.fillRect(x1,3,w,h);
        });
    }    
    

    /**
     * This method is called when the user clicks the Start button,
     * If no thread is running, it starts a new thread, after setting
     * the signaling variable, running, to true; it also changes the text
     * on the Start button to "Finish". If the user clicks the button while
     * a thread is running, then a signal is sent to the thread to terminate,
     * by setting the value of the signaling variable, running, to false.
     * Note that the thread changes the text on the button back
     * to "Start" before it terminates.
     */
    private void doStartOrStop() {
        if (running == false) { // start a thread
            startButton.setText("Finish");
            runner = new Runner();
            running = true;  // Set the signal before starting the thread!
            runner.start();
        }
        else { // stop the running thread

            /* Set the value of the signaling variable to false as a signal
             * to the thread to terminate.  When this is seen in the
             * recursive algorithm, it will throw a ThreadTerminationException
             * to terminate the thread.
             */

            running = false; 

            /* Wake the thread, in case it is sleeping, to get a more
             * immediate reaction to the signal.
             */

            runner.interrupt(); 

        }
    }



    /**
     * This method is called frequently by the thread that is running
     * the recursion, in order to insert delays.  The delay
     * will give the system a chance to update the display, and it
     * gives the user a chance to see what is going on in the sort.
     * Since this method is called regularly while the recursion is in 
     * progress, it is also used as a convenient place to check the value
     * of the signaling variable, running.  If the value of running has
     * been set to false, this method throws an exception of type
     * ThreadTerminationException.  This exception will cause all active
     * levels of the recursion to be terminated.  It is caught in the
     * run() method of the thread.
     * @param millis  The number of milliseconds to sleep.
     */
    private void delay(int millis) {
        if (! running)
            throw new ThreadTerminationException();
        try {
            Thread.sleep(millis);
        }
        catch (InterruptedException e) {
        }
        if (! running)
            throw new ThreadTerminationException();
    }


    /**
     * The basic non-recursive QuickSortStep algorithm, which
     * uses hue[lo] as a "pivot" and rearranges elements of the 
     * hue array from positions lo through hi so that
     * the pivot value is in its correct location, with smaller
     * items to the left and bigger items to the right.  The
     * position of the pivot is returned.  In this version,
     * we conceptually remove the pivot from the array, leaving
     * an empty space.  The space is marked by a -1, and it moves
     * around as the algorithm proceeds.  It is shown as a black
     * bar in the display. Every time a change is made, the
     * delay() method is called to insert a 1/10 second delay
     * to let the user see the change.  All changes to the hue
     * array are made by calling setHue(), which also changes the
     * color of the corresponding line on the canvas.
     */
    private int quickSortStep(int lo, int hi) {
        int pivot = hue[lo];  // Save pivot item.
        setHue( lo, -1);  // Mark location lo as empty.
        delay(100);
        while (true) {
            while (hi > lo  && hue[hi] > pivot)
                hi--;
            if (hi == lo)
                break;
            setHue(lo,hue[hi]); // Move hue[hi] into empty space.
            setHue(hi,-1);      // Mark location hi as empty.
            delay(100);
            while (lo < hi && hue[lo] < pivot)
                lo++;
            if (hi == lo)
                break;
            setHue(hi,hue[lo]);  // Move hue[lo] into empty space.
            setHue(lo, -1);      // Mark location lo as empty.
            delay(100);
        }
        setHue(lo,pivot);  // Move pivot item into the empty space.
        delay(100);
        return lo;
    }


    /**
     * The recursive quickSort algorithm, for sorting the hue
     * array from positions lo through hi into increasing order.
     * Most of the actual work is done in quickSortStep().
     * This method is called by the animation thread as  
     * quickSort(0,hue.length-1)  to sort the entire array.
     */
    private void quickSort(int lo, int hi) {
        if (hi <= lo)
            return;
        int mid = quickSortStep(lo, hi);
        quickSort(lo, mid-1);
        quickSort(mid+1, hi);
    }


    /**
     * This class defines the thread that runs the recursive
     * QuickSort algorithm.  The thread begins by randomizing the
     * hue array.  It then calls quickSort() to sort the entire array.
     * If quickSort() is aborted by a ThreadTerminationException,
     * which would be caused by the user clicking the Finish button,
     * then the thread will restore the array to sorted order before
     * terminating, so that whether or not the quickSort is aborted,
     * the array ends up sorted.  In any case, in the end, it 
     * resets the text on the button to "Start".
     */
    private class Runner extends Thread {
        Runner() {
                // The constructor sets this thread to be a Daemon thread.
                // Otherwise, the thread will keep the Java Virtual Machine
                // from exiting when the window is closed.
            setDaemon(true);
        }
        public void run() {
            for (int i = 0; i < hue.length; i++) {
                   // fill hue array with indices in order
                hue[i] = i;
            }
            for (int i = hue.length-1; i > 0; i--) { 
                   // Randomize the order of the hues.
                int r = (int)((i+1)*Math.random());
                int temp = hue[r];
                hue[r] = hue[i];
                   // The last assignment that needs to be done in this
                   // loop is hue[i] = temp.  The value of hue[i] will
                   // not change after this, so the assignment is done
                   // by calling setHue(i,temp) which will change
                   // the value in the array and also use Platform.runLater()
                   // to change the color of the i-th line in the canvas.
                setHue(i,temp);
            }
            try {
                delay(1000);  // Wait one second before starting the sort.
                quickSort(0,hue.length-1);  // Sort the whole array.
            }
            catch (ThreadTerminationException e) { // User aborted quickSort.
                    // Put the colors back into sorted order.  The drawSorted()
                    // method draws all of the color bars in sorted order.
                Platform.runLater( () -> drawSorted() );
            }
            finally {
                running = false;  // make sure running is false; this is only
                                  //   really necessary if the thread terminated
                                  //   normally
                Platform.runLater( () -> startButton.setText("Start") );
            }
        }
    }

} // end QuicksortThreadDemo
