I have been asked to build a group of functions that carry out set theory operations such as intersection and union.
The functions below that I must complete are set_intersectWith, set_unionWith, set_minusWith, set_powerset, where:
set_intersectWith = A ∩ B
set_unionWith = A ∪ B
set_minusWith = complement = A \ B
set_powerset = P(S)
The following file is what I am working on, set.c:
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "clist.h"
#include "set.h"
struct set_implementation
{
clist * items;
printer item_printer;
equals item_compare;
};
set * new_set(printer item_printer, equals item_compare)
{
set * s = (set *) malloc (sizeof(set));
assert (s!=NULL);
s->items = new_clist();
s->item_printer = item_printer;
s->item_compare = item_compare;
return s;
}
int set_isempty(set *s)
{
assert(s!=NULL);
return 0; // needs to be implemented
}
int set_isSubset(set *s, set * t)
{
assert(s!=NULL);
clist_goto_head(s->items);
while (clist_cursor_inlist(s->items))
if (!set_isin(t,clist_get_item(s->items)))
return 0; // if not in t then not a subset
else
clist_goto_next(s->items);
return set_count(s) < set_count(t); // all in t, but check t is larger than s
}
int set_isEqualTo(set *s, set * t)
{
assert(s!=NULL);
return set_isSubsetEq(s,t) && set_isSubsetEq(t,s);
}
int set_isSubsetEq(set *s, set * t)
{
assert(s!=NULL);
clist_goto_head(s->items);
while (clist_cursor_inlist(s->items))
if (!set_isin(t,clist_get_item(s->items)))
return 0; // if not in t then not a subset
else
clist_goto_next(s->items);
return 1;
}
int set_count(set *s)
{
assert(s!=NULL);
return clist_size(s->items);
}
int set_isin(set *s, any x)
{
assert(s!=NULL);
clist_goto_head(s->items);
while (clist_cursor_inlist(s->items))
if (s->item_compare(clist_get_item(s->items),x))
return 1; // found it
else
clist_goto_next(s->items);
return 0; // not found
}
void set_insertInto(set *s, any x) // s = s u {x}
{
assert(s!=NULL);
if (!set_isin(s,x))
clist_ins_before(s->items,x);
}
void set_removeFrom(set *s, any x) // s = s \ {x}
{
// needs to be implemented
}
void set_intersectWith(set *s, set * t) // s = s n t t is unchanged
{
assert(s!=NULL);
// needs to be implemented
}
void set_unionWith(set *s, set * t) // s = s u t t is unchanged
{
assert(s!=NULL);
// needs to be implemented
}
void set_minusWith(set *s, set * t) // s = s \ t t is unchanged
{
assert(s!=NULL);
// needs to be implemented
}
set* set_powerset(set *s) // generates new set
{
assert(s!=NULL);
return NULL; // needs to be implemented
}
void set_print(set *s)
{
assert(s!=NULL);
printf("{");
clist_goto_head(s->items);
if (clist_cursor_inlist(s->items)) {
s->item_printer(clist_get_item(s->items));
clist_goto_next(s->items);
while (clist_cursor_inlist(s->items)) {
printf(", ");
s->item_printer(clist_get_item(s->items));
clist_goto_next(s->items);
}
}
printf("}");
}
void set_release(set *s)
{
assert(s!=NULL);
assert(clist_isempty(s->items));
clist_release(s->items);
free(s);
}
int seteq(any s, any t)
{
return set_isEqualTo((set*)s,(set*)t);
}
void setprn(any s)
{
set_print((set*)s);
}
As shown, it uses a circular list data structure as reference, clist.c:
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include "clist.h"
struct node
{
any item;
struct node * next;
struct node * prev;
};
struct clist_implementation
{
struct node * sentinel;
struct node * cursor;
int size;
};
clist * new_clist()
{
clist * c = (clist *)malloc(sizeof(clist));
if (c==NULL) {
printf("new_clist: malloc failure.\n");
exit(1);
}
c->size = 0;
c->sentinel = (struct node *) malloc(sizeof(struct node));
if (c->sentinel==NULL) {
printf("new_clist(sentinel): malloc failure.\n");
exit(1);
}
c->sentinel->item = NULL;
c->sentinel->next = c->sentinel;
c->sentinel->prev = c->sentinel;
c->cursor = c->sentinel;
return c;
}
int clist_size(clist *c)
{
assert(c!=NULL);
return c->size;
}
int clist_isempty(clist *c)
{
assert(c!=NULL);
return c->size == 0;
}
void clist_goto_head(clist *c)
{
assert(c!=NULL);
c->cursor = c->sentinel->next;
}
void clist_goto_last(clist *c)
{
assert(c!=NULL);
c->cursor = c->sentinel->prev;
}
void clist_goto_next(clist *c)
{
assert(c!=NULL);
c->cursor = c->cursor->next;
}
void clist_goto_prev(clist *c)
{
assert(c!=NULL);
c->cursor = c->cursor->prev;
}
int clist_cursor_inlist(clist *c)
{
assert(c!=NULL);
return c->cursor != c->sentinel;
}
any clist_get_item(clist *c)
{
assert(c!=NULL);
return (clist_cursor_inlist(c)) ? c->cursor->item : NULL;
}
void clist_ins_before(clist *c, any item)
{
assert(c!=NULL);
struct node * n = (struct node *) malloc(sizeof(struct node));
if (n==NULL) {
printf("clist_ins_before: malloc failure.\n");
exit(1);
}
n->item = item;
n->next = c->cursor;
n->prev = c->cursor->prev;
c->cursor->prev->next = n;
c->cursor->prev = n;
c->size++;
}
void clist_ins_after(clist *c, any item)
{
assert(c!=NULL);
struct node * n = (struct node *) malloc(sizeof(struct node));
if (n==NULL) {
printf("clist_ins_after: malloc failure.\n");
exit(1);
}
n->item = item;
n->prev = c->cursor;
n->next = c->cursor->next;
c->cursor->next->prev = n;
c->cursor->next = n;
c->size++;
}
int clist_delete(clist *c)
{
assert(c!=NULL);
struct node * p = c->cursor;
if (clist_cursor_inlist(c))
{
c->cursor = c->cursor->next;
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
c->size--;
return 1;
}
else
return 0;
}
void clist_iterate(clist *c, modify f)
{
assert(c!=NULL);
struct node * n = c->cursor;
clist_goto_head(c);
while (clist_cursor_inlist(c))
{
f(c->cursor->item);
clist_goto_next(c);
}
c->cursor = n;
}
int clist_find(clist *c, pred p)
{
assert(c!=NULL);
clist_goto_head(c);
while (clist_cursor_inlist(c) && (!p(c->cursor->item)))
clist_goto_next(c);
return clist_cursor_inlist(c);
}
int clist_find_next(clist *c, pred p)
{
assert(c!=NULL);
struct node * n = c->cursor;
while (clist_cursor_inlist(c) && (!p(c->cursor->item)))
clist_goto_next(c);
if (clist_cursor_inlist(c))
return 1;
else {
c->cursor = n;
return 0;
}
}
void clist_print(clist *c, void (* item_print)(any item))
{
assert(c!=NULL);
struct node * n = c->cursor;
printf("CL[");
clist_goto_head(c);
if (clist_cursor_inlist(c)) {
item_print(c->cursor->item);
clist_goto_next(c);
while (clist_cursor_inlist(c)) {
printf(", ");
item_print(c->cursor->item);
clist_goto_next(c);
}
}
printf("]");
c->cursor = n;
}
void clist_release(clist *c)
{
assert(c!=NULL);
free(c->sentinel);
free(c);
}
int clist_backspace(clist *c) {
assert(c!=NULL);
struct node * p = c->cursor;
if (clist_cursor_inlist(c))
{
c->cursor = c->cursor->prev;
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
c->size--;
return 1;
}
else
return 0;
}
And, finally, the test file for set.c, set_demo.c:
#include <stdio.h>
#include "any.h"
#include "set.h"
void intprn(any x)
{
printf("%li", (long)x);
}
int inteq(any x, any y)
{
if ((long)x == (long)y)
return 1;
else
return 0;
}
int main()
{
set * s, *t, *u, *i, *v;
s = new_set(intprn,inteq);
t = new_set(intprn,inteq);
set_insertInto(s,(any)3);
set_insertInto(s,(any)5);
set_insertInto(s,(any)7);
printf("s = ");
set_print(s);
printf("\n");
set_insertInto(t,(any)4);
set_insertInto(t,(any)5);
set_insertInto(t,(any)6);
printf("t = ");
set_print(t);
printf("\n");
u = new_set(setprn,seteq);
set_insertInto(u,s);
set_insertInto(u,t);
printf("u = ");
set_print(u);
printf("\n");
set_insertInto(s,(any)9);
printf("s = ");
set_print(s);
printf("\n");
printf("u = ");
set_print(u);
printf("\n");
i = new_set(setprn,seteq);
set_insertInto(i,s);
set_intersectWith(i,t);
printf("i = ");
set_print(i);
printf("\n");
v = new_set(intprn,inteq);
//set_insertInto(v,s);
//set_insertInto(v,(any)5);
set_unionWith(v,s);
printf("v = ");
set_print(v);
printf("\n");
set_minusWith(t,s);
printf("t = ");
set_print(t);
printf("\n");
set_removeFrom(s,(any)5);
set_removeFrom(s,(any)3);
set_removeFrom(s,(any)9);
set_removeFrom(s,(any)7);
printf("s = ");
set_print(s);
printf("\n");
printf("set_isempty: %i", set_isempty(s));
printf("\n");
set_powerset(t);
printf("t = ");
set_print(t);
printf("\n");
}
All the functions I am working on are not working. For example, at the moment, when I test intersectWith:
set_insertInto(i,s);
set_intersectWith(i,t);
When I output set i, only the values from s are in it.
Please help!
