Finished implementation of sets with linked lists.

1 files changed, 116 insertions, 32 deletions

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);
+}