+/EE312
software design
git clone https://git.julia.blue/+/EE312
7bf8175
master
1#include <stdio.h> 2#include <stdint.h> 3#include <stdlib.h> 4#include <assert.h> 5#include <chrono> 6#include <time.h> 7#include "Set.h" 8 9unsigned time (); 10int const number_of_tests = 1000 ; 11int const maximum_set_size = 100 ; 12 13void randomSet (Set * s ); 14void visualTests (void ); 15void equalityTests (void ); 16void specialCaseTests (void ); 17void relationalTests (void ); 18void algebraicTests (void ); 19void testTime (void ); 20 21int main (void ) { 22visualTests (); 23equalityTests (); 24specialCaseTests (); 25relationalTests (); 26algebraicTests (); 27testTime (); 28printf ("The tests are over\n" ); 29return 0 ; 30} 31 32void randomSet (Set * s ) { 33Set t ; 34int n = rand () %maximum_set_size + 1 ; 35int i ; 36 37createEmptySet (& t ); 38for (i = 0 ;i < n ;i += 1 ) { 39insertSet (& t ,rand () %maximum_set_size ); 40 } 41assignSet (s ,& t ); 42destroySet (& t ); 43} 44 45void showOutput (const char * str ,Set * set ) { 46printf ("%s" ,str ); 47displaySet (set ); 48printf ("\n" ); 49} 50 51void visualTests () { 52Set s ; 53Set t ; 54int i ; 55createEmptySet (& s ); 56showOutput ("The set constructed with the default constructor: " ,& s ); 57 58for (i = 0 ;i < 10 ;i += 1 ) { 59insertSet (& s ,i ); 60 } 61showOutput ("The set should be {0, ..., 9}: " ,& s ); 62 63// test Insert() and Contains() with '<<' 64for (i = 0 ;i < 10 ;i += 1 ) { 65insertSet (& s ,i ); 66 } 67showOutput ("The set should be {0, ..., 9}: " ,& s ); 68 69createCopySet (& t ,& s ); 70showOutput ("The copy of s constructed with the copy constructor = " ,& t ); 71 72randomSet (& t ); 73showOutput ("The random set generated equals = " ,& t ); 74 75printf ("The visual tests are over\n" ); 76destroySet (& s ); 77destroySet (& t ); 78} 79 80void equalityTests (void ) { 81int i ; 82for (i = 0 ;i < number_of_tests ;i += 1 ) { 83Set s ; 84Set t ; 85 86createEmptySet (& s ); 87randomSet (& s ); 88createCopySet (& t ,& s ); 89assert (isEqualToSet (& t ,& s )); 90assert (isEqualToSet (& s ,& t )); 91insertSet (& t ,maximum_set_size ); 92assert (!isEqualToSet (& s ,& t )); 93assert (!isEqualToSet (& t ,& s )); 94randomSet (& t ); 95assert (!isEqualToSet (& t ,& s )); 96destroySet (& s ); 97destroySet (& t ); 98 }// This test could fail with small probability 99printf ("The equality tests have been passed\n" ); 100} 101 102typedef void (* setFun )(Set * ,const Set * ); 103void checkCase (setFun fun ,Set * s1 ,Set * s2 ,Set * expect ) { 104Set res ; 105createCopySet (& res ,s1 ); 106 (* fun )(& res ,s2 ); 107assert (isEqualToSet (& res ,expect )); 108destroySet (& res ); 109} 110 111void specialCaseTests (void ) { 112Set empty ; 113Set universal ; 114int i ; 115Set s ; 116Set r ; 117 118createEmptySet (& empty ); 119createEmptySet (& universal ); 120createEmptySet (& r ); 121for (i = 0 ;i < maximum_set_size ;i += 1 ) { 122insertSet (& universal ,i ); 123 } 124checkCase (& subtractFromSet ,& universal ,& universal ,& empty ); 125checkCase (& unionInSet ,& universal ,& universal ,& universal ); 126checkCase (& intersectFromSet ,& universal ,& universal ,& universal ); 127checkCase (& intersectFromSet ,& universal ,& empty ,& empty ); 128checkCase (& intersectFromSet ,& empty ,& universal ,& empty ); 129checkCase (& unionInSet ,& universal ,& empty ,& universal ); 130checkCase (& unionInSet ,& empty ,& universal ,& universal ); 131checkCase (& unionInSet ,& empty ,& empty ,& empty ); 132checkCase (& subtractFromSet ,& empty ,& empty ,& empty ); 133checkCase (& intersectFromSet ,& empty ,& empty ,& empty ); 134 135createEmptySet (& s ); 136assert (isEmptySet (& s )); 137for (i = 0 ;i < 10 ;i += 1 ) { 138insertSet (& s ,i ); 139 } 140assert (s .len == 10 ); 141for (i = 0 ;i < 10 ;i += 1 ) { 142assert (isMemberSet (& s ,i )); 143 } 144for (i = 0 ;i < 10 ;i += 1 ) { 145removeSet (& s ,i ); 146removeSet (& s ,i ); 147assert (s .len == 9 - i ); 148 } 149assert (isEmptySet (& s )); 150for (i = 0 ;i < number_of_tests ;i += 1 ) { 151randomSet (& s ); 152assert (isSubsetOf (& empty ,& s )); 153assert (!isSubsetOf (& s ,& empty )); 154assert (isSubsetOf (& s ,& universal )); 155assert (!isSubsetOf (& universal ,& s )); 156 157checkCase (& intersectFromSet ,& empty ,& s ,& empty ); 158checkCase (& intersectFromSet ,& s ,& empty ,& empty ); 159checkCase (& intersectFromSet ,& universal ,& s ,& s ); 160checkCase (& intersectFromSet ,& s ,& universal ,& s ); 161 162checkCase (& unionInSet ,& universal ,& s ,& universal ); 163 164checkCase (& unionInSet ,& s ,& universal ,& universal ); 165 166checkCase (& subtractFromSet ,& s ,& empty ,& s ); 167 168assignSet (& r ,& universal ); 169subtractFromSet (& r ,& s );// r = u - s; 170checkCase (& subtractFromSet ,& universal ,& r ,& s );// (u - (u - s) == s) 171checkCase (& unionInSet ,& s ,& r ,& universal );// s + (u - s) == u 172checkCase (& unionInSet ,& r ,& s ,& universal );// (u - s) + s == u 173 } 174printf ("The special case tests have been passed\n" ); 175destroySet (& empty ); 176destroySet (& universal ); 177destroySet (& s ); 178destroySet (& r ); 179} 180 181void relationalTests () { 182Set s ; 183Set t ; 184int i ; 185 186createEmptySet (& s ); 187createEmptySet (& t ); 188for (i = 0 ;i < number_of_tests ;i += 1 ) { 189randomSet (& s ); 190assignSet (& t ,& s ); 191assert (isSubsetOf (& s ,& t )); 192assert (isSubsetOf (& t ,& s )); 193assert (isEqualToSet (& s ,& t )); 194assert (isEqualToSet (& t ,& s )); 195insertSet (& s ,rand () %maximum_set_size + maximum_set_size ); 196assert (isSubsetOf (& t ,& s )); 197assert (!isSubsetOf (& s ,& t )); 198 } 199printf ("The relational tests have been passed\n" ); 200destroySet (& s ); 201destroySet (& t ); 202} 203 204void algebraicTests (void ) { 205Set empty ; 206Set universal ; 207int i ; 208Set s ; 209Set t ; 210Set u ; 211Set v ; 212Set w ; 213 214createEmptySet (& empty ); 215createEmptySet (& universal ); 216for (i = 0 ;i < maximum_set_size ;i += 1 ) { 217insertSet (& universal ,i ); 218 } 219 220createEmptySet (& s ); 221createEmptySet (& t ); 222createEmptySet (& u ); 223createEmptySet (& v ); 224createEmptySet (& w ); 225 226for (i = 0 ;i < number_of_tests ;i += 1 ) { 227randomSet (& u ); 228randomSet (& v ); 229randomSet (& w ); 230 231/* u + v == v + u */ 232assignSet (& s ,& u ); 233unionInSet (& s ,& v ); 234assignSet (& t ,& v ); 235unionInSet (& t ,& u ); 236assert (isEqualToSet (& s ,& t )); 237 238/* u + (v + w) == (u + v) + w */ 239assignSet (& t ,& v ); 240unionInSet (& t ,& w ); 241assignSet (& s ,& u ); 242unionInSet (& s ,& t ); 243assignSet (& t ,& u ); 244unionInSet (& t ,& v ); 245unionInSet (& t ,& w ); 246assert (isEqualToSet (& s ,& t )); 247 248/* u * v == v * u */ 249assignSet (& s ,& u ); 250intersectFromSet (& s ,& v ); 251assignSet (& t ,& v ); 252intersectFromSet (& t ,& u ); 253assert (isEqualToSet (& s ,& t )); 254 255/* u * (v * w) == (u * v) * w */ 256assignSet (& t ,& v ); 257intersectFromSet (& t ,& w ); 258assignSet (& s ,& u ); 259intersectFromSet (& s ,& t ); 260assignSet (& t ,& u ); 261intersectFromSet (& t ,& v ); 262intersectFromSet (& t ,& w ); 263assert (isEqualToSet (& s ,& t )); 264 265/* u - v == u - (u * v) */ 266assignSet (& s ,& u ); 267intersectFromSet (& s ,& v ); 268assignSet (& t ,& u ); 269subtractFromSet (& t ,& s ); 270assignSet (& s ,& u ); 271subtractFromSet (& s ,& v ); 272assert (isEqualToSet (& s ,& t )); 273 274/* additional tests, not implemented 275assert(w * (u - v) == w * u - w * v); 276assert(u * (v + w) == (u * v) + (u * w)); 277assert(universal - (u * v) == (universal - u) + (universal - v)); 278assert(universal - (u + v) == (universal - u) * (universal - v)); 279*/ 280 } 281printf ("The algebraic tests have been passed\n" ); 282destroySet (& empty ); 283destroySet (& universal ); 284destroySet (& s ); 285destroySet (& t ); 286destroySet (& u ); 287destroySet (& v ); 288destroySet (& w ); 289} 290 291/* 292* create two sets with n random elements 293* the sets should have 50% of the elements in common 294*/ 295void createRandomSetN (int n ,Set * a ,Set * b ) { 296int x ; 297int last_size = 0 ; 298createEmptySet (a ); 299while (a -> len < n ) { 300// printf("doing stuff %d\n", last_size); 301if (a -> len != last_size ) { 302last_size = a -> len ; 303if (last_size %1000 == 0 ) { 304printf ("%d.." ,last_size ); 305fflush (stdout ); 306 } 307 } 308x = 2 * (5 * n - (rand () % (10 * n ))); 309if (isMemberSet (a ,x )) { 310continue ;// try another number 311 } 312/* a will have only even elements */ 313insertSet (a ,x ); 314if ((rand () %2 )== 0 ) { 315insertSet (b ,x ); 316 }else { 317insertSet (b ,x + 1 );// an odd value, can't be in a 318 } 319 } 320assert (a -> len == b -> len ); 321} 322 323typedef void (* Function )(void ); 324 325double timeFunction (Function f ) { 326int reps = 128 ; 327uint64_t time = 0 ; 328volatile int k ; 329while (time < 6000 ) { 330if (reps > 1000000000 ) { 331return 0.0 ;// overflow? 332 } 333auto start = std::chrono::high_resolution_clock::now (); 334for (k = 0 ;k < reps ;k += 1 ) { 335f (); 336 } 337auto end = std::chrono::high_resolution_clock::now (); 338time = std::chrono::duration_cast < std::chrono::milliseconds > 339 (end - start ).count (); 340reps *=2 ; 341 } 342 343return ((double )time ) /reps ; 344} 345 346volatile int 347bogus_value ;// used to ensure compiler does not optimize away our func calls 348 349Set * setA ; 350Set * setB ; 351Set * setAPrime ;// almost exactly the same as A 352 353int is_mem_x ; 354void isMemberTimeFun (void ) { 355if (isMemberSet (setA ,is_mem_x )) { 356is_mem_x ^=1 ; 357is_mem_x <<=1 ; 358 }else { 359is_mem_x >>=1 ; 360is_mem_x ^=2 ; 361 } 362} 363 364void isEqualTimeFun (void ) { 365bogus_value = isEqualToSet (setA ,setAPrime ); 366} 367 368void isSubsetTimeFun (void ) { 369bogus_value = isSubsetOf (setA ,setAPrime ); 370} 371 372void unionTimeFun (void ) { 373Set t ; 374createCopySet (& t ,setA ); 375unionInSet (& t ,setB ); 376destroySet (& t ); 377} 378 379void intersectTimeFun (void ) { 380Set t ; 381createCopySet (& t ,setA ); 382intersectFromSet (& t ,setB ); 383destroySet (& t ); 384} 385 386void subtractTimeFun (void ) { 387Set t ; 388createCopySet (& t ,setA ); 389subtractFromSet (& t ,setB ); 390destroySet (& t ); 391} 392 393bool checkLinear (double times [],int sizes [],int first ,int last ) { 394double time_ratio = times [last ] /times [first ]; 395double size_ratio = sizes [last ] /sizes [first ]; 396 397if (time_ratio < size_ratio * 1.25 ) { 398return true; 399 }else { 400return false; 401 } 402} 403 404bool checkSubLinear (double times [],int sizes [],int first ,int last ) { 405double time_ratio = times [last ] /times [first ]; 406double size_ratio = sizes [last ] /sizes [first ]; 407 408if (time_ratio < size_ratio * 0.5 ) { 409return true; 410 }else { 411return false; 412 } 413} 414 415enum Tests { 416IS_MEMBER = 0 , 417INSERT = 1 , 418REMOVE = 2 , 419IS_EQUAL_TO = 3 , 420IS_SUBSET_OF = 4 , 421UNION_IN = 5 , 422INTERSECT_FROM = 6 , 423SUBTRACT_FROM = 7 , 424 425NUM_TESTS /* MUST BE LAST */ 426}; 427 428typedef enum Scales { 429SUB_LINEAR , 430LINEAR , 431SUPER_LINEAR 432}Scales ; 433/* NOTE: the order of these strings MUST MATCH EXACTLY the order of the Scales enum */ 434const char * scaling_strings []= { 435"sub linear (YAHOO!)" , 436"linear" , 437"super linear, yuck." 438}; 439 440int sizes []= {100 ,400 ,1600 ,6400 ,25600 }; 441//const unsigned num_times = sizeof(sizes) / sizeof(int); 442#define num_times (sizeof(sizes) / sizeof(int)) 443Set setsA [num_times ]; 444Set setsAPrime [num_times ]; 445Set setsB [num_times ]; 446double times [num_times ]; 447 448Scales determineScaling (Function fun ) { 449bool linear ; 450bool sublinear ; 451 452unsigned trial = 0 ; 453for (;trial < num_times ;trial += 1 ) { 454if (trial > 0 && ((times [trial - 1 ]* sizes [trial ])> 10 )) { 455break ; 456 } 457setA = & setsA [trial ]; 458setB = & setsB [trial ]; 459setAPrime = & setsAPrime [trial ]; 460times [trial ]= timeFunction (fun ); 461printf ("time taken for size %d was %g\n" , 462sizes [trial ],times [trial ]); 463 } 464 465if (trial < 3 ) { 466printf ("I'm sorry, your program is way too inefficient.\n" ); 467printf ("you'll need to find a way-faster computer to test it on\n" ); 468return SUPER_LINEAR ; 469 } 470linear = checkLinear (times ,sizes ,0 ,trial - 1 ) 471|| checkLinear (times ,sizes ,1 ,trial - 1 ); 472sublinear = checkSubLinear (times ,sizes ,0 ,trial - 1 ) 473|| checkSubLinear (times ,sizes ,1 ,trial - 1 ); 474 475if (sublinear ) { 476return SUB_LINEAR ; 477 }else if (linear ) { 478return LINEAR ; 479 }else { 480return SUPER_LINEAR ; 481 } 482} 483 484void testTime (void ) { 485Scales behavior [NUM_TESTS ]; 486 487for (uint32_t k = 0 ;k < num_times ;k += 1 ) { 488printf ("creating a random set with %d elements..." ,sizes [k ]); 489fflush (stdout ); 490createRandomSetN (sizes [k ],& setsA [k ],& setsB [k ]); 491printf ("done creating\n" ); 492int x = 10 * sizes [k ]; 493createCopySet (& setsAPrime [k ],& setsA [k ]); 494insertSet (& setsA [k ],x ); 495insertSet (& setsAPrime [k ],x + 1 ); 496insertSet (& setsB [k ],x ); 497printf ("done\n" ); 498 } 499 500printf ("checking scaling of isMember\n" ); 501behavior [IS_MEMBER ]= determineScaling (& isMemberTimeFun ); 502printf ("isMember's scaling appears to be: %s\n" , 503scaling_strings [behavior [IS_MEMBER ]]); 504 505printf ("checking scaling of isEqualTo\n" ); 506behavior [IS_EQUAL_TO ]= determineScaling (& isEqualTimeFun ); 507printf ("isEqualTo's scaling appears to be: %s\n" , 508scaling_strings [behavior [IS_EQUAL_TO ]]); 509 510printf ("checking scaling of isSubsetOf\n" ); 511behavior [IS_SUBSET_OF ]= determineScaling (& isSubsetTimeFun ); 512printf ("isSubsetOf's scaling appears to be: %s\n" , 513scaling_strings [behavior [IS_SUBSET_OF ]]); 514 515printf ("checking scaling of unionIn\n" ); 516behavior [UNION_IN ]= determineScaling (& unionTimeFun ); 517printf ("unionIn's scaling appears to be: %s\n" , 518scaling_strings [behavior [UNION_IN ]]); 519 520printf ("checking scaling of intersectFrom\n" ); 521behavior [INTERSECT_FROM ]= determineScaling (& intersectTimeFun ); 522printf ("intersectFrom's scaling appears to be: %s\n" , 523scaling_strings [behavior [INTERSECT_FROM ]]); 524 525printf ("checking scaling of subtractFrom\n" ); 526behavior [SUBTRACT_FROM ]= determineScaling (& subtractTimeFun ); 527printf ("subtractFrom's scaling appears to be: %s\n" , 528scaling_strings [behavior [SUBTRACT_FROM ]]); 529 530printf ("Performance Summary:\n" ); 531printf ("isMemberSet\t\t%s\n" ,scaling_strings [behavior [IS_MEMBER ]]); 532printf ("isEqualToSet\t\t%s\n" ,scaling_strings [behavior [IS_EQUAL_TO ]]); 533printf ("isSubsetOf\t\t%s\n" ,scaling_strings [behavior [IS_SUBSET_OF ]]); 534printf ("unionInSet\t\t%s\n" ,scaling_strings [behavior [UNION_IN ]]); 535printf ("intersectFromSet\t%s\n" ,scaling_strings [behavior [INTERSECT_FROM ]]); 536printf ("subtractFromSet\t\t%s\n" ,scaling_strings [behavior [SUBTRACT_FROM ]]); 537for (int i = 0 ;i < num_times ;i ++ ) { 538destroySet (& setsA [i ]); 539destroySet (& setsAPrime [i ]); 540destroySet (& setsB [i ]); 541 } 542}