#include #include #include #include #include "ensemble.h" #include "vecteur_extensible.h" enum { TAILLE_INITIALE = 56 }; struct ensemble { void **elements; size_t cardinal; vex delta; enum { NORMALISE, AUGMENTE, RESTREINT } etat; }; static int compare_adresse (const void *a, const void *b); static void trier (void **elements, size_t cardinal); static void difference (void ***res, size_t * card_res, void **a, size_t card_a, void **b, size_t card_b); static void reunion (void ***res, size_t * card_res, void **a, size_t card_a, void **b, size_t card_b); static void ens_normaliser (ensemble e); ensemble ens_creer () { ensemble e = malloc (sizeof (struct ensemble)); assert (e != NULL); e->elements = NULL; e->cardinal = 0; e->delta = vex_creer (TAILLE_INITIALE, 2, realloc); e->etat = NORMALISE; return e; } void ens_detruire (ensemble e) { assert (e != NULL); realloc (e->elements, 0); vex_detruire (e->delta); free (e); } void ens_ajouter (ensemble e, void *elt) { assert (e != NULL); if (e->etat == RESTREINT) ens_normaliser (e); vex_ajouter_element (e->delta, elt); e->etat = AUGMENTE; } void ens_supprimer (ensemble e, void *elt) { assert (e != NULL); if (e->etat == AUGMENTE) ens_normaliser (e); vex_ajouter_element (e->delta, elt); e->etat = RESTREINT; } int ens_appartient (ensemble e, void *elt) { assert (e != NULL); ens_normaliser (e); return bsearch (&elt, e->elements, e->cardinal, sizeof (void *), compare_adresse) != NULL; } ensemble ens_union (ensemble a, ensemble b) { ensemble e; assert (a != NULL && b != NULL); ens_normaliser (a); ens_normaliser (b); e = ens_creer (); reunion (&e->elements, &e->cardinal, a->elements, a->cardinal, b->elements, b->cardinal); return e; } ensemble ens_difference (ensemble a, ensemble b) { ensemble e; assert (a != NULL && b != NULL); ens_normaliser (a); ens_normaliser (b); e = ens_creer (); difference (&e->elements, &e->cardinal, a->elements, a->cardinal, b->elements, b->cardinal); return e; } ensemble ens_instersection (ensemble a, ensemble b) { ensemble e; assert (a != NULL && b != NULL); ens_normaliser (a); ens_normaliser (b); e = ens_creer (); e->elements = malloc ((a->cardinal > b->cardinal ? b->cardinal : a->cardinal) * sizeof (void *)); { size_t i, j, p; for (i = j = p = 0; i < a->cardinal && j < b->cardinal;) if (a->elements[i] == b->elements[j]) { e->elements[p] = a->elements[i]; p++, i++, j++; } else if (a->elements[i] > b->elements[j]) j++; else i++; e->cardinal = p; } e->elements = realloc (e->elements, e->cardinal * sizeof (void *)); return e; } static void ens_normaliser (ensemble e) { void **delta, **norme; size_t nb_delta, nb_norme; if (e->etat == NORMALISE) return; nb_delta = vex_cardinal (e->delta); delta = vex_vers_vecteur (e->delta); trier (delta, nb_delta); if (e->etat == RESTREINT) difference (&norme, &nb_norme, e->elements, e->cardinal, delta, nb_delta); else reunion (&norme, &nb_norme, e->elements, e->cardinal, delta, nb_delta); free (e->elements); free (delta); e->elements = norme; e->cardinal = nb_norme; e->delta = vex_creer (TAILLE_INITIALE, 2, realloc); e->etat = NORMALISE; } static int compare_adresse (const void *a, const void *b) { return (*(void **) a > *(void **) b) - (*(void **) b > *(void **) a); } static void trier (void **elements, size_t cardinal) { qsort (elements, cardinal, sizeof (void *), compare_adresse); } static void difference (void ***res, size_t * card_res, void **a, size_t card_a, void **b, size_t card_b) { size_t i, j, p; *res = malloc (card_a * (sizeof (void *))); for (i = j = p = 0; i < card_a && j < card_b;) if (a[i] == b[j]) i++, j++; else if (a[i] > b[j]) j++; else (*res)[p++] = a[i++]; if (i < card_a) { memcpy (*res + p, a + i, (card_a - i) * (sizeof (void *))); *card_res = p + card_a - i; } else *card_res = p; *res = realloc (*res, *card_res * sizeof (void *)); } static void reunion (void ***res, size_t * card_res, void **a, size_t card_a, void **b, size_t card_b) { size_t i, j, p; *res = malloc ((card_a + card_b) * (sizeof (void *))); for (i = j = p = 0; i < card_a && j < card_b; p++) { if (a[i] > b[j]) (*res)[p] = b[j++]; else { (*res)[p] = a[i]; if (a[i] == b[j]) j++; i++; } } if (i < card_a) { memcpy (*res + p, a + i, (card_a - i) * (sizeof (void *))); *card_res = p + card_a - i; } else if (j < card_b) { memcpy (*res + p, b + j, (card_b - j) * (sizeof (void *))); *card_res = p + card_b - j; } else *card_res = p; *res = realloc (*res, *card_res * sizeof (void *)); } int ens_cardinal (ensemble e) { assert (e != NULL); ens_normaliser (e); return e->cardinal; }