Below is the code,
/****** list.h **********/
#include<stddef.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
/***************** Usage-start ************/
typedef enum{false, true}bool;
typedef enum {CREATE_NEW_LIST, DOUBLE_THE_LIST, HALF_THE_LIST}Op;
#if defined(ARRAY)
/* To ensure Encapsulation(i.e., maintain invariants of array) */
typedef struct List List;
#elif defined(LINKED_LIST)
/* To ensure Encapsulation(i.e., maintain invariants of linked list) */
/* User will not get access to node*/
typedef struct List List;
#else
#error "Wrong list implementation macro name !!!"
#endif
void insertItem(List *, void *newItem);
void *deleteItem(List *, int listIndex);
List* createList(List *, Op opType);
/************* arrayImpl.c ***********/
#include"list.h"
/************ Representation - start ************/
typedef struct List{
void **array;
/* Following members for Housekeeping - Array enhancement*/
int lastItemPosition;
int size;
}List;
#define INITIAL_LIST_SIZE 50
List *createList(List *list, Op opType){
if(opType == CREATE_NEW_LIST){
list = malloc(sizeof(List));
list->array = malloc(INITIAL_LIST_SIZE*sizeof(void*));
/* Is it safe to initialise zero to array of pointers? */
list->array = memset(list->array, 0, INITIAL_LIST_SIZE*sizeof(void *));
list->lastItemPosition = -1;
list->size = INITIAL_LIST_SIZE;
}else if(opType == DOUBLE_THE_LIST){
list->array = realloc(list->array, 2*(list->size)*sizeof(void *));
list->lastItemPosition = list->lastItemPosition;;
list->size = 2*(list->size);
}else if(opType == HALF_THE_LIST){
list->array = realloc(list->array, ((list->size)/2)*sizeof(void *));
list->lastItemPosition = list->lastItemPosition;
list->size = (list->size)/2;
}
return list;
}
/********** arrayImpl.c*********/
void *deleteItem(List *arrayList, int listIndex){
void *returnElement; //Deep copy before freeing the object
free(arrayList->array[listIndex]);
/* Delete operation - O(n) operation */
for(int accumulator = listIndex; accumulator <= arrayList->lastItemPosition; accumulator++){
arrayList->array[accumulator] = arrayList->array[++accumulator];
}
arrayList->lastItemPosition--;
/* House keeping - Half the list */
if(arrayList->size > INITIAL_LIST_SIZE){ /* Minimum size maintained */
if((arrayList->lastItemPosition + 1) == ((arrayList->size)/2)){
arrayList = createList(arrayList, HALF_THE_LIST);
}
}
return returnElement;
}
/***************arrayImpl.c***************/
void insertItem(List *arrayList, void *newItem){
/* House keeping - Enhance the array */
if(arrayList->lastItemPosition + 1 == arrayList->size){
arrayList = createList(arrayList, DOUBLE_THE_LIST);
}
/* Insert new element - O(1) operation */
arrayList->array[++(arrayList->lastItemPosition)] = newItem;
return;
}
User code,
#include"list.h"
int main(void){
List *arrayList = createList((List *)NULL, CREATE_NEW_LIST);
if (arrayList == (List *)0){
fprintf(stderr, "Unable to create list \n");
exit(1); //Nothing else to do without arrayList
}
// Objects should only be on heap
int *object1 = malloc(sizeof(int));
*object1 = 777;
insertItem(arrayList, object1);
int *object2 = malloc(sizeof(int));
*object2 = 888;
insertItem(arrayList, object2);
object1 = deleteItem(arrayList, 0);
}
I want to re-use List
abstraction for writing Stack
abstraction, as shown below with push()
/pop()
#include"../list/list.h"
typedef struct Stack{
List *stack;
}Stack;
Question:
In deleteItem()
function, how to deep copy arrayList->array[listIndex]
and return returnElement
from deleteItem()
function?
pop()
would be calling deleteItem()
Note: Compilation >gcc -DARRAY main.c arrayImpl.c
insertItem
didn't allocate an item - sodeleteItem
shouldn'tfree
it.