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


/*
 * alguns destes algoritmos foram retirados e/ou convertidos de Java dos seguintes sites
 *
 *		http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
 *
 *		http://www.scs.carleton.ca/~morin/misc/sortalg/
 *
 *		http://www.cs.hope.edu/~alganim/ccaa/sorts.html
 *
 *
 * informação geral sobre algoritmos com uma pequena descrição e animação pode ser encontrada em
 *
 *		http://www.people.fas.harvard.edu/~toub/cs50/sorting/
 *
 */


#include <vector>
#include <ctime>
#include <string>
#include <iostream>
#include <iomanip>
//#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;

#include "../ei-include/erro.h"

#include "utils.h"
#include "cronometro.h"
#include "cvector.h"

#include "shearsort.h"
#include "oddevensort.h"
#include "quicksort.h"
#include "bubblesort.h"
#include "insertionsort.h"
#include "biinsertionsort.h"
#include "selectionsort.h"
#include "bibubblesort.h"
#include "shellsort.h"
#include "heapsort.h"
#include "shakersort.h"
#include "mergesort.h"
#include "combsort11.h"
#include "jsort.h"
#include "stoogesort.h"


//
// algoritmos de ordenação e politicas de preenchimentos
//

enum preenchimento {ordenado = 0, invertido, aleatorio};
const int NUM_PREENCHIMENTOS = 3;

void preenche(preenchimento FP, int vec[], int nTam);



enum algoritmo {qsort1 = 0, qsort2, qsort3, qsort4, qsort5, qsort6, qsort7, qsort8, qsort9, qsort10, qsort11,
				shell1, shell2, shell3, shell4, shell5, shell6, shell7,
				shaker1, shaker2, shaker3,
				merge1, merge2, merge3, merge4,
				comb11_1,
				heap1, 
				jsort1,
				shear1,	shear2,
				// algoritmos lentos
				insertion, 
				biins1,
				selsort1, selsort2,
				oddeven1,
				bubble1, bubble2, bubble3, bubble4, bubble5,
				bibubble1, 
				// algoritmos demasiado lentos (sem utilização prática)
				stooge1,
				perm1,
				bozo1,
				};
const int NUM_ALGORITMOS = 41;
const int NUM_ALGORITMOS_LENTOS = 3;

//
// vector auxiliar com os limites (dimensão do array) razoaveis (<25seg 2xPIII 533MHz 256MB)
// para cada algoritmo
//
const int vnLimites[][NUM_PREENCHIMENTOS] = {
/* qsort1 */	{-1,	-1,		-1},					
/* qsort2 */	{29001, 29001,	-1},	// limites de stack
/* qsort3 */	{-1,	150001,	-1},	// esta variante ** é ** relativamente lenta
/* qsort4 */	{29001, 29001,	-1},	// limites de stack
/* qsort5 */	{-1,	-1,		-1},					
/* qsort6 */	{30001, 30001,	-1},	// lentidão e limites de stack
/* qsort7 */	{50001, 50001,	-1},	// lentidão e limites de stack
/* qsort8 */	{-1,	-1,		-1},					
/* qsort9 */	{-1,	-1,		-1},
/* qsort10 */	{28001,	21001,	-1},
/* qsort10 */	{-1,	-1,		-1},	
/* shell1 */	{-1,	-1,		-1},					
/* shell2 */	{-1,	-1,		-1},					
/* shell3 */	{-1,	-1,		-1},					
/* shell4 */	{-1,	-1,		-1},					
/* shell5 */	{-1,	-1,		-1},					
/* shell6 */	{-1,	-1,		-1},					
/* shell7 */	{-1,	-1,		-1},					
/* shaker1 */	{60001, 60001,	60001},	// esta variante ** é ** lenta
/* shaker2 */	{-1,	-1,		40001},	// esta variante ** é ** lenta para vectores aleatorios
/* shaker3 */	{-1,	-1,		-1},					
/* merge1 */	{-1,	50001,	80001},	// esta variante ** é ** lenta
/* merge2 */	{-1,	-1,		-1},					
/* merge3 */	{-1,	-1,		-1},
/* merge4 */	{-1,	-1,		-1},
/* comb11_1 */	{-1,	-1,		-1},					
/* heap1 */		{-1,	-1,		-1},					
/* jsort1 */	{-1,	-1,		-1},					
/* shear1 */	{-1,	100001,	90001},
/* shear2 */	{-1,	202501,	122501},
				// algoritmos lentos
/* insertion */	{-1,	40001,	60001},					
/* biins1 */	{-1,	45001,	65001},
/* selsort1 */	{50001, 50001,	70001},
/* selsort2 */	{-1,	55001,	70001},					
/* oddeven1 */	{50001,	20001,	20001},
/* bubble1 */	{20001, 20001,	20001},			
/* bubble2 */	{-1,	20001,	20001},				
/* bubble3 */	{-1,	20001,	20001},
/* bubble4 */	{45001,	45001,	32001},
/* bubble5 */	{-1,	15001,	20001},
/* bibubble1 */	{-1,	20001,	20001},				
				// algoritmos demasiado lentos
/* stooge1 */	{2001,	2001,	2001},				
/* perm1 */		{2001,	101,	101},				
/* bozo1 */		{101,	101,	101}				
};



string tostring(preenchimento FP);
string tostring(algoritmo SP);

//
// funções de teste
//
int gera_vec_sp(algoritmo*& vec_sp);

void view_teste_modo_1(algoritmo vec[], int nAlgs, int tamanho, int runs, int ignore);
void modo_1(bool bUseAllSP);

void view_teste_modo_2(algoritmo vec[], int nAlgs, preenchimento fp, int tamInf, int tamSup, int inc, int runs, int ignore);
void modo_2(bool bUseAllSP);

void view_teste_modo_3(algoritmo sp, int tamInf, int tamSup, int inc, int runs, int ignore);
void modo_3();

void view_teste_modo_4(algoritmo sp, preenchimento fp, int tamanho, int runs, int ignore);
void modo_4();



//
// variavel global contendo as opcoes de configuracao
//
typedef struct {
	bool bOutput2File;	// não usado
	string sFileName;	// não usado
	bool bUseLimits;	// utilização do array de limites ou não
	bool bUseSlow;		// utilização dos algoritmos muito lentos ou não
	bool bUseMiliseg;	// unidades de tempo em segundos ou milisegundos
} configuracao_t; 

extern configuracao_t g_configuracao;