import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
/**
* A panel 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 from which the "pivot" element has been removed.
* The user can abort the sort by clicking the button again.
* <p>
* 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. 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.
* <p>
* This class contains a main() routine that allows the demo to be run as a
* stand-alone application.
*/
public class QuicksortThreadDemo extends JPanel {
/**
* This main routine just shows a panel of type QuicksortThreadDemo.
*/
public static void main(String[] args) {
JFrame window = new JFrame("Demo: Recursion in a Thread");
QuicksortThreadDemo content = new QuicksortThreadDemo();
window.setContentPane(content);
window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
window.pack();
Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
window.setLocation((screenSize.width - window.getWidth()) / 2,
(screenSize.height - window.getHeight()) / 2);
window.setVisible(true);
}
private final static int ARRAY_SIZE = 150; // The number of colored bars.
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 Display display; // The panel that displays the colored bars.
private JButton 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 true as a signal to
// the
// thread to abort.
/**
* 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 {
}
/**
* A subpanel of type Display shows the colored bars that are being sorted.
* The current pivot, if any, is shown in black. A 3-pixel gray border is
* left around the bars.
*/
private class Display extends JPanel {
Display() {
setPreferredSize(new Dimension(606, 206));
setBackground(Color.GRAY);
}
protected void paintComponent(Graphics g) {
super.paintComponent(g);
double barWidth = (double) (getWidth() - 6) / hue.length;
int h = getHeight() - 6;
for (int i = 0; i < hue.length; i++) {
int x1 = 3 + (int) (i * barWidth + 0.49);
int x2 = 3 + (int) ((i + 1) * barWidth + 0.49);
int w = x2 - x1;
if (hue[i] == -1)
g.setColor(Color.BLACK);
else
g.setColor(palette[hue[i]]);
g.fillRect(x1, 3, w, h);
}
}
}
/**
* The constructor sets up the panel, containing the Display and the Start
* button below it.
*/
public QuicksortThreadDemo() {
for (int i = 0; i < ARRAY_SIZE; i++) {
palette[i] = Color.getHSBColor((i * 230) / (ARRAY_SIZE * 255.0F),
1, 1);
hue[i] = i;
}
setLayout(new BorderLayout());
display = new Display();
add(display, BorderLayout.CENTER);
startButton = new JButton("Start");
JPanel bottom = new JPanel();
bottom.add(startButton);
bottom.setBackground(Color.WHITE);
add(bottom, BorderLayout.SOUTH);
startButton.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent e) {
if (running)
stop();
else
start();
}
});
}
/**
* This method is called when the user clicks the Start button, while no
* thread is running. It starts a new thread and sets the signaling
* variable, running, to true; Also changes the text on the Start button to
* "Finish".
*/
private void start() {
startButton.setText("Finish");
runner = new Runner();
running = true; // Set the signal before starting the thread!
runner.start();
}
/**
* This method is called when the user clicks the button while a thread is
* running. A signal is sent to the thread to terminate, by setting the
* value of the signaling variable, running, to false.
*/
private void stop() {
/*
* Set the value of the signaling variable to false as a signal to the
* thread to terminate.
*/
running = false;
/*
* Wake the thread, in case it is sleeping, to get a more immediate
* reaction to the signal.
*/
runner.interrupt();
/*
* Wait for the thread to stop before setting runner = null. One second
* should be plenty of time for this to happen, but in case something
* goes wrong, it's better not to
*/
try {
runner.join(1000); // Wait for thread to stop. One second should be
// plenty of time.
} catch (InterruptedException e) {
}
runner = null;
}
/**
* This method is called frequently by the thread that is running the
* recursion, in order to insert delays. It calls the repaint() method of
* the display to allow the user to see what is going on; the delay will
* give the system a chance to actually update the display. 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 ThreadTerminatedException. 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();
display.repaint();
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 positions 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.
*/
private int quickSortStep(int lo, int hi) {
int pivot = hue[lo]; // Save pivot item.
hue[lo] = -1; // Mark location lo as empty.
delay(100);
while (true) {
while (hi > lo && hue[hi] > pivot)
hi--;
if (hi == lo)
break;
hue[lo] = hue[hi]; // Move hue[hi] into empty space.
hue[hi] = -1; // Mark location hi as empty.
delay(100);
while (lo < hi && hue[lo] < pivot)
lo++;
if (hi == lo)
break;
hue[hi] = hue[lo]; // Move hue[lo] into empty space.
hue[lo] = -1; // Mark location lo as empty.
delay(100);
}
hue[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().
*/
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 treads that run the recursive QuickSort algorithm.
* The thread begins by randomizing the array. It then calls quickSort() to
* sort the entire array. If quickSort() is aborted by a
* ThreadTerminationExcpetion, 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.
*/
private class Runner extends Thread {
public void run() {
try {
for (int i = hue.length - 1; i > 0; i--) { // Randomize array.
int r = (int) ((i + 1) * Math.random());
int temp = hue[r];
hue[r] = hue[i];
hue[i] = temp;
}
delay(1000); // Wait one second before starting the sort.
quickSort(0, hue.length - 1); // Sort the whole array.
} catch (ThreadTerminationException e) { // User aborted quickSort.
for (int i = 0; i < hue.length; i++)
hue[i] = i;
} finally {// Make sure running is false and button label is
// correct.
running = false;
startButton.setText("Start");
display.repaint();
}
}
}
} // end QuicksortThreadDemo
`
