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

struct i_a_b { int etiquette; struct i_a_b* fg; struct i_a_b* fd; };
typedef struct i_a_b abi;

struct i_a { int etiq; int nb_fils; struct i_a* fils; };
typedef struct i_a ai;

// Exercice 1

int taille_abi(abi a)
{
  int n = 1;
  if (a.fg != NULL) n += taille_abi(*a.fg);
  if (a.fd != NULL) n += taille_abi(*a.fd);
  return n;
}

// Exercice 2

int somme_abi(abi a)
{
  int n = a.etiquette;
  if (a.fg != NULL) n += somme_abi(*a.fg);
  if (a.fd != NULL) n += somme_abi(*a.fd);
  return n;
}

// Exercice 3

int min_abi(abi a)
{
  int n = a.etiquette;
  if (a.fg != NULL)
  {
    int m = min_abi(*a.fg);
    if (m < n) n = m;
  }
  if (a.fd != NULL)
  {
    int m = min_abi(*a.fd);
    if (m < n) n = m;
  }
  return n;
}

// Exercice 4

int hauteur_abi(abi a)
{
  int rep = 0;
  if (a.fg != NULL) rep = 1 + hauteur_abi(*a.fg);
  if (a.fd != NULL)
  {
    int hfd = 1 + hauteur_abi(*a.fd);
    if (hfd > rep) rep = hfd;
  }
  return rep;
}

// Exercice 5

int nb_abi(int n)
{
  int* mem = malloc((n+1) * sizeof(int));
  mem[0] = 1;
  for (int i = 1 ; i <= n ; i += 1)
  {
    mem[i] = 0;
    for (int j = 0 ; j < i ; j += 1)
    {
      mem[i] += mem[j] * mem[i-j-1];
    }
  }
  int rep = mem[n];
  free(mem);
  return rep;
}

// Exercice 6

int* tous_nb_abi(int n) // En pratique ceci devrait remplacer la fonction précédente en manipulant bien la mémoire
{
  int* mem = malloc((n+1) * sizeof(int));
  mem[0] = 1;
  for (int i = 1 ; i <= n ; i += 1)
  {
    mem[i] = 0;
    for (int j = 0 ; j < i ; j += 1)
    {
      mem[i] += mem[j] * mem[i-j-1];
    }
  }
  return mem;
}

abi** tous_abi(int n)
{
  assert(n >= 1);
  int* tailles = tous_nb_abi(n);
  abi** toutes_rep = malloc((n+1) * sizeof(abi*));
  for (int i = 0 ; i <= n ; i += 1)
  {
    toutes_rep[i] = malloc(tailles[i] * sizeof(abi));
  }
  toutes_rep[1][0].etiquette = 0;
  toutes_rep[1][0].fg = NULL;
  toutes_rep[1][0].fd = NULL;
  for (int i = 2 ; i <= n ; i += 1)
  {
    int j = 0;
    for (int nd = 0 ; nd < tailles[i-1] ; nd += 1)
    {
      toutes_rep[i][j].etiquette = 0;
      toutes_rep[i][j].fg = NULL;
      toutes_rep[i][j].fd = &(toutes_rep[i-1][nd]);
      j += 1;
    }
    for (int k = 1 ; k < i-1 ; k += 1)
    {
      for (int ng = 0 ; ng < tailles[k] ; ng += 1)
      {
        for (int nd = 0 ; nd < tailles[i-k-1] ; nd += 1)
        {
          toutes_rep[i][j].etiquette = 0;
          toutes_rep[i][j].fg = &(toutes_rep[k][ng]);
          toutes_rep[i][j].fd = &(toutes_rep[i-k-1][nd]);
          j += 1;
        }
      }
    }
    for (int ng = 0 ; ng < tailles[i-1] ; ng += 1)
    {
      toutes_rep[i][j].etiquette = 0;
      toutes_rep[i][j].fg = &(toutes_rep[i-1][ng]);
      toutes_rep[i][j].fd = NULL;
      j += 1;
    }
  }
  free(tailles);
  return toutes_rep;
}

// Exercice 7

// Fonction utile désormais

int taille_ai(ai a)
{
  int rep = 1;
  for (int i = 0 ; i < a.nb_fils ; i += 1)
  {
    rep += taille_ai(a.fils[i]);
  }
  return rep;
}

void ppp(ai a)
{
  printf("%d ", a.etiq);
  for (int i = 0 ; i < a.nb_fils ; i += 1)
  {
    ppp(a.fils[i]);
  }
}

void pps(ai a)
{
  for (int i = 0 ; i < a.nb_fils ; i += 1)
  {
    pps(a.fils[i]);
  }
  printf("%d ", a.etiq);
}

void pl(ai a)
{
  int n = taille_ai(a);
  ai* file = malloc(n * sizeof(ai));
  file[0] = a;
  int i = 0;
  int ind = 1;
  while (i < n)
  {
    printf("%d ", file[i].etiq);
    for (int j = 0 ; j < file[i].nb_fils ; j += 1)
    {
      file[ind] = file[i].fils[j];
      ind += 1;
    }
    i += 1;
  }
  printf("\n");
  free(file);
}

// Exercice 8

void pppb(abi a)
{
  printf("%d ", a.etiquette);
  if (a.fg != NULL) pppb(*a.fg);
  if (a.fd != NULL) pppb(*a.fd);
}

void ppib(abi a)
{
  if (a.fg != NULL) ppib(*a.fg);
  printf("%d ", a.etiquette);
  if (a.fd != NULL) ppib(*a.fd);
}

void ppsb(abi a)
{
  if (a.fg != NULL) ppsb(*a.fg);
  if (a.fd != NULL) ppsb(*a.fd);
  printf("%d ", a.etiquette);
}

void plb(abi a)
{
  int n = taille_abi(a);
  abi* file = malloc(n * sizeof(abi));
  file[0] = a;
  int i = 0;
  int ind = 1;
  while (i < n)
  {
    printf("%d ", file[i].etiquette);
    if (file[i].fg != NULL)
    {
      file[ind] = *file[i].fg;
      ind += 1;
    }
    if (file[i].fd != NULL)
    {
      file[ind] = *file[i].fd;
      ind += 1;
    }
    i += 1;
  }
  printf("\n");
  free(file);
}

// Exercice 9

int* ppp_tab(ai a)
{
  int n = taille_ai(a);
  int* rep = malloc(n * sizeof(int));
  int ind = 0;
  void aux(ai arb)
  {
    rep[ind] = arb.etiq;
    ind += 1;
    for (int i = 0 ; i < arb.nb_fils ; i += 1)
    {
      aux(arb.fils[i]);
    }
  }
  aux(a);
  return rep;
}

int* pps_tab(ai a)
{
  int n = taille_ai(a);
  int* rep = malloc(n * sizeof(int));
  int ind = 0;
  void aux(ai arb)
  {
    ind += 1;
    for (int i = 0 ; i < arb.nb_fils ; i += 1)
    {
      aux(arb.fils[i]);
    }
    rep[ind] = arb.etiq;
  }
  aux(a);
  return rep;
}

int* pl_tab(ai a)
{
  int n = taille_ai(a);
  int* rep = malloc(n * sizeof(int));
  ai* file = malloc(n * sizeof(ai));
  file[0] = a;
  int i = 0;
  int ind = 1;
  while (i < n)
  {
    rep[i] = file[i].etiq;
    for (int j = 0 ; j < file[i].nb_fils ; j += 1)
    {
      file[ind] = file[i].fils[j];
      ind += 1;
    }
    i += 1;
  }
  free(file);
  return rep;
}

int* pppb_tab(abi a)
{
  int n = taille_abi(a);
  int* rep = malloc(n * sizeof(int));
  int ind = 0;
  void aux(abi arb)
  {
    rep[ind] = arb.etiquette;
    ind += 1;
    if (arb.fg != NULL) aux(*arb.fg);
    if (arb.fd != NULL) aux(*arb.fd);
  }
  aux(a);
  return rep;
}

int* ppib_tab(abi a)
{
  int n = taille_abi(a);
  int* rep = malloc(n * sizeof(int));
  int ind = 0;
  void aux(abi arb)
  {
    if (arb.fg != NULL) aux(*arb.fg);
    rep[ind] = arb.etiquette;
    ind += 1;
    if (arb.fd != NULL) aux(*arb.fd);
  }
  aux(a);
  return rep;
}

int* ppsb_tab(abi a)
{
  int n = taille_abi(a);
  int* rep = malloc(n * sizeof(int));
  int ind = 0;
  void aux(abi arb)
  {
    if (arb.fg != NULL) aux(*arb.fg);
    if (arb.fd != NULL) aux(*arb.fd);
    rep[ind] = arb.etiquette;
    ind += 1;
  }
  aux(a);
  return rep;
}

int* plb_tab(abi a)
{
  int n = taille_abi(a);
  abi* file = malloc(n * sizeof(abi));
  int* rep = malloc(n * sizeof(int));
  file[0] = a;
  int i = 0;
  int ind = 1;
  while (i < n)
  {
    rep[i] = file[i].etiquette;
    if (file[i].fg != NULL)
    {
      file[ind] = *file[i].fg;
      ind += 1;
    }
    if (file[i].fd != NULL)
    {
      file[ind] = *file[i].fd;
      ind += 1;
    }
    i += 1;
  }
  free(file);
  return rep;
}

// Exercice 10 en OCaml

int main()
{
  abi a3 = { .etiquette = 3, .fg = NULL, .fd = NULL };
  abi a4 = { .etiquette = 4, .fg = NULL, .fd = NULL };
  abi a6 = { .etiquette = 6, .fg = NULL, .fd = NULL };
  abi a7 = { .etiquette = 7, .fg = NULL, .fd = NULL };
  abi a2 = { .etiquette = 2, .fg = &a3, .fd = &a4 };
  abi a5 = { .etiquette = 5, .fg = &a6, .fd = &a7 };
  abi a1 = { .etiquette = 1, .fg = &a2, .fd = &a5 };

  printf("Taille de l'arbre enraciné en a1 : %d.\n", taille_abi(a1));

  printf("Somme des étiquettes de l'arbre enraciné en a1 : %d.\n", somme_abi(a1));

  printf("Minimum de l'arbre enraciné en a1 : %d.\n", min_abi(a1));

  printf("Hauteur de l'arbre enraciné en a1 : %d.\n", hauteur_abi(a1));

  printf("Le nombre de formes d'arbres binaires de taille 5 est %d.\n", nb_abi(5));

  abi** toutes_rep = tous_abi(5);

  printf("Bon, on n'a rien prévu pour imprimer, mais toutes_rep est bien créé.\n");

  for (int i = 0 ; i <= 5 ; i += 1)
  {
    free(toutes_rep[i]);
  }
  free(toutes_rep);

  printf("Liste des étiquettes de l'arbre enraciné en a1 (parcours en profondeur préfixe) :\n");

  int* l = pppb_tab(a1);
  int n = taille_abi(a1);
  for (int i = 0 ; i < n ; i += 1)
  {
    printf("%d ", l[i]);
  }
  printf("\n");

  free(l);

  return 0;
}

/*
Bonus : programme qui fait les exercices 1 à 4 en une fois, trouvé par Philippe S. en 2024
*/

// f combine le résultat du sous-arbre gauche et celui du sous-arbre de droite avec l'étiquette de l'arbre
// def est une valeur par défaut qui sera attribuée à un arbre vide
int work(BinTree *bt, int def, int(*f)(int, int, int)) {
    if (bt == NULL) return def;
    int left_res = work(bt -> left, def, f);
    int right_res = work(bt -> right, def, f);
    return f(bt -> label, left_res, right_res);
}

int ex1(int _, int left, int right) {
    return left + right + 1;
}

int ex2(int label, int left, int right) {
    return label + left + right;
}

int ex3(int label, int left, int right) {
    return min(label, min(left, right));
}

int ex4(int _, int left, int right) {
    return max(left + 1, right + 1);
}

int main() {
    /*
                    2                   
              3           4            
          5                             
            6                           
          7                             
    */
    BinTree lcccc = { .label = 7, .left = NULL, .right = NULL };
    BinTree rccc = { .label = 6, .left = &lcccc, .right = NULL };
    BinTree lcc = { .label = 5, .left = NULL, .right = &rccc };
    BinTree lc = { .label = 3, .left = &lcc, .right = NULL };
    BinTree rc = { .label = 4, .left = NULL, .right = NULL };
    BinTree tree = { .label = 2, .left = &lc, .right = &rc };
    int size = work(&tree, 0, &ex1);
    printf("Taille de l'arbre : %d\n", size);
    
    int sum = work(&tree, 0, &ex2);
    printf("Somme des étiquettes de l'arbre : %d\n", sum);

    int min_label = work(&tree, 2147483647, &ex3);
    printf("Etiquette minimale : %d\n", min_label);

    int height = work(&tree, -1, &ex4);
    printf("Hauteur de l'arbre : %d\n", height);
}