/* Steven Andrews, 4/20/95, modified 9/98, modified 1/21/02 */
/* Performs basic set operations with an unordered linked list */
/* See documentation called Set doc */
/* Copyright 2003 by Steven Andrews.  Permission is granted
   for non-commercial use of and modifications to the code. */

#include <stdlib.h>
#include "Set.h"

int FindCell(void *k,void *x,set s,struct scell **prevptr,struct scell **cellptr);
int FindKey(void *k,set s,struct scell **prevptr,struct scell **cellptr);
int FindItem(void *x,set s,struct scell **prevptr,struct scell **cellptr);
struct scell *SetCellAlloc();
void SetCellFree(struct scell *cell,int freek,int freex);


struct scell *SetCellAlloc() {
	struct scell *cell;

	cell=(struct scell *) malloc(sizeof(struct scell));
	if(!cell) return NULL;
	cell->key=NULL;
	cell->item=NULL;
	cell->next=NULL;
	return cell; }

void SetCellFree(struct scell *cell,int freek,int freex) {
	if(!cell) return;
	if(freek&&cell->key) free(cell->key);
	if(freex&&cell->item) free(cell->item);
	free(cell);
	return; }

int FindCell(void *k,void *x,set s,struct scell **prevptr,struct scell **cellptr) {
/* If not in set, returns 0, prev points to last filled cell if any, cell points to final empty cell. */
/* If in set, returns 1 and prev points before or NULL if none before, cell points to member. */
	struct scell *c;
	
	*prevptr=NULL;
	*cellptr=c=s->list;
	while(c->next&&(s->keycmp&&(*s->keycmp)(k,c->key)||s->itemcmp&&(*s->itemcmp)(x,c->item)))	{
		*prevptr=c;
		*cellptr=c=c->next; }
	if(c->next) return 1;
	return 0; }

int FindKey(void *k,set s,struct scell **prevptr,struct scell **cellptr) {
/* See FindCell */
	struct scell *c;
	
	*prevptr=NULL;
	*cellptr=c=s->list;
	if(!s->keycmp) return 0;
	while(c->next&&(*s->keycmp)(k,c->key))	{
		*prevptr=c;
		*cellptr=c=c->next; }
	if(c->next) return 1;
	return 0; }

int FindItem(void *x,set s,struct scell **prevptr,struct scell **cellptr) {
/* See FindCell */
	struct scell *c;

	*prevptr=NULL;
	*cellptr=c=s->list;
	if(!s->itemcmp) return 0;
	while(c->next&&(*s->itemcmp)(x,c->item))	{
		*prevptr=c;
		*cellptr=c=c->next; }
	if(c->next) return 1;
	return 0; }


set SetAlloc(int (*keycmp)(void *,void *),int (*itemcmp)(void *,void *)) {
	set s;

	if(!keycmp&&!itemcmp) return NULL;
	s=(set) malloc(sizeof(struct sstruct));
	if(!s) return NULL;
	s->keycmp=keycmp;
	s->itemcmp=itemcmp;
	s->list=SetCellAlloc();
	if(!s->list) {SetFree(s,0,0);return NULL;}
	return s; }

void SetFree(set s,int freek,int freex) {
	if(!s) return;
	if(s->list) {
		SetNull(s,freek,freex);
		SetCellFree(s->list,freek,freex); }
	free(s); }

void SetNull(set s,int freek,int freex) {
	struct scell *cell,*prev;
	
	cell=s->list;
	while(cell->next)	{
		prev=cell;
		cell=cell->next;
		SetCellFree(prev,freek,freex);	}
	s->list=cell; }

int SetInsert(void *k,void *x,set s) {
	struct scell *cell,*prev,*cz;
	int i;
	
	i=FindCell(k,x,s,&prev,&cell);
	if(i) return 2;	
	if(!prev)	{
		prev=SetCellAlloc();
		if(!prev) return 0;
		s->list=prev;	}
	else	{
		cz=SetCellAlloc();
		if(!cz) return 0;
		prev->next=cz;
		prev=cz; }
	prev->key=k;
	prev->item=x;
	prev->next=cell;
	return 1; }

int SetDelete(void *k,void *x,set s,int freek,int freex) {
	struct scell *cell,*prev;
	int i;
	
	i=FindCell(k,x,s,&prev,&cell);
	if(!i) return 0;
	if(!prev)	s->list=cell->next;
	else	prev->next=cell->next;
	SetCellFree(cell,freek,freex);
	return 1; }

int SetMember(void *k,void *x,set s) {
	struct scell *cell,*prev;
	
	return FindCell(k,x,s,&prev,&cell); }

void *SetItem(void *k,set s) {
	struct scell *cell,*prev;
	
	return(FindKey(k,s,&prev,&cell)?cell->item:0); }

void **SetItemAt(void *k,set s) {
	struct scell *cell,*prev;

	return(FindKey(k,s,&prev,&cell)?&(cell->item):0); }

void *SetKey(void *x,set s) {
	struct scell *cell,*prev;
	
	return(FindItem(x,s,&prev,&cell)?cell->key:0); }

struct scell *SetNext(struct scell *ptr,void **k,void **x,set s) {
	if(!ptr)
		ptr=s->list;
	*k=ptr->key;
	*x=ptr->item;
	ptr=ptr->next;
	return ptr; }

int Subset(set s1,set s2) {
	struct scell *cell1,*cell2,*prev2;
	
	cell1=s1->list;
	while(cell1->next&&FindCell(cell1->key,cell1->item,s2,&cell2,&prev2))
		cell1=cell1->next;
	return(cell1->next)?0:1; }

int SetEqual(set s1,set s2) {
	return(Subset(s1,s2)&&Subset(s2,s1))?1:0; }

set SetUnion(set s1,set s2) {
	struct scell *cell;
	set s3;
	int ok;

	s3=SetAlloc(s1->keycmp,s1->itemcmp);
	if(!s3) return 0;
	ok=1;
	for(cell=s1->list;ok&&cell->next;cell=cell->next)
		ok=SetInsert(cell->key,cell->item,s3);
	for(cell=s2->list;ok&&cell->next;cell=cell->next)
		ok=SetInsert(cell->key,cell->item,s3);
	if(!ok) {SetFree(s3,0,0);return 0;}
	return s3; }

set SetIntersect(set s1,set s2) {
	struct scell *cell,*cell2,*prev2;
	set s3;
	int ok;
	
	s3=SetAlloc(s1->keycmp,s1->itemcmp);
	if(!s3) return 0;
	ok=1;
	for(cell=s1->list;ok&&cell->next;cell=cell->next)
		if(FindCell(cell->key,cell->item,s2,&prev2,&cell2))
			ok=SetInsert(cell->key,cell->item,s3);
	if(!ok) {SetFree(s3,0,0);return 0;}
	return s3; }

set SetDiff(set s1,set s2) {
	struct scell *cell,*cell2,*prev2;
	set s3;
	int ok;
	
	s3=SetAlloc(s1->keycmp,s1->itemcmp);
	if(!s3) return 0;
	ok=1;
	for(cell=s1->list;ok&&cell->next;cell=cell->next)
		if(!FindCell(cell->key,cell->item,s2,&prev2,&cell2))
			ok=SetInsert(cell->key,cell->item,s3);
	if(!ok) {SetFree(s3,0,0);return 0;}
	return s3; }

int SetCard(set s) {
	struct scell *cell;
	int i=0;
	
	for(cell=s->list;cell->next;cell=cell->next)
		i++;
	return i; }