From fdd5de0c84cbddcc6b31d579d7006773682059ac Mon Sep 17 00:00:00 2001 From: Alex AUVOLAT Date: Mon, 18 Nov 2013 20:01:05 +0100 Subject: Finished implementation of sets with linked lists. --- Makefile | 16 +++--- set_linked_lists.c | 148 +++++++++++++++++++++++++++++++++++++++++------------ set_test.c | 97 +++++++++++++++++++++++++++++++++++ set_treaps.c | 20 ++++++++ sets.c | 41 +++++++++++++++ sets.h | 3 ++ 6 files changed, 286 insertions(+), 39 deletions(-) create mode 100644 set_test.c create mode 100644 sets.c diff --git a/Makefile b/Makefile index 2714366..5dbe549 100644 --- a/Makefile +++ b/Makefile @@ -1,14 +1,16 @@ -all : exe_ll exe_bs exe_tr +all : exe_ll exe_bs exe_tr exe_ll_test -exe_ll : main.c sets.h set_linked_lists.c - gcc -o exe_ll main.c set_linked_lists.c -DLINKEDLISTS +exe_ll : main.c sets.h set_linked_lists.c sets.c + gcc -o exe_ll main.c set_linked_lists.c sets.c -DLINKEDLISTS -g +exe_ll_test : set_test.c sets.h set_linked_lists.c sets.c + gcc -o exe_ll_test set_test.c set_linked_lists.c sets.c -DLINKEDLISTS -g -exe_bs : main.c sets.h set_bitsets.c - gcc -o exe_bs main.c set_bitsets.c -DBITSETS +exe_bs : main.c sets.h set_bitsets.c sets.c + # gcc -o exe_bs main.c set_bitsets.c sets.c -DBITSETS -g -exe_tr : main.c sets.h set_treaps.c - gcc -o exe_tr main.c set_treaps.c -DTREAPS +exe_tr : main.c sets.h set_treaps.c sets.c + # gcc -o exe_tr main.c set_treaps.c sets.c -DTREAPS -g clean : diff --git a/set_linked_lists.c b/set_linked_lists.c index 05ed4ca..56163bf 100644 --- a/set_linked_lists.c +++ b/set_linked_lists.c @@ -1,4 +1,5 @@ #include +#include #include "sets.h" /* Question théorique pertinente : @@ -32,6 +33,9 @@ temps constant ne permet pas de gagner en complexité asymptotique. On fait donc le choix de maintenir une liste triée. + + Seul intérêt de cette implémentation utilisant des listes chaînées : manipuler + des listes chaînées en C, ce qui est autrement plus difficile à faire qu'en ML. */ typedef struct set_elt *element; @@ -43,19 +47,6 @@ set empty_set(int n) { return k; } -set singleton(int n, int x) { - set k = malloc(sizeof(t_set_descriptor)); - - element e = malloc(sizeof(struct set_elt)); - e->value = x; - e->next = NULL; - - k->first = k->last = NULL; - k->size = 1; - - return k; -} - set copy_set(const set s) { element iter, prev; @@ -97,15 +88,88 @@ void delete_set(set s) { } void set_union_ip(set a, const set b) { - //TODO + if (b->size == 0) return; + + element ita = a->first, prev = NULL, itb = b->first; + while (itb != NULL) { + if (ita != NULL && ita->value == itb->value) { + prev = ita; + ita = ita->next; + itb = itb->next; + } else if (ita != NULL && ita->value < itb->value) { + prev = ita; + ita = ita->next; + } else { + // either ita = NULL (we are at end of set a) or itb < ita + // insert element at itb between prev and ita + element e = malloc(sizeof(struct set_elt)); + e->value = itb->value; + e->next = ita; + if (prev == NULL) { + a->first = e; + } else { + prev->next = e; + } + if (e->next == NULL) a->last = e; + a->size++; + prev = e; + itb = itb->next; + } + } } void set_inter_ip(set a, const set b) { - //TODO + element ita = a->first, prev = NULL, itb = b->first, tmp; + while (ita != NULL) { + if (itb != NULL && itb->value == ita->value) { + prev = ita; + ita = ita->next; + itb = itb->next; + } else if (itb != NULL && itb->value < ita->value) { + itb = itb->next; + } else { + // either itb = NULL or element at ita is smaller than that at itb + // in all case, remove element at ita. + if (prev == NULL) { + a->first = ita->next; + } else { + prev->next = ita->next; + } + tmp = ita->next; + if (tmp == NULL) a->last = prev; + free(ita); + ita = tmp; + a->size--; + } + } } void set_diff_ip(set a, const set b) { - //TODO + element ita = a->first, prev = NULL, itb = b->first, tmp; + while (ita != NULL) { + if (itb != NULL && itb->value > ita->value) { + prev = ita; + ita = ita->next; + itb = itb->next; + } else if (itb != NULL && itb->value < ita->value) { + itb = itb->next; + } else if (itb == NULL) { + break; + } else { + // either itb = NULL or element at ita is smaller than that at itb + // in all case, remove element at ita. + if (prev == NULL) { + a->first = ita->next; + } else { + prev->next = ita->next; + } + tmp = ita->next; + if (tmp == NULL) a->last = prev; + free(ita); + ita = tmp; + a->size--; + } + } } bool is_set_empty(const set s) { @@ -123,6 +187,18 @@ bool set_mem(int x, const set s) { return false; } +bool sets_equal(const set a, const set b) { + element ita, itb; + + if (a->size != b->size) return false; + + for (ita = a->first, itb = b->first; ita != NULL; ita = ita->next, itb = itb->next) { + if (ita->value != itb->value) return false; + } + + return true; +} + int elt_of_set(const set s) { if (s->first != NULL) return s->first->value; return -1; // should raise exception... hope this will be handled properly @@ -131,25 +207,23 @@ int elt_of_set(const set s) { void set_add_ip(int x, set s) { element prev, iter, e; - prev = s->first; - if (prev == NULL || x < prev->value) { - e = malloc(sizeof(struct set_elt)); - e->value = x; - e->next = prev; - s->first = e; - } else { - for (iter = prev->next; iter != NULL; iter = iter->next) { - if (iter->value = x) return; // element already in here - if (iter->value > x) break; - prev = iter; - } + prev = NULL; + for (iter = s->first; iter != NULL; iter = iter->next) { + if (iter->value == x) return; // element already in here + if (iter->value > x) break; + prev = iter; + } - e = malloc(sizeof(struct set_elt)); - e->value = x; - e->next = iter; + e = malloc(sizeof(struct set_elt)); + e->value = x; + e->next = iter; + if (prev != NULL) { prev->next = e; + } else { + s->first = e; } - if (e->next == NULL) s->last = e; + if (iter == NULL) s->last = e; + s->size++; } @@ -173,3 +247,13 @@ void set_remove_ip(int x, set s) { prev = iter; } } + +void dump_set(const set s) { + element iter; + printf("["); + + for (iter = s->first; iter != NULL; iter = iter->next) { + printf(" %d ", iter->value); + } + printf("] (%d)\n", s->size); +} diff --git a/set_test.c b/set_test.c new file mode 100644 index 0000000..eca2663 --- /dev/null +++ b/set_test.c @@ -0,0 +1,97 @@ +#include +#include "sets.h" + +int fails = 0; + +#define ASSERT(x) if (!(x)) { fprintf(stderr, "Assert fail: %s\n", #x); fails++; } + +int main() { + set empty = empty_set(1000); + + set s = empty_set(1000); + dump_set(s); + + set_add_ip(42, s); + dump_set(s); + + set k = singleton(1000, 12); + dump_set(k); + + set_add_ip(126, k); + dump_set(k); + + set j = set_add(76, k); + dump_set(j); + + ASSERT(set_mem(76, j)); + ASSERT(set_mem(126, j)); + ASSERT(!set_mem(42, k)); + ASSERT(set_mem(42, s)); + + set r = set_remove(42, s); + ASSERT(!set_mem(42, r)); + ASSERT(is_set_empty(r)); + set_remove_ip(42, s); + ASSERT(!set_mem(42, s)); + ASSERT(is_set_empty(s)); + ASSERT(sets_equal(s, r)); + + set_add_ip(4, r); + set_add_ip(12, r); + set_add_ip(3, r); + set_add_ip(6, r); + printf("A: "); dump_set(r); + + set x = empty_set(1000); + set_union_ip(x, r); + printf("A(copy): "); dump_set(x); + + set_add_ip(3, s); + set_add_ip(7, s); + set_add_ip(4, s); + set_add_ip(1, s); + set_add_ip(2, s); + set_add_ip(4, s); + set_add_ip(7, s); + printf("B: "); dump_set(s); + + set u = set_union(r, s); + printf("AuB: "); dump_set(u); + set d = set_diff(r, s); + printf("A\\B: "); dump_set(d); + set n = set_inter(r, s); + printf("AnB: "); dump_set(n); + + set A = set_inter(empty, r); + set B = set_inter(r, empty); + printf("@nA: "); dump_set(A); + printf("An@: "); dump_set(B); + ASSERT(is_set_empty(A)); + ASSERT(is_set_empty(B)); + set_union_ip(A, r); + printf("@uA: "); dump_set(A); + set C = set_union(r, empty); + printf("Au@: "); dump_set(C); + ASSERT(sets_equal(A, r)); + ASSERT(sets_equal(C, r)); + set_diff_ip(A, empty); + printf("A\\@: "); dump_set(A); + ASSERT(sets_equal(A, r)); + set_diff_ip(C, u); + printf("A\\(AuB): "); dump_set(C); + ASSERT(is_set_empty(C)); + + delete_set(s); + delete_set(k); + delete_set(j); + delete_set(r); + delete_set(u); + delete_set(d); + delete_set(n); + delete_set(empty); + delete_set(A); + delete_set(B); + delete_set(C); + + return fails; +} diff --git a/set_treaps.c b/set_treaps.c index f37773f..365c521 100644 --- a/set_treaps.c +++ b/set_treaps.c @@ -1,3 +1,23 @@ #include "sets.h" +/* + Étude de complexité : + - Ajout d'un élément : O(log n) + - Suppression d'un élément : O(log n) + - Différence de deux ensembles : O(n) + - Union de deux ensembles : O(n) + - Intersection de deux ensembles : O(n) + - Ensemble vide ? : O(1) + - Copie d'un ensemble : O(n) + - Suppression d'un ensemble : O(n) + - Trouver un élément dans un ensemble non vide : O(1) + + Seul intérêt de cette implémentation utilisant des tarbres : manipuler + des arbres en C, ce qui est autrement plus difficile à faire qu'en ML. +*/ + +/* + TODO +*/ + diff --git a/sets.c b/sets.c new file mode 100644 index 0000000..b574576 --- /dev/null +++ b/sets.c @@ -0,0 +1,41 @@ +#include "sets.h" + +/* + GENERIC FUNCTION FOR ALL KIND OF SETS +*/ + +set singleton(int n, int x) { + set k = empty_set(n); + set_add_ip(x, k); + return k; +} + +set set_union(const set a, const set b) { + set q = copy_set(a); + set_union_ip(q, b); + return q; +} + +set set_inter(const set a, const set b) { + set q = copy_set(a); + set_inter_ip(q, b); + return q; +} + +set set_diff(const set a, const set b) { + set q = copy_set(a); + set_diff_ip(q, b); + return q; +} + +set set_add(int x, const set s) { + set q = copy_set(s); + set_add_ip(x, q); + return q; +} + +set set_remove(int x, const set s) { + set q = copy_set(s); + set_remove_ip(x, q); + return q; +} diff --git a/sets.h b/sets.h index 930314d..44114d1 100644 --- a/sets.h +++ b/sets.h @@ -54,6 +54,7 @@ set set_diff(const set a, const set b); bool is_set_empty(const set s); bool set_mem(int x, const set s); +bool sets_equal(const set a, const set b); int elt_of_set(const set s); @@ -63,6 +64,8 @@ void set_add_ip(int x, set s); set set_remove(int x, const set s); void set_remove_ip(int x, set s); +void dump_set(const set s); + #endif -- cgit v1.2.3