/*
 * Sort.cpp
 *
 *  Created on: 03/05/2009
 *      Author: derzu
 */

#include "sort.h"
#include <string.h>
#include <map>
#include <vector>

using namespace std;

namespace Util {

Sort::Sort() {
}

Sort::~Sort() {
}

void Sort::quickSort(double array[], int length)
{
	quickSort(array, length, 0, length - 1);              // quicksort all the elements in the array
}

void Sort::quickSort(double array[], int length, int start, int end) {
	int i = start;                          // index of left-to-right scan
	int k = end;                            // index of right-to-left scan

	if (length==0)
		return;

	if (end - start >= 1) // check that there are at least two elements to sort
	{
		double pivot = array[start];       // set the pivot as the first element in the partition

		while (k > i) // while the scan indices from left and right have not met,
		{
			while (array[i] <= pivot && i <= end && k > i) // from the left, look for the first
				i++;
				// element greater than the pivot
			while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
				k--;
                // element not greater than the pivot
			if (k > i) // if the left seekindex is still smaller than
				swap(array, i, k);
				// the right index, swap the corresponding elements
		}

		swap(array, start, k);          // after the indices have crossed, swap the last element in
		// the left partition with the pivot
		quickSort(array, length, start, k - 1); // quicksort the left partition
		quickSort(array, length, k + 1, end);   // quicksort the right partition
	}
	else // if there is only one element in the partition, do not do any sorting
		return; // the array is sorted, so exit
}

/*void Sort::quickSort(int array[], int length)
{
	quickSort(array, length, 0, length - 1);              // quicksort all the elements in the array
}

void Sort::quickSort(int array[], int length, int start, int end) {
	int i = start;                          // index of left-to-right scan
	int k = end;                            // index of right-to-left scan

	if (length==0)
		return;

	if (end - start >= 1) // check that there are at least two elements to sort
	{
		int pivot = array[start];       // set the pivot as the first element in the partition

		while (k > i) // while the scan indices from left and right have not met,
		{
			while (array[i] <= pivot && i <= end && k > i) // from the left, look for the first
				i++;
				// element greater than the pivot
			while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
				k--;
                // element not greater than the pivot
			if (k > i) // if the left seekindex is still smaller than
				swap(array, i, k);
				// the right index, swap the corresponding elements
		}

		swap(array, start, k);          // after the indices have crossed, swap the last element in
		// the left partition with the pivot
		quickSort(array, length, start, k - 1); // quicksort the left partition
		quickSort(array, length, k + 1, end);   // quicksort the right partition
	}
	else // if there is only one element in the partition, do not do any sorting
		return; // the array is sorted, so exit
}*/


void Sort::quickSort(char * array[], int length)
{
	quickSort(array, length, 0, length - 1);              // quicksort all the elements in the array
}

void Sort::quickSort(char * array[], int length, int start, int end) {
	int i = start;                          // index of left-to-right scan
	int k = end;                            // index of right-to-left scan

	if (length==0)
		return;

	if (end - start >= 1) // check that there are at least two elements to sort
	{
		char * pivot = array[start];       // set the pivot as the first element in the partition

		while (k > i) // while the scan indices from left and right have not met,
		{
			//while (array[i] <= pivot && i <= end && k > i) // from the left, look for the first
			while ((strcasecmp(array[i], pivot)<=0) && i <= end && k > i) // from the left, look for the first
				i++;
				// element greater than the pivot
			//while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
			while ((strcasecmp(array[k], pivot)>0) && k >= start && k >= i) // from the right, look for the first
				k--;
                // element not greater than the pivot
			if (k > i) // if the left seekindex is still smaller than
				swap(array, i, k);
				// the right index, swap the corresponding elements
		}

		swap(array, start, k);          // after the indices have crossed, swap the last element in
		// the left partition with the pivot
		quickSort(array, length, start, k - 1); // quicksort the left partition
		quickSort(array, length, k + 1, end);   // quicksort the right partition
	}
	else // if there is only one element in the partition, do not do any sorting
		return; // the array is sorted, so exit
}


    void Sort::quickSort(vector<Dicionario::DicNode*> * array, bool ignore) // pre: array is full, all elements are non-null integers
    // post: the array is sorted in ascending order
    {
        quickSort(array, 0, (int)array->size() - 1, ignore);              // quicksort all the elements in the array
    }

    void Sort::quickSort(vector<Dicionario::DicNode*> * array, int start, int end, bool ignore) {
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start >= 1) // check that there are at least two elements to sort
        {
            char * pivot = (*array)[start]->palavra;       // set the pivot as the first element in the partition

            if (ignore) {
                while (k > i) // while the scan indices from left and right have not met,
                {
                    //while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                    while (strcasecmp((*array)[i]->palavra, pivot) <= 0 && i <= end && k > i) // from the left, look for the first
                    {
                        i++;
                    }                                    // element greater than the pivot
                    //while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                    while (strcasecmp((*array)[k]->palavra, pivot) > 0 && k >= start && k >= i) // from the right, look for the first
                    {
                        k--;
                    }                                        // element not greater than the pivot
                    if (k > i) // if the left seekindex is still smaller than
                    {
                        swap(array, i, k);
                    }                      // the right index, swap the corresponding elements
                }
            } else {
                while (k > i) // while the scan indices from left and right have not met,
                {
                    //while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                    while (strcmp((*array)[i]->palavra, pivot) <= 0 && i <= end && k > i) // from the left, look for the first
                    {
                        i++;
                    }                                    // element greater than the pivot
                    //while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                    while (strcmp((*array)[k]->palavra, pivot) > 0 && k >= start && k >= i) // from the right, look for the first
                    {
                        k--;
                    }                                        // element not greater than the pivot
                    if (k > i) // if the left seekindex is still smaller than
                    {
                        swap(array, i, k);
                    }                      // the right index, swap the corresponding elements
                }
            }
            swap(array, start, k);          // after the indices have crossed, swap the last element in
            // the left partition with the pivot
            quickSort(array, start, k - 1, ignore); // quicksort the left partition
            quickSort(array, k + 1, end, ignore);   // quicksort the right partition
        } else // if there is only one element in the partition, do not do any sorting
        {
            return;                     // the array is sorted, so exit
        }
    }


    void Sort::quickSort2(vector<pair<string, int> > * array, bool ignore) // pre: array is full, all elements are non-null integers
    // post: the array is sorted in ascending order
    {
        quickSort2(array, 0, (int)array->size() - 1, ignore);              // quicksort all the elements in the array
    }

    void Sort::quickSort2(vector<pair<string, int> > * array, int start, int end, bool ignore) {
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start >= 1) // check that there are at least two elements to sort
        {
            const char * pivot = (*array)[start].first.c_str();       // set the pivot as the first element in the partition

            if (ignore) {
                while (k > i) // while the scan indices from left and right have not met,
                {
                    //while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                    while (strcasecmp((*array)[i].first.c_str(), pivot) <= 0 && i <= end && k > i) // from the left, look for the first
                    {
                        i++;
                    }                                    // element greater than the pivot
                    //while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                    while (strcasecmp((*array)[k].first.c_str(), pivot) > 0 && k >= start && k >= i) // from the right, look for the first
                    {
                        k--;
                    }                                        // element not greater than the pivot
                    if (k > i) // if the left seekindex is still smaller than
                    {
                        swap2(array, i, k);
                    }                      // the right index, swap the corresponding elements
                }
            } else {
                while (k > i) // while the scan indices from left and right have not met,
                {
                    //while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                    while (strcmp((*array)[i].first.c_str(), pivot) <= 0 && i <= end && k > i) // from the left, look for the first
                    {
                        i++;
                    }                                    // element greater than the pivot
                    //while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                    while (strcmp((*array)[k].first.c_str(), pivot) > 0 && k >= start && k >= i) // from the right, look for the first
                    {
                        k--;
                    }                                        // element not greater than the pivot
                    if (k > i) // if the left seekindex is still smaller than
                    {
                        swap2(array, i, k);
                    }                      // the right index, swap the corresponding elements
                }
            }
            swap2(array, start, k);          // after the indices have crossed, swap the last element in
            // the left partition with the pivot
            quickSort2(array, start, k - 1, ignore); // quicksort the left partition
            quickSort2(array, k + 1, end, ignore);   // quicksort the right partition
        } else // if there is only one element in the partition, do not do any sorting
        {
            return;                     // the array is sorted, so exit
        }
    }

/*void Sort::quickSort(map< string, int > * array)
{
	quickSort(array, array->size(), 0, array->size() - 1);              // quicksort all the elements in the array
}

void Sort::quickSort(map< string, int > * array, int length, int start, int end) {
	int i = start;                          // index of left-to-right scan
	int k = end;                            // index of right-to-left scan

	if (length==0)
		return;

	if (end - start >= 1) // check that there are at least two elements to sort
	{
		map<string, int> pivot = (*array)[start];       // set the pivot as the first element in the partition

		while (k > i) // while the scan indices from left and right have not met,
		{
			while ((*array)[i] <= pivot && i <= end && k > i) // from the left, look for the first
				i++;
				// element greater than the pivot
			while ((*array)[k] > pivot && k >= start && k >= i) // from the right, look for the first
				k--;
                // element not greater than the pivot
			if (k > i) // if the left seekindex is still smaller than
				swap(array, i, k);
				// the right index, swap the corresponding elements
		}

		swap(array, start, k);          // after the indices have crossed, swap the last element in
		// the left partition with the pivot
		quickSort(array, length, start, k - 1); // quicksort the left partition
		quickSort(array, length, k + 1, end);   // quicksort the right partition
	}
	else // if there is only one element in the partition, do not do any sorting
		return; // the array is sorted, so exit
}*/




/**
 * the values at indices 1 and 2 have been swapped
 *
 * @param array
 * @param index1
 * @param index2
 */
void Sort::swap(double array[], int index1, int index2)
{
	double temp = array[index1];           // store the first value in a temp
	array[index1] = array[index2];      // copy the value of the second into the first
	array[index2] = temp;               // copy the value of the temp into the second
}

/*void Sort::swap(int array[], int index1, int index2)
{
	int temp = array[index1];           // store the first value in a temp
	array[index1] = array[index2];      // copy the value of the second into the first
	array[index2] = temp;               // copy the value of the temp into the second
}*/

void Sort::swap(char * array[], int index1, int index2)
{
	char * temp = array[index1];           // store the first value in a temp
	array[index1] = array[index2];      // copy the value of the second into the first
	array[index2] = temp;               // copy the value of the temp into the second
}

void Sort::swap(vector<Dicionario::DicNode*> * array, int index1, int index2) // pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
    Dicionario::DicNode * temp = (*array)[index1];           // store the first value in a temp
    (*array)[index1] = (*array)[index2];      // copy the value of the second into the first
    (*array)[index2] = temp;               // copy the value of the temp into the second
}


void Sort::swap2(vector<pair<string, int> > * array, int index1, int index2) // pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
    pair<string, int> temp = (*array)[index1]; // store the first value in a temp
    (*array)[index1] = (*array)[index2];       // copy the value of the second into the first
    (*array)[index2] = temp;                   // copy the value of the temp into the second
}

/*void Sort::swap(map< string, int > * array, int index1, int index2)
{
	map temp    = (*array)[index1];   // store the first value in a temp
	(*array)[index1] = (*array)[index2];   // copy the value of the second into the first
	(*array)[index2] = temp;               // copy the value of the temp into the second
}*/




}