/*
set.c
Pedro Flynn - pflynn@microsoftsucks.org
*/

#include "set.h"


Set* set_create(int (*s_match)(const void*,const void*),void (*s_destroy)(void*))
{
Set* new_set;

new_set = (Set*) malloc(sizeof(Set));

new_set->s_first = new_set->s_last = NULL;
new_set->s_size = 0;
new_set->s_match = s_match;
new_set->s_destroy = s_destroy;
return new_set;
}


int set_insert_element_no_compare(Set* set,SetElmt* prev,const void* data)
{
SetElmt* new_element;
	
new_element = (SetElmt*) malloc(sizeof(SetElmt));
new_element->se_data = (void*) data;	

if(!prev){
	if(!set->s_size)
		new_element->se_next = NULL;
	else
		new_element->se_next = set->s_first;
	
	set->s_first = new_element;
	}else{
		if(!prev->se_next)
			new_element->se_next = NULL;
		else
			new_element->se_next = prev->se_next;
		
		prev->se_next = new_element;
		}
		
		if(!new_element->se_next)
			set->s_last = new_element;

set->s_size++;
return 0;
}

int set_is_member(const Set* set,const void* data)
{
SetElmt* element;

for(element = set->s_first;element;element = element->se_next)
	if(set->s_match(element->se_data,data))
		return 1;

return 0;
}

int set_insert_element(Set* set,const void* data)
{

	if(set_is_member(set,data))
		return -1;

	return set_insert_element_no_compare(set,set->s_last,data);

}

int set_remove_element_no_compare(Set* set,SetElmt* prev,void** data)
{
SetElmt* old_element;
	
	if(!set->s_size)
		return -1;
	
	if(!prev){
	old_element = set->s_first;
	*data = old_element->se_data;
		if(!old_element->se_next)
			set->s_last = NULL;
		set->s_first = set->s_first->se_next;
		}else{
			
			if(!prev->se_next)
				return -1;
			
			old_element = prev->se_next;
			*data = old_element->se_data;
			
			if(!old_element->se_next)
				set->s_last = prev;
			  
			  prev->se_next = prev->se_next->se_next;
			}
			
free(old_element);
set->s_size--;
return 0;
}

int set_remove_element(Set* set,void** data)
{
SetElmt *prev,*element;
	
if(!set->s_size)
	return -1;

prev = NULL;

for(element=set->s_first;element;element=element->se_next){
	if(set->s_match(element->se_data,*data))
		break;
	prev = element;
}

if(!element)
	return -1;

return set_remove_element_no_compare(set,prev,data);
}

Set* set_union(Set* set1,Set* set2)
{
Set* union_set;
SetElmt* element;
	
if(!(set1 && set2))
	return NULL;

if(!(union_set = set_create(set1->s_match,set1->s_destroy)))
	return NULL;

for(element=set1->s_first;element;element=element->se_next)
	set_insert_element_no_compare(union_set,union_set->s_last,element->se_data);

for(element=set2->s_first;element;element=element->se_next)
	if(!set_is_member(set1,element->se_data))
		set_insert_element_no_compare(union_set,union_set->s_last,element->se_data);

return union_set;
}

Set* set_intersection(Set* set1,Set* set2)
{
Set *set,*seti;	
SetElmt* element;
	
if(!(set1 && set2))
	return NULL;

seti = set_create(set1->s_match,set1->s_destroy);

((set1->s_size)>(set2->s_size))?(set=set2):(set=set1);

for(element=set->s_first;element;element=element->se_next)
	if(set_is_member(set2,element->se_data))
		set_insert_element_no_compare(seti,NULL,element->se_data);
	
	return seti;
}

Set* set_diference(Set* set1,Set* set2)
{
Set* setdi;
SetElmt* element;
	
if(!(set1 && set2))
	return NULL;

setdi = set_create(set1->s_match,set1->s_destroy);

for(element=set1->s_first;element;element=element->se_next)
	if(!set_is_member(set2,element->se_data))
  	set_insert_element_no_compare(setdi,NULL,element->se_data);
	
return setdi;
}

int set_is_subset(Set* set1,Set* set2)
{
SetElmt* element;
	
if(!(set1 && set2))
	return 0;

if(set1->s_size>set2->s_size)
	return 0;

for(element=set1->s_first;element;element=element->se_next)
	if(!set_is_member(set2,element->se_data))
		return 0;

return 1;
}

int set_is_equal(Set* set1,Set* set2)
{
if(!(set1 && set2))
	return 0;

if(set1->s_size!=set2->s_size)
	return 0;

return set_is_subset(set1,set2);
}

void set_empty(Set* set)
{
void* data;

if(!set)
	return;
if(!set->s_size)
	return;

while(!set_remove_element_no_compare(set,NULL,&data));
	return;

}

void set_destroy(Set* set)
{
void* data;
	
	if(!set)
		return;

	while(set->s_size)	
	if(!set_remove_element_no_compare(set,NULL,&data) && set->s_destroy)
		set->s_destroy(data);

free(set);
}