//---------------------------------
// RadixSort.Java
// Written By: Russell Schwager
//             russells@jhu.edu
// February 4, 1997
//---------------------------------

// Insert Copyright comments

//------------------ BEGIN UI CODE ----------------
import java.awt.Graphics;
import java.awt.Color;
//------------------ END UI CODE ------------------

// Radix Sort algorithm

public class RadixSort extends SortAlgorithm 
{											

	//---------BEGIN UI CODE----------------------
	SortPanel panel;
	int currentDigit;

	public RadixSort(SortableObject anObject, SortPanel panel)
	{ // Constructor

		super(anObject);
		algorithmName = "Radix-Sort";
		this.panel = panel;
		currentDigit = -1;
	}
	//---------END UI CODE----------------------

	public RadixSort(SortableObject anObject)
	{ // Constructor

		super(anObject);
		algorithmName = "Radix-Sort";
	}

	public RadixSort()
	{ // Default Constructor

		super();
		algorithmName = "Radix-Sort";
	}

	public void sort()
	{
		if (!objectToSort.getStatus())
		{
			sort(objectToSort, objectToSort.numDigits());
			objectToSort.setStatus(true);
		}
	}

	
	private void sort(SortableObject anObject, int numDigits)
	{ // Perform a stable sort on each of the digits.
	
		for (int i = numDigits - 1; i >= 0; i--)
		{
			countingSort(anObject, i, 26);
		}
	}

	//----------------------BEGIN UI CODE------------
	public void demoSort() throws Exception
	{


		if (!objectToSort.getStatus() && currentDigit == -1)
		{
			currentDigit = objectToSort.numDigits() - 1;
			while (!objectToSort.getStatus())
			{
				countingSort(objectToSort, currentDigit--, 26);

				if (currentDigit == -1)
					objectToSort.setStatus(true);
				panel.pause();
			}
		}
	}

	public void drawMiscInfo(Graphics g)
	{ // paints info about the sort
		
		// Draw Sort Method
		g.setColor(Color.blue);
		g.drawString("Notes: ", 215, 175);

		g.setColor(Color.red);
		g.drawString("Works with strings only.", 215, 190);

		g.setColor(Color.blue);
		g.drawString("Description: ", 400, 25);

		g.setColor(Color.red);
		g.drawString("Radix sort works by ", 400, 40); 
		g.drawString("iteratively sorting each ", 400, 55);
		g.drawString("digit in the collection from ", 400, 70);
		g.drawString("least significant to most", 400, 85);
		g.drawString("significant using a stable sort.", 400, 100);

		g.setColor(Color.blue);
		g.drawString("Current Digit", 450, 200);
		
		g.setColor(Color.gray);
		g.drawLine(445, 200, 420, 200);
		g.drawLine(420, 200, 420, 195);

		int x[] = { 416, 420, 424 };
		int y[] = { 195, 191, 195 };
		g.fillPolygon(x, y, 3);

	}

	public void init()
	{
		objectToSort.setStatus(false);

	}

	//-------------------END UI CODE------------------

	private void countingSort(SortableObject anObject, int digit,
		int digitRange)
	{ // Radix sort requires a stable sort as part of the algorithm
	  // so counting-sort is used.  This sort algorithm could be
	  // made into a class like radix sort but was made into a method
	  // because it has been modified to be used with SortableObject
	  // to sort on specific digits.

		Object newArray[] = new Object[anObject.size()];
		int count[] = new int[digitRange];

		for (int i = 0; i < digitRange; i++)
			count[i] = 0;

		for (int i = 0; i < anObject.size(); i++)
		{
			char newChar = ((String)anObject.at(i)).charAt(digit);
			count[getIndex(newChar)]++;
		}

		for (int i = 1; i < digitRange; i++)
		{
			count[i] += count[i - 1];
		}

		for (int i = anObject.size() - 1; i >= 0; i--)
		{
			char newChar = ((String)anObject.at(i)).charAt(digit);
			int position = count[getIndex(newChar)] - 1;
			if (position < 0)
				position = 0;
			newArray[position] = anObject.at(i);
			count[getIndex(newChar)]--;
		}

		for (int i = 0; i < anObject.size(); i++)
			anObject.setElementAt(newArray[i], i);

	}

	private int getIndex(char letter)
	{ // Returns the index of the character within the alphabet
	  // a=0, b=1, ... z=25
	
		return letter - 'a';
	}
}