import java.awt.Color;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JFrame;


public class QuickSortAnimation extends SortAnimation {
	protected int sorterCount = 0;
	protected boolean reallyStarted;
	protected static boolean parallel = true, medianOf3 = true;

	protected class QuickSorter implements ActionListener {
		protected int i, j, left, right, id;

		protected QuickSorter(int lft, int rght) {
			tick.addActionListener(this);
			id = ++sorterCount;
			right = rght;
			setLeft(lft);
		}

		protected void setLeft(int lft) {
			if (lft < right) {
				i = left = lft;
				j = right;
			} else {
				tick.removeActionListener(this);
				sorterCount--;
				g.setColor(Color.GREEN);
				safeDrawIndices(lft, right);
				g.setColor(Color.YELLOW);
			}
		}

		protected void preparePivot() {
			int center = (right - left) / 2 + left;
			int med;
			if (a[left] < a[center] && a[left] < a[right])
				med = (a[center] < a[right] ? center : right);
			else if (a[left] > a[center] && a[left] > a[right])
				med = (a[center] > a[right] ? center : right);
			else return;
			int temp = a[med];
			a[med] = a[left];
			a[left] = temp;
			drawIndices(left, med);
		}

		protected void moveOn() {
			int temp = a[j];
			a[j] = a[left];
			a[left] = temp;
			g.setColor(Color.GREEN);
			drawIndex(j);
			g.setColor(Color.YELLOW);
			drawIndex(left);
			new QuickSorter(left, j - 1);
			setLeft(j + 1);
		}

		public void actionPerformed(ActionEvent evt) {
			if (!parallel && id < sorterCount) return;
			if (i == left) {
				i++;
				if (medianOf3) preparePivot();
			} else if (i > j) {
				moveOn();
			} else if (a[i] < a[left]) {
				i++;
			} else if (a[j] >= a[left]) {
				j--;
			} else {
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
				drawIndices(i, j);
			}
		}
	}

	public void actionPerformed(ActionEvent evt) {
		if (reallyStarted) {
			if (sorterCount < 1) finish();
		} else {
			reallyStarted = true;
			new QuickSorter(0, a.length - 1);
		}
	}

	public static void main(String... args) {
		JFrame frame = new JFrame("QuickSort animation");
		frame.setSize(400, 300);
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.setContentPane(new QuickSortAnimation());
		frame.setVisible(true);
	}
}