#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct collection {
  int n;
  int* t;
};

struct collection creerCollectionVide(void) {
  struct collection c;
  c.n = 0;
  c.t = NULL;
  return c;
};

void afficherCollection(struct collection c) {
  printf("%d valeur(s) :", c.n);
  for (int i = 0; i < c.n; i++) {
    printf(" %d", c.t[i]);
  }
  printf("\n");
}

void viderCollection(struct collection* c) {
  if (c->t != NULL) {
    free(c->t);
    c->t = NULL;
  }
  c->n = 0;
}

bool creerCollection(struct collection* c, int n, int max) {
  viderCollection(c);
  c->n = n;
  c->t = (int*) calloc(n, sizeof(int));
  if (c->t == NULL) {
    c->n = 0;
    return false;
  }
  else {
    for (int i = 0; i < n; i++) {
      c->t[i] = 1 + rand() % max;
    }
    return true;
  }
}

bool etreVide(struct collection* c) {
  return c->n == 0;
}

bool exister(int val, int* t, int indi, int indf) {
  bool res = false;
  int i = indi;
  while ((i <= indf) && ((res = (t[i] == val)) == false)) {
    i++;
  }
  return res;
}

bool etreEnsemble(struct collection* c) {
  if (c->n <= 1) {
    return true;
  }
  bool res = true;
  int i = 0;
  do {
    if (exister(c->t[i], c->t, i + 1, c->n - 1)) {
      res = false;
    }
    i++;
  } while (i < c->n - 1);
  return res;
}

bool etreInclus(int val, struct collection c) {
  return exister(val, c.t, 0, c.n - 1);
}

int chercherIndice(int val, struct collection c) {
  bool trouve = false;
  int i = 0;
  while ((i <= c.n - 1) && ((trouve = (c.t[i] == val)) == false)) {
    i++;
  }
  if (trouve == false) {
    return -1;
  }
  return i;
}

bool ajouterEntier(int val, struct collection* c) {
  if (etreInclus(val, *c) == true) {
    return false;
  }
  int* nt = (int*) realloc(c->t, (c->n + 1) * sizeof(int));
  if (nt == NULL) {
    return false;
  }
  nt[c->n] = val;
  c->n++;
  c->t = nt;
  return true;
}

bool retirerEntier(int val, struct collection* c) {
  int ind = chercherIndice(val, *c);
  if (ind == -1) {
    return false;
  }
  if (c->n == 1) {
    free(c->t);
    c->t = NULL;
    c->n = 0;
    return true;
  }
  if (ind != c->n - 1) {
    int aux = c->t[ind];
    c->t[ind] = c->t[c->n - 1];
    c->t[c->n - 1] = aux;
  }
  int* nt = (int*) realloc(c->t, (c->n - 1) * sizeof(int));
  if (nt == NULL) {
    return false;
  }
  c->n--;
  c->t = nt;
  return true;
}

bool creerCopie(struct collection e, struct collection* resultat) {
  viderCollection(resultat);
  int i = 0;
  bool onGo = true;
  while ((i < e.n) && (onGo == true)) {
    if (ajouterEntier(e.t[i], resultat) == false) {
      onGo = false;
      viderCollection(resultat);
    }
    i++;
  }
  return onGo;
}

bool calculerSoustraction(struct collection e1, struct collection e2, struct collection* resultat) {
  viderCollection(resultat);
  int i = 0;
  bool onGo = true;
  while ((i < e1.n) && (onGo == true)) {
    if (etreInclus(e1.t[i], e2) == false) {
      if (ajouterEntier(e1.t[i], resultat) == false) {
        onGo = false;
        viderCollection(resultat);
      }
    }
    i++;
  }
  return onGo;
}

bool calculerUnion(struct collection e1, struct collection e2, struct collection* resultat) {
  viderCollection(resultat);
  if (creerCopie(e1,resultat) == false) {
    return false;
  }
  struct collection s = creerCollectionVide();
  if (calculerSoustraction(e2, e1, &s) == false) {
    viderCollection(resultat);
    return false;
  }
  int i = 0;
  bool onGo = true;
  while ((i < s.n) && (onGo == true)) {
      if (ajouterEntier(s.t[i], resultat) == false) {
        onGo = false;
        viderCollection(resultat);
        viderCollection(&s);
      }
    i++;
  }
  viderCollection(&s);
  return onGo;
}

bool calculerIntersection(struct collection e1, struct collection e2, struct collection* resultat) {
  viderCollection(resultat);
  int i = 0;
  bool onGo = true;
  while ((i < e1.n) && (onGo == true)) {
    if (etreInclus(e1.t[i], e2) == true) {
      if (ajouterEntier(e1.t[i], resultat) == false) {
        onGo = false;
        viderCollection(resultat);
      }
    }
    i++;
  }
  return onGo;
}

void testerCreationVide(void) {
  struct collection col = creerCollectionVide();
  printf("Collection vide cree\n");
  viderCollection(&col);
  printf("Collection vide videe (!)\n");
  printf("\n");
}

void testerCreationNonVide(void) {
  struct collection col;
  const int MAX = 100;
  if (creerCollection(&col, 20, MAX) == true) {
    printf("Collection cree\n");
    afficherCollection(col);
    for (int i = 1; i <= MAX; i++) {
      if (etreInclus(i, col) == true) {
        printf("%3d", i);
      }
    }
    printf("\n");
    if (etreEnsemble(&col) == true) {
      printf("C'est un ensemble\n");
    }
    else {
      printf("Ce n'est pas un ensemble\n");
    }
    viderCollection(&col);
    printf("Collection videe\n");
  }
  printf("\n");
}

void testerAjoutsEtRetraits(void) {
  struct collection col = creerCollectionVide();
  afficherCollection(col);
  int v = 11;
  if (ajouterEntier(v, &col) == true) {
    printf("Ajout de %d reussi\n", v);
  }
  else {
    printf("Ajout de %d ratee\n", v);
  }
  v = -6;
  if (ajouterEntier(v, &col) == true) {
    printf("Ajout de %d reussi\n", v);
  }
  else {
    printf("Ajout de %d ratee\n", v);
  }
  afficherCollection(col);
  v = 2;
  if (ajouterEntier(v, &col) == true) {
    printf("Ajout de %d reussi\n", v);
  }
  else {
    printf("Ajout de %d ratee\n", v);
  }
  afficherCollection(col);
  v = 11;
  if (ajouterEntier(v, &col) == true) {
    printf("Ajout de %d reussi\n", v);
  }
  else {
    printf("Ajout de %d ratee\n", v);
  }
  afficherCollection(col);
  v = 2;
  if (retirerEntier(v, &col) == true) {
    printf("Retrait de %d reussi\n", v);
  }
  else {
    printf("Retrait de %d rate\n", v);
  }
  afficherCollection(col);
  v = -6;
  if (retirerEntier(v, &col) == true) {
    printf("Retrait de %d reussi\n", v);
  }
  else {
    printf("Retrait de %d rate\n", v);
  }
  afficherCollection(col);
  v = 11;
  if (retirerEntier(v, &col) == true) {
    printf("Retrait de %d reussi\n", v);
  }
  else {
    printf("Retrait de %d rate\n", v);
  }
  afficherCollection(col);
  viderCollection(&col);
  printf("Collection videe\n");
  printf("\n");
}

void testerSoustraction(void) {
  struct collection e1 = creerCollectionVide();
  struct collection e2 = creerCollectionVide();
  struct collection res = creerCollectionVide();
  ajouterEntier(3, &e1);
  ajouterEntier(4, &e1);
  ajouterEntier(8, &e1);
  ajouterEntier(-2, &e1);
  ajouterEntier(0, &e1);
  ajouterEntier(-2, &e2);
  ajouterEntier(8, &e2);
  ajouterEntier(9, &e2);
  ajouterEntier(-3, &e2);
  printf("e1      : ");
  afficherCollection(e1);
  printf("e2      : ");
  afficherCollection(e2);
  calculerSoustraction(e1, e2, &res);
  printf("e1 - e2 : ");
  afficherCollection(res);
  calculerSoustraction(e2, e1, &res);
  printf("e2 - e1 : ");
  afficherCollection(res);
  viderCollection(&e1);
  viderCollection(&e2);
  viderCollection(&res);
  printf("\n");
}

void testerCopie(void) {
  struct collection e = creerCollectionVide();
  struct collection res = creerCollectionVide();
  ajouterEntier(3, &e);
  ajouterEntier(4, &e);
  ajouterEntier(8, &e);
  ajouterEntier(-2, &e);
  ajouterEntier(0, &e);
  ajouterEntier(9, &e);
  ajouterEntier(-3, &e);
  printf("e          : ");
  afficherCollection(e);
  creerCopie(e, &res);
  printf("copie de e : ");
  afficherCollection(res);
  viderCollection(&e);
  viderCollection(&res);
  printf("\n");
}

void testerUnion(void) {
  struct collection e1 = creerCollectionVide();
  struct collection e2 = creerCollectionVide();
  struct collection res = creerCollectionVide();
  ajouterEntier(3, &e1);
  ajouterEntier(4, &e1);
  ajouterEntier(8, &e1);
  ajouterEntier(-2, &e1);
  ajouterEntier(0, &e1);
  ajouterEntier(-2, &e2);
  ajouterEntier(8, &e2);
  ajouterEntier(9, &e2);
  ajouterEntier(-3, &e2);
  printf("e1           : ");
  afficherCollection(e1);
  printf("e2           : ");
  afficherCollection(e2);
  calculerUnion(e1, e2, &res);
  printf("union(e1,e2) : ");
  afficherCollection(res);
  calculerUnion(e2, e1, &res);
  printf("union(e2,e1) : ");
  afficherCollection(res);
  viderCollection(&e1);
  viderCollection(&e2);
  viderCollection(&res);
  printf("\n");
}

void testerIntersection(void) {
  struct collection e1 = creerCollectionVide();
  struct collection e2 = creerCollectionVide();
  struct collection res = creerCollectionVide();
  ajouterEntier(3, &e1);
  ajouterEntier(4, &e1);
  ajouterEntier(8, &e1);
  ajouterEntier(-2, &e1);
  ajouterEntier(0, &e1);
  ajouterEntier(-2, &e2);
  ajouterEntier(8, &e2);
  ajouterEntier(9, &e2);
  ajouterEntier(-3, &e2);
  printf("e1                  : ");
  afficherCollection(e1);
  printf("e2                  : ");
  afficherCollection(e2);
  calculerIntersection(e1, e2, &res);
  printf("intersection(e1,e2) : ");
  afficherCollection(res);
  calculerIntersection(e2, e1, &res);
  printf("intersection(e2,e1) : ");
  afficherCollection(res);
  viderCollection(&e1);
  viderCollection(&e2);
  viderCollection(&res);
  printf("\n");
}

int main(void) {
  testerCreationVide();
  testerCreationNonVide();
  testerAjoutsEtRetraits();
  testerCopie();
  testerSoustraction();
  testerUnion();
  testerIntersection();
  return 0;
}