For your circular dynamic array class, the header file, cda.h, should look like:

 #ifndef __CDA_INCLUDED__ #define __CDA_INCLUDED__ #include  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 *,CDA *items); extern void displayCDA(FILE *,CDA *items); #endif 

The header file contains the function signatures of your public methods while the code module, cda.c, contains their implementations. The only local includes that cda.c should have is cda.h.

Method behavior

Here are some of the behaviors your methods should have. This listing is not exhaustive; you are expected, as a computer scientist, to complete the implementation in the best possible and most logical manner. The circular dynamic array uses zero-based indexing.

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

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

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

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

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

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

getCDA - The get method returns the value at the given index, from the perspective of the user. In the user's view, the first item is at index zero, the second item at index 1, and so on. So this routine has to translate between the users view and the internal view (where the first item can be anywhere in the underlying array. It runs in constant time.

setCDA - The set method updates the value at the given index, from the perspective of the user. If the given index is equal to the size, the value is inserted via the insertCDAbackmethod. If the given index is equal to -1, the value is inserted via the insertCDAfront method. The method returns the replaced value or the null pointer 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.

extractCDA - The extract method returns the underlying C array. The array is shrunk to an exact fit prior to being returned. The DA object gets a new array of capacity one and size zero.

sizeCDA - The size method returns the number of items stored in the array.

visualizeCDA - The visualize method prints out the filled region, enclosed in parentheses 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 the first item onwards) 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).

displayCDA - The display method is similar to the visualize method, except the parenthesized size of the unfilled region is not printed.

Assertions

Include the following assertions in your methods:

newCDA - The memory allocated shall be not be zero.

insertCDAfront - The memory allocated shall not be zero.

insertCDAback - The memory allocated shall not be zero.

removeCDAfront - The size shall be greater than zero.

removeCDAback - The size shall be greater than zero.

getCDA - The index shall be greater than or equal to zero and less than the size.

setCDA - The index shall be greater than or equal to -1 and less than or equal to the size.

extractCDA - The memory allocated shall not be zero.

Testing your CDA class

Modify the testing program found in the sll class description to work with circular dynamic arrays. Make sure you add additional testing to make sure the time constraints of all methods are met.