0

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!

2
Contributors
1
Reply
17
Views
3 Years
Discussion Span
Last Post by rubberman
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.