Finished implementation of sets with linked lists.

6 files changed, 286 insertions, 39 deletions

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 <stdlib.h>
+#include <stdio.h>
 #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 <stdio.h>
+#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