StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<pre><code>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 </code></pre> <p>`</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload