/* ShowSort.java:  visual demonstration of sorting algorithms.
 * (C) 1999 Neil Moore <neil@cs.uky.edu>
 *
 * This program may be freely distributed under the terms of the
 * GPL; see the file COPYING for more information.
 */
import java.applet.*;
import java.lang.Math;
import java.util.Random;
import java.awt.*;

/**
 * The ShowSort class provides the framework for a visual demonstation of
 * sorting algorithms.  Individual classes, one for each algorithm, use this
 * class by deriving it and providing the doSort() method.  This method
 * should sort the <a href="#array">array[]</a> member, calling
 * <a href="#compared">compared()</a> and <a href="#compared">swapped()</a>
 * as appropriate.
 *
 * @see ShowSortFrame
 * @author Neil Moore <a href="mailto:neil@cs.uky.edu">
 *         &lt;neil@cs.uky.edu&gt;</a>
 * @version 0.12
 */
abstract class ShowSort extends Applet implements Runnable {
	/**
	 * The main applet thread, created by ShowSort::start().
	 *
	 * @see ShowSort#start
	 */
	Thread sortThread=null;    // The applet thread.

	/**
	 * The array being sorted.
	 */
	int array[];   // The array being sorted.
	int current;   // The element being processed (see ShowSort::paint())

	/**
	 * Time (in milliseconds) to pause for each call to compared().
	 *
	 * @see ShowSort#compared
	 * @see ShowSort#swap_time
	 */
	int compare_time = 25;
	
	/**
	 * Time (in milliseconds) to pause for each call to swapped().
	 *
	 * @see ShowSort#swapped
	 * @see ShowSort#compare_time
	 */
	int swap_time = 25;

	/**
	 * Default colour for the graphical representation of elements of
	 * array[]
	 *
	 * @see ShowSort#paint
	 */
	Color def_bar_color     = Color.black;

	/**
	 * Used as the colour for the current element of array[].
	 *
	 * @see ShowSort#paint
	 */
	Color curr_bar_color    = Color.red;

	/**
	 * Used as the colour for correctly-placed elements of array[].
	 *
	 * @see ShowSort#paint
	 * @see ShowSort#inplace_pos
	 * @see ShowSort#inplace_dir
	 */
	Color inplace_bar_color = Color.blue;

	/**
	 * Colour all elements before or after (depending on
	 * <a href="#inplace_dir">inplace_dir</a>) this position in array[]
	 * with <a href="#inplace_bar_color">inplace_bar_color</a>.
	 *
	 * @see ShowSort#paint
	 * @see ShowSort#inplace_bar_color
	 * @see ShowSort#inplace_dir
	 */
	int inplace_pos = -1;

	/**
	 * Indicates the direction in which elements are placed.  true means
	 * that all elements following inplace_pos are in place, false that
	 * all elements preceding inplace_pos are in place.
	 *
	 * @see ShowSort#paint
	 * @see ShowSort#inplace_bar_color
	 * @see ShowSort#inplace_pos
	 */
	boolean inplace_dir = false;

	/**
	 * The number of elements in array[].
	 *
	 * @see ShowSort#array
	 */
	int NUM=100;   // Number of elements in the array.

	/**
	 * Random-number generator, used for shuffling.
	 */
	private Random r;

	/**	   
	 * This method will do the actual sorting of array[].  It should
	 * call compared() whenever it compares two elements, swapped()
	 * whenever it moves or swaps elements.
	 *
	 * @see ShowSort#compared
	 * @see ShowSort#swapped
	 */
	abstract void doSort();

	/**
	 * Create a new ShowSort object.  Does not actually initialise
	 * the array (allowing derived classes to modify this
	 * behaviour).  This constuctor performs only those actions
	 * which will remain the same for all derived classes.
	 *
	 * @see ShowSort#init
	 * @see ShowSort#launch
	 */
	ShowSort() {
		r = new Random();
	}
		
	/**
	 * Begin a ShowSort applet running within a ShowSortFrame.  This
	 * should be called by the main() method of any derived classes.
	 *
	 * @param title the title to be used for the frame
	 * @see ShowSortFrame
	 */
	void launch(String title) {
		ShowSortFrame app = new ShowSortFrame(this, title);
		int size=NUM;
		app.setSize(size+20,size+40);
		app.show();
		start();
	}

	/**
	 * Allocate the array and perform other initialisation tasks.  This
	 * function should do only things which may be safely overridden by
	 * a derived class.
	 */
	public void init() {
		array = new int[NUM];
		current = -1;
		setBackground(Color.white);
	}

	/**
	 * Begin running the applet.  This method starts up the sorting
	 * thread.
	 *
	 * @see ShowSort#run
	 */
	public void start() {
		repaint();
		if (sortThread == null) {
			/* Completely reinitialise the array; this must be
			 * done here because a stop() during an update could
			 * leave the array in an unconsistent state.  It
			 * would be somewhat cleaner to use monitors, but it
			 * hardly seems worth it.
			 */
			for (int i=0; i<NUM; i++)
				array[i]=i;
			shuffle();
			sortThread = new Thread(this);
			sortThread.start();
		}
	}

	/**
	 * Stop the execution of the applet.  This method stops the sorting
	 * thread.
	 */
	public void stop() {
		if (sortThread != null)
			sortThread = null;
		sortThread = null;
	}

	/**
	 * Begin sorting the array.  This method is primarily a wrapper
	 * around doSort(); the wrapper ensures that the display is correct
	 * when the sort is finished.
	 *
	 * @see ShowSort#start
	 * @see ShowSort#doSort
	 */
	public void run() {
		doSort();

		// Show all elements as `inplace'.
		current = -1;
		inplace_pos = 0;
		inplace_dir=true;
		
		repaint();
	}

	/**
	 * Randomise the array.  This method makes array[] a permutation of
	 * its original self; i.e., it consists of the same elements, in a
	 * different order.  Uses the Fischer-Yates algorithm.
	 */
	void shuffle() {
		for (int i=NUM-1; i>0; --i) {
			int j = (Math.abs(r.nextInt() % (i + 1)));
			if(i != j) {
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
	}

	/**
	 * Paint the applet.  array[] is displayed as a group of vertical
	 * lines, ranging from index 0 (at the left) to index NUM-1 (at the
	 * right).  Each line's height is directly proportional to the size
	 * of that element of array[].
	 *
	 * Lines are coloured according to their indices, as follows: <ul>
	 * <li> Indices greater than inplace_pos (if inplace_dir is true),
	 *   or less than inplace_pos (if inplace_dir is false) are painted
	 *   with inplace_bar_color (blue by default).
	 * <li> The line indicated by current is painted with curr_bar_color
	 *   (red by default).
	 * <li> Other lines are painted with def_bar_color (black by
	 *   default).
	 *
	 * @param g a graphics context
	 * @see ShowSort#drawBar
	 */
	public void paint(Graphics g) {
		if ((inplace_dir && inplace_pos != 0) || inplace_pos < 0)
			g.setColor(def_bar_color);
		else
			g.setColor(inplace_bar_color);
		
		for (int i=0; i<NUM; i++) {
			if (i == current)
				g.setColor(curr_bar_color);
			else if (i == inplace_pos) {
				if (inplace_dir)
					g.setColor(inplace_bar_color);
				else
					g.setColor(def_bar_color);
			}
			drawBar(g,i);
			if (i == current) {
				if ((inplace_dir && i >= inplace_pos) ||
				    (!inplace_dir && i < inplace_pos)) {
					g.setColor(inplace_bar_color);
				} else {
					g.setColor(def_bar_color);
				}
				
			}
		
			
		}		
	}

	/**
	 * Draw a bar representing an array element.  This function is called 
	 * by ShowSort.paint for each array element.  It assumes the correct
	 * color has been set by its caller.
	 *
	 * @param g a graphics context
	 * @param pos the element to draw (0 &lt;= pos &lt; NUM).
	 * @see ShowSort#paint.
	 */
	void drawBar(Graphics g, int pos) {
		Rectangle r = g.getClipBounds();
		int x0 = (r.width-NUM)/2;
		int y0 = (r.height-NUM)/2;
		g.drawLine(x0+pos, y0+NUM, x0+pos, y0+NUM-array[pos]);
	}

	/**
	 * Repaint the applet, and pause for a short interval.  This method
	 * should be called by doSort() whenever an element of array[] is
	 * compared (whether with a constant, a variable, or another element
	 * of array[]).  The length of time to pause is determined by the
	 * compare_time member (measured in milliseconds).
	 *
	 * @param elt the index of one of the elements being compared
	 * @see ShowSort#swapped
	 */
	void compared(int elt) {
		current = elt;
		repaint();
		try {
			Thread.sleep(compare_time);
		} catch (InterruptedException e) {
			repaint();
		}
	}

	/**
	 * Repaint the applet, and pause for a short interval.  This method
	 * should be called by doSort() whenever an element of array[] is
	 * moved or swapped.  The length of time to pause is determined by
	 * the swap_time member (measured in milliseconds).
	 *
	 * @param elt the index of one of the elements affected
	 * @see ShowSort#compared
	 */
	void swapped(int elt) {
		current = elt;
		repaint();
		try {
			Thread.sleep(swap_time);
		} catch (InterruptedException e) {
			repaint();
		}
	}
	
}