#include "toset.h" #include #include #include typdef struct cell *list; struct cell { void *element; list next; }; struct toset { int (*compare)(void *, void *); list elements; }; toset toset_create(int (*compare)(void *, void *)) { toset t = malloc(sizeof (struct toset)); t -> compare = compare; t -> elements = elements; return t; } static int equal(int (*compare)(void *, void *), void *e1, void *e2) { return !compare(e1, e2) && !compare(e2, e1); } /* return the position of the first element not less than element */ static list * position(toset t, void *element) { list *lp; for(lp = &(t -> elements); *lp && t -> compare((*lp) -> element, element); lp = &((*lp) -> next)) ; return lp; } toset toset_insert(toset t, void *element) { list *lp = position(t, element); ; /* don't insert it if it is already there */ if(equal(t -> compare, element, (*lp) -> element)) return; { list temp = malloc(sizeof(struct cell)); temp -> element = element; temp -> next = *lp; *lp = temp; } } toset toset_delete(toset t, void *element) { list *lp = position(t, element); /* don't delete it if it isn't there */ if(!equal(t -> compare, element, (*lp) -> element)) return; { list temp = *lp; *lp = (*lp) -> next; free(temp); } } extern int toset_member(toset t, void *element) { list *lp = position(t, element); return equal(t -> compare, element, (*lp) -> element); } extern int toset_empty(toset t) { return t -> list == NULL; } extern void * toset_smallest(toset t) { assert(!toset_empty(t)); return t -> elements -> element; } extern void toset_union(toset s, toset t) { list l; for(l = t -> elements; l; l = l -> next) { toset_insert(s, l -> element); } } extern void toset_intersection(toset s, toset t) { list *lp; for(lp = &(s -> elements); *lp;) { if(toset_member(t, (*lp) -> element)) lp = &((*lp) -> next); else { list temp = *lp; *lp = (*lp) -> next; free(temp); } } }