//---------------------------------
// QuickSort.Java
// Written By: Russell Schwager
//             russells@jhu.edu
// January 29, 1997
//---------------------------------

// Insert Copyright comments
//------------------ BEGIN UI CODE ----------------
import java.awt.Graphics;
//------------------ END UI CODE ------------------

// Quick Sort algorithm

public class QuickSort extends SortAlgorithm
{											
	//---------BEGIN UI CODE----------------------
	SortPanel panel;
	
	public QuickSort(SortableObject anObject, SortPanel panel)
	{ // Constructor

		super(anObject);
		algorithmName = "Quick-Sort";
		this.panel = panel;
	}

	public void demoSort() throws Exception
	{
		if (!objectToSort.getStatus())
		{
			demoSort(objectToSort, 0, objectToSort.size() - 1);
			objectToSort.setStatus(true);
		}
	}

	private void demoSort(SortableObject anObject, 
		int from, int to) throws Exception
	{
		
		int mid;

		if (from < to)
		{
			panel.pause();
			mid = demoPartition(anObject, from, to);
			demoSort(anObject, from, mid);
			demoSort(anObject, mid + 1, to);
		}
	}

	private int demoPartition(SortableObject anObject, 
		int from, int to)
	{

		int i = from - 1;
		int j = to + 1;

		while (true)
		{

			// SortableObject.compare(int, int) returns max
			// of the two elements indexed by the parameters
			while (anObject.compare(from, --j) != anObject.at(from));
				
			while (anObject.compare(from, ++i) != anObject.at(i));
			
			if (i < j)
			{
				anObject.swap(i, j);
				panel.pause();
			}
			else
				return j;
		}

	}

	public void drawMiscInfo(Graphics g)
	{
		// Do nothing for now
		int i = 5;
	}

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

	}

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

	public QuickSort(SortableObject anObject)
	{ // Constructor

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

	public QuickSort()
	{ // Default Constructor

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


	public void sort()
	{
		if (!objectToSort.getStatus())
		{
			sort(objectToSort, 0, objectToSort.size() - 1);
			objectToSort.setStatus(true);
		}
	}

	
	private void sort(SortableObject anObject, 
		int from, int to)
	{
		
		int mid;

		if (from < to)
		{
			mid = partition(anObject, from, to);
			sort(anObject, from, mid);
			sort(anObject, mid + 1, to);
		}
	}

	private int partition(SortableObject anObject, 
		int from, int to)
	{

		int i = from - 1;
		int j = to + 1;

		while (true)
		{

			// SortableObject.compare(int, int) returns max
			// of the two elements indexed by the parameters
			while (anObject.compare(from, --j) != anObject.at(from));
				
			while (anObject.compare(from, ++i) != anObject.at(i));
				
			if (i < j)
				anObject.swap(i, j);
			else
				return j;
		}

	}
}