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

// Exercice 1

struct t_r_i { int taille; int capacite; int* donnees; };
typedef struct t_r_i itr;

itr creer_itr(int capacite)
{
  assert(capacite > 0);
  itr t = { .taille = 0, .capacite = capacite, .donnees = malloc(capacite * sizeof(int)) };
  return t;
}

int taille_itr(itr t) // Sera utile ultérieurement
{
  return t.taille;
}

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

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

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

void append_itr(itr* t, int x)
{
  if (t->taille == t->capacite) redimensionne_itr(t);
  t->donnees[t->taille] = x;
  t->taille += 1;
}

int pop_itr(itr* t)
{
  assert(t->taille > 0);
  int rep = t->donnees[t->taille-1];
  t->taille -= 1;
  return rep;
}

// Exercice 2 en OCaml

// Exercice 3

struct m_l_c_i { int valeur; struct m_l_c_i* suivant; };
typedef struct m_l_c_i milc;

struct l_c_i { milc* debut; };
typedef struct l_c_i ilc;

ilc creer_ilc()
{
  ilc l = { .debut = NULL };
  return l;
}

milc* tete_ilc(ilc l)
{
  return l.debut;
}

milc* suivant_ilc(milc m)
{
  return m.suivant;
}

void inserer_ilc(ilc* l, milc* m, int x)
{
  milc* p = l->debut;
  if (p == m)
  {
    milc* xm = malloc(sizeof(milc));
    xm->valeur = x;
    xm->suivant = m;
    l->debut = xm;
    return;
  }
  while (p != NULL && p->suivant != m)
  {
    p = p->suivant;
  }
  assert(p != NULL);
  milc* xm = malloc(sizeof(milc));
  xm->valeur = x;
  xm->suivant = m;
  p->suivant = xm;
}

void retirer_ilc(ilc* l, milc* m)
{
  assert(m != NULL);
  milc* p = l->debut;
  if (p == m)
  {
    l->debut = m->suivant;
    free(m);
    return;
  }
  while (p != NULL && p->suivant != m)
  {
    p = p->suivant;
  }
  assert(p != NULL);
  p->suivant = m->suivant;
  free(m);
}

int acceder_ilc(milc m)
{
  return m.valeur;
}

void modifier_ilc(milc* m, int x)
{
  m->valeur = x;
}

void inserer_tete_ilc(ilc* l, int x)
{
  milc* xm = malloc(sizeof(milc));
  xm->valeur = x;
  xm->suivant = l->debut;
  l->debut = xm;
}

int retirer_tete_ilc(ilc* l)
{
  assert (l->debut != NULL);
  milc* p = l->debut;
  int rep = p->valeur;
  l->debut = p->suivant;
  free(p);
  return rep;
}

void inserer_fond_ilc(ilc* l, int x)
{
  milc* xm = malloc(sizeof(milc));
  xm->valeur = x;
  xm->suivant = NULL;
  milc* p = l->debut;
  if (p == NULL)
  {
    l->debut = xm;
    return;
  }
  while (p->suivant != NULL)
  {
    p = p->suivant;
  }
  p->suivant = xm;
}

int retirer_fond_ilc(ilc* l)
{
  assert (l->debut != NULL);
  milc* p = l->debut;
  int rep;
  if (p->suivant == NULL)
  {
    rep = p->valeur;
    l->debut = NULL;
    free(p);
    return rep;
  }
  while ((p->suivant)->suivant != NULL) // Parenthèses pas forcément nécessaires… à vérifier
  {
    p = p->suivant;
  }
  rep = (p->suivant)->valeur;
  free(p->suivant);
  p->suivant = NULL;
  return rep;
}

// Exercice 4

itr creer_ilc_itr(int estimation_capacite)
{
  return creer_itr(estimation_capacite);
}

void inserer_ilc_itr(itr* t, int indice, int x)
{
  int n = taille_itr(*t);
  assert(0 <= indice && indice <= n); // Si ==, insertion à la fin
  if (n == 0)
  {
    append_itr(t, x);
    return;
  }
  append_itr(t, acces_itr(*t, n-1));
  for (int i = t->taille-1; i > indice; i-= 1)
  {
    modif_itr(*t, i, acces_itr(*t, i-1));
  }
  modif_itr(*t, indice, x);
}

void retirer_ilc_itr(itr* t, int indice)
{
  int n = taille_itr(*t);
  assert(0 <= indice && indice < n);
  for (int i = indice ; i < n-1 ; i += 1)
  {
    modif_itr(*t, i, acces_itr(*t, i+1));
  }
  pop_itr(t);
}

int acceder_ilc_itr(itr t, int indice)
{
  int n = taille_itr(t);
  assert(0 <= indice && indice < n); // Parce que rien ne garantit que l'implémentation future vérifiera encore
  return acces_itr(t, indice);
}

void modifier_ilc_itr(itr t, int indice, int x)
{
  int n = taille_itr(t);
  assert(0 <= indice && indice < n); // Parce que rien ne garantit que l'implémentation future vérifiera encore
  modif_itr(t, indice, x);
}

void inserer_tete_ilc_itr(itr* t, int x)
{
  inserer_ilc_itr(t, 0, x);
}

int retirer_tete_ilc_itr(itr* t)
{
  int rep = acceder_ilc_itr(*t, 0);
  retirer_ilc_itr(t, 0);
  return rep;
}

void inserer_fond_ilc_itr(itr* t, int x)
{
  inserer_ilc_itr(t, taille_itr(*t), x);
}

int retirer_fond_ilc_itr(itr* t)
{
  int n = taille_itr(*t);
  int rep = acceder_ilc_itr(*t, n-1);
  retirer_ilc_itr(t, n-1);
  return rep;
}

// Exercice 5 en OCaml

// Exercice 6 en Ocaml

// Exercice 7

int* creer_pileb(int capacite)
{
  int* p = malloc((capacite+1) * sizeof(int));
  p[0] = 0;
  return p;
}

void empiler_pileb(int* p, int capacite, int x)
{
  assert(p[0] < capacite);
  p[0] += 1;
  p[p[0]] = x;
}

int depiler_pileb(int* p)
{
  assert(p[0] > 0);
  int reponse = p[p[0]];
  p[0] -= 1;
  return reponse;
}

bool est_vide_pileb(int* p)
{
  return p[0] == 0;
}

// Exercice 8

ilc creer_pile()
{
  return creer_ilc();
}

void empiler_pile(ilc* p, int x)
{
  inserer_tete_ilc(p, x);
}

int depiler_pile(ilc* p)
{
  return retirer_tete_ilc(p);
}

bool est_vide_pile(ilc p)
{
  return p.debut == NULL;
}

// Exercice 9 en OCaml

// Exercice 10 en OCaml

int main()
{
  // Faire les tests qu'on souhaite…
  return 0;
}