+/EE312

software design

git clone https://git.julia.blue/+/EE312

Joseph RyanProject 57bf8175

master
7.1 KiB260 linesraw
1// Set Project5.cpp
2// EE 312 Project 5 submission by
3// Joseph Ryan
4// jbr2558
5// Slip days used: <0>
6// Spring 2018
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <assert.h>
11#include "Set.h"
12
13/*
14 * Several of the required functions have been written already
15 * You may use these functions as-is or you may modify them in any way.
16 * Please NOTE, you are responsible for ensuring that the functions work correctly in
17 * your project solution. Just because the function works correctly in my solution does
18 * NOT mean that the function will work correctly in yours.
19 */
20
21/*
22 * Design NOTES:
23 *
24 * The design provided in this starter kit assumes
25 * (1) empty sets will be represented with length == 0 and elements == nullptr (i.e., address 0)
26 * (2) amortized doubling is not used, and capacity is ignored/unused. Functions should assume that
27 * the amount of storage available in the elements[] array is equal to length
28 */
29
30
31
32/* done for you already */
33void destroySet(Set* self) {
34    free(self->elements);
35}
36
37/* done for you already */
38void createEmptySet(Set* self) {
39    self->len = 0;
40    self->elements = 0;
41}
42
43/* done for you already */
44void createSingletonSet(Set* self, int x) {
45    self->elements = (int*) malloc(sizeof(int));
46    self->elements[0] = x;
47    self->len = 1;
48}
49
50/* done for you already */
51void createCopySet(Set* self, const Set* other) {
52    self->elements = (int*) malloc(other->len * sizeof(int));
53    for (int k = 0; k < other->len; k += 1) {
54        self->elements[k] = other->elements[k];
55    }
56    self->len = other->len;
57}
58
59/* done for you already */
60void assignSet(Set* self, const Set* other) {
61    if (self == other) {
62        return;
63    }
64
65    destroySet(self);
66    createCopySet(self, other);
67}
68
69/* return true if x is an element of self */
70bool isMemberSet(const Set* self, int x) {
71    int low = 0;
72    int high = self->len - 1;
73    while(low <= high) {
74        int temp = (high + low) / 2;
75        if(self->elements[temp] == x) {
76            return 1;
77        } else if(self->elements[temp] > x) {
78            high = temp - 1;
79        } else {
80            low = temp + 1;
81        }
82    }
83    return 0;
84}
85
86/*
87 * add x as a new member to this set.
88 * If x is already a member, then self should not be changed
89 * Be sure to restore the design invariant property that elemnts[] remains sorted
90 * (yes, you can assume it is sorted when the function is called, that's what an invariant is all about)
91 */
92void insertSet(Set* self, int x) {
93    int i;
94    for(i = 0; i < self->len && self->elements[i] < x; ++i);
95    if(i < self->len && self->elements[i] == x) {
96        return;
97    }
98    int temp = self->len;
99    ++self->len;
100    self->elements = (int*)realloc(self->elements, sizeof(int) * self->len);
101    while(temp > i) {
102        self->elements[temp] = self->elements[temp - 1];
103        --temp;
104    }
105    self->elements[i] = x;
106}
107
108
109/*
110 * don't forget: it is OK to try to remove an element
111 * that is NOT in the set.
112 * If 'x' is not in the set 'self', then
113 * removeSet should do nothing (it's not an error)
114 * Otherwise, ('x' IS in the set), remove x. Be sure to update self->length
115 * It is not necessary (nor recommended) to call malloc -- if removing an element means the
116 * array on the heap is "too big", that's almost certainly OK, and reallocating a smaller array
117 * is almost definitely NOT worth the trouble
118 */
119void removeSet(Set* self, int x) {
120    for(int i = 0; i < self->len; ++i) {
121        if(self->elements[i] == x) {
122            --self->len;
123            while(i < self->len) {
124                self->elements[i] = self->elements[i + 1];
125                ++i;
126            }
127            return;
128        }
129    }
130}
131
132/* done for you already */
133void displaySet(const Set* self) {
134    int k;
135
136    printf("{");
137
138    if (self->len == 0) {
139        printf("}");
140    } else {
141        for (k = 0; k < self->len; k += 1) {
142            if (k < self->len - 1) {
143                printf("%d,", self->elements[k]);
144            } else {
145                printf("%d}", self->elements[k]);
146            }
147        }
148    }
149}
150
151/* return true if self and other have exactly the same elements */
152bool isEqualToSet(const Set* self, const Set* other) {
153    if(self->len != other->len) {
154        return 0;
155    }
156    int i = 0, j = 0;
157    while(i < self->len && j < other->len) {
158        if(self->elements[i] == other->elements[j]) {
159            ++i;
160            ++j;
161        } else {
162            return 0;
163        }
164    }
165    return i == j;
166}
167
168/* return true if every element of self is also an element of other */
169bool isSubsetOf(const Set* self, const Set* other) {
170    int i = 0, j = 0;
171    while( i < self->len ) {
172        while(j < other->len && other->elements[j] < self->elements[i]) {
173            ++j;
174        }
175        if(j == other->len || other->elements[j] != self->elements[i]) {
176            return 0;
177        }
178        ++i;
179    }
180    return 1;
181}
182
183/* done for you */
184bool isEmptySet(const Set* self) {
185    return self->len == 0;
186}
187
188/* remove all elements from self that are not also elements of other */
189void intersectFromSet(Set* self, const Set* other) {
190    int i = 0, j = 0, found = 0;
191    while(i < self->len && j < other->len) {
192        if(self->elements[i] == other->elements[j]) {
193            self->elements[found] = self->elements[i];
194            ++j;
195            ++i;
196            ++found;
197        } else if(self->elements[i] < other->elements[j]) {
198            ++i;
199        } else {
200            ++j;
201        }
202    }
203    self->len = found;
204}
205
206/* remove all elements from self that are also elements of other */
207void subtractFromSet(Set* self, const Set* other) {
208    int i = 0, j = 0, k = 0;
209    while(i < self->len && j < other->len) {
210        if(self->elements[i] < other->elements[j]) {
211            self->elements[k] = self->elements[i];
212            ++i;
213            ++k;
214        } else if(self->elements[i] == other->elements[j]) {
215            ++i;
216            ++j;
217        } else {
218            ++j;
219        }
220    }
221    while(i < self->len) {
222        self->elements[k] = self->elements[i];
223        ++i;
224        ++k;
225    }
226    self->len = k;
227}
228
229/* add all elements of other to self (obviously, without creating duplicate elements) */
230void unionInSet(Set* self, const Set* other) {
231    int* newElements = (int*)malloc((self->len + other->len) * sizeof(int));
232    int i = 0, j = 0, k = 0;
233    while(i < self->len && j < other->len) {
234        if(self->elements[i] == other->elements[j]) {
235            newElements[k] = self->elements[i];
236            ++i;
237            ++j;
238        } else if(self->elements[i] < other->elements[j]) {
239            newElements[k] = self->elements[i];
240            ++i;
241        } else {
242            newElements[k] = other->elements[j];
243            ++j;
244        }
245        ++k;
246    }
247    while(i < self->len) {
248        newElements[k] = self->elements[i];
249        ++i;
250        ++k;
251    }
252    while(j < other->len) {
253        newElements[k] = other->elements[j];
254        ++j;
255        ++k;
256    }
257    free(self->elements);
258    self->elements = newElements;
259    self->len = k;
260}