Can't get the adjustHeap function to work, doesn't seem right. Help! I inserted what i have so far in the fix me sections of dynamicArray.c

There are two parts to this assignment. In the first part, you will complete the implementation of heap-based Priority Queue and implement the Heapsort algorithm. In the second part, you will use the Priority Queue to implement a to-do list application. Heap implementation We will approach the heap implementation by adding an interface, in the form of a set of functions, to the dynamic array. You are required to implement all functions in dynamicArray.c that begin with the // FIXME: implement comment. The dynamic array uses the void* type for elements, so some of the heap functions will also take a function pointer as a parameter to use for element comparisons. This compare function has the following signature and will be implemented for use with the struct Task type in the todo list part of the assignment. #define TYPE void* ... /** * Returns * -1 if left < right, * 1 if left > right, * 0 if left == right. */ int compare(TYPE left, TYPE right); All heap interface function names begin with dyHeap . Refer to worksheets 33 and 34 for more information about them. Remember that all heap operations must maintain the heap property. Tests A test suite, using the CuTest library, is provided in tests.c . It covers all functions you are required to implement for this part of the assignment. If your implementation looks reasonable and passes all these tests, it is probably correct and will earn full points for this part of the assignment. To build the test suite, enter make tests on the command line. This will create a binary named tests . When you run it with ./tests , it will print a report detailing which tests failed with the line of the assertion that caused the failure. Each test function in tests.c has a name prefixed with test and suffixed with the name of the function being tested, and takes a CuTest* as a parameter. Feel free to add your own tests there is more on how to do that in the tests.c comments. Side note: any failed test may elicit a memory leak report in Valgrind. This is because the test halted on an assertion and did not reach the following cleanup code. If a memory leak is reported for a call stack containing a failing test, you may ignore it until that test passes. There are two parts to this assignment. In the first part, you will complete the implementation of heap-based Priority Queue and implement the Heapsort algorithm. In the second part, you will use the Priority Queue to implement a to-do list application. Heap implementation We will approach the heap implementation by adding an interface, in the form of a set of functions, to the dynamic array. You are required to implement all functions in dynamicArray.c that begin with the // FIXME: implement comment. The dynamic array uses the void* type for elements, so some of the heap functions will also take a function pointer as a parameter to use for element comparisons. This compare function has the following signature and will be implemented for use with the struct Task type in the todo list part of the assignment. #define TYPE void* ... /** * Returns * -1 if left < right, * 1 if left > right, * 0 if left == right. */ int compare(TYPE left, TYPE right); All heap interface function names begin with dyHeap . Refer to worksheets 33 and 34 for more information about them. Remember that all heap operations must maintain the heap property. Tests A test suite, using the CuTest library, is provided in tests.c . It covers all functions you are required to implement for this part of the assignment. If your implementation looks reasonable and passes all these tests, it is probably correct and will earn full points for this part of the assignment. To build the test suite, enter make tests on the command line. This will create a binary named tests . When you run it with ./tests , it will print a report detailing which tests failed with the line of the assertion that caused the failure. Each test function in tests.c has a name prefixed with test and suffixed with the name of the function being tested, and takes a CuTest* as a parameter. Feel free to add your own tests there is more on how to do that in the tests.c comments. Side note: any failed test may elicit a memory leak report in Valgrind. This is because the test halted on an assertion and did not reach the following cleanup code. If a memory leak is reported for a call stack containing a failing test, you may ignore it until that test passes.

dynamicArray.c - fill in code skeleton

#include "dynamicArray.h" #include #include #include

#define TESTING

#ifndef TESTING static void adjustHeap(DynamicArray* heap, int last, int position, compareFunction compare); static void buildHeap(DynamicArray* heap, compareFunction compare); #endif

struct DynamicArray { TYPE* data; int size; int capacity; };

// --- Dynamic array ---

static void setCapacity(DynamicArray* array, int capacity) { TYPE* data = malloc(sizeof(TYPE) * capacity); for (int i = 0; i < array->size; i++) { data[i] = array->data[i]; } free(array->data); array->data = data; array->capacity = capacity; }

static void init(DynamicArray* array, int capacity) { assert(capacity > 0); array->data = NULL; array->size = 0; setCapacity(array, capacity); }

DynamicArray* dyNew(int capacity) { DynamicArray* array = malloc(sizeof(DynamicArray)); init(array, capacity); return array; }

void dyDelete(DynamicArray* array) { free(array->data); free(array); }

void dyAdd(DynamicArray* array, TYPE value) { if (array->size >= array->capacity) { setCapacity(array, 2 * array->capacity); } array->data[array->size] = value; array->size++; }

void dyAddAt(DynamicArray* array, TYPE value, int position) { assert(position <= array->size); dyAdd(array, value); for (int i = array->size - 1; i > position; i--) { dySwap(array, i, i - 1); } }

void dyPut(DynamicArray* array, TYPE value, int position) { assert(position < array->size); array->data[position] = value; }

void dyRemoveAt(DynamicArray* array, int position) { assert(position < array->size); for (int i = position; i < array->size - 1; i++) { array->data[position] = array->data[position + 1]; } array->size--; }

TYPE dyGet(DynamicArray* array, int position) { assert(position < array->size); return array->data[position]; }

int dySize(DynamicArray* array) { return array->size; }

void dySwap(DynamicArray* array, int position1, int position2) { assert(position1 < array->size); assert(position2 < array->size); TYPE temp = array->data[position1]; array->data[position1] = array->data[position2]; array->data[position2] = temp; }

// --- Stack ---

void dyStackPush(DynamicArray* stack, TYPE value) { dyAdd(stack, value); }

void dyStackPop(DynamicArray* stack) { dyRemoveAt(stack, stack->size - 1); }

TYPE dyStackTop(DynamicArray* stack) { return dyGet(stack, stack->size - 1); }

int dyStackIsEmpty(DynamicArray* stack) { return stack->size == 0; }

// --- Bag ---

static int findFirst(DynamicArray* array, TYPE value, compareFunction compare) { for (int i = 0; i < array->size; i++) { if (compare(value, array->data[i]) == 0) { return i; } } return -1; }

void dyBagAdd(DynamicArray* bag, TYPE value) { dyAdd(bag, value); }

void dyBagRemove(DynamicArray* bag, TYPE value, compareFunction compare) { int position = findFirst(bag, value, compare); if (position != -1) { dyRemoveAt(bag, position); } }

int dyBagContains(DynamicArray* bag, TYPE value, compareFunction compare) { return findFirst(bag, value, compare) != -1; }

// --- Ordered bag ---

static int binarySearch(DynamicArray* array, TYPE value, compareFunction compare) { int low = 0; int high = array->size - 1; while (low <= high) { int middle = (low + high) / 2; if (compare(value, array->data[middle]) < 0) { high = middle - 1; } else if (compare(value, array->data[middle]) > 0) { low = middle + 1; } else { return middle; } } return low; }

void dyOrderedAdd(DynamicArray* bag, TYPE value, compareFunction compare) { int position = binarySearch(bag, value, compare); dyAddAt(bag,value, position); }

void dyOrderedRemove(DynamicArray* bag, TYPE value, compareFunction compare) { int position = binarySearch(bag, value, compare); if (compare(value, bag->data[position]) == 0) { dyRemoveAt(bag, position); } }

int dyOrderedContains(DynamicArray* bag, TYPE value, compareFunction compare) { int position = binarySearch(bag, value, compare); return compare(value, dyGet(bag, position)) == 0; }

// --- Heap ---

/** * Adjusts heap to maintain the heap property. * @param heap * @param last index to adjust up to. * @param position index where adjustment starts. * @param compare pointer to compare function. */ void adjustHeap(DynamicArray* heap, int last, int position, compareFunction compare) { // FIXME: implement

assert(position >= 0);

int leftChild = 2 * position + 1;

int rightChild = 2 * position + 2;

//if there's two children

if (rightChild < last) {

int leftNum = *(int*)dyGet(heap, leftChild);

int rightNum = *(int*)dyGet(heap, rightChild);

printf("left:%d, right: %d ", leftNum, rightNum);

//get index of smallest child

int comparison = compare(dyGet(heap, leftChild), dyGet(heap, rightChild));

int smallest;

if (comparison == -1) {

smallest = leftChild;

}

else if (comparison == 1) {

smallest = rightChild;

}

else

smallest = leftChild;

//if the position is greater than value of the smallest child

if (compare(dyGet(heap, position), dyGet(heap, smallest)) == 1) {

//swap smallest child

dySwap(heap, position, smallest);

//adjust the heap

adjustHeap(heap, last, smallest, compare);

last--;

}

}

else

printf("No children ");

}

/** * Builds a valid heap from an arbitrary array. * @param heap array with elements in any order. * @param compare pointer to compare function. */ void buildHeap(DynamicArray* heap, compareFunction compare) { // FIXME: implement

int max = dySize(heap);

int i = (max / 2) - 1;

while (i >= 0) {

adjustHeap(heap, max, i, compare);

while (i >= 0) {

adjustHeap(heap, max, i, compare);

i--;

}

}

}

/** * Adds an element to the heap. * @param heap * @param value value to be added to heap. * @param compare pointer to compare function. */ void dyHeapAdd(DynamicArray* heap, TYPE value, compareFunction compare) { // FIXME: implement

}

/** * Removes the first element, which has the min priority, form the heap. * @param heap * @param compare pointer to the compare function. */ void dyHeapRemoveMin(DynamicArray* heap, compareFunction compare) { // FIXME: implement

assert(dySize(heap)>0);

int last = dySize(heap) - 1; //get last element

dyPut(heap, dyGet(heap, last), 0); //put at min

dyRemoveAt(heap, last); //remove last element

adjustHeap(heap, last, 0, compare);//adjust heap

}

/** * Returns the first element, which has the min priority, from the heap. * @param heap * @return Element at the top of the heap. */ TYPE dyHeapGetMin(DynamicArray* heap) {

// FIXME: implement

assert(dySize(heap) > 0);

TYPE min;

min = dyGet(heap, 0); //minimum

return min;

}

/** * Sorts arbitrary array in-place. * @param heap array with elements in arbitrary order. * @param compare pointer to the compare function. */ void dyHeapSort(DynamicArray* heap, compareFunction compare) { // FIXME: implement

assert(dySize(heap) > 0);

buildHeap(heap, compare); //build the heap

int last = dySize(heap) - 1;

while (last > 0) {

dySwap(heap, 0, last); //swap first and last

adjustHeap(heap, last, 0, compare); //adjust heap from 0 to last

last--; //decrement last and repeat till 0

}

}

// --- Iterator ---

DynamicArrayIterator* dyIteratorNew(DynamicArray* array) { DynamicArrayIterator* iterator = malloc(sizeof(DynamicArrayIterator)); iterator->array = array; iterator->current = 0; return iterator; }

void dyIteratorDelete(DynamicArrayIterator* iterator) { free(iterator); }

int dyIteratorHasNext(DynamicArrayIterator* iterator) { return iterator->current < iterator->array->size; }

TYPE dyIteratorNext(DynamicArrayIterator* iterator) { TYPE value = dyGet(iterator->array, iterator->current); iterator->current++; return value; }

void dyIteratorRemove(DynamicArrayIterator* iterator) { iterator->current--; dyRemoveAt(iterator->array, iterator->current); }

// --- Utility ---

void dyPrint(DynamicArray* array, printFunction print) { printf(" size: %d capacity: %d [ ", array->size, array->capacity); for (int i = 0; i < array->size; i++) { printf("%d : ", i); print(array->data[i]); printf(" "); } printf("] "); }

void dyCopy(DynamicArray* source, DynamicArray* destination) { free(destination->data); init(destination, source->capacity); for (int i = 0; i < source->size; i++) { destination->data[i] = source->data[i]; } destination->size = source->size; }

dynamicArray.h

#ifndef DYNAMIC_ARRAY_H #define DYNAMIC_ARRAY_H

#define TYPE void*

typedef struct DynamicArray DynamicArray; typedef int (*compareFunction)(TYPE, TYPE); typedef void (*printFunction)(TYPE);

struct DynamicArray;

DynamicArray* dyNew(int capacity); void dyDelete(DynamicArray* array);

// Dynamic array void dyAdd(DynamicArray* array, TYPE value); void dyAddAt(DynamicArray* array, TYPE value, int position); void dyPut(DynamicArray* array, TYPE value, int position); void dyRemoveAt(DynamicArray* array, int position); TYPE dyGet(DynamicArray* array, int position); int dySize(DynamicArray* array); void dySwap(DynamicArray* array, int position1, int position2);

// Stack void dyStackPush(DynamicArray* stack, TYPE value); void dyStackPop(DynamicArray* stack); TYPE dyStackTop(DynamicArray* stack); int dyStackIsEmpty(DynamicArray* stack);

// Bag void dyBagAdd(DynamicArray* bag, TYPE value); void dyBagRemove(DynamicArray* bag, TYPE value, compareFunction compare); int dyBagContains(DynamicArray* bag, TYPE value, compareFunction compare);

// Ordered bag void dyOrderedAdd(DynamicArray* bag, TYPE value, compareFunction compare); void dyOrderedRemove(DynamicArray* bag, TYPE value, compareFunction compare); int dyOrderedContains(DynamicArray* bag, TYPE value, compareFunction compare);

// Heap void dyHeapAdd(DynamicArray* heap, TYPE value, compareFunction compare); void dyHeapRemoveMin(DynamicArray* heap, compareFunction compare); TYPE dyHeapGetMin(DynamicArray* heap); void dyHeapSort(DynamicArray* heap, compareFunction compare);

// Iterator typedef struct DynamicArrayIterator DynamicArrayIterator;

struct DynamicArrayIterator { DynamicArray* array; int current; };

DynamicArrayIterator* dyIteratorNew(DynamicArray* array); void dyIteratorDelete(DynamicArrayIterator* iterator); int dyIteratorHasNext(DynamicArrayIterator* iterator); TYPE dyIteratorNext(DynamicArrayIterator* iterator); void dyIteratorRemove(DynamicArrayIterator* iterator);

// Utility /** * Prints the size, capacity, and elements of array, calling the print * function on each element. * @param array * @param print */ void dyPrint(DynamicArray* array, printFunction print); void dyCopy(DynamicArray* source, DynamicArray* destination);

#endif

CUTest.c

#include

#include

#include

#include

#include

#include

#include

#include "CuTest.h"

/*-------------------------------------------------------------------------*

* CuStr

*-------------------------------------------------------------------------*/

char* CuStrAlloc(int size)

{

char* newStr = (char*) malloc( sizeof(char) * (size) );

return newStr;

}

char* CuStrCopy(const char* old)

{

int len = strlen(old);

char* newStr = CuStrAlloc(len + 1);

strcpy(newStr, old);

return newStr;

}

/*-------------------------------------------------------------------------*

* CuString

*-------------------------------------------------------------------------*/

void CuStringInit(CuString* str)

{

str->length = 0;

str->size = STRING_MAX;

str->buffer = (char*) malloc(sizeof(char) * str->size);

str->buffer[0] = '\0';

}

CuString* CuStringNew(void)

{

CuString* str = (CuString*) malloc(sizeof(CuString));

str->length = 0;

str->size = STRING_MAX;

str->buffer = (char*) malloc(sizeof(char) * str->size);

str->buffer[0] = '\0';

return str;

}

void CuStringDelete(CuString *str)

{

if (!str) return;

free(str->buffer);

free(str);

}

void CuStringResize(CuString* str, int newSize)

{

str->buffer = (char*) realloc(str->buffer, sizeof(char) * newSize);

str->size = newSize;

}

void CuStringAppend(CuString* str, const char* text)

{

int length;

if (text == NULL) {

text = "NULL";

}

length = strlen(text);

if (str->length + length + 1 >= str->size)

CuStringResize(str, str->length + length + 1 + STRING_INC);

str->length += length;

strcat(str->buffer, text);

}

void CuStringAppendChar(CuString* str, char ch)

{

char text[2];

text[0] = ch;

text[1] = '\0';

CuStringAppend(str, text);

}

void CuStringAppendFormat(CuString* str, const char* format, ...)

{

va_list argp;

char buf[HUGE_STRING_LEN];

va_start(argp, format);

vsprintf(buf, format, argp);

va_end(argp);

CuStringAppend(str, buf);

}

void CuStringInsert(CuString* str, const char* text, int pos)

{

int length = strlen(text);

if (pos > str->length)

pos = str->length;

if (str->length + length + 1 >= str->size)

CuStringResize(str, str->length + length + 1 + STRING_INC);

memmove(str->buffer + pos + length, str->buffer + pos, (str->length - pos) + 1);

str->length += length;

memcpy(str->buffer + pos, text, length);

}

/*-------------------------------------------------------------------------*

* CuTest

*-------------------------------------------------------------------------*/

void CuTestInit(CuTest* t, const char* name, TestFunction function)

{

t->name = CuStrCopy(name);

t->failed = 0;

t->ran = 0;

t->parents = 0;

t->message = NULL;

t->function = function;

t->jumpBuf = NULL;

}

CuTest* CuTestNew(const char* name, TestFunction function)

{

CuTest* tc = CU_ALLOC(CuTest);

CuTestInit(tc, name, function);

return tc;

}

CuTest* CuTestCopy(CuTest* t)

{

CuTest* copy = CU_ALLOC(CuTest);

memcpy(copy, t, sizeof(CuTest));

return copy;

}

void CuTestDelete(CuTest *t)

{

if (!t) return;

if (--t->parents < 1)

{

free(t->name);

free(t->message);

free(t);

}

}

void CuTestRun(CuTest* tc)

{

jmp_buf buf;

tc->jumpBuf = &buf;

if (setjmp(buf) == 0)

{

tc->ran = 1;

(tc->function)(tc);

}

tc->jumpBuf = 0;

}

static void CuFailInternal(CuTest* tc, const char* file, int line, CuString* string)

{

char buf[HUGE_STRING_LEN];

sprintf(buf, "%s:%d: ", file, line);

CuStringInsert(string, buf, 0);

tc->failed = 1;

tc->message = string->buffer;

if (tc->jumpBuf != 0) longjmp(*(tc->jumpBuf), 0);

}

void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message)

{

CuString string;

CuStringInit(&string);

if (message2 != NULL)

{

CuStringAppend(&string, message2);

CuStringAppend(&string, ": ");

}

CuStringAppend(&string, message);

CuFailInternal(tc, file, line, &string);

}

void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition)

{

if (condition) return;

CuFail_Line(tc, file, line, NULL, message);

}

void CuAssertStrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message,

const char* expected, const char* actual)

{

CuString string;

if ((expected == NULL && actual == NULL) ||

(expected != NULL && actual != NULL &&

strcmp(expected, actual) == 0))

{

return;

}

CuStringInit(&string);

if (message != NULL)

{

CuStringAppend(&string, message);

CuStringAppend(&string, ": ");

}

CuStringAppend(&string, "expected <");

CuStringAppend(&string, expected);

CuStringAppend(&string, "> but was <");

CuStringAppend(&string, actual);

CuStringAppend(&string, ">");

CuFailInternal(tc, file, line, &string);

}

void CuAssertIntEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message,

int expected, int actual)

{

char buf[STRING_MAX];

if (expected == actual) return;

sprintf(buf, "expected <%d> but was <%d>", expected, actual);

CuFail_Line(tc, file, line, message, buf);

}

void CuAssertDblEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message,

double expected, double actual, double delta)

{

char buf[STRING_MAX];

if (fabs(expected - actual) <= delta) return;

sprintf(buf, "expected <%f> but was <%f>", expected, actual);

CuFail_Line(tc, file, line, message, buf);

}

void CuAssertPtrEquals_LineMsg(CuTest* tc, const char* file, int line, const char* message,

void* expected, void* actual)

{

char buf[STRING_MAX];

if (expected == actual) return;

sprintf(buf, "expected pointer <0x%p> but was <0x%p>", expected, actual);

CuFail_Line(tc, file, line, message, buf);

}

/*-------------------------------------------------------------------------*

* CuSuite

*-------------------------------------------------------------------------*/

void CuSuiteInit(CuSuite* testSuite)

{

testSuite->count = 0;

testSuite->failCount = 0;

memset(testSuite->list, 0, sizeof(testSuite->list));

}

CuSuite* CuSuiteNew(void)

{

CuSuite* testSuite = CU_ALLOC(CuSuite);

CuSuiteInit(testSuite);

return testSuite;

}

void CuSuiteDelete(CuSuite *testSuite)

{

unsigned int n;

for (n=0; n < MAX_TEST_CASES; n++)

{

if (testSuite->list[n])

{

CuTestDelete(testSuite->list[n]);

}

}

free(testSuite);

}

void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase)

{

assert(testSuite->count < MAX_TEST_CASES);

testSuite->list[testSuite->count] = testCase;

testSuite->count++;

if (testCase->parents != INT_MAX)

{

testCase->parents++;

}

else

{

testCase = CuTestCopy(testCase);

}

}

void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2)

{

int i;

for (i = 0 ; i < testSuite2->count ; ++i)

{

CuTest* testCase = testSuite2->list[i];

CuSuiteAdd(testSuite, testCase);

}

}

void CuSuiteConsume(CuSuite* testSuite, CuSuite* testSuite2)

{

CuSuiteAddSuite(testSuite, testSuite2);

CuSuiteDelete(testSuite2);

}

void CuSuiteRun(CuSuite* testSuite)

{

int i;

for (i = 0 ; i < testSuite->count ; ++i)

{

CuTest* testCase = testSuite->list[i];

CuTestRun(testCase);

if (testCase->failed) { testSuite->failCount += 1; }

}

}

void CuSuiteSummary(CuSuite* testSuite, CuString* summary)

{

int i;

for (i = 0 ; i < testSuite->count ; ++i)

{

CuTest* testCase = testSuite->list[i];

CuStringAppend(summary, testCase->failed ? "F" : ".");

}

CuStringAppend(summary, " ");

}

void CuSuiteDetails(CuSuite* testSuite, CuString* details)

{

int i;

int failCount = 0;

if (testSuite->failCount == 0)

{

int passCount = testSuite->count - testSuite->failCount;

const char* testWord = passCount == 1 ? "test" : "tests";

CuStringAppendFormat(details, "OK (%d %s) ", passCount, testWord);

}

else

{

if (testSuite->failCount == 1)

CuStringAppend(details, "There was 1 failure: ");

else

CuStringAppendFormat(details, "There were %d failures: ", testSuite->failCount);

for (i = 0 ; i < testSuite->count ; ++i)

{

CuTest* testCase = testSuite->list[i];

if (testCase->failed)

{

failCount++;

CuStringAppendFormat(details, "%d) %s: %s ",

failCount, testCase->name, testCase->message);

}

}

CuStringAppend(details, " !!!FAILURES!!! ");

CuStringAppendFormat(details, "Runs: %d ", testSuite->count);

CuStringAppendFormat(details, "Passes: %d ", testSuite->count - testSuite->failCount);

CuStringAppendFormat(details, "Fails: %d ", testSuite->failCount);

}

}

CUTest.h

#ifndef CU_TEST_H

#define CU_TEST_H

#include

#include

#define CUTEST_VERSION "CuTest 1.5"

/* CuString */

char* CuStrAlloc(int size);

char* CuStrCopy(const char* old);

#define CU_ALLOC(TYPE) ((TYPE*) malloc(sizeof(TYPE)))

#define HUGE_STRING_LEN 8192

#define STRING_MAX 256

#define STRING_INC 256

typedef struct

{

int length;

int size;

char* buffer;

} CuString;

void CuStringInit(CuString* str);

CuString* CuStringNew(void);

void CuStringRead(CuString* str, const char* path);

void CuStringAppend(CuString* str, const char* text);

void CuStringAppendChar(CuString* str, char ch);

void CuStringAppendFormat(CuString* str, const char* format, ...);

void CuStringInsert(CuString* str, const char* text, int pos);

void CuStringResize(CuString* str, int newSize);

void CuStringDelete(CuString* str);

/* CuTest */

typedef struct CuTest CuTest;

typedef void (*TestFunction)(CuTest *);

struct CuTest

{

char* name;

TestFunction function;

int failed;

int ran;

int parents;

char* message;

jmp_buf *jumpBuf;

};

void CuTestInit(CuTest* t, const char* name, TestFunction function);

CuTest* CuTestNew(const char* name, TestFunction function);

CuTest* CuTestCopy(CuTest* t);

void CuTestRun(CuTest* tc);

void CuTestDelete(CuTest *t);

/* Internal versions of assert functions -- use the public versions */

void CuFail_Line(CuTest* tc, const char* file, int line, const char* message2, const char* message);

void CuAssert_Line(CuTest* tc, const char* file, int line, const char* message, int condition);

void CuAssertStrEquals_LineMsg(CuTest* tc,

const char* file, int line, const char* message,

const char* expected, const char* actual);

void CuAssertIntEquals_LineMsg(CuTest* tc,

const char* file, int line, const char* message,

int expected, int actual);

void CuAssertDblEquals_LineMsg(CuTest* tc,

const char* file, int line, const char* message,

double expected, double actual, double delta);

void CuAssertPtrEquals_LineMsg(CuTest* tc,

const char* file, int line, const char* message,

void* expected, void* actual);

/* public assert functions */

#define CuFail(tc, ms) CuFail_Line( (tc), __FILE__, __LINE__, NULL, (ms))

#define CuAssert(tc, ms, cond) CuAssert_Line((tc), __FILE__, __LINE__, (ms), (cond))

#define CuAssertTrue(tc, cond) CuAssert_Line((tc), __FILE__, __LINE__, "assert failed", (cond))

#define CuAssertStrEquals(tc,ex,ac) CuAssertStrEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac))

#define CuAssertStrEquals_Msg(tc,ms,ex,ac) CuAssertStrEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac))

#define CuAssertIntEquals(tc,ex,ac) CuAssertIntEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac))

#define CuAssertIntEquals_Msg(tc,ms,ex,ac) CuAssertIntEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac))

#define CuAssertDblEquals(tc,ex,ac,dl) CuAssertDblEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac),(dl))

#define CuAssertDblEquals_Msg(tc,ms,ex,ac,dl) CuAssertDblEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac),(dl))

#define CuAssertPtrEquals(tc,ex,ac) CuAssertPtrEquals_LineMsg((tc),__FILE__,__LINE__,NULL,(ex),(ac))

#define CuAssertPtrEquals_Msg(tc,ms,ex,ac) CuAssertPtrEquals_LineMsg((tc),__FILE__,__LINE__,(ms),(ex),(ac))

#define CuAssertPtrNotNull(tc,p) CuAssert_Line((tc),__FILE__,__LINE__,"null pointer unexpected",(p != NULL))

#define CuAssertPtrNotNullMsg(tc,msg,p) CuAssert_Line((tc),__FILE__,__LINE__,(msg),(p != NULL))

/* CuSuite */

#define MAX_TEST_CASES 1024

#define SUITE_ADD_TEST(SUITE,TEST) CuSuiteAdd(SUITE, CuTestNew(#TEST, TEST))

typedef struct

{

int count;

CuTest* list[MAX_TEST_CASES];

int failCount;

} CuSuite;

void CuSuiteInit(CuSuite* testSuite);

CuSuite* CuSuiteNew(void);

void CuSuiteDelete(CuSuite *testSuite);

void CuSuiteAdd(CuSuite* testSuite, CuTest *testCase);

void CuSuiteAddSuite(CuSuite* testSuite, CuSuite* testSuite2);

void CuSuiteConsume(CuSuite* testSuite, CuSuite* testSuite2);

void CuSuiteRun(CuSuite* testSuite);

void CuSuiteSummary(CuSuite* testSuite, CuString* summary);

void CuSuiteDetails(CuSuite* testSuite, CuString* details);

#endif /* CU_TEST_H */

tests.c

#include "CuTest.h" #include "dynamicArray.h" #include "task.h" #include #include #include

// --- Internal functions to be tested ---

void adjustHeap(DynamicArray* heap, int last, int position, compareFunction compare); void buildHeap(DynamicArray* heap, compareFunction compare);

// --- Test helper functions ---

void shuffle(DynamicArray* array) { for (int i = 0; i < dySize(array); i++) { int j = rand() % dySize(array); dySwap(array, i, j); } }

Task* createTasks(const int n) { Task* tasks = malloc(sizeof(Task) * n); for (int i = 0; i < n; i++) { tasks[i].priority = i; sprintf(tasks[i].name, "Task %d", i); } return tasks; }

void assertHeapProperty(CuTest* test, DynamicArray* heap) { for (int i = 0; i < dySize(heap); i++) { int priority = ((Task*)dyGet(heap, i))->priority; int left = 2 * i + 1; int right = 2 * i + 2; if (left < dySize(heap)) { int leftPriority = ((Task*)dyGet(heap, left))->priority; CuAssertTrue(test, priority <= leftPriority); } if (right < dySize(heap)) { int rightPriority = ((Task*)dyGet(heap, right))->priority; CuAssertTrue(test, priority <= rightPriority); } } }

// --- Tests ----

/* * adjustHeap * buildHeap * dyHeapAdd * dyHeapRemoveMin * dyHeapGetMin * dyHeapSort * taskNew * taskCompare */

void testAdjustHeap(CuTest* test) { const int n = 100; Task* tasks = createTasks(n); for (int j = 0; j < n; j++) { DynamicArray* heap = dyNew(1); for (int i = 0; i < n; i++) { dyAdd(heap, &tasks[i]); } for (int i = 0; i < n; i++) { dyPut(heap, &tasks[rand() % n], 0); adjustHeap(heap, dySize(heap) - 1, 0, taskCompare); assertHeapProperty(test, heap); } dyDelete(heap); } free(tasks); }

void testBuildHeap(CuTest* test) { const int n = 100; Task* tasks = createTasks(n); DynamicArray* heap = dyNew(1); for (int i = 0; i < n; i++) { dyAdd(heap, &tasks[i]); } for (int i = 0; i < n; i++) { shuffle(heap); buildHeap(heap, taskCompare); CuAssertIntEquals(test, n, dySize(heap)); assertHeapProperty(test, heap); } dyDelete(heap); free(tasks); }

void testDyHeapAdd(CuTest* test) { const int n = 100; Task* tasks = createTasks(n); for (int i = 0; i < n; i++) { DynamicArray* heap = dyNew(1); for (int j = 0; j < n; j++) { dyHeapAdd(heap, &tasks[rand() % n], taskCompare); CuAssertIntEquals(test, j + 1, dySize(heap)); assertHeapProperty(test, heap); } dyDelete(heap); } free(tasks); }

void testDyHeapRemoveMin(CuTest* test) { const int n = 100; Task* tasks = createTasks(n); DynamicArray* heap = dyNew(1); for (int i = 0; i < n; i++) { dyAdd(heap, &tasks[i]); } for (int i = 0; i < n; i++) { CuAssertIntEquals(test, n - i, dySize(heap)); CuAssertTrue(test, dyGet(heap, 0) == &tasks[i]); dyHeapRemoveMin(heap, taskCompare); assertHeapProperty(test, heap); CuAssertIntEquals(test, n - i - 1, dySize(heap)); } dyDelete(heap); free(tasks); }

void testDyHeapGetMin(CuTest* test) { const int n = 10; DynamicArray* heap = dyNew(1); Task* tasks = createTasks(n); for (int i = 0; i < n; i++) { dyAdd(heap, &tasks[i]); } CuAssertPtrNotNull(test, dyHeapGetMin(heap)); CuAssertTrue(test, dyGet(heap, 0) == dyHeapGetMin(heap)); shuffle(heap); CuAssertPtrNotNull(test, dyHeapGetMin(heap)); CuAssertTrue(test, dyGet(heap, 0) == dyHeapGetMin(heap)); free(tasks); dyDelete(heap); }

void testDyHeapSort(CuTest* test) { const int n = 100; struct Task* tasks = createTasks(n); DynamicArray* heap = dyNew(1); for (int i = 0; i < n; i++) { dyAdd(heap, &tasks[i]); } shuffle(heap); dyHeapSort(heap, taskCompare); CuAssertIntEquals(test, n, dySize(heap)); for (int i = 0; i < n; i++) { CuAssertTrue(test, dyGet(heap, i) == &tasks[n - i - 1]); } free(tasks); dyDelete(heap); }

void testTaskNew(CuTest* test) { const int n = 4; char* names[] = { "get up", "eat food", "study", "go to bed" }; for (int i = 0; i < n; i++) { Task* task = taskNew(i, names[i]); CuAssertPtrNotNull(test, task); CuAssertStrEquals(test, names[i], task->name); CuAssertIntEquals(test, i, task->priority); taskDelete(task); } }

void testTaskCompare(CuTest* test) { const int n = 10; Task tasks[n]; for (int i = 0; i < n; i++) { tasks[i].priority = i; sprintf(tasks[i].name, "Task %d", i); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int relation = taskCompare(&tasks[i], &tasks[j]); if (i < j) { CuAssertTrue(test, relation < 0); } else if (i > j) { CuAssertTrue(test, relation > 0); } else { CuAssertIntEquals(test, 0, relation); } } } }

/** * Just a skeleton code function test. * @param test */ void testDyOrderedAdd(CuTest* test) { const int n = 100; Task* tasks = createTasks(n); DynamicArray* array = dyNew(1); for (int i = 0; i < n; i++) { dyOrderedAdd(array, &tasks[rand() % n], taskCompare); } int maxPriority = ((Task*)dyGet(array, 0))->priority; for (int i = 0; i < n; i++) { Task* task = (Task*)dyGet(array, i); CuAssertTrue(test, task->priority >= maxPriority); if (task->priority > maxPriority) { maxPriority = task->priority; } } dyDelete(array); free(tasks); }

// --- Test suite ---

/* * To add a test, just write a function above with the following prototype, * void testFunction(CuTest* test) * , and add it to this function with the following line of code, * SUITE_ADD_TEST(suite, testFunction); * * See CuTest.h for all the different assert macro functions. */ void addTests(CuSuite* suite) { SUITE_ADD_TEST(suite, testAdjustHeap); SUITE_ADD_TEST(suite, testBuildHeap); SUITE_ADD_TEST(suite, testDyHeapAdd); SUITE_ADD_TEST(suite, testDyHeapRemoveMin); SUITE_ADD_TEST(suite, testDyHeapGetMin); SUITE_ADD_TEST(suite, testDyHeapSort); SUITE_ADD_TEST(suite, testTaskNew); SUITE_ADD_TEST(suite, testTaskCompare); //SUITE_ADD_TEST(suite, testDyOrderedAdd); }

void runTests() { srand(0); CuSuite* suite = CuSuiteNew(); CuString* output = CuStringNew(); addTests(suite); CuSuiteRun(suite); CuSuiteSummary(suite, output); CuSuiteDetails(suite, output); printf("%s ", output->buffer); CuSuiteDelete(suite); CuStringDelete(output); }

int main() { runTests(); return 0; }