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 - to fill in

/* * CS 261 Assignment 5 * Name: * Date: */

#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 }

/** * 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 }

/** * 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 }

/** * 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 return NULL; }

/** * 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 }

// --- 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; }

Header file

#ifndef DYNAMIC_ARRAY_H #define DYNAMIC_ARRAY_H

/* * CS 261 Data Structures * Name: Sean Moore * Date: April 27, 2016 */

#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