import java.awt.*;
import java.awt.event.*;
import java.awt.image.BufferedImage;
import javax.swing.*;


public abstract class SortAnimation extends JComponent
implements ActionListener, MouseListener {

	protected static java.util.Random rands = new java.util.Random();
	protected int[] a;  // The array to be sorted.

	protected BufferedImage img;
	protected Graphics2D g;
	// Subclasses will use g mostly for changing colors, and
	// will rarely use img at all.

	protected Dimension dims;  // Subclasses shouldn't need this often.

	protected boolean started = false;
	protected Timer tick;
	// These can be useful in parallel algorithms.

	public SortAnimation() {
		super();
		setBackground(new Color(0, 0, 64));
		setForeground(Color.YELLOW);
		tick = new Timer(0, this);
		addMouseListener(this);
		setVisible(true);
		// Subclasses can extend the constructor to choose different
		// background and foreground colors.
	}

	public void paintComponent(Graphics gg) {
		if (!started) {
			dims = getSize();
			img = new BufferedImage(dims.width, dims.height, BufferedImage.TYPE_INT_RGB);
			g = img.createGraphics();
			g.setClip(0, 0, dims.width, dims.height);
			g.setBackground(getBackground());
			g.setColor(getForeground());
			g.clearRect(0, 0, dims.width, dims.height);
			g.setFont(new Font("SansSerif", Font.BOLD, 16));
			g.drawString("Click to start", 40, 50);
		}
		gg.drawImage(img, getX(), getY(), this);
	}

	public void mousePressed(MouseEvent e) {
		// Click to start, pause, or resume the animation.
		if (started) tick.setRepeats(!tick.isRepeats());
		else {
			initArray();
			started = true;
			repaint(getBounds());
		}
		tick.restart();
	}

	public void mouseReleased(MouseEvent e) {}
	public void mouseClicked(MouseEvent e) {}
	public void mouseEntered(MouseEvent e) {}
	public void mouseExited(MouseEvent e) {}

	protected void drawIndex(int n) {
		// Use this method to redraw one index.
		g.clearRect(n, 0, 1, a[n]);
		g.drawLine(n, a[n], n, dims.height);
		repaint(getX() + n, getY(), 1, getHeight());
	}

	protected void safeDrawIndex(int n) {
		/* Attempts to draw an index and returns silently if the index
		is invalid.  Actually, I put this in here mostly for
		consistency with the more useful safeDrawIndexes. */
		try {
			g.clearRect(n, 0, 1, a[n]);
			g.drawLine(n, a[n], n, dims.height);
			repaint(getX() + n, getY(), 1, getHeight());
		} catch (IndexOutOfBoundsException e) {}
	}

	protected void drawIndices(int... indices) {
		// Use this for drawing more than one index.
		for (int n : indices) {
			g.clearRect(n, 0, 1, a[n]);
			g.drawLine(n, a[n], n, dims.height);
			repaint(getX() + n, getY(), 1, getHeight());
		}
	}

	protected void safeDrawIndices(int... indices) {
		/* Draw multiple indices.  If an index is invalid, skip
		it and continue drawing the rest of them. */
		for (int n : indices) {
			try {
				g.clearRect(n, 0, 1, a[n]);
				g.drawLine(n, a[n], n, dims.height);
				repaint(getX() + n, getY(), 1, getHeight());
			} catch (IndexOutOfBoundsException e) {}
		}
	}

	protected void drawIndexRange(int start, int stop) {
		g.clearRect(start, 0, stop - 1, dims.height);
		for (int n = start; n < stop; n++)
			g.drawLine(n, a[n], n, dims.height);
		repaint(getX() + start, getY(), stop - start - 1, dims.height);
	}

	protected void safeDrawIndexRange(int start, int stop) {
		/* Redraw the intersection of a range of indices with the
		boundaries of the array. */
		start = Math.max(start, 0);
		stop = Math.min(stop, a.length);
		g.clearRect(start, 0, stop - 1, dims.height);
		for (int n = start; n < stop; n++)
			g.drawLine(n, a[n], n, dims.height);
		repaint(getX() + start, getY(), stop - start - 1, dims.height);
	}

	protected void initArray() {
		// Most subclasses will not want to call or override this method.
		paintImmediately(getBounds());
		a = new int[dims.width];
		g.clearRect(0, 0, dims.width, dims.height);
		for (int n = 0; n < a.length; n++)
			g.drawLine(n, a[n] = rands.nextInt(dims.height), n, dims.height);
	}

	protected void finish() {
		// Call this method when you are done sorting.
		tick.stop();
		removeMouseListener(this);
		String title = "WIN!", s = "";
		g.setColor(Color.GREEN);
		g.clearRect(0, 0, 1, a[0]);
		g.drawLine(0, a[0], 0, dims.height);
		for (int n = 1; n < a.length; n++) {
			if (a[n - 1] > a[n]) {
				g.setColor(Color.RED);
				g.clearRect(n, 0, 1, a[n]);
				g.drawLine(n, a[n], n, dims.height);
				g.drawLine(0, 0, dims.width, dims.height);
				g.drawLine(0, dims.height, dims.width, 0);
				title = "FAIL!";
				s = " not";
				break;
			}
			g.clearRect(n, 0, 1, a[n]);
			g.drawLine(n, a[n], n, dims.height);
		}
		paintImmediately(getBounds());
		JOptionPane.showMessageDialog(this, new JLabel("Array is" + s + " sorted."), title, JOptionPane.PLAIN_MESSAGE);
	}
}