Copies of the files listed below: There are two parts to this assignment. In the

ID: 3869236 • Letter: C

Question

Copies of the files listed below:

There are two parts to this assignment. In the first part, using C, 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.

To-do list implementation
In this part of the assignment you will implement a to-do list application with a heap-based priority queue. This interactive application allows the user to manage a prioritized to-do list by
adding new tasks, viewing the highest priority task, removing the highest priority task, saving the list to a file, and loading the list from a file.

When ran, the to-do list must prompt 7 options to the user:

l to load the list from a file (function implemented for you).
s to save the list to a file (function implemented for you).
a to add a new task to the list.
g to get the first task from the list.
r to remove the first task from the list.
p to print the list (function implemented for you).
e to exit the program.

Once the user picks an option, the program should carry out the operation and then present the user with the 7 options again. This should continue until the user selects e to exit the program.

You must implement the option-handling function with the // FIXME: implement comment in toDo.c to complete the application logic. You must also implement some functions in task.c , including a compare function, to complete the Task type interface.

In addition to the skeleton code and tests, you are provided with the following files.
todo.txt – An example file storing a saved to-do list. Your save function should generate a to-do list file with the same format.
programDemo.txt – A log demonstrating the approximate behavior your application should emulate.
Note: If you wish to complete the to-do list application before completing the heap implementation, you can simulate the heap with the following function call replacements:
dyOrderedAdd instead of dyHeapAdd .
dyGet(heap, 0) instead of dyHeapGetMin .
dyRemoveAt(heap, 0) instead of dyHeapRemoveMin

These replacements can only be used temporarily. You must replace them with the proper heap functions before submitting.

Tests
This program will be tested interactively, but there are also tests in tests.c for two Task related functions you must implement in task.c .

CuTest.c

#include <assert.h>
#include <setjmp.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>

#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] = '';
}

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] = '';
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] = '';
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 <setjmp.h>
#include <stdarg.h>

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

dynamicArray.c

#include "dynamicArray.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

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

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

task.c

#include "task.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/**
* Creates a new task with the given priority and name.
* @param priority
* @param name
* @return The new task.
*/
Task* taskNew(int priority, char* name)
{
// FIXME: implement
return NULL;
}

/**
* Frees a dynamically allocated task.
* @param task
*/
void taskDelete(Task* task)
{
free(task);
}

/**
* Casts left and right to Task pointers and returns
* -1 if left's priority < right's priority,
* 1 if left's priority > right's priority,
* 0 if left's priority == right's priority.
* @param left Task pointer.
* @param right Task pointer.
* @return
*/
int taskCompare(void* left, void* right)
{
// FIXME: implement
return 0;
}

/**
* Prints a task as a (priority, name) pair.
* @param value Task pointer.
*/
void taskPrint(void* value)
{
Task* task = (Task*)value;
printf("(%d, %s)", task->priority, task->name);
}

task.h

#ifndef TASK_H
#define TASK_H

#define TASK_NAME_SIZE 128

typedef struct Task Task;

struct Task
{
int priority;
char name[TASK_NAME_SIZE];
};

Task* taskNew(int priority, char* name);
void taskDelete(Task* task);
int taskCompare(void* left, void* right);
void taskPrint(void* value);

#endif /* TASK_H */

test.c

#include "CuTest.h"
#include "dynamicArray.h"
#include "task.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

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

toDo.c

#include "dynamicArray.h"
#include "task.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/**
* Loads into heap a list from a file with lines formatted like
* "priority, name".
* @param heap
* @param file
*/
void listLoad(DynamicArray* heap, FILE* file)
{
    const int FORMAT_LENGTH = 256;
    char format[FORMAT_LENGTH];
    snprintf(format, FORMAT_LENGTH, "%%d, %%%d[^ ]", TASK_NAME_SIZE);

    Task temp;
    while (fscanf(file, format, &temp.priority, &temp.name) == 2)
    {
        dyHeapAdd(heap, taskNew(temp.priority, temp.name), taskCompare);
    }
}

/**
* Writes to a file all tasks in heap with lines formatted like
* "priority, name".
* @param heap
* @param file
*/
void listSave(DynamicArray* heap, FILE* file)
{
    for (int i = 0; i < dySize(heap); i++)
    {
        Task* task = dyGet(heap, i);
        fprintf(file, "%d, %s ", task->priority, task->name);
    }
}

/**
* Prints every task in heap.
* @param heap
*/
void listPrint(DynamicArray* heap)
{
    DynamicArray* temp = dyNew(1);
    dyCopy(heap, temp);
     while (dySize(temp) > 0)
    {
        Task* task = dyHeapGetMin(temp);
        printf(" ");
        taskPrint(task);
        printf(" ");
        dyHeapRemoveMin(temp, taskCompare);
    }
    dyDelete(temp);
}

/**
* Handles the given command.
* @param list
* @param command
*/
void handleCommand(DynamicArray* list, char command)
{
// FIXME: Implement
}

int main()
{
    // Implement
    printf(" ** TO-DO LIST APPLICATION ** ");
    DynamicArray* list = dyNew(8);
    char command = ' ';
    do
    {
        printf("Press: "
               "'l' to load to-do list from a file "
               "'s' to save to-do list to a file "
               "'a' to add a new task "
               "'g' to get the first task "
               "'r' to remove the first task "
               "'p' to print the list "
               "'e' to exit the program "
        );
        command = getchar();
        // Eat newlines
        while (getchar() != ' ');
        handleCommand(list, command);
    }
    while (command != 'e');
/* free dynamically allocated List pointers in array to avoid memory leaks */
         /* Fix it */

dyDelete(list);
return 0;
}

programDemo.txt

** TO-DO LIST APPLICATION **

Press:
'l' to load to-do list from a file
's' to save to-do list to a file
'a' to add a new task
'g' to get the first task
'r' to remove the first task
'p' to print the list
'e' to exit the program
a
Please enter the task description: do assignment 5
Please enter the task priority (0-999): 3
The task 'do assignment 5' has been added to your to-do list.

Press:
'l' to load to-do list from a file
's' to save to-do list to a file
'a' to add a new task
'g' to get the first task
'r' to remove the first task
'p' to print the list
'e' to exit the program
a
Please enter the task description: study heap-based priority queue
Please enter the task priority (0-999): 1
The task 'study heap-based priority queue' has been added to your to-do list.

Press:
'l' to load to-do list from a file
's' to save to-do list to a file
'a' to add a new task
'g' to get the first task
'r' to remove the first task
'p' to print the list
'e' to exit the program
a
Please enter the task description: review trees for Final
Please enter the task priority (0-999): 101
The task 'review trees for Final' has been added to your to-do list.

Press:
'l' to load to-do list from a file
's' to save to-do list to a file
'a' to add a new task
'g' to get the first task
'r' to remove the first task
'p' to print the list
'e' to exit the program
a
Please enter the task description: take a nap
Please enter the task priority (0-999): 0
The task 'take a nap' has been added to your to-do list.

Press:
'l' to load to-do list from a file
's' to save to-do list to a file
'a' to add a new task
'g' to get the first task
'r' to remove the first task
'p' to print the list
'e' to exit the program
s
Please enter the filename: todo.txt
The list has been saved into the file successfully.

============

flip ~/cs261/as5/todo_list 613% ./toDo

** TO-DO LIST APPLICATION **

Press:
'l' to load to-do list from a file
's' to save to-do list to a file
'a' to add a new task
'g' to get the first task
'r' to remove the first task
'p' to print the list
'e' to exit the program
l
Please enter the filename: todo.txt
The list has been loaded from file successfully.

do assignment 5

review trees for Final

Press:
'l' to load to-do list from a file
's' to save to-do list to a file
'a' to add a new task
'g' to get the first task
'r' to remove the first task
'p' to print the list
'e' to exit the program
r
Your first task 'study heap-based priority queue' has been removed from the list.

Press:
'l' to load to-do list from a file
's' to save to-do list to a file
'a' to add a new task
'g' to get the first task
'r' to remove the first task
'p' to print the list
'e' to exit the program
r
Your first task 'review trees for Final' has been removed from the list.

toDo.txt

0, take a nap
1, study heap-based priority queue
101, review trees for Midterm 2
3, do assignment 5

Explanation / Answer

#ifndef CU_TEST_H
#define CU_TEST_H

#include <setjmp.h>
#include <stdarg.h>

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

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

/* public assert functions */

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

#endif /* CU_TEST_H */

dynamicArray.c

#include "dynamicArray.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#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 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 dyPut(DynamicArray* array, TYPE value, int position)
{
assert(position < array->size);
array->data[position] = value;
}

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

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

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

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

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

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

Navigate

Copies of case study; Of the four things that HP was required to do, which one d

Copies of the files listed below: There are two parts to this assignment. In the

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Copies of the files listed below: There are two parts to this assignment. In the

Question

Explanation / Answer

Related Questions

Navigate