package edu.vt.marian.common;

import java.util.*;
import java.io.*;

import edu.vt.marian.common.*;

/**
 * A quicksort object which can be used to sort the elements of
 * an enumeration in either non-increasing or non-decreasing order.
 * The only requirement is that each element of the object being
 * sorted implements the Sortable interface.  Basically, this means
 * an object provides a compare() method which can be used to
 * determine whether one object is less than, equal to, or greater
 * than another object.
 *
 * @author Paul Mather
 * @version 0.9
 */
public class QuickSort
{
    /**
     * Vector holding the elements of the object being sorted
     * whilst they are sorted in-place.
     */
    protected Vector objects;

    /**
     * Flag to indicate whether we are performing a non-decreasing
     * sort (true) or a non-increasing sort (false)
     */
    protected boolean sortIncreasing;

    /**
     * Make a new object to quicksort the supplied enumeration.
     * The constructor copies the elements of the enumeration to
     * a local vector, so they can be sorted in-place.
     * It also keeps track of the desired type of sort
     * (non-increasing or non-decreasing).
     * @param elts the enumeration to be sorted
     * @param sortType the type of order in which to sort:
     * Sortable.INCREASING or Sortable.DESCREASING.
     * @see edu.vt.marian.common.Sortable
     * @see java.util.Vector
     * @see java.util.Enumeration
     */
    public QuickSort(Enumeration elts, int sortType)
    {
	// Check the sort type is valid; default to non-increasing if not
	if (sortType == Sortable.INCREASING)
	    sortIncreasing = true;
	else
	{
	    if (sortType == Sortable.DECREASING)
		sortIncreasing = false;
	    else
		// Default to non-increasing if not valid
		sortIncreasing = true;
	}
	objects = new Vector();
	// Copy elements from enumeration to local vector for
	// sorting in-place
	while( elts.hasMoreElements() )
	{
	    objects.addElement( elts.nextElement() );
	}
    }

    /**
     * Return an enumeration containing the elements contained in
     * this object in sorted order.  Basically, this method simply
     * invokes quicksort on the local vector, and then returns
     * an enumeration of the objects in that vector after quicksort
     * has sorted them.
     * @return an enumeration of the sorted objects
     * @see java.util.Vector#elements
     */
    public Enumeration elements()
    {
	// Perform quicksort on local vector
	quicksort(0, objects.size()-1);
	// Return an enumeration of the now-sorted vector
	return objects.elements();
    }

    /**
     * Perform a comparison relative to the type of sort being
     * undertaken.  Think of this as doing "lhs compareOp rhs"
     * where lhs and rhs are objects being sorted, and compareOp
     * is a comparison operator based upon the order in which
     * the items are being ranked.  This compareOp will always
     * be either <= or >=.
     * @param lhs the left hand side of the two items being compared
     * @param rhs the right hand side of the two items being compared
     * @return true if lhs <= rhs and we are doing a Sortable.INCREASING
     * sort; true if lhs >= rhs and we are doing a Sortable.DECREASING
     * sort; false otherwise.
     */
    private boolean comparison(Sortable lhs, Sortable rhs)
    {
	int compareResult = lhs.compare(rhs);

	if (compareResult == Sortable.INCOMPARABLE)
	{
	    System.out.println("comparison() returned INCOMPARABLE!");
	    return false;
	}

    	if (compareResult == Sortable.EQUAL)
    	    return true;
	if (sortIncreasing)
	    return (compareResult == Sortable.LESS);
	else
	    return (compareResult == Sortable.GREATER);
    }

    /**
     * The classic quicksort algorithm.  This version is implemented
     * from pseudocode provided in Cormen, Lieserson, and Rivest,
     * _Introduction to Algorithms_, Chapter 8: Quicksort, p. 154.
     * @param start the start of the portion of the vector to be sorted
     * @param end the end of the portion of the vector to be sorted
     */
    protected void quicksort(int start, int end)
    {
	if (start < end)
	{
	    int pivot = partition(start, end);
	    quicksort(start, pivot);
	    quicksort(pivot+1, end);
	}
    }

    /**
     * The partitioning phase of the classic quicksort algorithm.
     * This version is implemented from pseudocode provided in
     * Cormen, Lieserson, and Rivest, _Introduction to Algorithms_,
     * Chapter 8: Quicksort, p. 154.
     * <P>
     * Partition chooses an element from the portion of the vector
     * being partitioned and then swaps elements such that
     * all elements in the vector portion to the left of the
     * partition value (pivot) are <= the pivot value, and all
     * those to the right of the pivot are >= the pivot.  (This
     * is when sorting into non-decreasing order; vice versa
     * for non-increasing order.)
     * @param start the start of the portion of the vector to be
     * partitioned
     * @param end the end of the portion of the vector to be
     * partitioned
     * @return the position in the vector portion at which the
     * partition pivot point lies
     */
    private int partition(int start, int end)
    {
	Object pivot = objects.elementAt( start );
	Object temp;

	start--;
	end++;
	while(true)
	{
	    do
		end--;
	    while(!comparison((Sortable)objects.elementAt(end),(Sortable)pivot));
	    do
		start++;
	    while(!comparison((Sortable)pivot,(Sortable)objects.elementAt(start)));
	    if (start < end)
	    {
		// Exchange elements objects[i] and objects[j]
		temp = objects.elementAt(start);
		objects.setElementAt(objects.elementAt(end), start);
		objects.setElementAt(temp, end);
	    }
	    else
		break;
	}

	return end;
    }
}