set.c

#include <stdio.h>
#include <stdlib.h>
#include "set.h"
#include "common.h"

typedef struct node node_t;
typedef struct set set_t;
typedef struct set_iter set_iter_t;

struct set{
	node_t *head;
	node_t *tail;
	
	int numitems;
	cmpfunc_t cmpfunc;
};

struct node{
	node_t *next;
	node_t *prev;
	
	void *elem;
	
};
struct set_iter{
	
	node_t *node;
};

void printsets(set_t *set){
	
	node_t *tmp;
	tmp=set->head;
	while(tmp!=NULL){
		
		printf("elementer i settet: %d\n", tmp->elem);
		tmp=tmp->next;
	}
	
}


void swap (node_t *a, node_t *b){
	
	void *tmp;
	tmp=a->elem;
	a->elem=b->elem;
	b->elem=tmp;
	
}



set_t *sort(set_t *set){
	
	if(set->head==NULL){
		return set;
	}
	if(set->head->next==NULL){
		return set;
	}
	
	node_t *tmp = set->head;
	node_t *tmp2 = set->head->next;
	
	while(tmp2!=NULL){
		while(tmp2!=tmp){
			
			if(tmp->elem>tmp2->elem){
				swap(tmp,tmp2);
			}
			
			tmp=tmp->next;
		}
		tmp=set->head;
		tmp2=tmp2->next;
	}
	return set;
}

node_t *addnode(void *elem){
	node_t *node = malloc(sizeof(node_t));
	node->next=NULL;
	node->prev=NULL;
	node->elem=elem;
	
	return node;
}

/*
 * Creates a new set using the given comparison function
 * to compare elements of the set.
 */
set_t *set_create(cmpfunc_t cmpfunc){
	
	set_t *new=malloc(sizeof(set_t));
	new->head=NULL;
	new->tail=NULL;
	new->numitems=0;
	new->cmpfunc=cmpfunc;
	
	return new;
}

/*
 * Destroys the given set.  Subsequently accessing the set
 * will lead to undefined behavior.
 */
void set_destroy(set_t *set){
	node_t *tmp, *node;
	tmp=set->head;
	while(tmp!=NULL){
		node=tmp;
		tmp=tmp->prev;
		free(node);
	}
	free(set);
}

/*
 * Returns the size (cardinality) of the given set.
 */
int set_size(set_t *set){
	
	return set->numitems;
}

/*
 * Adds the given element to the given set.
 */
void set_add(set_t *set, void *elem){
	
	if((set_contains(set,elem))){
		return;
	}
	
	node_t *node = addnode(elem);
    if (set->head == NULL) {
	    set->head = set->tail = node;
    }
    else {
	    set->head->prev = node;
	    node->next = set->head;
	    set->head = node;
    }
	set=sort(set);
    set->numitems++;
}

/*
 * Returns 1 if the given element is contained in
 * the given set, 0 otherwise.
 */
int set_contains(set_t *set, void *elem){
	
	node_t *tmp;
	tmp=set->head;
	while(tmp!=NULL){
		if (set->cmpfunc(elem, tmp->elem) == 0){
			return 1;
		}
		tmp=tmp->next;
	}
	return 0;
}

/*
 * Returns the union of the two given sets; the returned
 * set contains all elements that are contained in either
 * a or b.
 */
set_t *set_union(set_t *a, set_t *b){
	
	a=sort(a);
	b=sort(b);
	set_t *unionset = set_create(a->cmpfunc);
	
	node_t *Aset;
	Aset=a->head;
	
	while(Aset!=NULL){
		
		set_add(unionset,Aset->elem);
		Aset=Aset->next;
	}
	
	node_t *tmp;
	tmp=b->head;
	while(tmp!=NULL){
		
		if((set_contains(unionset,tmp->elem))){
			
			tmp=tmp->next;
		}else{
			set_add(unionset,tmp->elem);
		}
	}
	unionset=sort(unionset);
	
	return unionset;
}

/*
 * Returns the intersection of the two given sets; the
 * returned set contains all elements that are contained
 * in both a and b.
 */
set_t *set_intersection(set_t *a, set_t *b){
	
	a=sort(a);
	b=sort(b);

	set_t *interset = set_create(a->cmpfunc);
	node_t *tmp = a->head;
	while(tmp!=NULL){
		if((set_contains(b,tmp->elem))){
			set_add(interset,tmp->elem);
		}
		tmp=tmp->next;
	}
	interset=sort(interset);
	
	return interset;

}

/*
 * Returns the set difference of the two given sets; the
 * returned set contains all elements that are contained
 * in a and not in b.
 */
set_t *set_difference(set_t *a, set_t *b){
	
	sort(a);
	sort(b);
	set_t *diffset = set_create(a->cmpfunc);
	node_t *tmp;
	tmp=a->head;
	
	while(tmp!=NULL){
		
		if((set_contains(b,tmp->elem))){
			
			tmp=tmp->next;
		}else{
			
			set_add(diffset,tmp->elem);
			tmp=tmp->next;
		}
	}
	diffset=sort(diffset);
	return diffset;
}

/*
 * Returns a copy of the given set.
 */
set_t *set_copy(set_t *set){
	
	set_t *kopi = set_create(set->cmpfunc);
	
	node_t *tmp = set->head;
	
	while(tmp!=NULL){
		
		set_add(kopi,tmp->elem);
		tmp=tmp->next;
	}
	kopi=sort(kopi);
	return kopi;
}

/*
 * The type of set iterators.
 */


/*
 * Creates a new set iterator for iterating over the given set.
 */
set_iter_t *set_createiter(set_t *set){
	
	set_iter_t *iter = malloc(sizeof(set_iter_t));
    
    iter->node = set->head;
    return iter;
}

/*
 * Destroys the given set iterator.
 */
void set_destroyiter(set_iter_t *iter){
	
	free(iter);
}

/*
 * Returns 0 if the given set iterator has reached the end of the
 * set, or 1 otherwise.
 */
int set_hasnext(set_iter_t *iter){
	
	
	if (iter->node == NULL)
	    return 0;
    else
	    return 1;
}

/*
 * Returns the next element in the sequence represented by the given
 * set iterator.
 */
void *set_next(set_iter_t *iter){
	
	void *elem;
	if (iter->node == NULL) {
	   exit(1); 
    }
    else {
	     elem = iter->node->elem;
	    iter->node = iter->node->next;
	    return elem;
    }
}