#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lista.h"


void InsereHeap(paciente Vetor[], int pos, paciente novo, int *comparacoesTotais, int *trocasTotais) {
    Vetor[pos] = novo;  
    int i = pos;
    paciente temp;

    while (i > 1) {   
        if (Vetor[i/2].prioridade > Vetor[i].prioridade) {
            (*comparacoesTotais)++;
            temp = Vetor[i/2];
            Vetor[i/2] = Vetor[i];
            Vetor[i] = temp; 
            (*trocasTotais)++;           
            i = i / 2;
        } else {
             (*comparacoesTotais)++;
             break; 
        }
    }
}

void Heapfy(paciente Vetor[], int N, int *comparacoesTotais, int *trocasTotais) {
    
    int comparacoes_iniciais = *comparacoesTotais;
    int trocas_iniciais = *trocasTotais;

    for (int i = 2; i <= N; i++)
        InsereHeap(Vetor, i, Vetor[i], comparacoesTotais, trocasTotais);
    
    printf("\nExecução Heapfy (Construção do Heap):\n");
    printf(" Foram feitas: %d comparacoes.\n", (*comparacoesTotais - comparacoes_iniciais));
    printf(" Foram feitas: %d trocas.\n", (*trocasTotais - trocas_iniciais));
}

int ChecaHeap(paciente Vetor[], int N) {
  for (int i = N; i > 1; i--)
    if (Vetor[i].prioridade > Vetor[i/2].prioridade)
      return 0;
  return 1;
}

void SacodeHeap(paciente Vetor[], int N, int *comparacoes, int *trocas) {
    int j = 1;      
    int i = 2 * j; 
    paciente temp;

    while (i <= N) {
        
        if (i < N) {
            (*comparacoes)++; 

            if (Vetor[i+1].prioridade < Vetor[i].prioridade)
                i++;
        }
        
        (*comparacoes)++; 
        if (Vetor[j].prioridade <= Vetor[i].prioridade)
            break;
            
        temp = Vetor[j];
        Vetor[j] = Vetor[i];
        Vetor[i] = temp;
        (*trocas)++;
        
        j = i; 
        i = 2 * j; 
    }
}

void HeapSort(paciente Vetor[], int N) {
  paciente temp;
  int comparacoesHeapSort = 0; 
  int trocasHeapSort = 0;
  int inicio = 1;
  int fim = N;

  Heapfy(Vetor, N, &comparacoesHeapSort, &trocasHeapSort);
  for (int i = N; i > 1; i--) {
    temp = Vetor[1];
    Vetor[1] = Vetor[i];
    Vetor[i] = temp;
    trocasHeapSort++;

    SacodeHeap(Vetor, i - 1, &comparacoesHeapSort, &trocasHeapSort);
  }

  while (inicio < fim) {
        temp = Vetor[inicio];
        Vetor[inicio] = Vetor[fim];
        Vetor[fim] = temp;
        
        inicio++; 
        fim--;   
    }

  printf("\nO HeapSort foi executado, e com isso:\n");
  printf(" Foram feitas: %d comparacoes totais no Heap Sort.\n", comparacoesHeapSort);
  printf(" Foram feitas: %d trocas totais no Heap Sort.\n\n", trocasHeapSort);
}

void InicHeap(paciente Vetor[], int N) {
  for (int i = 1; i <= N; i++) {
    strcpy(Vetor[i].nome, "NULL");
    Vetor[i].prioridade = 0;
  }
}

void AlteraHeap(paciente Vetor[], int N, int indice_paciente, int nova_prioridade) {
  if (indice_paciente > N || indice_paciente < 1) {
    printf("\nO índice que você digitou não está correto.\n\n");
    return;
  }

  if (Vetor[indice_paciente].prioridade == 0) {
    printf("\nNão há paciente inicializado na posição que você está tentando acessar.\n\n");
    return;
  }

  Vetor[indice_paciente].prioridade = nova_prioridade;

  printf("\nA prioridade do paciente %s foi alterada para %d\n\n", Vetor[indice_paciente].nome, nova_prioridade);

}

void RemoveHeap(paciente Vetor[], int N) {
  for (int i = 1; i < N; i++) {
    strcpy(Vetor[i].nome, Vetor[i + 1].nome);
    Vetor[i].prioridade = Vetor[i + 1].prioridade;
  }
  strcpy(Vetor[N].nome, "NULL");
  Vetor[N].prioridade = 0;
  N--;

  if (!ChecaHeap(Vetor, N)) {
    HeapSort(Vetor, N);
    printf("O Heap foi alterado\n");
  } else {
    printf("Mesmo com a alteração da prioridade, a ordem do Heap permanece a mesma.\n");
  }
}

void ImprimeHeap(paciente Vetor[], int N) {
  for (int i = 1; i <= N; i++) {
    printf("Pessoa #%d:\n", i);
    printf(" Nome: %s\n", Vetor[i].nome);
    printf(" Prioridade: %d\n", Vetor[i].prioridade);
    printf("\n");
  }
}