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

struct grapho { char* sommets; char* arcs; };
typedef struct grapho graphe_oriente;


struct m_l_c_s { int sommet; struct m_l_c_s* suivant; };
typedef struct m_l_c_s mlcs;

struct l_c_s { mlcs* tete; };
typedef struct l_c_s lcs;

struct grapho_l_a { int nb_sommets; lcs* liste_adj; };
typedef struct grapho_l_a graphe_oriente_liste_adjacence;


struct grapho_m_a { int nb_sommets; bool** matrice_adj; };
typedef struct grapho_m_a graphe_oriente_matrice_adjacence;

// Fonctions utiles

int est_mot(char* s, char* m)
{
  int n = strlen(s);
  int stop = 0;
  for (int i = 0 ; i <= n ; i += 1)
  {
    if (s[i] == ' ' || i == n)
    {
      char* buff = malloc(i-stop+1);
      for (int j = stop ; j < i ; j += 1) buff[j-stop] = s[j];
      buff[i-stop] = '\0';
      if (strcmp(m, buff) == 0)
      {
        free(buff);
        return stop;
      }
      free(buff);
      stop = i+1;
    }
  }
  return -1;
}

void free_lcs(lcs l)
{
  mlcs* p = l.tete;
  while (p != NULL)
  {
    mlcs* suiv = p->suivant;
    free(p);
    p = suiv;
  }
}

// Exercice 1

// Première représentation

int est_sommet1(graphe_oriente g, char* s)
{
  return est_mot(g.sommets, s);
}

void ajoute_sommet1(graphe_oriente* g, char* s)
{
  assert (est_sommet1(*g, s) == -1);
  int ns = strlen(g->sommets);
  if (ns == 0) ns -= 1; // compenser l'espace comptée en trop (cf. le 2 de la ligne suivante)
  char* nv_s = malloc(strlen(g->sommets) + strlen(s) + 2);
  if (g->sommets[0] == '\0') strcpy(nv_s, s);
  else sprintf(nv_s, "%s %s", g->sommets, s);
  free(g->sommets);
  g->sommets = nv_s;
}

int main_1_1()
{
  char s[] = "a b c d";
  char* s_malloc = malloc(8);
  strcpy(s_malloc, s);
  char a[] = "a-b a-c b-c c-d d-a";
  char* a_malloc = malloc(20);
  strcpy(a_malloc, a);
  graphe_oriente g = { .sommets = s_malloc, .arcs = a_malloc };
  ajoute_sommet1(&g, "e");
  printf("Nouvelle chaine pour les sommets : %s.\n", g.sommets);

  free(g.sommets);
  free(g.arcs);

  return 0;
}

// Deuxième représentation

void ajoute_sommet2(graphe_oriente_liste_adjacence* g)
{
  g->nb_sommets += 1;
  lcs* nv_sommets = malloc(g->nb_sommets * sizeof(lcs));
  for (int i = 0 ; i < g->nb_sommets - 1 ; i += 1)
  {
    nv_sommets[i] = g->liste_adj[i];
  }
  nv_sommets[g->nb_sommets - 1].tete = NULL;
  free(g->liste_adj);
  g->liste_adj = nv_sommets;
}

int main_1_2()
{
  mlcs ac = { .sommet = 2 , .suivant = NULL };
  mlcs ab = { .sommet = 1 , .suivant = &ac };
  mlcs bc = { .sommet = 2 , .suivant = NULL };
  mlcs cd = { .sommet = 3 , .suivant = NULL };
  mlcs da = { .sommet = 0 , .suivant = NULL };
  lcs* l = malloc(4 * sizeof(lcs));
  l[0].tete = &ab;
  l[1].tete = &bc;
  l[2].tete = &cd;
  l[3].tete = &da;
  graphe_oriente_liste_adjacence g = { .nb_sommets = 4 , .liste_adj = l };
  ajoute_sommet2(&g);

  free(g.liste_adj);

  return 0;
}

// Troisième représentation


// Exercice 2

// Première représentation

int est_arc1(graphe_oriente g, char* s, char* t)
{
  char* st = malloc(strlen(s) + strlen(t) + 2);
  sprintf(st, "%s-%s", s, t);
  int rep = est_mot(g.arcs, st);
  free(st);
  return rep;
}

void ajoute_arc1(graphe_oriente* g, char* s, char* t)
{
  if (est_sommet1(*g, s) == -1) ajoute_sommet1(g, s);
  if (est_sommet1(*g, t) == -1) ajoute_sommet1(g, t);
  assert(est_arc1(*g, s, t) == -1);
  int na = strlen(g->arcs);
  if (na == 0) na -= 1; // compenser l'espace comptée en trop (cf. le 3 de la ligne suivante)
  char* nv_a = malloc(na + strlen(s) + strlen(t) + 3);
  if (g->arcs[0] == '\0') sprintf(nv_a, "%s-%s", s, t);
  else sprintf(nv_a, "%s %s-%s", g->arcs, s, t);
  free(g->arcs);
  g->arcs = nv_a;
}

int main_2_1()
{
  char s[] = "a b c d";
  char* s_malloc = malloc(8);
  strcpy(s_malloc, s);
  char a[] = "a-b a-c b-c c-d d-a";
  char* a_malloc = malloc(20);
  strcpy(a_malloc, a);
  graphe_oriente g = { .sommets = s_malloc, .arcs = a_malloc };
  ajoute_arc1(&g, "d", "e");
  ajoute_arc1(&g, "d", "b");
  printf("Nouvelle chaine pour les sommets : %s.\n", g.sommets);
  printf("Nouvelle chaine pour les arcs : %s.\n", g.arcs);

  free(g.sommets);
  free(g.arcs);

  return 0;
}

// Deuxième représentation

void ajoute_arc2(graphe_oriente_liste_adjacence* g, int s, int t)
{
  assert (0 <= s && s < g->nb_sommets && 0 <= t && t < g->nb_sommets);
  mlcs* p = g->liste_adj[s].tete;
  if (p == NULL)
  {
    g->liste_adj[s].tete = malloc(sizeof(mlcs));
    g->liste_adj[s].tete->sommet = t;
    g->liste_adj[s].tete->suivant = NULL;
    return;
  }
  while (p->suivant != NULL)
  {
    assert (p->sommet != t);
    p = p->suivant;
  }
  assert(p->sommet != t);
  p->suivant = malloc(sizeof(mlcs));
  p->suivant->sommet = t;
  p->suivant->suivant = NULL;
}

int main_2_2()
{
  mlcs* ac = malloc(sizeof(mlcs));
  ac->sommet = 2;
  ac->suivant = NULL;
  mlcs* ab = malloc(sizeof(mlcs));
  ab->sommet = 1;
  ab->suivant = ac;
  mlcs* bc = malloc(sizeof(mlcs));
  bc->sommet = 2;
  bc->suivant = NULL;
  mlcs* cd = malloc(sizeof(mlcs));
  cd->sommet = 3;
  cd->suivant = NULL;
  mlcs* da =  malloc(sizeof(mlcs));
  da->sommet = 0;
  da->suivant = NULL;
  lcs* l = malloc(4 * sizeof(lcs));
  l[0].tete = ab;
  l[1].tete = bc;
  l[2].tete = cd;
  l[3].tete = da;
  graphe_oriente_liste_adjacence g = { .nb_sommets = 4 , .liste_adj = l };
  ajoute_arc2(&g, 3, 1);
  printf("Deuxième successeur de 3 dans g : %d.\n", g.liste_adj[3].tete->suivant->sommet);

  for (int i = 0 ; i < 4 ; i += 1) free_lcs(g.liste_adj[i]);
  free(g.liste_adj);

  return 0;
}

// Troisième représentation


// Exercice 3

// Première représentation

void retire_arc1(graphe_oriente* g, char* s, char* t)
{
  int pos = est_arc1(*g, s, t);
  int ns = strlen(s);
  int nt = strlen(t);
  assert (est_sommet1(*g, s) != -1 && est_sommet1(*g, t) != -1 && pos != -1);
  int nv_taille = strlen(g->arcs) - ns - nt - 1; // strlen + 1 pour le \0 puis - ns - nt - 1
  if (nv_taille == -1)
  {
    char* nv_a = malloc(1);
    nv_a[0] = '\0';
    free(g->arcs);
    g->arcs = nv_a;
    return;
  }
  char* nv_a = malloc(nv_taille);
  for (int i = 0 ; i < pos ; i += 1) nv_a[i] = g->arcs[i];
  if (g->arcs[pos + ns + nt + 1] == '\0')
  {
    nv_a[pos-1] = '\0';
  }
  else
  {
    int ind = pos;
    for (int i = pos + ns + nt + 2 ; g->arcs[i] != '\0' ; i += 1)
    {
      nv_a[ind] = g->arcs[i];
      ind += 1;
    }
    nv_a[ind] = '\0';
  }
  free(g->arcs);
  g->arcs = nv_a;
}

int main_3_1()
{
  char s[] = "a b c d";
  char* s_malloc = malloc(8);
  strcpy(s_malloc, s);
  char a[] = "a-b a-c b-c c-d d-a";
  char* a_malloc = malloc(20);
  strcpy(a_malloc, a);
  graphe_oriente g = { .sommets = s_malloc, .arcs = a_malloc };
  retire_arc1(&g, "d", "a");
  retire_arc1(&g, "a", "b");
  printf("Nouvelle chaine pour les arcs : %s.\n", g.arcs);

  free(g.sommets);
  free(g.arcs);

  return 0;
}

// Deuxième représentation

// Troisième représentation


// Exercice 4

// Première représentation

void retire_sommet1(graphe_oriente* g, char* s)
{
  int pos = est_sommet1(*g, s);
  assert (pos != -1);
  int ns = strlen(s);
  int nv_taille = strlen(g->sommets) - ns; // + 1 - 1 donc
  if (nv_taille == -1)
  {
    char* nv_s = malloc(1);
    nv_s[0] = '\0';
    free(g->sommets);
    g->sommets = nv_s;
    return;
  }
  char* nv_s = malloc(nv_taille);
  for (int i = 0 ; i < pos ; i += 1) nv_s[i] = g->sommets[i];
  if (g->sommets[pos + ns] == '\0')
  {
    nv_s[pos-1] = '\0';
  }
  else
  {
    int ind = pos;
    for (int i = pos + ns + 1 ; g->sommets[i] != '\0' ; i += 1)
    {
      nv_s[ind] = g->sommets[i];
      ind += 1;
    }
    nv_s[ind] = '\0';
  }
  free(g->sommets);
  g->sommets = nv_s;
  int na = strlen(g->arcs);
  char* nv_a_trop_gros = malloc(na + 1);
  int ind_nv_a = 0;
  int ind_deb = 0;
  int ind_tiret;
  for (int i = 0 ; i <= na ; i += 1)
  {
    if (g->arcs[i] == '-') ind_tiret = i;
    else if (g->arcs[i] == ' ' || g->arcs[i] == '\0')
    {
      char* ori = malloc(ind_tiret - ind_deb + 1);
      for (int ind = ind_deb ; ind < ind_tiret ; ind += 1) ori[ind - ind_deb] = g->arcs[ind];
      ori[ind_tiret - ind_deb] = '\0';
      char* dest = malloc(i - ind_tiret);
      for (int ind = ind_tiret + 1 ; ind < i ; ind += 1) dest[ind - ind_tiret - 1] = g->arcs[ind];
      dest[i - ind_tiret - 1] = '\0';
      if (strcmp(ori, s) != 0 && strcmp(dest, s) != 0)
      {
        for (int ind = ind_deb ; ind < i ; ind += 1)
        {
          nv_a_trop_gros[ind_nv_a] = g->arcs[ind];
          ind_nv_a += 1;
        }
        nv_a_trop_gros[ind_nv_a] = ' ';
        ind_nv_a += 1;
      }
      free(ori);
      free(dest);
      ind_deb = i+1;
    }
  }
  if (ind_nv_a > 0) ind_nv_a -= 1;
  char* nv_a = malloc(ind_nv_a + 1);
  for (int i = 0 ; i < ind_nv_a ; i += 1) nv_a[i] = nv_a_trop_gros[i];
  nv_a[ind_nv_a] = '\0';
  free(nv_a_trop_gros);
  free(g->arcs);
  g->arcs = nv_a;
}

int main_4_1()
{
  char s[] = "a b c d";
  char* s_malloc = malloc(8);
  strcpy(s_malloc, s);
  char a[] = "a-b a-c b-c c-d d-a";
  char* a_malloc = malloc(20);
  strcpy(a_malloc, a);
  graphe_oriente g = { .sommets = s_malloc, .arcs = a_malloc };
  retire_sommet1(&g, "c");
  printf("Nouvelle chaine pour les sommets : %s.\n", g.sommets);
  printf("Nouvelle chaine pour les arcs : %s.\n", g.arcs);

  free(g.sommets);
  free(g.arcs);

  return 0;
}

// Deuxième représentation

// Troisième représentation


int main()
{
  int zero = main_2_2();
  exit(zero);
}