+/EE312
software design
git clone https://git.julia.blue/+/EE312
7bf8175
master
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 ) { 34free (self -> elements ); 35} 36 37/* done for you already */ 38void createEmptySet (Set * self ) { 39self -> len = 0 ; 40self -> elements = 0 ; 41} 42 43/* done for you already */ 44void createSingletonSet (Set * self ,int x ) { 45self -> elements = (int * )malloc (sizeof (int )); 46self -> elements [0 ]= x ; 47self -> len = 1 ; 48} 49 50/* done for you already */ 51void createCopySet (Set * self ,const Set * other ) { 52self -> elements = (int * )malloc (other -> len * sizeof (int )); 53for (int k = 0 ;k < other -> len ;k += 1 ) { 54self -> elements [k ]= other -> elements [k ]; 55 } 56self -> len = other -> len ; 57} 58 59/* done for you already */ 60void assignSet (Set * self ,const Set * other ) { 61if (self == other ) { 62return ; 63 } 64 65destroySet (self ); 66createCopySet (self ,other ); 67} 68 69/* return true if x is an element of self */ 70bool isMemberSet (const Set * self ,int x ) { 71int low = 0 ; 72int high = self -> len - 1 ; 73while (low <=high ) { 74int temp = (high + low ) /2 ; 75if (self -> elements [temp ]== x ) { 76return 1 ; 77 }else if (self -> elements [temp ]> x ) { 78high = temp - 1 ; 79 }else { 80low = temp + 1 ; 81 } 82 } 83return 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 ) { 93int i ; 94for (i = 0 ;i < self -> len && self -> elements [i ]< x ;++ i ); 95if (i < self -> len && self -> elements [i ]== x ) { 96return ; 97 } 98int temp = self -> len ; 99++ self -> len ; 100self -> elements = (int * )realloc (self -> elements ,sizeof (int )* self -> len ); 101while (temp > i ) { 102self -> elements [temp ]= self -> elements [temp - 1 ]; 103-- temp ; 104 } 105self -> 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 ) { 120for (int i = 0 ;i < self -> len ;++ i ) { 121if (self -> elements [i ]== x ) { 122-- self -> len ; 123while (i < self -> len ) { 124self -> elements [i ]= self -> elements [i + 1 ]; 125++ i ; 126 } 127return ; 128 } 129 } 130} 131 132/* done for you already */ 133void displaySet (const Set * self ) { 134int k ; 135 136printf ("{" ); 137 138if (self -> len == 0 ) { 139printf ("}" ); 140 }else { 141for (k = 0 ;k < self -> len ;k += 1 ) { 142if (k < self -> len - 1 ) { 143printf ("%d," ,self -> elements [k ]); 144 }else { 145printf ("%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 ) { 153if (self -> len != other -> len ) { 154return 0 ; 155 } 156int i = 0 ,j = 0 ; 157while (i < self -> len && j < other -> len ) { 158if (self -> elements [i ]== other -> elements [j ]) { 159++ i ; 160++ j ; 161 }else { 162return 0 ; 163 } 164 } 165return 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 ) { 170int i = 0 ,j = 0 ; 171while (i < self -> len ) { 172while (j < other -> len && other -> elements [j ]< self -> elements [i ]) { 173++ j ; 174 } 175if (j == other -> len || other -> elements [j ]!= self -> elements [i ]) { 176return 0 ; 177 } 178++ i ; 179 } 180return 1 ; 181} 182 183/* done for you */ 184bool isEmptySet (const Set * self ) { 185return 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 ) { 190int i = 0 ,j = 0 ,found = 0 ; 191while (i < self -> len && j < other -> len ) { 192if (self -> elements [i ]== other -> elements [j ]) { 193self -> 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 } 203self -> len = found ; 204} 205 206/* remove all elements from self that are also elements of other */ 207void subtractFromSet (Set * self ,const Set * other ) { 208int i = 0 ,j = 0 ,k = 0 ; 209while (i < self -> len && j < other -> len ) { 210if (self -> elements [i ]< other -> elements [j ]) { 211self -> 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 } 221while (i < self -> len ) { 222self -> elements [k ]= self -> elements [i ]; 223++ i ; 224++ k ; 225 } 226self -> len = k ; 227} 228 229/* add all elements of other to self (obviously, without creating duplicate elements) */ 230void unionInSet (Set * self ,const Set * other ) { 231int * newElements = (int * )malloc ((self -> len + other -> len )* sizeof (int )); 232int i = 0 ,j = 0 ,k = 0 ; 233while (i < self -> len && j < other -> len ) { 234if (self -> elements [i ]== other -> elements [j ]) { 235newElements [k ]= self -> elements [i ]; 236++ i ; 237++ j ; 238 }else if (self -> elements [i ]< other -> elements [j ]) { 239newElements [k ]= self -> elements [i ]; 240++ i ; 241 }else { 242newElements [k ]= other -> elements [j ]; 243++ j ; 244 } 245++ k ; 246 } 247while (i < self -> len ) { 248newElements [k ]= self -> elements [i ]; 249++ i ; 250++ k ; 251 } 252while (j < other -> len ) { 253newElements [k ]= other -> elements [j ]; 254++ j ; 255++ k ; 256 } 257free (self -> elements ); 258self -> elements = newElements ; 259self -> len = k ; 260}