path: root/set_linked_lists.c

/*
	Projet d'algorithmique et programmation 2013-2014
	(cours de C.Matthieu et J.Stern)
	Alex AUVOLAT, Mendes OULAMARA

	Implémentation des ensembles d'entiers sous forme de liste chaînée.
	Code sous la juridiction d'Alex AUVOLAT.
*/

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

	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;

set empty_set(int n) {
	set k = malloc(sizeof(t_set_descriptor));
	k->N = n;
	k->first = k->last = NULL;
	k->size = 0;
	return k;
}

set full_set(int n) {
	int i;
	set k = malloc(sizeof(t_set_descriptor));
	k->N = n;

	element prev = NULL;
	for (i = 0; i < n; i++) {
		element e = malloc(sizeof(struct set_elt));
		e->value = i;
		e->next = NULL;
		if (prev == NULL) {
			k->first = e;
		} else {
			prev->next = e;
		}
		k->last = prev = e;
	}

	k->size = n;
	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 > 0) {
		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));
			assert(e != NULL);
			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);
}

int set_size(const set s) {
	return s->size;
}

void set_union_ip(set a, const set b) {
	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) {
	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) {
	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) {
	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;
}

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;

	fprintf(stderr, "No element in empty set...\n");
	dump_set(s);
	assert(false);
}

int elt_of_set_heur(const set s, int h) {
    return elt_of_set(s);
}

void set_add_ip(int x, set s) {
	element prev, iter, e;

	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;
	if (prev != NULL) {
		prev->next = e;
	} else {
		s->first = e;
	}
	if (iter == 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;
	}
}

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