Started implementation of sets based on linked lists.

3 files changed, 177 insertions, 4 deletions

diff --git a/README b/README
index 61a9cc3..699f8f2 100644
--- a/README
+++ b/README
@@ -1,5 +1,5 @@
 Projet d'Algorithmique et Programmation
-Alex AUVOLAT, Mendès OULAMARA
+Alex AUVOLAT, Mendes OULAMARA
 2013-2014
 
 Sujet : Algorithme de Bron-Kerbosch pour Maximum-Clique
diff --git a/set_linked_lists.c b/set_linked_lists.c
index f37773f..05ed4ca 100644
--- a/set_linked_lists.c
+++ b/set_linked_lists.c
@@ -1,3 +1,175 @@
+#include <stdlib.h>
 #include "sets.h"
 
+/* Question théorique pertinente :
+	Faut-il représenter les entiers par des listes d'entiers triées ou non triées ?
 
+	Coût des opérations élémentaires dans le cas trié :
+	- Ajout d'un élément : O(n)
+	- Suppression d'un élément : O(n)
+	- Différence de deux ensemble : O(n)
+	- Union de deux ensembles : O(n)
+	- Intersection de deux ensembles : O(n)
+	- Ensemble vide ? : O(1)
+	- Copie d'un ensemble : O(n)
+	- Supression d'un ensemble : O(n)
+	- Trouver un élément d'un ensemble non vide : O(1)
+
+	Coût des opérations élémentaires dans le cas non trié :
+	- Ajout d'un élément : O(1)
+	- Suppression d'un élément : O(n)
+	- Différence de deux ensembles : O(n log n)
+	- Union de deux ensembles : O(n log n)
+	- Intersection de deux ensembles : O(n log n)
+	- Ensemble vide ? : O(1)
+	- Copie d'un ensemble : O(n)
+	- Suppression d'un ensemble : O(n)
+	- Trouver un élément d'un ensemble non vide : O(1)
+
+	La seule opération qui gagne à ne pas travailler sur une liste triée
+	est l'insertion d'un élément, or celle-ci s'accompagne généralement d'autres
+	opérations telles que l'union ou l'intersection, donc l'effectuer en
+	temps constant ne permet pas de gagner en complexité asymptotique.
+
+	On fait donc le choix de maintenir une liste triée.
+*/
+
+typedef struct set_elt *element;
+
+set empty_set(int n) {
+	set k = malloc(sizeof(t_set_descriptor));
+	k->first = k->last = NULL;
+	k->size = 0;
+	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;
+
+	set t = malloc(sizeof(t_set_descriptor));
+	t->size = s->size;
+
+	t->first = NULL;
+	if (s->size) {
+		prev = malloc(sizeof(struct set_elt));
+		prev->value = s->first->value;
+		t->first = prev;
+
+		for (iter = s->first->next; iter != NULL; iter = iter->next) {
+			element e = malloc(sizeof(struct set_elt));
+			e->value = iter->value;
+			prev->next = e;
+			prev = e;
+		}
+
+		prev->next = NULL;
+		t->last = prev;
+	} else {
+		t->last = NULL;
+	}
+
+	return t;
+}
+
+void delete_set(set s) {
+	element iter;
+
+	for (iter = s->first; iter != NULL; ) {
+		element next = iter->next;
+		free(iter);
+		iter = next;
+	}
+
+	free(s);
+}
+
+void set_union_ip(set a, const set b) {
+	//TODO
+}
+
+void set_inter_ip(set a, const set b) {
+	//TODO
+}
+
+void set_diff_ip(set a, const set b) {
+	//TODO
+}
+
+bool is_set_empty(const set s) {
+	return (s->size == 0 ? true : false);
+}
+
+bool set_mem(int x, const set s) {
+	element iter;
+
+	for (iter = s->first; iter != NULL; iter = iter->next) {
+		if (iter->value == x) return true;
+		if (iter->value > x) break;
+	}
+
+	return false;
+}
+
+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
+}
+
+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;
+		}
+
+		e = malloc(sizeof(struct set_elt));
+		e->value = x;
+		e->next = iter;
+		prev->next = e;
+	}
+	if (e->next == NULL) s->last = e;
+	s->size++;
+}
+
+void set_remove_ip(int x, set s) {
+	element prev, iter;
+
+	prev = NULL;
+	for (iter = s->first; iter != NULL; iter = iter->next) {
+		if (iter->value == x) {
+			if (prev == NULL) {
+				s->first = iter->next;
+			} else {
+				prev->next = iter->next;
+			}
+			if (iter->next == NULL) s->last = prev;
+			free(iter);
+			s->size--;
+			return;
+		}
+
+		prev = iter;
+	}
+}
diff --git a/sets.h b/sets.h
index 59768f0..930314d 100644
--- a/sets.h
+++ b/sets.h
@@ -25,11 +25,12 @@ struct set_elt {
     int value;
     struct set_elt *next;
 };
-struct set {
+typedef struct {
     struct set_elt *first, *last;
-};
+	int size;	// number of elements
+} t_set_descriptor;
 
-typedef struct set *set;
+typedef t_set_descriptor *set;
 #endif
 
 #ifdef TREAPS