Presently, the dynamicArray.c file is failing 7 of 8 tests. Please correct the b
ID: 3866905 • Letter: P
Question
Presently, the dynamicArray.c file is failing 7 of 8 tests. Please correct the below dynamicArray.c FIXME sections so it passes.
dymaicArray.c - fix me
#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)
{
//FIX ME
//Declare ml, mr, mn
int ml,mr,mn;
//DEclare tp
int tp;
//set ml
ml=(2*position)+1;
//set mr
mr=(2*position)+2;
//check mr and ml
if(mr<ml)
{
//compare values at ml and mr
tp=compare(dyGet(heap,ml),dyGet(heap,mr));
//condition
if(tp==-1)
//update mn
mn=ml;
//otherwise
else
//update mn
mn=mr;
//compare values at mn and position
tp=compare(dyGet(heap,mn),dyGet(heap,position));
//compare tp value
if(tp==-1)
{
//Call Function
dySwap(heap, position, mn);
//Call Function
adjustHeap(heap, last,mn,compare);
}
}
//compare ml and mr
else if(ml<mr)
{
//compare values at ml and position
tp=compare(dyGet(heap,ml),dyGet(heap,position));
//compare values
if(tp==-1)
{
//call function
dySwap(heap, position, ml);
//call function
adjustHeap(heap, last,ml,compare);
}
}
}
/**
* 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)
{
//FIX ME
//Declare kk and aa
int kk,aa;
//call Function
kk=dySize(heap);
//Use loop
for(aa=kk/2-1;aa>=0;aa--)
//Call Function
adjustHeap(heap,kk,aa,compare);
}
void dyHeapAdd(DynamicArray* heap, TYPE value, compareFunction compare)
{
//FIX ME
//declare kk
int kk;
//declare myparindx
int myparindx;
//declare myparval
void* myparval;
//Assert
assert(heap != 0);
//Call function
dyAdd(heap, value);
//get size
kk = heap->size - 1;
//update myparindx
myparindx = (kk - 1) / 2;
//update myparval
myparval = heap->data[myparindx];
//loop
while (kk > 0 && compare(value, myparval) == -1)
{
//Call function
dySwap(heap, kk, myparindx);
//update kk
kk = myparindx;
//update myparindx
myparindx = (kk - 1) / 2;
//update myparval;
myparval = heap->data[myparindx];
}
}
void dyHeapRemoveMin(DynamicArray* heap, compareFunction compare)
{
//FIX ME
//Declare kk;
int kk;
//check heap
assert(heap != 0);
//update kk
kk=dySize(heap);
//check heap size
assert(kk != 0);
//update
heap->data[0] = heap->data[kk - 1];
//decrease
heap->size--;
//call function
adjustHeap(heap, kk, 0, compare);
}
TYPE dyHeapGetMin(DynamicArray* heap)
{
//FIX ME
//Declare kk;
int kk;
//check heap
assert(heap != 0);
//update kk
kk=dySize(heap);
//check heap size
assert(kk != 0);
//return
return heap->data[0];
}
void dyHeapSort(DynamicArray* heap, compareFunction compare)
{
//FIX ME
//declare muindx
int muindx;
//call function
buildHeap(heap, compare);
//loop
for (muindx = heap->size - 1; muindx >= 0; muindx--)
{
//call function
dySwap(heap, 0, muindx);
//call function
adjustHeap(heap, muindx, 0, compare);
}
}
// --- 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
/*
* 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
tests.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;
}
CuTests.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);
}
}
CuTests.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 */
Tasks.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 */
Just to compile - tasks.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);
}
makefile
CC = gcc
CFLAGS = -g -Wall -std=c99
all : tests toDo
tests : tests.o dynamicArray.o CuTest.o task.o
$(CC) $(CFLAGS) -o $@ $^
toDo : toDo.o dynamicArray.o task.o
$(CC) $(CFLAGS) -o $@ $^
dynamicArray.o : dynamicArray.h dynamicArray.c
toDo.o : toDo.c dynamicArray.h task.h
task.o : task.c task.h
tests.o : tests.c dynamicArray.h CuTest.h task.h
CuTest.o : CuTest.h CuTest.c
.PHONY : memCheckTests memCheckToDo clean
memCheckTests :
valgrind --tool=memcheck --leak-check=yes tests
memCheckToDo :
valgrind --tool=memcheck --leak-check=yes toDo
clean :
-rm *.o
-rm tests
-rm toDo
Explanation / Answer
#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;
};
static int i,j;
// --- Dynamic array ---
static void setCapacity(DynamicArray* array, int capacity)
{
TYPE* data = malloc(sizeof(TYPE) * capacity);
for (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 (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 (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 (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
//Declare ml, mr, mn
int ml,mr,mn;
//DEclare tp
int tp;
ml = (2 * position) + 1;
mr = (2 * position) + 2;
//check mr and ml
if (mr < ml)
{
//compare values at ml and mr
tp=compare(dyGet(heap,ml),dyGet(heap,mr));
if (tp == -1)
mn = ml;
else
mn = mr;
if (tp == -1)
{
//Call Function
dySwap(heap, position, mn);
//Call Function
adjustHeap(heap, last, mn, compare);
}
}
//compare ml and mr
else if (ml < mr)
{
//compare values at ml and position
tp=compare(dyGet(heap,ml),dyGet(heap,position));
if (tp == -1)
{
dySwap(heap, position, ml);
adjustHeap(heap, last, ml, compare);
}
}
}
/**
* 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
//Declare kk and aa
int kk,aa;
//call Function
kk=dySize(heap);
for (aa = kk / 2 - 1; aa >= 0; aa--)
adjustHeap(heap, kk, aa, compare);
}
/**
* 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
int kk;
//declare myparindx
int myparindx;
//declare myparval
void* myparval;
assert(heap != 0);
//Call function
dyAdd(heap, value);
//get size
kk = heap->size - 1;
myparindx = (kk - 1) / 2;
myparval = heap->data[myparindx];
while (kk > 0 && compare(value, myparval) == -1)
{
dySwap(heap, i, myparindx);
kk = myparindx;
myparindx = (kk - 1) / 2;
myparval = heap->data[myparindx];
}
}
/**
* 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
int kk;
assert(heap != 0);
kk=dySize(heap);
assert(kk!= 0);
heap->data[0] = heap->data[kk - 1];
heap->size--;
adjustHeap(heap, kk, 0, compare);
}
/**
* 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
int kk;
assert(heap != 0);
kk=dySize(heap);
assert(kk != 0);
return heap->data[0];
}
/**
* 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
int muindx;
buildHeap(heap, compare);
for (muindx = heap->size - 1; muindx >= 0; muindx--)
{
dySwap(heap, 0, muindx);
adjustHeap(heap, muindx, 0, compare);
}
}
// --- 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 (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 (i = 0; i < source->size; i)
{
destination->data[i] = source->data[i];
}
destination->size = source->size;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.