1
\$\begingroup\$

After following the comment from greybeard,

Below is the design for given first phase of implementation,

enter image description here

Code directory structure,

$ ls -LR
.:
type.h  list  testList.c  testList.exe

./list:
arrayImpl.c   config.c virtualImplLayer.c linkedListImpl.c  list.h listHandler.h  listInterface.h


Below is the implementation,

type.h

/********* type.h ********/

 #include<stdbool.h>
 #include<stddef.h>
 #include<stdlib.h>
 #include<stdio.h>
 #include<string.h>
 #include<time.h>

list.h

/************ list.h ************/

/*
   List is an ordered collection of homogenuous type elements(unique or duplicate).
   List is not designed to have collection of heterogenuous type elements
   All elements in a List are related.
   List is mutable
   Each element has a position.
   If an element is deleted, then still the remaining elements sit in new order.

   Array implementation of List
   Linked implementation of List
*/

#ifndef LIST_H /* Header guard */
#define LIST_H
#include"type.h"

/***************** Usage-start ************/



  /* To ensure Encapsulation(i.e., maintain invariants of array & linked list)
     So, Just provide the `List` declartion, to avoid mis-use of `List`
  */
  typedef struct List List;



 typedef int (*compareTo)(const void *key, const void *item);
 typedef bool (*isLess)(const void *key, const void *item);
 typedef bool (*isEqual)(const void *key, const void *item);

#endif

listHandler.h

/***********listHandler.h ***********/
#include"list/list.h"

#ifndef LISTHANDLER_H
#define LISTHANDLER_H

typedef struct {

         bool(*canHandle)(char*);
        List*(*createList)(void);
         void(*freeList)(List*);
         void(*swim)(List*, int, isLess);
         void(*sink)(List*, int, isLess);
        void*(*listDeleteMaxElement)(List*, isLess);
        void*(*sortedListDeleteMaxElement)(List*);
          int(*listGetSize)(List*);
  const void*(*listGetItem)(List*, const int);
        List*(*sortedListInsertItem)(List*, void*, compareTo);
         void(*listInsertItem)(List*, void*);
        void*(*listDeleteItem)(List*, int);
        void*(*listDeleteLastItem)(List*);
        void*(*listDeleteFirstItem)(List*);
        void*(*linearSearch)(const void*, List*, size_t, isEqual);
        void*(*binarySearch)(const void*, List*, size_t, compareTo);
         void(*insertionSort)(List*, size_t, isLess);
         void(*mergeSort)(List*, size_t, isLess);
         void(*swap)(List*, int, int);

}ListHandler;

/*
  "config.c" lookup below 2 global symbols created in impl handlers,
   before linking time, so "extern" keyword
*/
extern ListHandler arrayImplHandler;
extern ListHandler linkedListImplHandler;

/*
  "viml.c" lookup below global symbol created in "config.c",
   before linking time, so "extern" keyword
*/
extern ListHandler *listHandlers[];
/* Prototypes for definitions in viml.c - start ********/
        List* vCreateList(char *);
         void vFreeList(List*, char *);
         void vSwim(List*, int, isLess, char *);
         void vSink(List*, int, isLess, char *);
        void* vListDeleteMaxElement(List*, isLess, char *);
        void* vSortedListDeleteMaxElement(List*, char *);
          int vListGetSize(List*, char *);
  const void* vListGetItem(List*, const int, char *);
        List* vSortedListInsertItem(List*, void*, compareTo, char *);
         void vListInsertItem(List*, void*, char *);
        void* vListDeleteItem(List*, int, char *);
        void* vListDeleteLastItem(List*, char *);
        void* vListDeleteFirstItem(List*, char *);
        void* vLinearSearch(const void*, List*, size_t, isEqual, char *);
        void* vBinarySearch(const void*, List*, size_t, compareTo, char *);
         void vInsertionSort(List*, size_t, isLess, char *);
         void vMergeSort(List*, size_t, isLess, char *);
         void vSwap(List*, int, int, char *);
/*****End ***********************************************/
#endif

listInterface.h

#ifndef LISTINTERFACE_H
#define LISTINTERFACE_H

#include"list/listHandler.h"

/*********** User Interface - start *****************/
#define createList()                   vCreateList(argv[1])
#define freeList(a)                    vFreeList(a, argv[1])
#define swim(a, b, c)                  vSwim(a, b, c, argv[1])
#define sink(a, b, c)                  vSink(a, b, c, argv[1])
#define deleteMax(a, b)                vListDeleteMaxElement(a, b, argv[1])
#define sortDeleteMax(a)               vSortedListDeleteMaxElement(a, argv[1])
#define getSize(a)                     vListGetSize(a, argv[1])
#define getItem(a, b)                  vListGetItem(a, b, argv[1])
#define sortInsertItem(a, b, c)        vSortedListInsertItem(a, argv[1])
#define insertItem(a, b)               vListInsertItem(a, b, argv[1])
#define deleteItem(a, b)               vListDeleteItem(a, b, argv[1])
#define deleteLastItem(a)              vListDeleteLastItem(a, argv[1])
#define deleteFirstItem(a)             vListDeleteFirstItem(a, argv[1])
#define lSearch(a, b, c, d)            vLinearSearch(a, b, c, d, argv[1])
#define bSearch(a, b ,c, d)            vBinarySearch(a, b, c, d, argv[1])
#define callInsertionSort(a, b, c)     vInsertionSort(a, b, c, argv[1])
#define callMergeSort(a, b, c)         vMergeSort(a, b, c, argv[1])
#define swap(a, b, c)                  vSwap(a, b, c, argv[1])

/*********** User Interface - end *****************/
#endif

arrayImpl.c

/***************** arrayImpl.c **************/


#include"list/listHandler.h" // for 'ListHandler' type
/*
  typedefs are always "local to a file".
  'ListResizeOperation' type is used only in array implementation
*/
typedef enum {DOUBLE_THE_LIST, HALF_THE_LIST}ListResizeOperation;


/****** Private symbols - start - Not visible to Linker*************/
static List *resizeList(List *, ListResizeOperation);
static void *bSearchRecur(const void *, void**, int, int, compareTo);
static void *bSearchIter(const void *, void **, int, int, compareTo);

static void insSort(List *, size_t, isLess);
static void merge(void **, void **, int, int, int, isLess);
static void mSort(void **, void **, int, int, isLess);
static void *delMaxListElem(void **, size_t, isLess);
/****** Private symbols - end ********************/


/*
  Representation - start
  Public symbol with restricted access to user to its details
*/
typedef struct List{

  void **array;

  /* For housekeeping - Array enhancement/shrink */
  int lastItemPosition;
  int size;
}List;

#define INITIAL_LIST_SIZE 50
#define FIRST_ITEM_INDEX 0
/********************* Representation - end ************/


/************* Public symbols - start ***************/

bool canArrayImplHandle(char *argvOneOption){
  if(strcmp(argvOneOption, "ARRAY") == 0){
    return true;
  }else{
    return false;
  }
}

List *arrayCreate(void){

    List *list = malloc(sizeof(List));
    if(list != NULL){

      list->array = malloc(INITIAL_LIST_SIZE*sizeof(void*));
      if(list->array != NULL){

        /* 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{
        free(list);
        list = NULL;
      }
    }

    return list;
}

void arrayFree(List *list){

  if(list != NULL){
    if(list->array != NULL){
      int index = 0;
      while( index <= list->lastItemPosition){
        free(list->array[index++]);
      }
      free(list->array);
    }else{
      fprintf(stderr, "Invalid list sent to freeList()\n");
    }
    free(list);
  }
}

int arrayGetSize(List *list){
  if(list != NULL){
    return list->lastItemPosition + 1;
  }else{
    fprintf(stderr, "List is NULL\n ");
    return -1;
  }
}

void *arrayDeleteItem(List *arrayList, int listIndex){

  if(arrayList == NULL){
    fprintf(stderr, "Invalid list \n");
    return NULL;
  }

  void *returnElement  = arrayList->array[listIndex];

  /* Delete operation - O(n) operation */
  for(int accumulator = listIndex; accumulator <= arrayList->lastItemPosition; accumulator++){
    arrayList->array[accumulator] = arrayList->array[accumulator + 1];
  }

  arrayList->lastItemPosition--;


  /* House keeping - Half the list */
  if(arrayList->size > INITIAL_LIST_SIZE){ /* Minimum size maintained */
    if((arrayList->lastItemPosition + 1) == ((arrayList->size)/2)){
      arrayList = resizeList(arrayList, HALF_THE_LIST);
      if(arrayList == NULL){
        fprintf(stderr, "deleteItem() - Unable to allocate memory \n");
        exit(1);
      }
    }
  }
  return returnElement; /* User must free this element*/
}

void * arrayDeleteLastItem(List *arrayList){

  return arrayDeleteItem(arrayList, arrayList->lastItemPosition);
}


void *arrayDeleteFirstItem(List *arrayList){

  return arrayDeleteItem(arrayList, FIRST_ITEM_INDEX);
}


void arraySwap(List *list, int i, int j){

  void **array = list->array;

  void *tempPointer = array[i];
  array[i] = array[j];
  array[j] = tempPointer;
}

void arraySwim(List *list, int index, isLess less){

  void **array = list->array;
  while(index > 1 &&  less(array[index/2], array[index]) ){
    arraySwap(list, index/2, index);
    index/=2;
  }
}

void arraySink(List *list, int parentIndex, isLess less){

  void **array = list->array;
  while( 2*parentIndex <= list->lastItemPosition ){

    int childIndex = 2*parentIndex;
    if( childIndex < list->lastItemPosition && //larger child
                (less(array[childIndex], array[childIndex+1])) ){
      childIndex = childIndex + 1;
    }
    if(!less(array[parentIndex], array[childIndex])) break;
    arraySwap(list, parentIndex, childIndex);
    parentIndex = childIndex;
  }
}


void *arrayDeleteMaxElement(List *list, isLess less){
  if(list != NULL){

    void *maxElement= delMaxListElem(list->array, arrayGetSize(list), less);
    list->lastItemPosition--;
    return maxElement;
  }else{
    fprintf(stderr, "listDeleteMaxElement() - NULL is passed\n");
    return NULL;
  }
  return NULL;
}

void *sortedArrayDeleteMaxElement(List *list){
  if(list != NULL){

    void *maxElement= arrayDeleteLastItem(list);
    return maxElement;
  }else{
    fprintf(stderr, "sortedListDeleteMaxElement() - NULL is passed\n");
    return NULL;
  }
  return NULL;
}


const void *arrayGetItem(List *list, const int index){
  if((index >=0) && (index < arrayGetSize(list))){
    return (const void *)list->array[index];
  }else{
    return NULL;
  }
}

void arrayInsertItem(List *arrayList, void *newItem){

  if(arrayList == NULL){
    fprintf(stderr, "listInsertItem() -Invalid list \n");
    return;
  }
  /* House keeping - Enhance the array */
  if(arrayList->lastItemPosition + 1 == arrayList->size){
    arrayList = resizeList(arrayList, DOUBLE_THE_LIST);
    if(arrayList == NULL){
      fprintf(stderr, "insertItem() - Unable to allocate memory \n");
      exit(1);
    }
  }

  /* Insert new element - O(1) operation */
  arrayList->array[++(arrayList->lastItemPosition)] = newItem;
}

List * sortedArrayInsertItem(List *arrayList, void *newItem, compareTo compare){

  if(arrayList == NULL){
    fprintf(stderr, "listInsertItem() -Invalid list \n");
    return NULL;
  }

  List *newlist = arrayCreate();

  /* Insert new element - O(n) operation */
  int index =0;
  for(; index <= arrayList->lastItemPosition; index++){
    if( compare(newItem, arrayList->array[index]) > 0){

      arrayInsertItem(newlist, arrayList->array[index]);
    }
    arrayList->array[index] = NULL;
  }//end for-loop

  arrayInsertItem(newlist, newItem);

  for(;index <= arrayList->lastItemPosition; index++){
    arrayInsertItem(newlist, arrayList->array[index]);
    arrayList->array[index] = NULL;
  }
  free(arrayList);
  arrayList = newlist;

  return arrayList;
}


/**************Searching & Sorting -start **************/
void *arrayLinearSearch(const void *key, List *list, size_t listSize, isEqual equal){

  if(list != NULL && (listSize > 0)){
    void ** array = list->array;
    for(int index =0; index < listSize; index++){
      if(equal(key, (array[index])) ){
        return array[index];
      }
    }
  }
  return NULL;
}


void *arrayBinarySearch(const void *key, List *list, size_t listSize, compareTo compare){

  if(list != NULL && (listSize > 0)){
    return bSearchIter(key, list->array, 0, listSize-1, compare);
    return bSearchRecur(key, list->array, 0, listSize-1, compare);
  }
  return NULL;
}


void arrayInsertionSort(List *list, size_t listSize, isLess less){

  if(list!=NULL && (listSize > 0)){
    insSort(list, listSize, less);
  }
}

void arrayMergeSort(List *list, size_t listSize, isLess less){

  if(list != NULL){

    void **aux = malloc(arrayGetSize(list) * sizeof(void*)); //Auxillary shadow copy
    if(aux != NULL){
      printf("Size of list: %d\n", listSize);
      mSort(list->array, aux, 0, listSize-1, less);
    }else{

      fprintf(stderr, "mergeSort() - Malloc failure");
      exit(EXIT_FAILURE);
    }
  }else{

    fprintf(stderr, "mergeSort() - List is NULL");
  }
}

/**************Searching & Sorting -end **************/



/****************Public symbols - end *******************/


/* Private symbols - start - Not visible to Linker****/

static void *delMaxListElem(void **array, size_t size, isLess less){

  if(size >0){

    const void *maxElement = array[0];
    int maxElementIndex = 0;
    printf("size of list: %d\n", size);
    for(int index = 1; index < size; index++){
      if( less(maxElement, array[index]) ){
        maxElement = array[index];
        maxElementIndex = index;
      }
    }

    for(int index = maxElementIndex; index < size-1; index++){
      array[index] = array[index+1];// Rearrange array
    }

    return (void *)maxElement;
  }else{
    return NULL;
  }
}


static void mSort(void **array, void **aux, int low, int high, isLess less){

  if(high <= low) return;
  int mid = (low + high)/2;

  mSort(array, aux, low, mid, less);
  mSort(array, aux, mid+1, high, less);
  merge(array, aux, low, mid, high, less);
}


static void merge(void **array, void **aux, int low, int mid, int high, isLess less){

  for(int index = low; index <= high; index++){
    aux[index] = array[index]; //Shallow copy
  }
  printf("Low-%d, Mid-%d, High-%d\n", low, mid, high);
  int leftIndex = low; int rightIndex = mid+1;
  printf("leftIndex-%d, rightIndex-%d\n", leftIndex, rightIndex);

  for(int index = low; index <= high; index++){

    if(leftIndex > mid)    /* right array exhausted */  array[index] = aux[rightIndex++];
    else if(rightIndex > high) /*left array exhausted*/ array[index] = aux[leftIndex++];
    else if( less(aux[rightIndex], aux[leftIndex]) )    array[index] = aux[rightIndex++];
    else                                                array[index] = aux[leftIndex++];
  }
}

static void insSort(List *list, size_t listSize, isLess less){

  for(int sortedBoundaryIndex = -1; sortedBoundaryIndex < (long long)listSize - 1; sortedBoundaryIndex++){
    /*
      -1 mean sorted pool is yet to form.
       0 mean first element is in sorted pool
    */

    for(int unSortedElementIndex = sortedBoundaryIndex + 1; unSortedElementIndex > 0; unSortedElementIndex--){
      /* Within this loop, sorted pool does not exist, as new element is being compared*/
      if(less(list->array[unSortedElementIndex], list->array[unSortedElementIndex-1])){
        arraySwap(list, unSortedElementIndex, unSortedElementIndex-1);
      }else{
        break; //If the unsorted element is > or ==, no swap, Stable sort
      }
    }
  }
}

static void *bSearchIter(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){

  int mid =0;
  while(lowerBound <= upperBound){

    mid = (lowerBound + upperBound)/2;

    if(compare(key, array[mid]) == 0){

      return array[mid];
    }else if(compare(key, array[mid]) < 0){
      upperBound = mid-1;
    }else if(compare(key, array[mid]) > 0){
      lowerBound = mid + 1;
    }
  }/* end while */

  return NULL;
}


static void *bSearchRecur(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){

  if(lowerBound > upperBound) return NULL;

  int mid = (lowerBound + upperBound)/2;

  if(compare(key, array[mid]) == 0){

    return array[mid];
  }else if(compare(key, array[mid]) < 0){

    return bSearchRecur(key, array, lowerBound, mid-1, compare);
  }else { // compare() > 0

    return bSearchRecur(key, array, mid+1, upperBound, compare);
  }
}

/* resizeList() is not visible to Linker (ld) */
static List *resizeList(List *list, ListResizeOperation opType){

  if(opType == DOUBLE_THE_LIST){

    list->array = realloc(list->array, 2*(list->size)*sizeof(void *));
    if(list->array == NULL){ return NULL; }
    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 *));
    if(list->array == NULL){ return NULL; }
    list->lastItemPosition = list->lastItemPosition;
    list->size = (list->size)/2;
  }

  return list;
}
/************* helper symbols - end  ************/

/* config.c requires below symbol */
ListHandler arrayImplHandler = {
  canArrayImplHandle,
  arrayCreate,
  arrayFree,
  arraySwim,
  arraySink,
  arrayDeleteMaxElement,
  sortedArrayDeleteMaxElement,
  arrayGetSize,
  arrayGetItem,
  sortedArrayInsertItem,
  arrayInsertItem,
  arrayDeleteItem,
  arrayDeleteLastItem,
  arrayDeleteFirstItem,
  arrayLinearSearch,
  arrayBinarySearch,
  arrayInsertionSort,
  arrayMergeSort,
  arraySwap,
};

linkedListImpl.c

/**********linkedListImpl.c ***********/


#include"list/listHandler.h" // for 'ListHandler' type

  /* typedef is alway local to file */
  typedef struct DListNode DListNode;

  /******Private symbol - start - Not visible to linker *****/
  static DListNode* createNode(void *);
  /******Helper function - end ******************/

/***************** Representation - start ******************/

  /* Private structure */
  struct DListNode{
    void *item;
    struct DListNode *next;
    struct DListNode *prev;
  };



  /*
    Reason to introduce 'List' type:

    Problem 1:
     Say, user code has 'x' and 'y' pointing to the same shopping list that is built using 'Node' type.
     Some part of user code update list with new item using 'x'
     'y' is not in sync with this updation
        Node *x = someCreatedList;
        Node *y = x;
        Node *z = malloc(sizeof(Node));
        z->next = x;
        x = z; //y misses that reference.
    Solution:
     Maintain a List type, whose job is to point to head(first node) of the list.
     User code will go via reference of List type


    Problem 2:
     It make sense to have references of 'Node' type pointing to NULL
     Applying operation[insertItem()] on NULL pointer will cause runtime errors
    Solution:
     Run operations over List type because it does not make sense to have reference of SList type pointing to NULL.

    To solve problem1 & problem2, here is 'List' type
  */



  /* Public structure with restricted access to user */

  typedef struct List{

    DListNode *head;
    int size; /*size attribute is not part of list definition,
               but quick way to help user code */
  }List;

#define SENTINEL_NODE_DATA_ITEM (void *)0

/************ Representation - end *************/


/****Public symbols - start **********/

bool canLinkedListImplHandle(char *argvOneOption){

  if(strcmp(argvOneOption, "LINKEDLIST") == 0){
    return true;
  }else{
    return false;
  }
}

List *linkListCreate(){

    /*
      Amidst performing insert/delete operations on 'List',
      To reduce the number of special checks, we designate one node as 'SENTINEL'
      After using sentinel, there will be no NULL assignments/check in code.
    */
    List *list = (List *)malloc(sizeof(List));
    if(list != NULL){
      DListNode *sentinel = createNode(SENTINEL_NODE_DATA_ITEM);
      list->head = sentinel;
      list->head->next = list->head;
      list->head->prev = list->head;
      list->size = 0;

      return list;
    }else{
      return NULL;
    }
}

void linkListFree(List *list){

  if(list != NULL){
    if(list->size > 0){

      int index = 0;
      DListNode *currentNode, *nextNode;
      currentNode = list->head->next;
      do{
        nextNode = currentNode->next;
        free(currentNode->item);
        free(currentNode);
        currentNode = nextNode;
      }while(++index < list->size);
      return;
    }else{
      return;
    }
  }else{
    fprintf(stderr, "Unable to free()\n");
    return;
  }
}


void linkListSwim(List *list, int index, isLess less){

  return;
}


void linkListSink(List *list, int parentIndex, isLess less){

  return;
}

void * linkListDeleteMaxElement(List *list, isLess less){

  return NULL;
}


void* sortedLinkListDeleteMaxElement(List *list){

  return NULL;
}


int linkListGetSize(List *list){

  if(list != NULL){
    return list->size;
  }else{
    fprintf(stderr, "List is NULL\n ");
    return -1;
  }
}

const void *linkListGetItem(List *list, int index){

  if((index >=0) && (index < list->size)){

    DListNode *node = list->head->next;
    while(index-- > 0){
      node = node->next;
    }
    return (const void *)node->item;
  }else{

    fprintf(stderr, "Invalid index \n");
    return NULL;
  }
}


/* O(1) operation - insert() operation */
void linkListInsertItem(List *linkedList, void *newItem){

  DListNode *newNode = createNode(newItem);
  if(linkedList->size == 0){

    linkedList->head->next = linkedList->head->prev = newNode;
  }else{

    /* Link with current last node in the linked list*/
    newNode->prev = linkedList->head->prev;
    linkedList->head->prev->next = newNode;

    /* Link with Sentinel node */
    newNode->next = linkedList->head;
    linkedList->head->prev = newNode;
  }

}

List* sortedLinkListInsertItem(List *list, void *item, compareTo compare){

  return NULL;
}

       /* O(n) - delete() operation*/
void *linkListDeleteItem(List *linkedList, int listIndex){

  int accumulator = 0;
  DListNode *nodeToDelete = linkedList->head->next;

  if(listIndex < linkedList->size){

     while(accumulator++ < listIndex){
      nodeToDelete = nodeToDelete->next;
     }
     nodeToDelete->prev->next = nodeToDelete->next;
     nodeToDelete->next->prev = nodeToDelete->prev;

     linkedList->size++;

     void *item = nodeToDelete->item;
     free(nodeToDelete);
     return item; /* User must delete by casting to free(item); */
  }else{

    fprintf(stderr, "deleteItem() - Invalid Index");
    return NULL;
  }
}


/* O(1) - deleteLastItem() operation */
void *linkListDeleteLastItem(List *linkedList){

  if(linkedList->size){

    DListNode *nodeToDelete = linkedList->head->prev;
    void *item = nodeToDelete->item;
    nodeToDelete->prev->next = nodeToDelete->next;
    nodeToDelete->next->prev = nodeToDelete->prev;

    free(nodeToDelete);
    return item; /* User must free this item,by casting, free(item) */
  }else{

    return NULL;
  }
}

/* O(1) - deleteFirstItem() operation */
void *linkListDeleteFirstItem(List *linkedList){

  if(linkedList->size){

    DListNode *nodeToDelete = linkedList->head->next;
    void *item = nodeToDelete->item;
    nodeToDelete->next->prev = nodeToDelete->prev;
    nodeToDelete->prev->next = nodeToDelete->next;

    free(nodeToDelete);
    return item; /* User must free this item,by casting, free(item) */
  }else{

    return NULL;
  }
}


void* linkListLinearSearch(const void *key, List *list, size_t size, isEqual equal){

  return NULL;
}


void* linkListBinarySearch(const void *key, List *list, size_t size, compareTo compare){

  return NULL;
}

void linkListInsertionSort(List *list, size_t size, isLess less){

  return;
}


void linkListMergeSort(List *list, size_t size, isLess less){

  return;
}


void linkListSwap(List *list, int i, int j){

  return;
}

/******Public symbols - end *************/



/******Private symbols - start - Not visible to linker*******/

static DListNode *createNode(void * value){

  DListNode *newNode= malloc(sizeof(DListNode));

  newNode->next = newNode;
  newNode->prev = newNode;
  newNode->item = value;

  return newNode;
}

/****Private symbols - end ********/


/* 'config.c' lookup below global symbol */
ListHandler linkedListImplHandler = {

  canLinkedListImplHandle,
  linkListCreate,
  linkListFree,
  linkListSwim,
  linkListSink,
  linkListDeleteMaxElement,
  sortedLinkListDeleteMaxElement,
  linkListGetSize,
  linkListGetItem,
  sortedLinkListInsertItem,
  linkListInsertItem,
  linkListDeleteItem,
  linkListDeleteLastItem,
  linkListDeleteFirstItem,
  linkListLinearSearch,
  linkListBinarySearch,
  linkListInsertionSort,
  linkListMergeSort,
  linkListSwap,
};

virtualImplLayer.c

#include "list/listHandler.h"

/*****Private symbol - start *****************/
static ListHandler * findListImplHandler(char *);
/*****Private symbol - end   *****************/


/***** User interface - start *************/
List* vCreateList(char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);

  if(listHandler != NULL){

    List *list = listHandler->createList();
    return list;
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;

}


void vFreeList(List *list, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    listHandler->freeList(list);
    return;
  }
  fprintf(stderr, "No implementation for this feature\n");
}


void vSwim(List *list, int parentIndex, isLess less, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    listHandler->swim(list, parentIndex, less);
    return;
  }
  fprintf(stderr, "No implementation for this feature\n");
}

void vSink(List *list, int index, isLess less, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    listHandler->sink(list, index, less);
    return;
  }
  fprintf(stderr, "No implementation for this feature\n");
}


void* vListDeleteMaxElement(List *list, isLess less, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    return listHandler->listDeleteMaxElement(list, less);
  }

  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}


void* vSortedListDeleteMaxElement(List *list, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    return listHandler->sortedListDeleteMaxElement(list);
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}


int vListGetSize(List *list, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    return listHandler->listGetSize(list);
  }
  fprintf(stderr, "No implementation for this feature\n");
  return -1;
}


const void* vListGetItem(List *list, const int index, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    return listHandler->listGetItem(list, index);
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}

List* vSortedListInsertItem(List *list, void *item, compareTo compare, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    list = listHandler->sortedListInsertItem(list, item, compare);
    return list;
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}


void vListInsertItem(List *list, void *item, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){

    listHandler->listInsertItem(list, item);
    return;
  }
  fprintf(stderr, "No implementation for this feature\n");
}

void* vListDeleteItem(List *list, int listIndex, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){
    return listHandler->listDeleteItem(list, listIndex);
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}


void* vListDeleteLastItem(List *list, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){
    return listHandler->listDeleteLastItem(list);
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}


void* vListDeleteFirstItem(List *list, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){
    return listHandler->listDeleteFirstItem(list);
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}

void* vLinearSearch(const void *key, List *list, size_t size, isEqual equal, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){
    return listHandler->linearSearch(key, list, size, equal);
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}


void* vBinarySearch(const void *key, List *list, size_t size, compareTo compare, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){
    return listHandler->binarySearch(key, list, size, compare);
  }
  fprintf(stderr, "No implementation for this feature\n");
  return NULL;
}

void vInsertionSort(List *list, size_t size, isLess less, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){
    listHandler->insertionSort(list, size, less);
    return;
  }
  fprintf(stderr, "No implementation for this feature\n");
}


void vMergeSort(List *list, size_t size, isLess less, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){
    listHandler->mergeSort(list, size, less);
    return;
  }
  fprintf(stderr, "No implementation for this feature\n");
}


void vSwap(List *list, int i, int j, char *argvOneOption){

  ListHandler *listHandler = findListImplHandler(argvOneOption);
  if(listHandler != NULL){
    listHandler->swap(list, i, j);
    return;
  }
  fprintf(stderr, "No implementation for this feature\n");
}

/***** User interface -end *************/


/*****Private symbol - start *****************/
static ListHandler * findListImplHandler(char *argvOneOption){

  ListHandler *implHandler = NULL;
  int handlerIndex = 0;
  while(listHandlers[handlerIndex] !=NULL){

    implHandler = listHandlers[handlerIndex];
    if(implHandler->canHandle(argvOneOption)){
      return implHandler;
    }
    handlerIndex++;
  }
  return NULL;
}
/*****Private symbol - end *****************/

config.c

#include"list/listHandler.h"


ListHandler *listHandlers[] ={

  &arrayImplHandler,
  &linkedListImplHandler,
  NULL // to indicate end of array
};

Compilation procedure

gcc -Wall -Werror -I. ./list/*.c testList.c -o testList


Output

$ ./testList.exe ARRAY
First item: 1569811009

Size of list: 10
One item deleted

Size of list: 9
Item found after linear search: 1569811009
Item found after Binary search: 1569811009

Before insertion sorting
Element: 1569811009
Element: 1908758481
Element: 554528820
Element: 1263345952
Element: 201076903
Element: 1012652741
Element: 1318747018
Element: 886917931
Element: 1308738937

After sorting
Element: 201076903
Element: 554528820
Element: 886917931
Element: 1012652741
Element: 1263345952
Element: 1308738937
Element: 1318747018
Element: 1569811009
Element: 1908758481

Question:

1) Implementations interchangeable at link time. In the above code, Are there improvements?

2) Can we improve the header file dependency and refine listInterface.h? For me, listInterface.h looks horrible

Note: after refining listInterface.h PQ would be implemented

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.