I need help creating the first three functions from my header file cda.h IN C# I
ID: 3743098 • Letter: I
Question
I need help creating the first three functions from my header file cda.h IN C#
I need help with *newcda, setCDADisplay and setCDAfree, below is the rest of my cda.c file
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "cda.h"
struct cda{
int first, last, size, capacity;
int items, index;
void **array;
void (*display)(void *, FILE *);
void (*free)(void *);
};
void sizeFix(CDA *items, int cap,int j)
{
void **temp = malloc(sizeof(void *) * cap);
for(int i = j; i < items->size + j; ++i)
temp[i] = getCDA(items,i-j);
items->capacity = cap;
items->array = temp;
items->first = 0;
items->last = items->size - 1;
}
// Insert CDA
void insertCDA(CDA*items, int index, void *value)
{
assert(value != 0);
if(items->size ==0)
{
items->array[0] = value;
items->first = 0;
items->last = 0;
index++;
}
// Insert CDA FRONT
else if (items->size < 0)
{
insertCDAfront(items,value);
if (items->size + 1 > items->capacity)
{
//displayCDA(stdout,items);
int cap = items->capacity * 2;
void **temp = malloc(sizeof(void *) * cap);
for(int i = 0; i < items->size; ++i)
temp[i+1] = getCDA(items,i);
items->array = temp;
items->capacity = cap;
items->last = items->size;
items->first = 0;
}
else if (items->first - 1 < 0)
items->first = items->capacity - 1;
else
--items->first;
items->array[items->first] = value;
}
// Insert CDA BACK
else if(items->size > 0)
{
//items->array[items->last] = value;
if (items->size + 1 > items->capacity)
{
insertCDAback(items, value);
int cap = items->capacity * 2;
void **temp = malloc(sizeof(void *) * cap);
for(int i = 0; i < items->size; ++i)
temp[i] = getCDA(items,i);
items->array = temp;
items->capacity = cap;
items->last = items->size;
items->first = 0;
}
else ++items->last;
items->array[items->last] = value;
}
else {
return;
}
++items->size;
}
//Remove CDA
void *removeCDA(CDA *items,int index)
//void *removeCDA(CDA *items,0)
{
// Remove CDA Front
if (items->first)
{
assert(items->size >=1);
//displayCDA(stdout,items);
--items->size;
void *val = items->array[items->first];
items->first = (items->first + 1) % items->capacity;
if (items->capacity > 1 && (double)items->size / items->capacity < .25)
{
int cap = items->capacity / 2;
sizeFix(items,cap,0);
}
index--;
//printf(" items size now %d ",items->size);
return val;
}
// Remove CDA BACK
else{
assert(items->size >=1);
--items->size;
void *val = items->array[items->last];
items->last = (items->last -1 + items->capacity) % items->capacity;
if(items->capacity > 1 && (double) items->size / items->capacity < .25)
{
int cap = items->capacity / 2;
sizeFix(items,cap,0);
}
return val;
}
}
void unionCDA(CDA *recipient,CDA *donor)
{
if(recipient->size == 0)
{
recipient->array = realloc(recipient->array,sizeof(void *) * donor->capacity);
recipient->capacity = donor->capacity;
recipient->first = donor->first;
recipient->last = donor->last;
}
for (int i = 0; i < donor->size; ++i)
insertCDAback(recipient,getCDA(donor,i));
free(donor->array);
donor->array = malloc(sizeof(void *));
donor->array[0] = 0;
donor->size = 0;
donor->first = 0;
donor->last = 0;
}
void *getCDA(CDA *items,int index)
{
assert(index >= 0);
assert(index < items->size);
//printf("in hither");
if (items->first > items->last)
{
//printf("this condition");
if (items->first + index < items->capacity)
return items->array[items->first + index];
else
return items->array[index+items->first-items->capacity];
}
else
{
//printf("okay we go here");
return items->array[items->first + index];
}
}
void *setCDA(CDA *items, int index, void *value)
{
if(index == items->size) insertCDAback(items,value);
else items->array[index] = value;
return items->array[index];
}
int sizeCDA(CDA *items)
{
return items->size;
}
void displayCDA(CDA *items, FILE * fp)
{
//printf("first %d, last %d, capacity %d, size %d ",items->first,items->last,items->capacity,items->size);
//printf("items->size = %d ",items->size);
fprintf(fp,"(");
for(int i = 0; i < items->size; ++i)
{
items->display(fp,getCDA(items,i));
if (i+1 < items->size)
fprintf(fp,",");
}
fprintf(fp,")");
}
#ifndef-CDA-INCLUDED- #define-CDA-INCLUDED- #include typedef struct cda CDA; extern CDA *newCDA (void); extern void setCDAdisplay(CDA *items, void (*display) (void *,FILE *)); extern void setCDAfree(CDA *items, void (*free) (void *)); extern void insertCDA (CDA *items,int index,void *value) extern void *removeCDA (CDA *items,int index); extern void unionCDA(CDA *recipient,CDA *donor); extern void *getCDA (CDA *items,int index); extern void *setCDA(CDA items,int index,void *value); extern int sizeCDA (CDA *items) extern void displayCDA (CDA *,FILE *); extern int debugCDA(CDA *,int level); extern void freeCDA (CDA *); #define #define #define #define insertCDAfront (items , value) insertCDAback(items,value) removeCDAfront(items) removeCDAback(items) insertCDA(items,0, value) insertCDA(1tems, sizeCDA(items),value, removeCDA(items,0) removeCDA( items, sizeCDA( Items )-1) #endifExplanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include "cda.h"
#include "integer.h"
static void showItems(CDA *items)
{
printf("The items are ");
displayCDA(stdout, items);
printf(". ");
printf("Items with space left are ");
visualizeCDA(stdout, items);
printf(". ");
}
int main()
{
CDA *items = newCDA(displayInteger);
showItems(items);
insertCDAback(items, newInteger(2)); //insert at back
insertCDAfront(items, newInteger(1)); //insert at front
insertCDAback(items, newInteger(3)); //insert at back
showItems(items);
printf("The value ");
displayInteger(stdout, removeCDAfront(items)); //remove from front
printf(" was removed. ");
showItems(items);
int x = getInteger((INTEGER *)getCDA(items, 0)); //get the first item
printf("The first item is %d. ", x);
setCDA(items, 0, newInteger(25));
showItems(items);
int size = sizeCDA(items);
printf("The array is %d long. ", size);
CDA *donor = newCDA(displayInteger);
showItems(donor);
insertCDAfront(donor, newInteger(1)); //insert at front
insertCDAfront(donor, newInteger(2)); //insert at front
insertCDAback(donor, newInteger(3)); //insert at back
insertCDAfront(donor, newInteger(4)); //insert at front
removeCDAfront(donor);
removeCDAfront(donor);
removeCDAback(donor);
removeCDAback(donor);
showItems(donor);
insertCDAfront(donor, newInteger(5)); //insert at front
insertCDAfront(donor, newInteger(6)); //insert at front
insertCDAback(donor, newInteger(3)); //insert at back
insertCDAfront(donor, newInteger(6)); //insert at front
showItems(donor);
removeCDAfront(donor);
showItems(donor);
CDA *recipient = newCDA(displayInteger);
showItems(recipient);
insertCDAback(recipient, newInteger(80)); //insert at back
insertCDAback(recipient, newInteger(90)); //insert at back
insertCDAback(recipient, newInteger(100)); //insert at back
showItems(recipient);
unionCDA(recipient, donor);
showItems(recipient);
extractCDA(recipient);
showItems(recipient);
return 0;
}
-----------------------------------------------------------------------------
cda.c
----------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "cda.h"
struct cda
{
int size;
int startIndex;
int endIndex;
int capacity;
void **store;
int factor;
void(*display) (FILE *, void *);
};
/******public methods******/
CDA *
newCDA(void(*d)(FILE *, void *)) //d is the display function
{
//The constructor is passed a function that knows how to display the generic value stored in an array slot.
//That function is stored in a display field of the CDA object.
CDA *items = malloc(sizeof(CDA));
assert(items != 0);
items->size = 0;
items->startIndex = 0; //first, leftmost element
items->endIndex = 0; //first open slot
items->capacity = 1;
items->store = malloc(sizeof(void *) * items->capacity);
assert(items->store != 0);
items->factor = 2;
items->display = d;
return items;
}
static int
incrementIndex(CDA *items, int index)
{
index = index + 1;
if (index > items->capacity)
{
index = index - items->capacity;
}
return index;
}
static int
decrementIndex(CDA *items, int index)
{
index = index - 1;
if (index < 0)
{
index = index + items->capacity;
}
return index;
}
static int
correctIndex(CDA *items, int index)
{
int correctedIndex = ((index + items->capacity) % items->capacity);
//fprintf(stdout, "correctedIndex %d, index %d, startindex %d, endindex %d ", correctedIndex, index, items->startIndex, items->endIndex);
return correctedIndex;
}
static void
grow(CDA *items)
{
int newCapacity = items->capacity * items->factor;
int i;
void **newArray = malloc(sizeof(void *) * newCapacity);
assert(newArray != 0);
for (i = 0; i < items->size; ++i)
{
newArray[i] = getCDA(items, i);
}
items->startIndex = 0;
items->endIndex = items->size;
items->store = newArray;
items->capacity = newCapacity;
//printf("in grow: ");
//visualizeCDA(stdout, items);
//printf(" ");
}
static void
shrink(CDA *items)
{
int newCapacity = items->capacity / items->factor;
int i;
void **newArray = malloc(sizeof(void *) * newCapacity);
assert(newArray != 0);
for (i = 0; i < items->size; ++i)
{
newArray[i] = getCDA(items, i);
}
items->startIndex = 0;
items->endIndex = items->size;
items->store = newArray;
items->capacity = newCapacity;
//printf("in shrink: ");
//visualizeCDA(stdout, items);
//printf(" ");
}
void
insertCDAfront(CDA *items, void *value)
{
//This insert method places the item in the slot just prior to the first item in the filled region.
//If there is no room for the insertion, the array grows by doubling.
//It runs in amortized constant time.
//printf("In insertFront, my start index is: %d ", items->startIndex);
assert(items != 0);
if (items->size == 0)
{
insertCDAback(items, value);
return;
}
if (items->size == items->capacity)
{
grow(items);
}
//items->startIndex = items->startIndex - 1;
items->startIndex = correctIndex(items, items->startIndex - 1);
items->store[items->startIndex] = value;
++items->size;
//printf("In insertFront, my start index has been changed to: %d ", items->startIndex);
return;
}
void
insertCDAback(CDA *items, void *value)
{
//This insert method places the item in the slot just after the last item in the filled region.
//If there is no room for the insertion, the array grows by doubling.
//It runs in amortized constant time.
//printf("In insertBack, my end index is: %d ", items->endIndex);
assert(items != 0);
if (items->size == items->capacity)
{
grow(items);
}
items->store[items->endIndex] = value;
items->endIndex = correctIndex(items, items->endIndex + 1);
++items->size;
//printf("In insertBack, my end index has been changed to: %d ", items->endIndex);
return;
}
void *
removeCDAfront(CDA *items)
{
//This remove method removes the first item in the filled region.
//If the ratio of the size to the capacity drops below 25%, the array shrinks by half.
//The array should never shrink below a capacity of 1.
//It runs in amortized constant time.
assert(items->size > 0);
if ((0.25 > items->size /(double) items->capacity) && items->capacity != 1)
{
shrink(items);
}
void* returnItem = getCDA(items, 0);
items->startIndex = correctIndex(items, items->startIndex + 1);
--items->size;
return returnItem;
}
void *
removeCDAback(CDA *items)
{
//This remove method removes the last item in the filled region.
//If the ratio of the size to the capacity drops below 25 % , the array shrinks by half.
//The array should never shrink below a capacity of 1.
//It runs in amortized constant time.
assert(items->size > 0);
if ((0.25 > items->size /(double) items->capacity) && items->capacity != 1)
{
shrink(items);
}
void* returnItem = getCDA(items, items->size - 1);
items->endIndex = correctIndex(items, items->endIndex - 1);
--items->size;
return returnItem;
}
void
unionCDA(CDA *recipient, CDA *donor)
{
//The union method takes two array and moves all the items in the donor array to the recipient array.
//Suppose the recipient array has the items [3,4,5] in the filled portion and the donor array has the items [1,2] in the filled portion,
//After the union, the donor array will be empty and recipient array will have the items [3,4,5,1,2] in the filled portion.
//The union method runs in linear time.
int i;
int donorLen = donor->size;
for (i = 0; i < donorLen; ++i)
{
insertCDAback(recipient, getCDA(donor, i));
}
for (i = 0; i < donorLen; ++i)
{
removeCDAfront(donor);
}
return;
}
void *
getCDA(CDA *items, int index)
{
//The get method returns the value at the given index.
//It runs in constant time.
assert(index >= 0);
assert(index < items->size);
//modify to, either through condition or modulo, give the correct value that is asked
int correctedIndex = correctIndex(items, index + items->startIndex);
return items->store[correctedIndex];
}
void *
setCDA(CDA *items, int index, void *value)
{
//The set method updates the value at the given index.
//If the given index is equal to the size, the value is inserted via the insertCDABack method.
//If the given index is equal to -1, the value is inserted via the insertCDAFront method.
//The method returns the replaced value or zero if no value was replaced.
//It runs in constant time if the array does not need to grow and amortized constant time if it does.
assert(index >= -1);
assert(index <= items->size);
if (index == items->size)
{
insertCDAback(items, value);
return 0;
}
else if (index == -1)
{
insertCDAfront(items, value);
return 0;
}
void *oldVal = getCDA(items, index);
int correctedIndex = correctIndex(items, index + items->startIndex);
items->store[correctedIndex] = value;
return oldVal;
}
void **
extractCDA(CDA *items)
{
//The extract method returns the underlying C array.
//The array is shrunk to an exact fit prior to being returned.
//The CDA object gets a new array of capacity zero and size one.
assert(items != 0);
shrink(items);
void **returnList = items->store;
items->capacity = 1;
items->size = 0;
items->store = malloc(sizeof(void *) * items->capacity);
assert(items->store != 0);
return returnList;
}
int
sizeCDA(CDA *items)
{
//The size method returns the number of items stored in the array.
return items->size;
}
void
visualizeCDA(FILE *fp, CDA *items)
{
//The display method prints out the filled region, enclosed in brackets and separated by commas, followed by the size of the unfilled region, enclosed in brackets.
//If the integers 5, 6, 2, 9, and 1 are stored in the array (listed from index 0 upwards) and the array has capacity 8, the method would generate this output: (5, 6, 2, 9, 1)(3)
//with no preceding or following whitespace.An empty array with capacity 1 displays as()(1).
int i;
fprintf(fp, "(");
for (i = 0; i < items->size; ++i)
{
items->display(fp, getCDA(items, i));
if (items->size > 1 && i != items->size - 1)
{
fprintf(fp, ",");
}
}
fprintf(fp, ")");
fprintf(fp, "(");
int unfillReg = items->capacity - items->size;
fprintf(fp, "%d", unfillReg);
fprintf(fp, ")");
}
void
displayCDA(FILE *fp, CDA *items)
{
//The display method is similar to the visualize method, except the parenthesized size of the unfilled region is not printed.
int i;
fprintf(fp, "(");
for (i = 0; i < items->size; ++i)
{
items->display(fp, getCDA(items, i));
if (items->size > 1 && i != items->size - 1)
{
fprintf(fp, ",");
}
}
fprintf(fp, ")");
}
---------------------------------------------------------------------------------------
cda.h
---------------------------------------------------
#ifndef __CDA_INCLUDED__
#define __CDA_INCLUDED__
#include <stdio.h>
typedef struct cda CDA;
extern CDA *newCDA(void(*d)(FILE *, void *));
extern void insertCDAfront(CDA *items, void *value);
extern void insertCDAback(CDA *items, void *value);
extern void *removeCDAfront(CDA *items);
extern void *removeCDAback(CDA *items);
extern void unionCDA(CDA *recipient, CDA *donor);
extern void *getCDA(CDA *items, int index);
extern void *setCDA(CDA *items, int index, void *value);
extern void **extractCDA(CDA *items);
extern int sizeCDA(CDA *items);
extern void visualizeCDA(FILE *fp, CDA *items);
extern void displayCDA(FILE *fp, CDA *items);
#endif
-------------------------------------------------------------------------------------
integer.c
-------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "integer.h"
INTEGER *
newInteger(int x)
{
INTEGER *p = malloc(sizeof(INTEGER));
if (p == 0)
{
fprintf(stderr, "out of memory ");
exit(-1);
}
p->value = x;
return p;
}
int
getInteger(INTEGER * v)
{
return v->value;
}
int
setInteger(INTEGER * v, int x)
{
int old = v->value;
v->value = x;
return old;
}
void
displayInteger(FILE * fp, void *v)
{
fprintf(fp, "%d", getInteger((INTEGER *)v));
}
int
compareInteger(void *v, void *w)
{
return ((INTEGER *)v)->value - ((INTEGER *)w)->value;
}
void
freeInteger(INTEGER * v)
{
free(v);
}
-------------------------------------------------------------------------------
integer.h
---------------------------------
#include <stdio.h>
#ifndef __INTEGER_INCLUDED__
#define __INTEGER_INCLUDED__
typedef struct INTEGER
{
int value;
} INTEGER;
extern INTEGER *newInteger(int);
extern int getInteger(INTEGER *);
extern int setInteger(INTEGER *, int);
extern void displayInteger(FILE *, void *);
extern int compareInteger(void *, void *);
extern void freeInteger(INTEGER *);
#define PINFINITY IN_MAX
#define NINFINITY IN_MIN
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.