#include <iostream>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
void print(int *a, int n)
{
    int i=0;
    while(i<n){
        cout<<a[i]<<",";
        i++;
    }
}

void swap(int i,int j, int *a){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

void QuickSortPivotPrimeiroOuSegundo(int *arr, int left, int right){
    cout<<"QS:"<<left<<","<<right<<"\n";
    int i = left;
    int j = right;
    int pivot;
    if(arr[left]> arr[left+1])
        pivot = arr[left];
    else
        pivot = arr[left+1];
    while(left<j || i<right)
    {
        while(arr[i]<pivot)
        i++;
        while(arr[j]>pivot)
        j--;
        if(i<=j){
            swap(i,j,arr);
            i++;
            j--;
        }
        else{
            if(left<j)
                QuickSortPivotPrimeiroOuSegundo(arr, left, j);
            if(i<right)
                QuickSortPivotPrimeiroOuSegundo(arr,i,right);
            return;
        }
    }
}

void QuickSortPivotPrimeiroOuMeio(int *arr, int left, int right){
    int min = (left+right)/2;
    //cout<<"QS:"<<left<<","<<right<<"\n";
    int i = left;
    int j = right;
    int pivot;
    if(arr[left]> arr[min])
    pivot = arr[left];
    else
        pivot = arr[min];
    while(left<j || i<right)
    {
        while(arr[i]<pivot)
        i++;
        while(arr[j]>pivot)
        j--;
        if(i<=j){
            swap(i,j,arr);
            i++;
            j--;
        }
        else{
            if(left<j)
                QuickSortPivotPrimeiroOuMeio(arr, left, j);
            if(i<right)
                QuickSortPivotPrimeiroOuMeio(arr,i,right);
            return;
        }
    }
}
void QuickSortPivotAleatorio(int *arr, int left, int right){
    cout<<"QS:"<<left<<","<<right<<"\n";
    srand( (unsigned)time(NULL) );
    int x = rand()%right;
    int y = rand()%right;

    int i = left;
    int j = right;
    int pivot;
    if(arr[x]> arr[y])
        pivot = arr[x];
    else
        pivot = arr[y];
    while(left<j || i<right)
    {
        while(arr[i]<pivot)
        i++;
        while(arr[j]>pivot)
        j--;
        if(i<=j){
            swap(i,j,arr);
            i++;
            j--;
        }
        else{
            if(left<j)
                QuickSortPivotAleatorio(arr, left, j);
            if(i<right)
                QuickSortPivotAleatorio(arr,i,right);
            return;
        }
    }
}
int main() {
     while((representacao != 1) && (representacao != 2) && (representacao != 3) && (representacao != 4) && (representacao != 5) && (representacao != 6) && (representacao != 7) && (representacao != 8) && (representacao != 9) && (representacao != 10) && (representacao != 11) && (representacao != 12) && (representacao != 13) && (representacao != 10) && (representacao != 11) && (representacao != 12) && (representacao != 13) && (representacao != 14) && (representacao != 15) && (representacao != 16)){
        printf("   ----------------------------------------------------------\n");
        printf("            Escolha o metodo de representacao:   \n\n");
        printf("              1 - HeapSort\n");
        printf("              2 - Grau de um no\n");
        printf("              3 - Grau de G\n");
        printf("              4 - Dado dois vertices, dizer se sao adjacentes\n");
        printf("              5 - Listar os adjacentes de um no\n");
        printf("              6 - Dado um conjunto x de vertice, retornar o grafo induzido por x\n");
        printf("              7 - Verificar se G eh k-regular\n");
        printf("              8 - Retornar o grafo complementar de G\n");
        printf("              9 - Verificar se G eh compelto\n");
        printf("              10- Verificar se G eh conexo\n");
        printf("              11- Verificar se um dado vertice eh de articulacao\n ");
        printf("              12- Verificar se uma dada aresta eh ponte \n");
        printf("              13- Algoritmo Guloso\n");
        printf("              14- Algoritmo Construtivo com Fator de Aleatoridade\n");
        printf("              15- Algoritmo Reativo\n");
        printf("              16- Sair\n");
        printf("  ----------------------------------------------------------\n");
        printf("\t\t\t");
        scanf("%d",&representacao);
    }
        time_t inicio, fim;
    switch(representacao)
    {
        case 1:

            ImprimeListaCompleta(lista,txt2);

            break;
        case 2:
            do{
                printf("\n Digite o no que se deseja saber o grau\n");
                scanf("%d",&aux);
            }while(aux<1 || aux>nos);
            printf("Grau do no: %d", GrauNoLista(lista,aux));
            fprintf(txt2,"Grau do no %d eh: %d\n",aux, GrauNoLista(lista,aux));
            break;
        case 3:
            printf("O grau do grafo eh: %d",GrauGrafo(lista));
            fprintf(txt2,"O grau do grafo eh: %d\n",GrauGrafo(lista));
            break;
        case 4:
            do{
                printf("\n Digite os nos que se deseja saber se sao adjacentes\n");
                scanf("%d %d",&aux,&aux2);
            }while(aux<1 || aux>nos || aux2<1 || aux2>nos);
            if(VerficarDoisNosAdjacentes(lista,aux,aux2)){
                printf("Os nos %d e %d sao adjacentes",aux,aux2);
                fprintf(txt2,"Os nos %d e %d sao adjacentes",aux,aux2);
            }
            else{
                printf("Os nos %d e %d nao sao adjacentes",aux,aux2);
                fprintf(txt2,"Os nos %d e %d nao sao adjacentes",aux,aux2);

            }

            break;
        case 5:
            do{
                printf("\n Digite o no que se deseja os nó adjacentes\n");
                scanf("%d",&aux);
            }while(aux<1 || aux>nos);
            printf("Os nos adjacentese de %d sao: ",aux);
            ImprimeAdjacentesNo(lista,aux,txt2);
            break;

        case 6:

            do{
                do{
                    printf("Digite os nos para encontrar o grafo induzido. Digite 0 para parar a leitura\n");
                    scanf("%d",&aux);
                    if(aux == 0)
                        break;
                }while(aux<1 || aux>nos);
                vet2[k] = aux;
                k++;
            }while(aux != 0);
            No* induzido = RetornaInduzido(lista,vet2,k,nos);
            ImprimeListaCompleta(induzido,txt2);
            break;
        case 7:
            KRegular(lista,txt2);
            break;
        case 8:
           complementar = GrafoComplementar(lista,nos);
           printf("Grafo complementar:\n");
           fprintf(txt2,"\nGrafo complementar:\n");
           ImprimeListaCompleta(complementar,txt2);
            break;
        case 9:
            VerificarGCompleto(lista,nos,txt2);
            break;
        case 10:
            if(VerificaConexo(nos,lista)){
                printf("O grafo eh Conexo");
                fprintf(txt2,"\nO grafo eh Conexo");
            }
            else{
                printf("O grafo nao eh Conexo");
                fprintf(txt2,"\nO grafo nao eh Conexo");
            }
            break;
        case 11:
            do{
                printf("\n Digite o no que se deseja saber se eh de articulacao\n");
                scanf("%d",&aux);
            }while(aux<1 || aux>nos);
            if(VerificaVerticeArticulacao(aux,lista,nos)){
                printf("O no eh de articulacao");
                fprintf(txt2,"\nO no eh de articulacao");
            }
            else{
                printf("O no nao eh de articulacao");
                fprintf(txt2,"\nO no nao eh de articulacao");
            }
            break;
        case 12:
            do{
                printf("\n Digite os nos que se deseja saber se eh ponte\n");
                scanf("%d %d",&aux,&aux2);
            }while(aux<1 || aux>nos || aux2<1 || aux2>nos);

            if(VerificaArestaPonte(aux,aux2,lista,nos)){
                printf("A aresta eh ponte");
                fprintf(txt2,"\nA aresta eh ponte");
            }
            else{
                printf("A aresta nao eh ponte");
                fprintf(txt2,"\nA aresta nao eh ponte");
            }
            break;
        case 13:
             inicio = clock();
             printf("Conjunto Dominante: %d\n",ConjuntoDominante(lista,nos));
             fim = clock();
             printf("tempo %f\n",(((float)(fim - inicio) / CLOCKS_PER_SEC)));
             break;

        case 14:
            alfa =0.1;
            melhorSemente = 0;
            while(alfa<=(float)0.3){
                inicio = clock();
                for(i =0;i<30;i++){
                    r = ConjuntoDominanteFatorAleatoriedade(lista,nos,alfa, i);
                    if(r< best){
                        best = r;
                        melhorSemente = i;
                    }
                }
                fim = clock();
                printf("Best %d para alfa %f tempo %f e semente %d\n",best,alfa,(((float)(fim - inicio) / CLOCKS_PER_SEC)),melhorSemente);
                melhorSemente = 0;
                alfa+=0.1;
            }
            break;
        case 15:
            melhorSemente = 0;
            inicio = clock();

            for(i =0;i<30;i++){
                res = ConjuntoDominanteReativo(lista,nos, i);
                if(res.melhor< best){
                    best = res.melhor;
                    melhorSemente = i;
                    melhorAlfa = res.alfa;
                }
            }
            fim = clock();
            printf("Best %d, tempo %f, semente %d e alfa %f\n",best,(((float)(fim - inicio) / CLOCKS_PER_SEC)),melhorSemente,melhorAlfa);
            melhorSemente = 0;
            break;
        case 16:
            exit(0);
            fclose(txt2);
            break;
    }

}

int main(int argc, char *argv[]){
    int fim = 0;
    Principal(argv);
    do{
        printf("\n\n\n\nDigite 1 para sair ou 0 para executar novamente:\n");
        scanf("%d",&fim);
    }while(fim!=1 && fim!=0);
    if(fim == 0){
        main(argc,argv);
    }
    int arr[8] = {110, 5, 10,3 ,22, 100, 1, 23};
    printf("%d", (sizeof(arr)/sizeof(arr[0]))-1);
    //QuickSortPivotAleatorio(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
    //QuickSortPivotPrimeiroOuMeio(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
    QuickSortPivotPrimeiroOuSegundo(arr, 0, (sizeof(arr)/sizeof(arr[0]))-1);
    print(arr, (sizeof(arr)/sizeof(arr[0])));
    return 0;
}