main.cpp

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <chrono>
#include "Set.h"

unsigned time();
int const number_of_tests = 1000;
int const maximum_set_size = 100;

void randomSet(Set* s);
void visualTests(void);
void equalityTests(void);
void specialCaseTests(void);
void relationalTests(void);
void algebraicTests(void);
void testTime(void);

int main (void) {
	visualTests();
	equalityTests();
	specialCaseTests();
	relationalTests();
	algebraicTests();
	testTime();
	printf("The tests are over\n"); 
}

void randomSet(Set* s) {
	Set t;
	int n = rand() % maximum_set_size + 1;
	int i;
	
	createEmptySet(&t);
	for (i = 0; i < n; i += 1) {
		insertSet(&t, rand() % maximum_set_size);
	}
	assignSet(s, &t); 
	destroySet(&t);
}

void showOutput(const char* str, Set* set) {
	printf("%s", str);
	displaySet(set);
	printf("\n");
}

void visualTests() {
	Set s;
	Set t;
	int i;
	createEmptySet(&s);
	showOutput("The set constructed with the default constructor: ", &s);

	for (i = 0; i < 10; i += 1) {
	  insertSet(&s, i);
	}
	showOutput("The set should be {0, ..., 9}:  ", &s);
	
	// test Insert() and Contains() with '<<'
	for (i = 0; i < 10; i += 1) {
		insertSet(&s, i);
	}
	showOutput("The set should be {0, ..., 9}:  ", &s);

	createCopySet(&t, &s);
	showOutput("The copy of s constructed with the copy constructor = ", &t);

	randomSet(&t);
	showOutput("The random set generated equals = ", &t);

	printf("The visual tests are over\n"); 
	destroySet(&s);
	destroySet(&t);
}

void equalityTests(void) {
	int i;
	for (i = 0; i < number_of_tests; i += 1) {
	  Set s;
	  Set t;
	  
	  createEmptySet(&s);
	  randomSet(&s);
	  createCopySet(&t, &s);
	  assert(isEqualToSet(&t, &s));
	  assert(isEqualToSet(&s, &t));
	  insertSet(&t, maximum_set_size);
	  assert(!isEqualToSet(&s, &t));
	  assert(!isEqualToSet(&t, &s));
	  randomSet(&t);
	  assert(!isEqualToSet(&t, &s)); 
	  destroySet(&s);
	  destroySet(&t);
	}       // This test could fail with small probability
	printf("The equality tests have been passed\n"); 
}

typedef void (*setFun)(Set*, const Set*);
void checkCase(setFun fun, Set* s1, Set* s2, Set* expect) {
	Set res;
	createCopySet(&res, s1);
	(*fun)(&res, s2);
	assert(isEqualToSet(&res, expect));
	destroySet(&res);
}

void specialCaseTests(void) {
	Set empty;
	Set universal;
	int i;
	Set s;
	Set r;
	
	createEmptySet(&empty);
	createEmptySet(&universal);
	createEmptySet(&r);
	for (i = 0; i < maximum_set_size; i += 1) {
	  insertSet(&universal, i);
	}
	checkCase(&subtractFromSet, &universal, &universal, &empty);
	checkCase(&unionInSet, &universal, &universal, &universal);
	checkCase(&intersectFromSet, &universal, &universal, &universal);
	checkCase(&intersectFromSet, &universal, &empty, &empty);
	checkCase(&intersectFromSet, &empty, &universal, &empty);
	checkCase(&unionInSet, &universal, &empty, &universal);
	checkCase(&unionInSet, &empty, &universal, &universal);
	checkCase(&unionInSet, &empty, &empty, &empty);
	checkCase(&subtractFromSet, &empty, &empty, &empty);
	checkCase(&intersectFromSet, &empty, &empty, &empty);
	
	createEmptySet(&s);
	assert(isEmptySet(&s));
	for (i = 0; i < 10; i += 1) {
		insertSet(&s, i);
	}
	assert(s.len == 10);
	for (i = 0; i < 10; i += 1) {
	  assert(isMemberSet(&s, i));
	}
	for (i = 0; i < 10; i += 1) {
	  removeSet(&s, i);
	  removeSet(&s, i);
	  assert(s.len == 9 - i); 
	}
	assert(isEmptySet(&s));
	for (i = 0; i < number_of_tests; i += 1) {
	  randomSet(&s);
	  assert(isSubsetOf(&empty, &s));
	  assert(!isSubsetOf(&s, &empty));
	  assert(isSubsetOf(&s, &universal));
	  assert(!isSubsetOf(&universal, &s));

		checkCase(&intersectFromSet, &empty, &s, &empty);
		checkCase(&intersectFromSet, &s, &empty, &empty);
		checkCase(&intersectFromSet, &universal, &s, &s);
		checkCase(&intersectFromSet, &s, &universal, &s);

		checkCase(&unionInSet, &universal, &s, &universal);
		checkCase(&unionInSet, &s, &universal, &universal);

		checkCase(&subtractFromSet, &s, &empty, &s);
		
		assignSet(&r, &universal);
		subtractFromSet(&r, &s); // r = u - s;
		checkCase(&subtractFromSet, &universal, &r, &s); // (u - (u - s) == s)
		checkCase(&unionInSet, &s, &r, &universal); // s + (u - s) == u
		checkCase(&unionInSet, &r, &s, &universal); // (u - s) + s == u
	}
	printf("The special case tests have been passed\n"); 
	destroySet(&empty);
	destroySet(&universal);
	destroySet(&s);
	destroySet(&r);
}

void relationalTests() {
	Set s;
	Set t;
	int i;
	  
	createEmptySet(&s);
	createEmptySet(&t);
	for (i = 0; i < number_of_tests; i += 1) {
		randomSet(&s);
		assignSet(&t, &s);
		assert(isSubsetOf(&s, &t));
		assert(isSubsetOf(&t, &s));
		assert(isEqualToSet(&s, &t));
		assert(isEqualToSet(&t, &s));
		insertSet(&s, rand() % maximum_set_size + maximum_set_size);
		assert(isSubsetOf(&t, &s));
		assert(! isSubsetOf(&s, &t));
	}
	printf("The relational tests have been passed\n"); 
	destroySet(&s);
	destroySet(&t);
}

void algebraicTests(void) {
	Set empty;
	Set universal;
	int i;
	Set s;
	Set t;
	Set u;
	Set v;
	Set w;
	
	createEmptySet(&empty);
	createEmptySet(&universal);
	for (i = 0; i < maximum_set_size; i += 1) {
		insertSet(&universal, i);
	}
	
	createEmptySet(&s);
	createEmptySet(&t);
	createEmptySet(&u);
	createEmptySet(&v);
	createEmptySet(&w);

	for (i = 0; i < number_of_tests; i += 1) {
		randomSet(&u);
		randomSet(&v);
		randomSet(&w);
	  
		/* u + v == v + u */
		assignSet(&s, &u);
		unionInSet(&s, &v);
		assignSet(&t, &v);
		unionInSet(&t, &u);
		assert(isEqualToSet(&s, &t));
			
		/* u + (v + w) == (u + v) + w */	  
		assignSet(&t, &v);
		unionInSet(&t, &w);
		assignSet(&s, &u);
		unionInSet(&s, &t);
		assignSet(&t, &u);
		unionInSet(&t, &v);
		unionInSet(&t, &w);
		assert(isEqualToSet(&s, &t));

		/* u * v == v * u */
		assignSet(&s, &u);
		intersectFromSet(&s, &v);
		assignSet(&t, &v);
		intersectFromSet(&t, &u);
		assert(isEqualToSet(&s, &t));

		/* u * (v * w) == (u * v) * w */	  
		assignSet(&t, &v);
		intersectFromSet(&t, &w);
		assignSet(&s, &u);
		intersectFromSet(&s, &t);
		assignSet(&t, &u);
		intersectFromSet(&t, &v);
		intersectFromSet(&t, &w);
		assert(isEqualToSet(&s, &t));

		/* u - v == u - (u * v) */
		assignSet(&s, &u);
		intersectFromSet(&s, &v);
		assignSet(&t, &u);
		subtractFromSet(&t, &s);
		assignSet(&s, &u);
		subtractFromSet(&s, &v);
		assert(isEqualToSet(&s, &t));

		/* additional tests, not implemented 
	  assert(w * (u - v) == w * u - w * v);
	  assert(u * (v + w) == (u * v) + (u * w));
	  assert(universal - (u * v) == (universal - u) + (universal - v));
	  assert(universal - (u + v) == (universal - u) * (universal - v)); 
	  */
	}
	printf("The algebraic tests have been passed\n"); 
	destroySet(&empty);
	destroySet(&universal);
	destroySet(&s);
	destroySet(&t);
	destroySet(&u);
	destroySet(&v);
	destroySet(&w);
}

/*
 * create two sets with n random elements
 * the sets should have 50% of the elements in common
 */
void createRandomSetN(int n, Set* a, Set* b) {
	int x;
	int last_size = 0;
	createEmptySet(a);
	while (a->len < n) {
		if (a->len != last_size) {
			last_size = a->len;
			if (last_size % 1000 == 0) {
				printf("%d..", last_size);
				fflush(stdout);
			}
		}
		x = 2 * (5 * n - (rand() % (10 * n)));
		if (isMemberSet(a, x)) { continue; } // try another number
		/* a will have only even elements */
		insertSet(a, x);
		if ((rand() % 2) == 0) {
			insertSet(b, x);
		} else {
			insertSet(b, x + 1); // an odd value, can't be in a
		}
	}
	assert(a->len == b->len);
}

typedef void (*Function)(void);

double timeFunction(Function f) {
	int reps = 128;
	uint64_t time = 0;
	volatile int k;
	while (time < 6000) {
		if (reps > 1000000000) { return 0.0; } // overflow?
		auto start = std::chrono::high_resolution_clock::now();
		for (k = 0; k < reps; k += 1) {
			f();
		}
		auto end = std::chrono::high_resolution_clock::now();
		time = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
		reps *= 2;
	}

	return ((double) time) / reps;
}

volatile int bogus_value; // used to ensure compiler does not optimize away our func calls

Set* setA;
Set* setB;
Set* setAPrime; // almost exactly the same as A

int is_mem_x;
void isMemberTimeFun(void) {
	if (isMemberSet(setA, is_mem_x)) {
		is_mem_x ^= 1;
		is_mem_x <<= 1;
	} else {
		is_mem_x >>= 1;
		is_mem_x ^= 2;
	}
}
		
void isEqualTimeFun(void) {
	bogus_value = isEqualToSet(setA, setAPrime);
}
	
void isSubsetTimeFun(void) {
	bogus_value = isSubsetOf(setA, setAPrime);
}

void unionTimeFun(void) {
	Set t;
	createCopySet(&t, setA);
	unionInSet(&t, setB);
	destroySet(&t);
}

void intersectTimeFun(void) {
	Set t;
	createCopySet(&t, setA);
	intersectFromSet(&t, setB);
	destroySet(&t);
}

void subtractTimeFun(void) {
	Set t;
	createCopySet(&t, setA);
	subtractFromSet(&t, setB);
	destroySet(&t);
}

bool checkLinear(double times[], int sizes[], int first, int last) {
	double time_ratio = times[last] / times[first];
	double size_ratio = sizes[last] / sizes[first];
	
	if (time_ratio < size_ratio * 1.25) {
		return true;
	} else {
		return false;
	}
}

bool checkSubLinear(double times[], int sizes[], int first, int last) {
	double time_ratio = times[last] / times[first];
	double size_ratio = sizes[last] / sizes[first];
	
	if (time_ratio < size_ratio * 0.5) {
		return true;
	} else {
		return false;
	}
}

enum Tests {
	IS_MEMBER = 0,
	INSERT = 1,
	REMOVE = 2,
	IS_EQUAL_TO = 3,
	IS_SUBSET_OF = 4,
	UNION_IN = 5,
	INTERSECT_FROM = 6,
	SUBTRACT_FROM = 7,
	
	NUM_TESTS /* MUST BE LAST */
};

typedef enum Scales {
	SUB_LINEAR,
	LINEAR,
	SUPER_LINEAR
} Scales;
/* NOTE: the order of these strings MUST MATCH EXACTLY the order of the Scales enum */
const char* scaling_strings[] = {
	"sub linear (YAHOO!)",
	"linear",
	"super linear, yuck."
};

int sizes[] = { 100, 400, 1600, 6400, 25600 };
//const unsigned num_times = sizeof(sizes) / sizeof(int);
#define num_times (sizeof(sizes) / sizeof(int))
Set setsA[num_times];
Set setsAPrime[num_times];
Set setsB[num_times];
double times[num_times];

Scales determineScaling(Function fun) {
	bool linear;
	bool sublinear;
	
	unsigned trial = 0;
	for (; trial < num_times; trial += 1) {	
		if (trial > 0 && ((times[trial - 1] * sizes[trial])	> 10)) { break; }
		setA = &setsA[trial];
		setB = &setsB[trial];
		setAPrime = &setsAPrime[trial];
		times[trial] = timeFunction(fun);
		printf("time taken for size %d was %g\n",
			sizes[trial], times[trial]);
	}
	
	if (trial < 3) {
		printf("I'm sorry, your program is way too inefficient.\n");
		printf("you'll need to find a way-faster computer to test it on\n");
		return SUPER_LINEAR;
	}
	linear = checkLinear(times, sizes, 0, trial - 1) 
		|| checkLinear(times, sizes, 1, trial - 1);
	sublinear = checkSubLinear(times, sizes, 0, trial - 1)
		|| checkSubLinear(times, sizes, 1, trial - 1);
	
	if (sublinear) { return SUB_LINEAR; }
	else if (linear) { return LINEAR; }
	else { return SUPER_LINEAR; }
}

void testTime(void) {
	Scales behavior[NUM_TESTS];

	for (uint32_t k = 0; k < num_times; k += 1) {
		printf("creating a random set with %d elements...", sizes[k]);
		fflush(stdout);
		createRandomSetN(sizes[k], &setsA[k], &setsB[k]);
		int x = 10 * sizes[k];
		createCopySet(&setsAPrime[k], &setsA[k]);
		insertSet(&setsA[k], x);
		insertSet(&setsAPrime[k], x + 1);
		insertSet(&setsB[k], x);
		printf("done\n");
	}
	
	printf("checking scaling of isMember\n");
	behavior[IS_MEMBER] = determineScaling(&isMemberTimeFun);
	printf("isMember's scaling appears to be: %s\n", scaling_strings[behavior[IS_MEMBER]]);

	printf("checking scaling of isEqualTo\n");
	behavior[IS_EQUAL_TO] = determineScaling(&isEqualTimeFun);
	printf("isEqualTo's scaling appears to be: %s\n", scaling_strings[behavior[IS_EQUAL_TO]]);

	printf("checking scaling of isSubsetOf\n");
	behavior[IS_SUBSET_OF] = determineScaling(&isSubsetTimeFun);
	printf("isSubsetOf's scaling appears to be: %s\n", scaling_strings[behavior[IS_SUBSET_OF]]);
	
	printf("checking scaling of unionIn\n");
	behavior[UNION_IN] = determineScaling(&unionTimeFun);
	printf("unionIn's scaling appears to be: %s\n", scaling_strings[behavior[UNION_IN]]);

	printf("checking scaling of intersectFrom\n");
	behavior[INTERSECT_FROM] = determineScaling(&intersectTimeFun);
	printf("intersectFrom's scaling appears to be: %s\n", scaling_strings[behavior[INTERSECT_FROM]]);
	
	printf("checking scaling of subtractFrom\n");
	behavior[SUBTRACT_FROM] = determineScaling(&subtractTimeFun);
	printf("subtractFrom's scaling appears to be: %s\n", scaling_strings[behavior[SUBTRACT_FROM]]);

	printf("Performance Summary:\n");
	printf("isMemberSet\t\t%s\n", scaling_strings[behavior[IS_MEMBER]]);
	printf("isEqualToSet\t\t%s\n", scaling_strings[behavior[IS_EQUAL_TO]]);
	printf("isSubsetOf\t\t%s\n", scaling_strings[behavior[IS_SUBSET_OF]]);
	printf("unionInSet\t\t%s\n", scaling_strings[behavior[UNION_IN]]);
	printf("intersectFromSet\t%s\n", scaling_strings[behavior[INTERSECT_FROM]]);
	printf("subtractFromSet\t\t%s\n", scaling_strings[behavior[SUBTRACT_FROM]]);
}

Makefile

# New Makefile that automatically depends itself
#
# $Id: Makefile,v 1.3 1996/12/17 19:52:37 chase Exp $
#

IFLAGS = 
DFLAGS = 
CXX = g++ --std=c++11
CC  = $(GCC)
GCC = g++ --std=c++11
LD  = $(CXX)

LIBS = 

WFLAGS = -Wall 
SYMFLAGS = -g

PROFILE = #-pg 
OPTFLAGS =#-O
CFLAGS = $(OPTFLAGS) $(PROFILE) $(WFLAGS) $(IFLAGS) $(SYMFLAGS)
CXXFLAGS = $(CFLAGS)
CPPFLAGS = $(IFLAGS) $(DFLAGS)
LDFLAGS = $(PROFILE) -g 

PROGRAM = proj5
#CXXSRCS = Source.cpp

CXXSRCS = $(shell ls *.cpp)
          

SRCS = $(CXXSRCS) 

OBJS = $(CXXSRCS:.cpp=.o)

all: $(PROGRAM)

$(PROGRAM): $(OBJS)
	$(LD) -o $@ $(LDFLAGS) $(OBJS) $(LIBS)

test: $(PROGRAM)
	./$(PROGRAM)

clean:
	-rm -f $(OBJS) $(PROGRAM)

tidy:
	-rm -f *.BAK *.bak *.CKP

undepend:
	-rm -f $(OBJS:%.o=.%.d) 

spotless: tidy clean undepend

.y.cpp:
	$(BISON) $(BISONFLAGS) -o $@ $<
	mv $@.h $*.h
	mv $@.output $*.output
.l.cpp:
	$(FLEX) ${FLEXFLAGS} -t $< > $@

# auto depend stuff for GNU make only
depend: undepend
	@echo ""
	@echo "Dependences are handled automatically, just \"make\""

ifneq ($(strip $(CSRCS)),)
.%.d: %.c 
	$(SHELL) -ec '$(GCC) -MM $(CPPFLAGS) $< > $@'


include $(CSRCS:%.c=.%.d)
endif 

ifneq ($(strip $(CXXSRCS)),)
.%.d: %.cpp
	$(SHELL) -ec '$(GCC) -MM $(CPPFLAGS) $< > $@'

include $(CXXSRCS:%.cpp=.%.d) 
endif 

Project5.cpp

/*
 * Project5.cpp
 *
 * <NAME HERE>
 *
 *
 */

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

/*
 * Design NOTES:
 *
 * The design provided in this starter kit assumes
 * (1) empty sets will be represented with length == 0 and elements == nullptr (i.e., address 0)
 * (2) amortized doubling is not used, and capacity is ignored/unused. Functions should assume that 
 * the amount of storage available in the elements[] array is equal to length
 */



/* Free the elements of the given set. */
void destroySet(Set* self) {
    free(self->elements);
}

/* Set elements to the null pointer and len to 0. */
void createEmptySet(Set* self) {
    self->len = 0;
    self->elements = 0;
    self->capacity = 0;
}

/* Initialize a set to be filled with one element only. */
void createSingletonSet(Set* self, int x) {
    self->elements = (int*) malloc(sizeof(int));
    self->elements[0] = x;
    self->len = 1;
    self->capacity = 1;
}

/* Copy the elements from the second set to the first set.
 * WARNING: Does no checking for capacity. */
void createCopySet(Set* self, const Set* other) {
    self->elements = (int*) malloc(other->len * sizeof(int));
    for (int k = 0; k < other->len; k += 1) {
        self->elements[k] = other->elements[k];
    }
    self->len = other->len;
    self->capacity = other->capacity;
}

/* Deallocates the set and copies the second set to the first. */
void assignSet(Set* self, const Set* other) {
    if (self == other) { return; }
    destroySet(self);
    createCopySet(self, other);
}

/* Return true if x is an element of self.
 * Otherwise, return false.
 */
bool isMemberSet(const Set* self, int x) {
    if (self->len == 0) {
        return false;
    }
    int min=0, mid, max=self->len;
    while (min < max) {
        mid = (min+max)/2;
        if (self->elements[mid] < x)
            min = mid+1;
        else
            max = mid;
    }
    return ((max == min) && (self->elements[min] == x));
}

/* Add x as a new member to this set. */
void insertSet(Set* self, int x) {
    if (self->len == 0) {
        createSingletonSet(self, x);
        return;
    }
    /* If x is already a member of the set,
     * then self should not be changed.
     */
    if (!isMemberSet(self, x)) {
        /* If there is no room left in the elements,
         * allocate double the length.
         */
        if (self->len+1 >= self->capacity) {
            self->capacity *= 2;
            int* new_elements = (int*) malloc(sizeof(int)*(2+(self->capacity)));
            int i = 0; //new_elements iterator
            int j = 0; //self->elements iterator
            /* Cleverly copy the elements */
            while (i <= (self->len)) {
                if ((i == j) && (self->len == 1) && (i == 0)) {
                    if (x < self->elements[j]) {
                        new_elements[i] = x;
                        new_elements[i+1] = self->elements[j];
                        i += 2; ++j;
                    } else {
                        new_elements[i] = self->elements[j];
                        ++i; ++j;
                    }
                    continue;
                }
                /* If we are at the end and we have not inserted x yet. */
                if ((i == j) && (i == self->len-1)) {
                    /* Copy the last element. */
                    new_elements[i] = self->elements[j];
                    /* Set the element after the last to x. */
                    new_elements[self->len] = x;
                    break;
                }
                /* If we are in the right spot to insert x. */
                if ((i == j) && (x < self->elements[j])) {
                    new_elements[i] = x;
                    new_elements[i+1] = self->elements[j];
                    /* Hop an extra time for the new element. */
                    i += 2; ++j;
                } else {
                    new_elements[i] = self->elements[j];
                    /* Iterate both arrays. */
                    ++i; ++j;
                }
            }
            printf("%d %d %d\n",
                    self->capacity, self->len, (self->elements)[0]);
            destroySet(self);
            /* Set the pointer of the copied array to the current array. */
            self->elements = new_elements;
            ++(self->len);
        } else {
            int min=0, mid, max=self->len;
            while (min < max) {
                mid = (min+max)/2;
                if (self->elements[mid] < x)
                    min = mid+1;
                else
                    max = mid;
            }
            int temp;
            int swap = self->elements[min];
            self->elements[min] = x;
            /* Rotate the remaining elements down. */
            for (int i = min+1; i < (self->len)+1; ++i) {
                temp = self->elements[i];
                self->elements[i] = swap;
                swap = temp;
            }
            ++(self->len);
        }
    }
}


/* Remove an element from the set. */
void removeSet(Set* self, int x) {
    if (self->len == 0) {
        return;
    }
    int min=0, mid, max=self->len;
    while (min < max) {
        mid = (min+max)/2;
        //assert(mid < max);
        if (self->elements[mid] < x)
            min = mid+1;
        else
            max = mid;
    }
    /* If the value was in the array, */
    if ((max == min) && (self->elements[min] == x)) {
        /* Rotate the elements down. */
        for (int i = min; i < (self->len)-1; ++i) {
            self->elements[i] = self->elements[i+1];
        }
        --(self->len);
    }
}

/* done for you already */
void displaySet(const Set* self) {
    int k;
    printf("{");
    if (self->len == 0) { 
        printf("}"); 
    } else {
        for (k = 0; k < self->len; k += 1) {
            if (k < self->len - 1) {
                printf("%d,", self->elements[k]);
            } else {
                printf("%d}", self->elements[k]);
            }
        }
    }
}

/* Return true if self and other have exactly the same elements.
 * Complexity: O(n)
 */
bool isEqualToSet(const Set* self, const Set* other) {
    if (self->len != other->len){ return false; }
    for (int i = 0; i < self->len; ++i) {
        if (self->elements[i] != other->elements[i]){
            return false;
        }
    }
    return true;
}

/* Return true if every element of self is also an element of other
 * Complexity: O(n)
 */
bool isSubsetOf(const Set* self, const Set* other) {
    if (self->len > other->len){ return false; }
    for (int i = 0; i < self->len; ++i) {
        if (isMemberSet(other, self->elements[i])) {
            return false;
        }
    }
    return true;
}

/* Check if the set is empty.
 * Complexity: O(1)
 */
bool isEmptySet(const Set* self) {
    return self->len == 0;
}

/* Remove all elements from self that are not also elements of other */
void intersectFromSet(Set* self, const Set* other) {
    for (int i = 0; i < other->len; ++i) {
        if (!isMemberSet(self, other->elements[i])) {
            removeSet(self, other->elements[i]);
        }
    }
}

/* Remove all elements from self that are also elements of other */
void subtractFromSet(Set* self, const Set* other) {
    for (int i = 0; i < other->len; ++i) {
        removeSet(self, other->elements[i]);
    }
}

/* Add all elements of other to self
 * (obviously, without creating duplicate elements) */
void unionInSet(Set* self, const Set* other) {
    for (int i = 0; i < other->len; ++i) {
        insertSet(self, other->elements[i]);
    }
}

Set.h

#ifndef _Set_h
#define _Set_h 1

struct Set {
	int* elements; 
	int len;
	int capacity; // NOTE: amortized doubling does not improve the time complexity for these problems
	/* in fact, you can safely ignore capacity entirely. I'm including it here just in case some
	 * students feel more comfortable tracking the array size and the number of elements independently
	 * REPEATNG: You do not need to to implement amortized doubling in order to achieve the time-complexity
	 * bounds for this problem. You can achieve all the time complexity bounds even when
	 * capacity is ignored (i.e., your design can assume capacity == len).
	 */
};

/* creation, assignment and destruction functions */
void createSingletonSet(Set* self, int x); // construct a set containing only the element x
void createEmptySet(Set* self); // construct a set containing no elements
void createCopySet(Set* self, const Set* other); // construct a new set that has the same elements as other
void assignSet(Set* self, const Set* other); // replace the elements in this set with the elements of other
void destroySet(Set* self);

/* predicate functions */
bool isMemberSet(const Set* self, int x); // return true iff x is an element in the set
bool isEmptySet(const Set* self); // return true iff the set contains zero elements
bool isEqualToSet(const Set* self, const Set* other); // return true iff this and other
	                                       	// contain the same elements
bool isSubsetOf(const Set* self, const Set* other);	// return true if all of the elements
	                                        	// self are also elements of other
	                                        	// NOTE: for any set, x, x is a subset
	                                        	// of itself.
	/* printing */
void displaySet(const Set* self);

/* scalar manipulation functions */
void insertSet(Set* self, int x); // insert x into this set.  does nothing if
	                   	//   x is already in the set
void removeSet(Set* self, int x); // remove x from this set.  does nothing if 
	                  	//   x is not in the set

/* manipulations with sets */
void unionInSet(Set* self, const Set* other); // replace the elements of self with self union other
void intersectFromSet(Set* self, const Set* other); // replace the elements of self with self intersection other
void subtractFromSet(Set* self, const Set* other); // replace the elements of self with self minus other

#endif /* _Set_h */