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

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

using namespace std;

const int REP = 20;
DataGenerator dg;
typedef vector<VElement> Vector;

void RadixSort(list<int> &v, double m);
void CountSort(vector<VElement> &v, int m,vector<VElement> &v2);
int digito(int pos, int num);
void CosteTemporalCountSort(unsigned ini, unsigned fin, int inc,int m, unsigned repeticiones, ostream & file);
void CosteTemporalRadix(unsigned ini, unsigned fin, int inc,int m, unsigned repeticiones, ostream & file);
void CosteRealCountSort(unsigned ini, unsigned fin, int inc,int m, unsigned repeticiones, ostream & file);
void CosteRealRadix(unsigned ini, unsigned fin, int inc,int m, unsigned repeticiones, ostream & file);

int main()
{

    	ofstream c1,c2, r1, r2, cR1, cR2;
	/*vector<VElement> v1(20);
	vector<VElement> v2(20);
	list <int> l;
	
	dg.vectorConRepeticionHastaM(v1, 255);

	dg.CrearLista(l,255,20);*/

	/*COUNTSORT*/
	/*CountSort(v1,255,v2);	
	dg.printVector(v2);
	cout << endl;*/

	/*RADIXSORT*/
	/*RadixSort(l,255);
	list<int>::iterator pos;
     	pos = l.begin();
     	while(pos != l.end())
     	{
      		cout << *pos << " ";
      		pos++;

      	}
	cout << endl;*/

	/*COUNTSORT_REAL*/
	cR1.open("cs_operaciones_255.dat");
	CosteRealCountSort(100, 2000, 100,255, REP, cR1);
	cR1.close();

	cR2.open("cs_operaciones_65535.dat");
	CosteRealCountSort(100, 2000, 100,65535, REP, cR2);
	cR2.close();



	/*COMPROBACIONES*/
	/*c1.open("cs_r_255.dat");
	CosteTemporalCountSort(100, 2000, 100, 255, REP, c1);
	c1.close();
	cout << "CalculoCoste de vectores desordenados COMPLETADO\n";
	
	c2.open("cs_r_65535.dat");
	CosteTemporalCountSort(100, 2000, 100, 65535, REP, c2);
	c2.close();
	cout << "CalculoCoste de vectores desordenados COMPLETADO\n";
	
    	r1.open("rs_r_255.dat");
	CosteTemporalRadix(100, 2000, 100, 255, REP, r1);
	r1.close();
	cout << "CalculoCoste de vectores desordenados COMPLETADO\n";
	
	r2.open("rs_r_65535.dat");
	CosteTemporalRadix(100, 2000, 100, 65535, REP, r2);
	r2.close();
	cout << "CalculoCoste de vectores desordenados COMPLETADO\n";*/

	return 0;
}

void RadixSort(list<int> &v, double m)
{
	list<int> bucket[10];
	int d;
	int x = v.size();
 
	for(int i=0; i<= log10(m); i++)
	{
		for(int j=1; j<=x; j++)
		{
                
			d = digito(i, v.front());
			bucket[d].splice(bucket[d].end(), v, v.begin()); //Insertar
		}
		for(int j = 0; j<=9; j++)
		{
			v.splice(v.end(), bucket[j]); //Concatenar
		}
	}
}

void CountSort(vector<VElement> &v, int m,vector<VElement> &v2)
{
	vector<VElement> v_aux(m+1);
	
	for(int i=1; i<=v.size(); i++)
	        v_aux[v[i].get()] = v_aux[v[i].get()].get() + 1;
	
	int pos = 1;
	for(int h = 2; h<=m; h++)
            v_aux[h] = v_aux[h].get() + v_aux[h -1].get();
            
	for(int j =1;j <= v.size();j++)
	{       
		v2[v_aux[v[j].get()].get()]= v[j];
                v_aux[v[j].get()]= v_aux[v[j].get()].get()-1;
         }
}

int digito(int pos, int num)
{
	int d;

	for(int i=0; i<=pos; i++)
	{
		d = num%10;
		num = num/10;
	}
	
	return d;	
}

void CosteTemporalCountSort(unsigned ini, unsigned fin, int inc,int m, unsigned repeticiones, ostream & file)
{	
	clock_t ini_time, fin_time;
	float time;
	
	for (unsigned n = ini; n <= fin; n += inc) 
	{
		vector<VElement> v(n);
		vector<VElement> v2(n);
		DataGenerator d;

        	d.vectorConRepeticionHastaM(v,m);

		ini_time = clock();
		for(unsigned i=1; i <= repeticiones; i++) 
		{
			CountSort(v, m, v2 );
		}
		fin_time = clock();
		time = fin_time - ini_time;
		file << n << " " << (time / (CLOCKS_PER_SEC * repeticiones)) << endl;
	}
}

void CosteTemporalRadix(unsigned ini, unsigned fin, int inc,int m, unsigned repeticiones, ostream & file)
{	
	clock_t ini_time, fin_time;
	float time;
	
	for (unsigned n = ini; n <= fin; n += inc) 
	{
	    	list <int> l;
		DataGenerator d;

        	d.CrearLista(l,m, n);
	        
		ini_time = clock();
		for(unsigned i=1; i <= repeticiones; i++) 
		{
			RadixSort(l, m);
		}
		fin_time = clock();
		time = fin_time - ini_time;
		file << n << " " << (time / (CLOCKS_PER_SEC * repeticiones)) << endl;
	}
}

void CosteRealCountSort(unsigned ini, unsigned fin, int inc,int m, unsigned repeticiones, ostream & file)
{	
	float coste;
	
	for (unsigned n = ini; n <= fin; n += inc) 
	{
		vector<VElement> v(n);
		vector<VElement> v2(n);
		DataGenerator d;
        coste = 0;
        d.vectorConRepeticionHastaM(v,m);

        VElement::initNAssign();
        VElement::initNComparison();
		for(unsigned i=1; i <= repeticiones; i++) 
		{
			CountSort(v, m, v2 );
		}
		
		coste = VElement::getNAssign() + VElement::getNComparison();
		file << n << " " << (coste / repeticiones) << endl;
	}
}

void CosteRealRadix(unsigned ini, unsigned fin, int inc,int m, unsigned repeticiones, ostream & file)
{	
	float coste;
	
	for (unsigned n = ini; n <= fin; n += inc) 
	{
		list <int> l;
		DataGenerator d;
        	d.CrearLista(l,m, n);   
		coste = 0;

        VElement::initNAssign();
        VElement::initNComparison();
		for(unsigned i=1; i <= repeticiones; i++) 
		{
			RadixSort(l, m);
		}
		coste = VElement::getNAssign() + VElement::getNComparison();
		file << n << " " << (coste / repeticiones) << endl;
	}
}
