/*
 * Instituto Superior de Engenharia do Porto
 *
 * Estruturas de Informação
 *
 * 2000/2001
 *
 * (C) Paulo Sousa
 *
 * ------------------------------------------
 *
 * Trabalho nº 1
 *
 *	algoritmo Jsort
 *
 */


#ifndef __JSORT_INC__
#define __JSORT_INC__


template <class T>
class JSort
{
	static void reheap(T A[], int length, int i);
	static void invreheap(T A[], int length, int i); 

public:
	static void jsort_1(T A[], int nSize);
};



//----------------------------------------------------------
//
//				I M P L E M E N T A Ç Ã O
//
//----------------------------------------------------------



/**
 * A JSort Demonstration algorithm.  The JSort algorithm is due to
 * Jason Morrison <http://www.scs.carleton.ca/~morrison>
 *	 
 * JSortAlgorithm.java
 *
 * @author Patrick Morin
 */
template <class T>
void JSort<T>::jsort_1(T A[], int nSize)
{
	if (nSize < 2)
		return;

	/**
	* Sort the input using the heap sort algorithm.
	*/

	// Heapify bottom up
	for (int i = nSize-1; i >= 0; i--)
		reheap (A, nSize, i);

	// Heapify top down
	for (i = nSize-1; i >= 0; i--)
		invreheap (A, nSize, i);

	// Do an insertion sort on the almost sorted array
	for (int j = 1; j < nSize; j++) 
	{
		T temp = A[j];
		int i = j - 1;
		while (i >= 0 && A[i] > temp) 
		{
			A[i+1] = A[i];
			i -= 1;
		}
		A[i+1] = temp;
	}
}


/**
 * Make the sub-array starting at position i into a a heap,
 * assuming that it's left and right children are already 
 * heaps.
 */
template <class T>
void JSort<T>::reheap(T A[], int length, int i) 
{
	bool done = false;
	T temp = A[i];
	int parent = i;
	int child = 2*(i+1)-1;
	while ((child < length) && (!done)) 
	{
		if (child < length - 1) 
		{
			if (A[child] >= A[child + 1]) 
			{
				child++;
			}
		}
		if (temp < A[child]) 
			done = true;
		else 
		{
			A[parent] = A[child];
			parent = child;
			child = 2*(parent+1)-1;
		}
	}
	A[parent] = temp;
}

/**
 * Make the sub-array starting at position length-i into a a heap,
 * assuming that it's left and right children are already 
 * heaps.
 */
template <class T>
void JSort<T>::invreheap(T A[], int length, int i) 
{
	bool done = false;
	T temp = A[length - 1 - i];		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
	int parent = i;
	int child = 2*(i+1)-1;
	while ((child < length) && (!done)) 
	{
		if (child < length - 1) 
		{
			TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			if (A[length - 1 - child] <= A[length - 1 - (child + 1)]) 
				child++;
		}
		TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
		if (temp > A[length - 1 - child]) 
			done = true;
		else 
		{
			A[length - 1 - parent] = A[length - 1 - child];	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
			parent = child;
			child = 2*(parent+1)-1;
		}
	}
	A[length - 1 - parent] = temp;	TEST_SMALL_DELAY	// teste a vectores de dimensão reduzida
}


#endif