/*****************************
 * Practica 5 MP             *
 * Curso 2008-2009           *
 *                           *
 * Vicente Lujan Mansilla    *
 * Lorena Margareto Bisquert *
 *****************************/

#include "DataGenerator.h"
#include "VElement.h"
#include <vector>
#include <list>
#include <iostream>
#include <fstream>

using namespace std;

const int REP = 100;
DataGenerator dg;

void MergeSort(vector<VElement> &v, int izq, int der);
void mezclar(vector<VElement> &v, int izq, int piv, int der);
void MSvectorDesordenado(int ini, int end, int inc, ostream& salida, float porcentaje);
void test_MS_real(int ini, int end, int inc, ostream& salida);
void particionOrd(vector<VElement> &v, int izq, int der);
void partir(vector<VElement> &v, int izq, int der, int& e, int& d);
void QSvectorDesordenado(int ini, int end, int inc, ostream& salida, float porcentaje);
void test_QS_real(int ini, int end, int inc, ostream& salida);
void Opcional(int ini, int end, int inc, ostream& outComp, ostream& outAsig, float porcentaje);

int main()
{

	ofstream f1, f2, f3, f4, f5, f6, f7, f8;
    
	/*****************
         * MERGE SORT    *
         *****************/
	cout << endl;
	cout << "**********************\n";
	cout << "*Algoritmo MERGE SORT*\n";
	cout << "**********************\n";
	cout << "Ejecutando el test y generando los datos.\n";
	cout << "Espere por favor...\n";
	cout << endl;
	cout << "Aplicando algoritmo MergeSort sobre un vector desordenado en un 100%...\n";

	f1.open("ms_des.dat");	
	MSvectorDesordenado(20, 200, 20, f1, 100);
	f1.close();

	cout << "Aplicando algoritmo MergeSort sobre un vector desordenado en un 10%...\n";
		
	f2.open("ms_quo.dat");	
	MSvectorDesordenado(20, 200, 20, f2, 10);
	f2.close();

	/*****************
         * QUICK SORT    *
         *****************/
	cout << endl;
		cout << endl;
	cout << "**********************\n";
	cout << "*Algoritmo QUICK SORT*\n";
	cout << "**********************\n";
	cout << "Ejecutando el test y generando los datos.\n";
	cout << "Espere por favor...\n";
	cout << endl;
	cout << "Aplicando algoritmo QuickSort sobre un vector desordenado en un 100%...\n";

	f3.open("qs_des.dat");	
	QSvectorDesordenado(20, 200, 20, f3, 100);
	f3.close();

	cout << "Aplicando algoritmo QuickSort sobre un vector desordenado en un 10%...\n";
	cout << endl;

	f4.open("qs_quo.dat");
	QSvectorDesordenado(20, 200, 20, f4, 10);
	f4.close();
	
	cout << "Calculando el coste temporal de QuickSort...\n";
	f5.open("qs_tiempos.dat");
	test_QS_real(20, 200, 20, f5);
	f5.close();
	

	cout << "Calculando el coste temporal de MergeSort...\n";
	f6.open("ms_tiempos.dat");
	test_MS_real(20, 200, 20, f6);
	f6.close();	
	cout << endl;

	cout << "Analizando el comportamiento de QuickSort en cuanto a comparaciones y asignaciones...\n";
	f7.open("qs_comparaciones.dat");
	f8.open("qs_asignaciones.dat");
	Opcional(20, 200, 20, f7, f8, 100);
	f7.close();
	f8.close();

	return 0;
}
/**************************************************************************/
void MergeSort(vector<VElement> &v, int izq, int der)
{
	int m;
	
	if(izq < der)
	{
        	m = (izq+der)/2;
          
		MergeSort(v, izq, m);
		MergeSort(v, m+1, der);
		mezclar(v, izq, m, der);
	}	
}

void mezclar(vector<VElement> &v, int izq, int piv, int der)
{
    	int i, j, k, l; 	
    	vector<VElement> v_aux(v.size());
    
	i = izq;
	j = piv + 1;
	k = izq;

	while((i<=piv) && (j<=der))
    	{        
		if(v[i] < v[j])
        	{
			v_aux[k] = v[i];
			i++;
		}
		
		else
        	{
			v_aux[k] = v[j];
			j++;
		}
	
		k++;
	}
	
	if(i > piv)
    	{
		for(l=k; l<=der; l++)
        	{
			v_aux[l] = v[j+(l-k)];
		}
	}
	
    	else
    	{
		for(l=k; (l<=der)&&(i+(l-k)<= piv); l++)
        	{
			v_aux[l] = v[i+(l-k)];
		}
	}

	for(l=izq; l<=der; l++)
    	{
		v[l] = v_aux[l];
	}
}

void MSvectorDesordenado(int ini, int end, int inc, ostream& salida, float porcentaje)
{
	vector<VElement> v;
	
	for(int talla=ini; talla<=end; talla+=inc)
	{
		VElement::initNAssign();
            	VElement::initNComparison();

     		for(int i=1; i<=REP; i++)
     		{

              		v.resize(talla);
              		dg.vectorSinRepeticion(v, porcentaje);
              		MergeSort(v, 0, v.size()-1);
     		}

		salida << talla << " " << (VElement::getNComparison()/REP) + (VElement::getNAssign()/REP) << endl;
     }
}

void test_MS_real(int ini, int end, int inc, ostream& salida)
{   
	int talla;
	vector<VElement> v;	
	clock_t ini_time, fin_time;
	float time;
	ini_time = clock();
	
	for(talla=ini; talla<=end; talla+=inc)
	{
		
		for(int i=1; i<=REP; i++)
		{
			v.resize(talla);
            		dg.vectorSinRepeticion(v, 100);
            		MergeSort(v, 0, v.size()-1);
		}
		
		fin_time = clock();
		time =fin_time - ini_time;
		salida << talla << " " << time / (CLOCKS_PER_SEC * REP) << endl;
	}
}

/***********************************************************************************/

void QuickSort(vector<VElement> &v, int izq, int der)
{
	int d ,e;

	if(izq < der)
	{
		partir(v, izq, der, e, d);
		QuickSort(v, izq, d);
		QuickSort(v, e, der);
	}
	
}

void partir(vector<VElement> &v, int izq, int der, int& e, int& d)
{
	VElement p, aux;
	
	e = izq;
	d = der;
	p = v[(e+d)/2];
	
	do
	{
		while(v[e] < p)
			e++;
		
		while(v[d] > p)
			d--;
		
		if(e <= d)
		{
			aux = v[d];
			v[d] = v[e];
			v[e] = aux;

			e++;
			d--;
		}
	}
	while(e <= d);
	
	
}

void QSvectorDesordenado(int ini, int end, int inc, ostream& salida, float porcentaje)
{
	vector<VElement> v;
	
	for(int talla=ini; talla<=end; talla+=inc)
	{
		VElement::initNAssign();
            	VElement::initNComparison();

     		for(int i=1; i<=REP; i++)
     		{

              		v.resize(talla);             
              		dg.vectorSinRepeticion(v, porcentaje);
              		QuickSort(v, 0, v.size()-1);
     		}
		
		salida << talla << " " << (VElement::getNComparison()/REP) + (VElement::getNAssign()/REP) << endl;

     }
}





void test_QS_real(int ini, int end, int inc, ostream& salida)
{
	int talla;
	vector<VElement> v;	
	clock_t ini_time, fin_time;
	float time;
	ini_time = clock();
	
	for(talla=ini; talla<=end; talla+=inc)
	{

		for(int i=1; i<=REP; i++)
		{
			v.resize(talla);
            		dg.vectorSinRepeticion(v, 100);
            		QuickSort(v, 0, v.size()-1);
		}
		
		fin_time = clock();
		time =fin_time - ini_time;
		salida << talla << " " << time / (CLOCKS_PER_SEC * REP) << endl; 
	}
}

void Opcional(int ini, int end, int inc, ostream& outComp, ostream& outAsig, float porcentaje)
{
	vector<VElement> v;

	for(int talla=ini; talla<=end; talla+=inc)
	{
		VElement::initNAssign();
            	VElement::initNComparison();

     		for(int i=1; i<=REP; i++)
     		{

              		v.resize(talla);
              		dg.vectorSinRepeticion(v, porcentaje);
              		QuickSort(v, 0, v.size()-1);
     		}

		outComp << talla << " " << VElement::getNComparison()/REP << endl;
		outAsig << talla << " " << VElement::getNAssign()/REP << endl;
     	}
}
