/*

 * Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). 

 * All rights reserved.

 * This component and the accompanying materials are made available

 * under the terms of the License "Eclipse Public License v1.0"

 * which accompanies this distribution, and is available

 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

 *

 * Initial Contributors:

 * Nokia Corporation - initial contribution.

 *

 * Contributors:

 *

 * Description: 

 *

 */

package com.nokia.carbide.cpp.internal.pi.utils;

import java.util.Stack;

import java.util.Vector;

public class QuickSortImpl

{

	public static void sort(Sortable[] array)

	{

		quickSort(array,0,array.length-1);

	}

	public static void sort(Vector sortables)

	{

		Sortable[] s = new Sortable[sortables.size()];

		s = (Sortable[])sortables.toArray(s);

		sort(s);

		sortables.clear();

		for (int i=0;i<s.length;i++)

		{

			sortables.add(s[i]);

		}

	}

	public static void sortReversed(Vector sortables)

	{

		Sortable[] s = new Sortable[sortables.size()];

		s = (Sortable[])sortables.toArray(s);

		sort(s);

		sortables.clear();

		for (int i=(s.length-1);i>=0;i--)

		{

			sortables.add(s[i]);

		}

	}

	public static void quickSort(Sortable[] a,int low, int high)

	{

		Stack stack = new Stack();

		//System.out.println("QS both sides "+low+" "+high);

		int pivot;

		/* Termination condition! */

		if ( high > low )

		{

			while(high > low)

			{

				pivot = partition( a, low, high );

				//System.out.println("QS left side is "+low+"-"+pivot+" right side is "+pivot+"-"+high);

				//quickSort( a, low, pivot-1 );

				stack.push(new Integer(pivot+1));

				stack.push(new Integer(high));

				//System.out.println("Pushed right side");

				high = pivot-1;

			}				

			while(!stack.isEmpty())

			{

				high = ((Integer)stack.pop()).intValue();

				low = ((Integer)stack.pop()).intValue();

				//System.out.println("Popping right side "+low+"-"+high);

				quickSort( a, low, high );

			}

		}

	}

	public static int partition(Sortable[] a,int low,int high)

	{

		int left, right;

		int pivot;

		pivot = left = low;

		right = high;

		long pivotValue = a[pivot].valueOf();

		Sortable pivotItem = a[pivot];

		while ( left < right ) 

		{

			// Move left while item < pivot 

				//System.out.println("Starting left "+left);

				while(a[left].valueOf() <= pivotValue ) 

				{

					//System.out.println(valueOf(a[left])+" < "+pivotValue);

					left++;

					//System.out.println("left ="+left);

					if (left == a.length)

						break;

				}

				//System.out.println("Final left = "+left);

			// Move right while item > pivot

			while( a[right].valueOf() > pivotValue ) 

			{

				right--;

				//System.out.println("right ="+right);

			}

			if ( left < right )

			{

				//System.out.println("Swapping "+left+" and "+right);

				Sortable tmp = a[left];

				a[left] = a[right];

				a[right] = tmp;

				//SWAP(a,left,right);

			}

		}

		// right is final position for the pivot

		a[low] = a[right];

		a[right] = pivotItem;

		//System.out.println("Pivot is now "+right+" pivot value "+valueOf(a[right]));

		return right;

	}

}