#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
#include <stddef.h>

// Structure d'arbre binaire de recherche

struct noeud_a_b_r { char* cle; int valeur; struct noeud_a_b_r* fg; struct noeud_a_b_r* fd; };
typedef struct noeud_a_b_r noeud_abr;

struct a_b_r { noeud_abr* racine; };
typedef struct a_b_r abr;

// Structure de tableau redimensionnable associée

struct elemabpc { char* element; int cle; };
typedef struct elemabpc elem_abpc;

struct ab_pc { int taille; int capacite; elem_abpc* donnees; };
typedef struct ab_pc abpc;

abpc creer_abpc()
{
  abpc t = { .taille = 0, .capacite = 8, .donnees = malloc(8 * sizeof(elem_abpc)) };
  return t;
}

int taille_abpc(abpc t)
{
  return t.taille;
}

elem_abpc acces_abpc(abpc t, int i)
{
  assert(0 <= i && i < t.taille);
  return t.donnees[i];
}

void modif_abpc(abpc t, int i, elem_abpc x)
{
  assert(0 <= i && i < t.taille);
  t.donnees[i] = x;
}

void redimensionne_abpc(abpc* t)
{
  int nv_capacite = t->capacite * 2;
  t->capacite = nv_capacite;
  elem_abpc* nv_tab = malloc(nv_capacite * sizeof(elem_abpc));
  for (int i = 0 ; i < t->taille ; i += 1)
  {
    nv_tab[i] = t->donnees[i];
  }
  free(t->donnees);
  t->donnees = nv_tab;
}

void append_abpc(abpc* t, elem_abpc x)
{
  if (t->taille == t->capacite) redimensionne_abpc(t);
  t->donnees[t->taille] = x;
  t->taille += 1;
}

elem_abpc pop_abpc(abpc* t)
{
  assert(t->taille > 0);
  elem_abpc rep = t->donnees[t->taille-1];
  t->taille -= 1;
  return rep;
}

// Exercice 1 en OCaml

// Exercice 2

abr creer_abr()
{
  abr rep = { .racine = NULL };
  return rep;
}

int consulter_abr(abr a, char* cle) // On peut aussi utiliser un abr* pour faire comme les fonctions où c'est nécessaire
{
  noeud_abr* p = a.racine;
  while (p != NULL)
  {
    int comp = strcmp(cle, p->cle);
    if (comp == 0) return p->valeur;
    if (comp > 0) p = p->fd;
    else p = p->fg;
  }
  assert (false);
}

void inserer_abr(abr* a, char* cle, int valeur)
{
  noeud_abr* nv = malloc(sizeof(noeud_abr));
  nv->cle = malloc(strlen(cle)+1);
  strcpy(nv->cle, cle);
  nv->valeur = valeur;
  nv->fg = NULL;
  nv->fd = NULL;
  if (a->racine == NULL)
  {
    a->racine = nv;
    return;
  }
  noeud_abr* p = a->racine;
  int stop = 0;
  while (stop == 0)
  {
    int comp = strcmp(cle, p->cle);
    if (comp == 0) // On peut changer d'avis, ce sera plus facile à écrire
    {
      // Pour le moment on fait comme dans le cas <
      if (p->fg == NULL) stop = -1;
      else p = p->fg;
    }
    else if (comp > 0)
    {
      if (p->fd == NULL) stop = 1;
      else p = p->fd;
    }
    else
    {
      if (p->fg == NULL) stop = -1;
      else p = p->fg;
    }
  }
  if (stop == 1) p->fd = nv;
  else p->fg = nv;
}

noeud_abr* minimum(noeud_abr* p)
{
  while (p->fg != NULL) p = p->fg;
  return p;
}

void redirige_mini(noeud_abr* p)
{
  assert (p->fg != NULL); // Normalement c'est bon
  while (p->fg->fg != NULL) p = p->fg;
  p->fg = p->fg->fd;
}

void supprimer_abr(abr* a, char* cle)
{
  noeud_abr* p = a->racine;
  noeud_abr* precedent = NULL;
  bool droite = true;
  bool found = false;
  while (p != NULL && !found)
  {
    int comp = strcmp(cle, p->cle);
    if (comp == 0) found = true;
    else if (comp > 0)
    {
      precedent = p;
      p = p->fd;
      droite = true;
    }
    else
    {
      precedent = p;
      p = p->fg;
      droite = false;
    }
  }
  assert (found);
  if (p->fd == NULL)
  {
    if (precedent == NULL) a->racine = p->fg;
    else if (droite) precedent->fd = p->fg;
    else precedent->fg = p->fg;
  }
  else if (p->fg == NULL)
  {
    if (precedent == NULL) a->racine = p->fd;
    else if (droite) precedent->fd = p->fd;
    else precedent->fg = p->fd;
  }
  else if (p->fd->fg == NULL)
  {
    p->fd->fg = p->fg;
    if (precedent == NULL) a->racine = p->fd;
    else if (droite) precedent->fd = p->fd;
    else precedent->fg = p->fd;
  }
  else
  {
    noeud_abr* mini = minimum(p->fd);
    redirige_mini(p->fd);
    mini->fd = p->fd;
    mini->fg = p->fg;
  }
  free(p->cle);
  free(p);
}

void imprimer_abr(abr a)
{
  void aux(noeud_abr* p, int imbrication)
  {
    if (p != NULL)
    {
      for (int i = 0 ; i < imbrication ; i += 1) printf("|");
      printf("\\%s\n", p->cle);
      for (int i = 0 ; i < imbrication ; i += 1) printf("|");
      printf("|\n");
      aux(p->fg, imbrication+1);
      aux(p->fd, imbrication+1);
    }
    else
    {
      for (int i = 0 ; i < imbrication ; i += 1) printf("|");
      printf("-¤\n");
    }
  }
  aux(a.racine, 0);
}

int main2()
{
  abr a = creer_abr();
  inserer_abr(&a, "2", 2);
  inserer_abr(&a, "1", 1);
  inserer_abr(&a, "3", 3);
  inserer_abr(&a, "0", 0);
  imprimer_abr(a);
  printf("\n########################################\n\n");
  supprimer_abr(&a, "2");
  imprimer_abr(a);
  supprimer_abr(&a, "3");
  supprimer_abr(&a, "1");
  supprimer_abr(&a, "0");
  return 0;
}

// Exercice 3 en OCaml

// Exercice 4

abpc creer_tas()
{
  return creer_abpc();
}

void inserer_tas(abpc* tas, char* element, int cle)
{
  elem_abpc nv = { .element = element , .cle = cle };
  append_abpc(tas, nv);
  int position = tas->taille - 1;
  while (position > 0)
  {
    int pere = (position - 1) / 2;
    if (tas->donnees[pere].cle > tas->donnees[position].cle)
    {
      elem_abpc buff = tas->donnees[pere];
      tas->donnees[pere] = tas->donnees[position];
      tas->donnees[position] = buff;
      position = pere;
    }
    else return;
  }
}

elem_abpc extraire_racine(abpc* tas)
{
  assert(tas->taille > 0);
  elem_abpc reponse = tas->donnees[0];
  tas->donnees[0] = pop_abpc(tas);
  int position = 0;
  while (2 * position + 1 < tas->taille)
  {
    int nv_position = position;
    if (2 * position + 2 < tas->taille && tas->donnees[position].cle > tas->donnees[2 * position + 2].cle) nv_position = 2 * position + 2;
    if (tas->donnees[nv_position].cle > tas->donnees[2 * position + 1].cle) nv_position = 2 * position + 1;
    if (nv_position != position)
    {
      elem_abpc buff = tas->donnees[nv_position];
      tas->donnees[nv_position] = tas->donnees[position];
      tas->donnees[position] = buff;
      position = nv_position;
    }
    else return reponse;
  }
  return reponse;
}

void modifier_valeur(abpc* tas, int position, int nv_cle) // Si on veut l'associer à un élément particulier, une autre fonction pourra le localiser par une recherche exhaustive
{
  assert(position < tas->taille);
  tas->donnees[position].cle = nv_cle;
  if (position > 0 && tas->donnees[(position - 1) / 2].cle > nv_cle)
  {
    while (position > 0)
    {
      int pere = (position - 1) / 2;
      if (tas->donnees[pere].cle > tas->donnees[position].cle)
      {
        elem_abpc buff = tas->donnees[pere];
        tas->donnees[pere] = tas->donnees[position];
        tas->donnees[position] = buff;
        position = pere;
      }
      else return;
    }
  }
  // Sinon on fait comme dans le cas de l'insertion, quitte à interrompre tout de suite.
  while (2 * position + 1 < tas->taille)
  {
    int nv_position = position;
    if (2 * position + 2 < tas->taille && tas->donnees[position].cle > tas->donnees[2 * position + 2].cle) nv_position = 2 * position + 2;
    if (tas->donnees[nv_position].cle > tas->donnees[2 * position + 1].cle) nv_position = 2 * position + 1;
    if (nv_position != position)
    {
      elem_abpc buff = tas->donnees[nv_position];
      tas->donnees[nv_position] = tas->donnees[position];
      tas->donnees[position] = buff;
      position = nv_position;
    }
    else return;
  }
}

int main4()
{
  abpc a = creer_tas();
  inserer_tas(&a, "A", 2);
  inserer_tas(&a, "B", 1);
  inserer_tas(&a, "C", 3);
  inserer_tas(&a, "D", 0);
  
  for (int i = 0 ; i < 4 ; i += 1)
  {
    elem_abpc e = extraire_racine(&a);
    printf("Extraction de la racine : élément %s et clé %d.\n", e.element, e.cle);
  }
  
  free(a.donnees);
  
  return 0;
}

// Exercice 5 en OCaml

// Exercice 6

// Au vu de la structure qu'on a faite pour les ABR et du polymorphisme limité dans l'enseignement fait en C, le travail est en pratique déjà terminé !
// Il manque juste la fonction de modification, et on pourra éventuellement renommer les fonctions, mais l'intérêt est limité dans un corrigé…

void modifier_abr(abr a, char* cle, int nv_valeur) // Seule la première occurrence de la clé sera modifiée.
{
  noeud_abr* p = a.racine;
  while (p != NULL)
  {
    int comp = strcmp(cle, p->cle);
    if (comp == 0)
    {
      p->valeur = nv_valeur;
      return;
    }
    if (comp > 0) p = p->fd;
    else p = p->fg;
  }
  assert (false);
}

// Exercice 7 en OCaml

// Exercice 8

// Même remarque. On notera qu'il est possible de passer de n en tant que priorité à -n en tant que clé si on veut retirer l'élément de priorité maximale.

// Exercice 9 en OCaml

// Exercice 10 en OCaml

// Exercice 11 en OCaml

// Exercice 12

int* tri_par_tas(int* tableau, int taille)
{
  abpc tas = creer_tas();
  for (int i = 0 ; i < taille ; i += 1) inserer_tas(&tas, "", tableau[i]);
  int* reponse = malloc(taille * sizeof(int));
  for (int i = 0 ; i < taille ; i += 1) reponse[i] = extraire_racine(&tas).cle;
  free(tas.donnees);
  return reponse;
}

int main()
{
  int tab[10] = { 5 , 4 , 7 , 6 , 2 , 8 , 1 , 9 , 3 , 0 };
  int* tabtrie = tri_par_tas(tab, 10);
  for (int i = 0 ; i < 10 ; i += 1)
  {
    printf("%d ", tabtrie[i]);
  }
  free(tabtrie);
  
  return 0;
}