set.c

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

typedef struct set_node set_node_t;
typedef struct set set_t;
struct set_node  {
	set_node_t *next;
    set_node_t *prev;
    void *elem;
	
};
struct set{
	set_node_t *head;
    set_node_t *tail;
    int size;
    cmpfunc_t cmpfunc;
	
};
set_t *sortingz(set_t *set);
void set_sort(set_t *set);
static set_node_t *mergesort_(set_node_t *head, cmpfunc_t cmpfunc);
static set_node_t *splitset(set_node_t *head);
static set_node_t *merge(set_node_t *a, set_node_t *b, cmpfunc_t cmpfunc);




static set_node_t *newnode(void *elem)
{
    set_node_t *node = malloc(sizeof(set_node_t));
    if (node == NULL)
	    
    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 *set = malloc(sizeof(set_t));
    
	 
    set->head = NULL;
    set->tail = NULL;
    set->size = 0;
    set->cmpfunc = cmpfunc;
    return set;
}

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

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

/*
 * Adds the given element to the given set.
 */
void set_add(set_t *set, void *elem){
	
	set_node_t *node = newnode(elem);
    if (set->head == NULL) {
	    set->head = set->tail = node;
    }
    else {
	    set->head->prev = node;
	    node->next = set->head;
	    set->head = node;
    }
	printf("hei");
    set->size++;

}

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

set_t *sorting(set_t *set){
	
	printf("hei");
	if(set==NULL || set->head==NULL){
		return set;
	}
	set_node_t *tmp1, *tmp2, *tmp3;
	tmp3=set->head;
	while(tmp3!=NULL){
		tmp1=tmp3;
		while(tmp1!=NULL){
		
			if(tmp1->elem>tmp1->prev->elem){
				printf("hei");
				tmp2->elem=tmp1->prev->elem;
				tmp1->prev->elem=tmp1->elem;
				tmp1->elem=tmp2->elem;
			}
		
			tmp1=tmp1->prev;
		}
		tmp3=tmp3->prev;
	}
	return set;
}

/*
 * 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){
	
	
}

/*
 * 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){
	
	
	
}

/*
 * 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){
	
	
}

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


/*
 * The type of set iterators.
 */

typedef struct set_iter set_iter_t;
struct set_iter{
	
	set_node_t *node;
};
/*
 * 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){
	if (iter->node == NULL) {
	   exit(1); 
    }
    else {
	    void *elem = iter->node->elem;
	    iter->node = iter->node->next;
	    return elem;
    }
}

static set_node_t *merge(set_node_t *a, set_node_t *b, cmpfunc_t cmpfunc)
{
	set_node_t *head, *tail;
	
	/* Pick the smallest head node */
	if (cmpfunc(a->elem, b->elem) < 0) {
		head = tail = a;
		a = a->next;
	}
	else {
		head = tail = b;
		b = b->next;
	}
	/* Now repeatedly pick the smallest head node */
	while (a != NULL && b != NULL) {
		if (cmpfunc(a->elem, b->elem) < 0) {
			tail->next = a;
			tail = a;
			a = a->next;
		}
		else {
			tail->next = b;
			tail = b;
			b = b->next;
		}
	}
	/* Append the remaining non-empty set (if any) */
	if (a != NULL) {
		tail->next = a;
	}
	else {
		tail->next = b;
	}
	return head;
}


static set_node_t *splitset(set_node_t *head)
{
	set_node_t *slow, *fast, *half;
	
	/* Move two pointers, a 'slow' one and a 'fast' one which moves
	 * twice as fast.  When the fast one reaches the end of the set,
	 * the slow one will be at the middle.
	 */
	slow = head;
	fast = head->next;
	while (fast != NULL && fast->next != NULL) {
		slow = slow->next;
		fast = fast->next->next;
	}
	/* Now 'cut' the set and return the second half */
	half = slow->next;
	slow->next = NULL;
	return half;
}

/*
 * Recursive merge sort.  This function is named mergesort_ to avoid
 * collision with the mergesort function that is defined by the standard
 * library on some platforms.
 */
static set_node_t *mergesort_(set_node_t *head, cmpfunc_t cmpfunc)
{
	if (head->next == NULL) {
		return head;
	}
	else {
		set_node_t *half = splitset(head);
		head = mergesort_(head, cmpfunc);
		half = mergesort_(half, cmpfunc);
		return merge(head, half, cmpfunc);
	}
}

void set_sort(set_t *set)
{
	if (set->head != NULL) {
		set_node_t *prev, *n;
	
		/* Recursively sort the set */
		set->head = mergesort_(set->head, set->cmpfunc);
	
		/* Fix the tail and prev links */
		prev = NULL;
		for (n = set->head; n != NULL; n = n->next) {
			n->prev = prev;
			prev = n;
		}
		set->tail = prev;
	}
}