//	This application demonstrates two simple sorting algorithms
//	(the Bubble and Selection sorts) and displays the data
//	items in graphical form.
//	
//	For selection sort, the sorting process may be animated:
//	Pairs of numbers being compared are hilited in green, pairs of numbers being swaped
//  are hilited in blue, and the sorted portion of the array is hilited in yellow.

import java.awt.*;
import java.awt.event.*;

public class Sortmeister extends Panel implements ActionListener
{
	private final int	SIZE = 15;		// number of data values
	private final int	DATA_MAX = 100;	// largest possible data
	private final long	DELAY = 300;	// ADJUST: delay amount (milliseconds) for animation
	
	private int			data[];			// the data to be sorted
	private TextField	display[];		// to display the data as text
	private Color		backgrounds[];  // the background colors of the text fields for animation
	
	private Button 		reset, sort;
	private Choice		sortChoice;
	private Rectangle	appDim, dataDim;
	
	private Panel		p1, p2;
	
	private	Font f = new Font("Helvetica", Font.BOLD, 10);	// For text fields
		

	
	public Sortmeister() 
	{
		setBackground(Color.white);
		setLayout(new BorderLayout());
		
		// Create the arrays to be the right SIZE
		data = new int[SIZE];
		display = new TextField[SIZE];
		backgrounds = new Color[SIZE];
				
		// Load random values into the data array
		for (int i = 0; i < SIZE; i++)
			data[i] = (int) (Math.random() * DATA_MAX);
			
		p1 = new Panel();
		p1.setLayout(new GridLayout(SIZE,1));
		
		// Create SIZE different text fields and add them to the display panel
		for (int i = 0; i < SIZE; i++) {
			display[i] = new TextField(3);
			display[i].setEditable(false);
			backgrounds[i] = Color.white;
			p1.add(display[i]);
		}
		this.add("West", p1);
		
		p2 = new Panel();
		p2.setBackground(Color.blue);
		reset = new Button("Reset");
		sort = new Button("Sort");
		
		sortChoice = new Choice();
		sortChoice.addItem("Bubble");
		sortChoice.addItem("Selection");
		sortChoice.addItem("Animated Selection");
		
		p2.add(reset);
		p2.add(sort);
		p2.add(sortChoice);
		this.add("South", p2);
		
		reset.addActionListener(this);
		sort.addActionListener(this);
	}
	
	
	public void paint(Graphics g)
	{
		// Determine the approximate height of each 
		// data field to control vertical spacing
		appDim = this.bounds();
		dataDim = p1.bounds();
		int unitY = dataDim.height / SIZE;
		double unitX = (appDim.width - dataDim.width - 10.0) / DATA_MAX;  
		
		for (int i = 0; i < SIZE; i++)
		{
			// Update the i-th display,
			TextField text = display[i];
			text.setBackground(backgrounds[i]);
			text.setForeground(Color.black);
			text.setText("" + data[i]);
			text.setFont(f);
			
			// Erase the old i-th line.
			g.setColor(this.getBackground());
			g.drawLine(dataDim.width + 10,  
						unitY / 2 + i * unitY,
						dataDim.width + 10 + (int)(unitX * DATA_MAX),
						unitY / 2 + i * unitY);
						
			// Draw the new i-th line.
			g.setColor(Color.red);
			g.drawLine(dataDim.width + 10,  
						unitY / 2 + i * unitY,
						dataDim.width + 10 + (int)(unitX * data[i]),
						unitY / 2 + i * unitY);      
		}
	}
	
	
	public void actionPerformed(ActionEvent e)
	{
		if (e.getSource() == reset)
			doReset();
		else if (e.getSource() == sort)
			doSort();
	}
	
	
	private void doReset()
	{
		// Reset all data items to random values (0-100), clear the
		// drawing area, and set the background colors back to white.
		
		for (int i = 0; i < SIZE; i++)
			data[i] = (int) (Math.random() * DATA_MAX);
			
		Graphics g = getGraphics();
		g.clearRect(dataDim.width + 1, 0, 
					appDim.width - dataDim.width - 1,
					appDim.height - dataDim.height);
					
		for (int i = 0; i < SIZE; i++)
			backgrounds[i] = Color.white;

		repaint();
	}


	private void doSort()
	{
		// Call the chosen sorting routine.
		
		String s = sortChoice.getSelectedItem();
		if (s.equals("Selection"))
			selectionSort(data);
		else if (s.equals("Bubble"))
			bubbleSort(data);
		else if (s.equals("Animated Selection"))
			animatedSelectionSort(data);
	}


	private void selectionSort(int[] a)
	{
		for (int i = 0; i < a.length - 1; i++) {
			int minPos = i;
			
			// Find the smallest remaining element.
			for (int j = i + 1; j < a.length; j++) {
				if (a[j] < a[minPos])
					minPos = j;
			}
			
			// Swap current element with the smallest remaining.
			int temp = a[i];                            
			a[i] = a[minPos];
			a[minPos] = temp;
		}
		
		repaint();
	}
	
	
	private void bubbleSort(int[] a)
	{
		for(int i = 0; i < a.length - 1; i++) {
		
			// Let the smallest remaining element bubble to the top
			for(int j = a.length - 1; j > i; j--) {
				if (a[j] < a[j-1]) {
					int tmp = a[j];
					a[j] = a[j-1];
					a[j-1] = tmp;
				}
			}
		}
		
		repaint();
	}
	

	private void animatedSelectionSort(int[] a)
	// Perform a Selection Sort on the argument array.
	{
		for (int i = 0; i < a.length - 1; i++)
		{
			int minPos = i;
			backgrounds[i] = Color.green;
			redrawAndPause();
			
			// Find the smallest remaining element.
			for (int j = i + 1; j < a.length; j++)
			{
				// Highlite the comparison
				backgrounds[j] = Color.green;
				redrawAndPause();
				backgrounds[j] = Color.white;

				// Do the comparison
				if (a[j] < a[minPos]) {
					backgrounds[minPos] = Color.white;
					minPos = j;
					backgrounds[minPos] = Color.green;
				}
				redrawAndPause();
			}
			
			
			// Hilite the swap.
			backgrounds[i] = Color.blue;
			backgrounds[minPos] = Color.blue;
			redrawAndPause();
			
			// Swap current element with the smallest remaining.
			int temp = a[i];                            
			a[i] = a[minPos];
			a[minPos] = temp;
			redrawAndPause();
			
			backgrounds[minPos] = Color.white;
			backgrounds[i] = Color.yellow;
			repaint();
		}
		backgrounds[a.length-1] = Color.yellow;
		repaint();
	}
	
	
	private void redrawAndPause()
	{
		paint(getGraphics());
		long t1 = System.currentTimeMillis();
		long t2 = t1 + DELAY;
		while (t1 < t2)
			t1 = System.currentTimeMillis();
	}
	
	
	public static void main(String[] argv)
	{
		Frame f = new Frame();
		f.add(BorderLayout.CENTER, new Sortmeister());
		f.resize(400,300);
		f.addWindowListener(new WindowCloser());
		f.show();
	}
}

class WindowCloser extends WindowAdapter
{
	public void windowClosing(WindowEvent e)
	{
		System.exit(0);
	}
}