import java.awt.*;
import java.applet.*;
import java.util.Date;
import java.util.Random;

public class MicrosoftColorSort extends Applet {
	java.awt.Button sort;
	java.awt.Button reset;
	Ball[] balls;
	int[] colors;
	boolean[] isColorUsed;
	int totalColors = 10;
	int totalBalls = 600;
	int xs[];
	int ys[];

	public void init() {
		setBackground(Color.WHITE);
		add(reset = new java.awt.Button("Reset"));
		add(sort = new java.awt.Button("Sort"));
	}

	public boolean handleEvent(Event event) {
		if (event.target == sort && event.id == Event.ACTION_EVENT) {
			doSort(event);
			return true;
		}
		
		if (event.target == reset && event.id == Event.ACTION_EVENT) {
			doReset(event);
			return true;
		}

		return super.handleEvent(event);
	}
	
	public void paint(Graphics g) {
		drawString("Usage: Click Reset, then Sort", 10, 20);
	}

	/**
	 * @param event
	 */
	private void doReset(Event event) {
		int x = 10;
		int y = 10;
		int xOffset = 20;
		int yOffset = 20;
		colors = new int[totalColors];
		isColorUsed = new boolean[totalColors];

		this.getGraphics().clearRect(0, 30, this.getWidth(), this.getHeight());
		
		// Assume ith color to be the int value of 'i'
		for (int i = 0; i < totalColors; i++) {
			colors[i] = i;
		}

		// Initialize ball colors using java.util.Random class 
		// to randomly assign colors to balls - Good enough for testing
		int theColor = 0;
		balls = new Ball[totalBalls];
		xs = new int[totalBalls];
		ys = new int[totalBalls];
		
		for (int i = 0; i < totalBalls; i++) {
			x += xOffset;
			
			// Display rows of 25
			if ((i % 25) == 0) {
				y += yOffset;
				x = 10;
			}
			
			theColor = new Random(new Date().getTime()).nextInt(1000000) % totalColors;
			balls[i] = new Ball(theColor);
			xs[i] = x;
			ys[i] = y;
			
			// We need to keep track of which colors are actually assigned.
			// I.e. We can't assume all colors will be used - our random generator 
			// doesn't assure us all colors will be used. 
			if (!isColorUsed[theColor]) {
				isColorUsed[theColor] = true;
			}
			
			// Let random generator breath
			try {
				Thread.sleep(10);
			} catch (Exception e) {
				// Empty
			}
			
			balls[i].draw(xs[i], ys[i], this.getGraphics());
		}
	}
	
	private void drawString(String message, int x, int y) {
		this.getGraphics().setColor(Color.black);
		this.getGraphics().drawString(message, x, y);
	}

	/**
	 * @param balls
	 */
	private void drawBalls() {
		this.getGraphics().clearRect(0, 30, 20 * 25, this.getHeight());
		for (int i = 0; i<totalBalls; i++) {
			balls[i].draw(xs[i], ys[i], this.getGraphics());
		}
		
	}

	void doSort(Event event) {
		int start = 0;
		int yOffset = 40;
		int x = 540;
		drawString("Start indices", 540, yOffset);
		Ball displayBall = null;
		for (int i = 0; i < totalColors; i++) {
			if (isColorUsed[i]) {
				displayBall = new Ball(i);
				// Note that the beginning of the first color is the trivial case of 0
				displayBall.draw(x, (i + 2) * yOffset, this.getGraphics());
				drawString(" - " + ((i == 0) ? 0: start), x + 22, ((i + 2) * yOffset) + 15 );

				start = partition(balls, colors[i], start);
				
				drawBalls();
				
				try {
					Thread.sleep(1000);
				} catch (Exception e) {
					// Empty
				}				
			}
		}		
	}
	
	/**
	 * In-line color sort array of Ball objects into 2 groups of Ball(s), putting Balls of 
	 * sortingColor at the front.
	 * <br>
	 * <br>
	 * Algorithm: 
	 * Compare both ends of the array by color and 
	 * increment ith and decrement jth location according the rules below.
	 * <pre>
	 * Let i, be the beginning of the array to sort.
	 * Let j, be the end of the array to sort.
	 * 
	 * WHILE (ith location < jth location)
	 * 		IF (ith color == sorting color) && (jth color == sorting color)
	 * 			increment ith location by one
	 * 		ELSE IF (ithColor == sorting color) && (jth color != sorting color)
	 * 			increment ith location by one
	 * 		ELSE IF (ith color != sorting color) && (jth color != sorting color)
	 * 			decrement jth location by one
	 * 		ELSE IF (ith color != sorting color) && (jth color == sorting color)
	 * 			swaped balls -> ith balls to jth location, and jth ball to ith location
	 * 			increment ith location by one
	 * 			decrement jth location by one
	 * 		FI
	 * ELIHW
	 * </pre>		
	 * <br>
	 * Analysis: Since the we are itariting from the front to the back and from the back to the front,
	 * until the ith and jth location meet, and if we have an array of size n, we have worst 
	 * run time of O(n) for sorting balls of int two groups, with sortingColor as the first group.
	 * <br>
	 * <br>
	 * @param balls Ball[]
	 * @param sortingColor int - Which color to sort by
	 * @param startIndex int - Start sorting from this index
	 * @return int Array index of second group of colors
	 */
	public int partition(Ball[] balls, int sortingColor, int startIndex) {
		int i = startIndex;
		int j = balls.length - 1;
		int ithColor = 0;
		int jthColor = 0;
		Ball tmpBall = null;

		while (i <= j) {
			ithColor = balls[i].getBallColor();
			jthColor = balls[j].getBallColor();

			if ((ithColor == sortingColor) && (jthColor == sortingColor)) {
				i++;
			} else if ((ithColor == sortingColor) && (jthColor != sortingColor)) {
				i++;
			} else if ((ithColor != sortingColor) && (jthColor != sortingColor)) {
				j--;
			} else if ((ithColor != sortingColor) && (jthColor == sortingColor)) {
				tmpBall = balls[i];				
				balls[i] = balls[j];				
				balls[j] = tmpBall;

				i++;
				j--;
			}
		}
		
		return i;
	}
}

/**
 * 
 * <b>Ball </b> <br>
 * <br>
 * Ball definition. <br>
 * <br>
 * 
 * @author Jose Sandoval - jose@josesandoval.com - http://www.josesandoval.com/
 * @version Jan 15, 2005
 */

class Ball {
	private Color ballColor;

	private int colorIndex;

	public Ball(int colorIndex) {
		switch (colorIndex) {
		case 0:
			ballColor = Color.black;
			break;

		case 1:
			ballColor = Color.blue;
			break;

		case 2:
			ballColor = Color.cyan;
			break;

		case 3:
			ballColor = Color.lightGray;
			break;

		case 4:
			ballColor = Color.green;
			break;

		case 5:
			ballColor = Color.magenta;
			break;

		case 6:
			ballColor = Color.orange;
			break;

		case 7:
			ballColor = Color.pink;
			break;

		case 8:
			ballColor = Color.red;
			break;

		case 9:
			ballColor = Color.yellow;
			break;
		}

		this.colorIndex = colorIndex;
	}

	public int getBallColor() {
		return colorIndex;
	}

	public void draw(int x, int y, Graphics g) {
		g.setColor(ballColor);
		g.fillOval(x, y, 20, 20);
		g.setColor(Color.white);
		g.drawString("" + colorIndex, x + 7, y + 14);
	}
}