From 91c9deef705fe60863ef32c86b81b8a94d35febf Mon Sep 17 00:00:00 2001
From: Alex AUVOLAT <alex.auvolat@ens.fr>
Date: Mon, 18 Nov 2013 16:51:51 +0100
Subject: Started implementation of sets based on linked lists.

---
 set_linked_lists.c | 172 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 172 insertions(+)

(limited to 'set_linked_lists.c')

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;
+	}
+}
-- 
cgit v1.2.3