2
\$\begingroup\$

Below is the unsorted array and sorted array implementation of priority queue.

Code directory structure:

./code$ ls -LR
.:
pqClient.exe pqClient.c list PriorityQueue  type.h

./list:
arrayImpl.c  linkedListImpl.c  list.h

./PriorityQueue:
arrayImpl.c  heapImpl.c  PQ.h  sortedArrayImpl.c

type.h

/********* type.h ********/
#ifndef TYPE_H
#define TYPE_H /* Header guard */
 #include<stdbool.h>
 #include<stddef.h>
 #include<stdlib.h>
 #include<stdio.h>
 #include<string.h>
#endif /* TYPE_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 ************/

#if defined(ARRAY) || (LINKED_LIST)

  /* 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;

#else
  #error "Wrong list implementation macro name !!!"
#endif

 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);


 void listInsertItem(List *, void *newItem);
 void *listDeleteItem(List *, int listIndex);
 void *listDeleteLastItem(List *);
 void *listDeleteFirstItem(List *);
 const void *listGetItem(List *, const int index); /* 'index' is array index */
 int listGetSize(List *);
 void *listDeleteMaxElement(List *, isLess);
 List* createList(void);
 void freeList(List *);
 void *sortedListDeleteMaxElement(List *);
 void *sortedListInsertItem(List *, void *, compareTo);

 /*********** Searching & Sorting algorithm - start*************/

 void *linearSearch(const void *key, List *, size_t listSize, isEqual);
 /*
   bsearch() function returns a pointer to a matching member
   of the array, or NULL if no match is found
 */
 void *binarySearch(const void *key, List *, size_t listSize, compareTo);


 /*'listSize' elements. First argument points to list.*/
void insertionSort(List *, size_t, isLess);
 void selectionSort(List *, size_t listSize, compareTo);
     void shellSort(List *, size_t listSize, compareTo);
     void mergeSort(List *, size_t, isLess);
     void quickSort(List *, size_t listSize, compareTo);
    void quickSelct(List *, size_t listSize, compareTo);
/**************** Sorting algorithm - end*************/

#endif /* LIST_H */

/***************** Usage-end ***************/

arrayImpl.c

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

#include"list/list.h"

#if defined(ARRAY)
typedef enum {DOUBLE_THE_LIST, HALF_THE_LIST}ListResizeOperation;

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 swap(void **, int i, int j);
static void insSort(void **, 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);


/************ Representation - start ************/
typedef struct List{
  void **array;

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

#define INITIAL_LIST_SIZE 50
#define FIRST_ITEM_INDEX 0
/********************* Representation - end ************/
/************* Usage - start ***************/
List *createList(){

    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 freeList(List *list){

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

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

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

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

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

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

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

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

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


  List *newlist = createList();



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

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

  listInsertItem(newlist, newItem);

  for(;index < listGetSize(arrayList); index++){
    listInsertItem(newlist, arrayList->array[index]);
    arrayList->array[index] = NULL;
  }

  free(arrayList);
  arrayList = newlist;

  return arrayList;

}

void listInsertItem(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;

}

void *listDeleteItem(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 * listDeleteLastItem(List *arrayList){
  return listDeleteItem(arrayList, arrayList->lastItemPosition);
}

void *listDeleteFirstItem(List *arrayList){
  return listDeleteItem(arrayList, FIRST_ITEM_INDEX);
}

/**************Searching & Sorting -start **************/
void *linearSearch(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 *binarySearch(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 insertionSort(List *list, size_t listSize, isLess less){
  if(list!=NULL && (listSize > 0)){
    insSort(list->array, listSize, less);
  }
}

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

  if(list != NULL){

    void **aux = malloc(listGetSize(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 **************/


/******************** Usage - end *******************/

/************* helper function - start     ********/

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 swap(void **array, int i, int j){
  void *tempPointer = array[i];
  array[i] = array[j];
  array[j] = tempPointer;
}


static void insSort(void **array, 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(array[unSortedElementIndex], array[unSortedElementIndex-1])){
        swap(array, 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 function - end     *************/

#endif

PQ.h

#include"list/list.h"

#ifndef PQ_H
#define PQ_H

/**************Usage-start ******************/
typedef struct PQ PQ;

bool isEmptyPQ(PQ *);

#if defined(PQ_USING_ARRAY)
 void insertPQElement(PQ *, void *);
 void *delMaxPQElement(PQ *, isLess);
#elif defined(PQ_USING_SORTED_ARRAY)
 void insertPQElement(PQ *, void *, compareTo);
 void *delMaxPQElement(PQ *);
#endif

PQ* createPQ(void);
void freePQ(PQ*);
/**************Usage-end ******************/
#endif

PriorityQueue/arrayImpl.c

#include "list/list.h"

#if defined (PQ_USING_ARRAY)
/***************Repr-start***********/
typedef struct PQ{
  List *array;
}PQ;
/****************Repr-end************/

/*************Usage-start **********/
PQ * createPQ(){

  PQ *pq = malloc(sizeof(PQ));
  pq->array = createList();
  return pq;
}

void freePQ(PQ *pq){
  if(pq != NULL){
    freeList(pq->array);
    free(pq);
  }
}

bool isEmptyPQ(PQ *pq){
  if(pq != NULL){

    return listGetSize(pq->array) > 0;
  }else{
    fprintf(stderr, "isEmptyPQ() - NULL is passed\n");
    return false;
  }
}

void insertPQElement(PQ *pq, void *item){
  if(pq != NULL){
    listInsertItem(pq->array, item);
  }else{
    fprintf(stderr, "insertPQElement() - NULL is passed\n");
  }

}

void *delMaxPQElement(PQ *pq, isLess less){
  if(pq != NULL){
    void *maxElement = listDeleteMaxElement(pq->array, less);
    if(maxElement != NULL){
      return maxElement;
    }else{
      fprintf(stdout, "PQ is empty\n");
      return NULL;
    }
  }else{
    fprintf(stderr, "delMaxPQ() - NULL PQ is passed\n");
    return NULL;
  }

}
/*****************Usage-end ************/
#endif

PriorityQueue/sortedArrayImpl.c

#include "list/list.h"

#if defined (PQ_USING_SORTED_ARRAY)
/***************Repr-start***********/
typedef struct PQ{
  List *array;
}PQ;
/****************Repr-end************/

/*************Usage-start **********/
PQ * createPQ(){

  PQ *pq = malloc(sizeof(PQ));
  pq->array = createList();
  return pq;
}

void freePQ(PQ *pq){
  if(pq != NULL){
    freeList(pq->array);
    free(pq);
  }
}

bool isEmptyPQ(PQ *pq){
  if(pq != NULL){

    return listGetSize(pq->array) > 0;
  }else{
    fprintf(stderr, "isEmptyPQ() - NULL is passed\n");
    return false;
  }
}

void insertPQElement(PQ *pq, void *item, compareTo compare){
  if(pq != NULL){
    pq->array = sortedListInsertItem(pq->array, item, compare);
  }else{
    fprintf(stderr, "insertPQElement() - NULL is passed\n");
  }

}

void *delMaxPQElement(PQ *pq){
  if(pq != NULL){
    void *maxElement = sortedListDeleteMaxElement(pq->array);
    if(maxElement != NULL){
      return maxElement;
    }else{
      fprintf(stdout, "PQ is empty\n");
      return NULL;
    }
  }else{
    fprintf(stderr, "delMaxPQ() - NULL PQ is passed\n");
    return NULL;
  }

}
/*****************Usage-end ************/
#endif

User code,

pqClient.c

/*
  A priority queue is an abstract data type which is like a 
  regular queue or stack data structure, but where additionally 
  each element has a "priority" associated with it. In a priority
  queue, an element with high priority is served before an element 
  with low priority. If two elements have the same priority, they 
  are served according to their order in the queue.

  While priority queues are often implemented with heaps, they are 
  conceptually distinct from heaps. A priority queue is an abstract 
  concept like "a list" or "a map"; just as a list can be implemented 
  with a linked list or an array, a priority queue can be implemented 
  with a heap or a variety of other methods such as an un-ordered array.
*/

#include"PriorityQueue/PQ.h"

bool less(const void *key, const void *item){

  if( *((int *)key) < *((int *)item) ){
    printf("Return true\n");
    return true;
  }else{
    printf("Return false\n");
    return false;
  }
}

int compare(const void *key, const void *item){

  if( *((int *)key) < *((int *)item) ){

    return -1;
  }else if( *((int *)key) == *((int *)item) ){

    return 0;
  }else if( *((int *)key) > *((int *)item) ){

    return 1;
  }
  return -1;
}

int main(void){


  PQ *pq = createPQ();


  for(int index =0; index < 5; index++){
    int *item = malloc(sizeof(int));
    *item = index;
    #if defined(PQ_USING_SORTED_ARRAY) // Just for testing
    insertPQElement(pq, item, compare);
    #elif defined(PQ_USING_ARRAY)
    insertPQElement(pq, item);
    #endif
  }
  void *item = NULL;
  #if defined(PQ_USING_SORTED_ARRAY) // Just for testing
  item = delMaxPQElement(pq);
  #elif defined(PQ_USING_ARRAY)
  item = delMaxPQElement(pq, less);
  #endif

  printf("Max element is: %d\n", *(int *)item);
  free(item);

  #if defined(PQ_USING_SORTED_ARRAY) // Just for testing
  item = delMaxPQElement(pq);
  #elif defined(PQ_USING_ARRAY)
  item = delMaxPQElement(pq, less);
  #endif


  printf("Max element is: %d\n", *(int *)item);
  free(item);

  freePQ(pq);

}

Compilation procedure:

To test priority queue using unsorted array:

1) Sit in code folder,

2) Run command - gcc -std=c99 -Wall -Werror -I. -DARRAY -DPQ_USING_ARRAY ./list/*.c ./PriorityQueue/*.c pqClient.c -o pqClient

To test priority queue using sorted array:

1) Sit in code folder,

2) Run command - gcc -std=c99 -Wall -Werror -I. -DARRAY -DPQ_USING_SORTED_ARRAY ./list/*.c ./PriorityQueue/*.c pqClient.c -o pqClient


Question:

From abstraction/encapsulation aspect, Can this code get further optimised?

Note1: Using binary heap representation to implement Priority Queue is my further task

Note2: Cygwin enviornment

\$\endgroup\$
  • \$\begingroup\$ You use different declarations for the PQ interface for different implementations - try to make them interchangeable at link time. \$\endgroup\$ – greybeard Jan 3 '17 at 21:26
  • 1
    \$\begingroup\$ (Check your usage of white space in general and empty lines in particular - the top rule being consistency. Use a spelling checker.) \$\endgroup\$ – greybeard Jan 3 '17 at 21:29
  • \$\begingroup\$ @greybeard instead of writing 3 comments within 5 minutes, you should give the OP an answer ^^ \$\endgroup\$ – Grajdeanu Alex. Jan 3 '17 at 21:37
  • \$\begingroup\$ @greybeard Are you saying to interchange at link time? using structure of function pointers for each implementation? I wrote such code here \$\endgroup\$ – overexchange Jan 3 '17 at 21:43
  • \$\begingroup\$ @Dex'ter We need to respect his available bandwidth to answer. I think it takes more than 5 mins to give an answer \$\endgroup\$ – overexchange Jan 3 '17 at 21:46
2
\$\begingroup\$

From abstraction/encapsulation aspect, Can this code get further optimized?

A small optimization would be to use an idiom recognized by many compilers for comparing two numbers.

return (a>b) - (a<b);

Applying that to compare():

int compare(const void *key, const void *item) {
  const int *aptr = (const int *) key; 
  const int *bptr = (const int *) item; 
  return (*aptr > *bptr) - (*aptr < *bptr);
}

A memory optimization, trading some code for constant data would be to combine error messages. Also I see this as more maintainable.

// fprintf(stderr, "isEmptyPQ() - NULL is passed\n");
...
// fprintf(stderr, "insertPQElement() - NULL is passed\n");

static const Error_format[] = "Error: %s() = %s\n";
static const Error_NULL_Argument[] = "NULL is passed";
...
fprintf(stderr, Error_format, "isEmptyPQ", Error_NULL_Argument);
...
fprintf(stderr, Error_format, "insertPQElement", Error_NULL_Argument);

Also see a common macro extention __func__

\$\endgroup\$
  • \$\begingroup\$ Is it possible to say List array instead of List *array in PQ typedef? If yes, what are the changes required in list.h? \$\endgroup\$ – overexchange Jan 4 '17 at 19:02
  • \$\begingroup\$ @overexchange Sure it is possible. Consider pq->array = createList();. This would need to change to pq->array = *createList(); I think list.h could remain unchanged, but how those functions are called would be different as well as the functions passed as args compareTo and equalTo. \$\endgroup\$ – chux Jan 4 '17 at 19:18
  • \$\begingroup\$ No, am asking, whether I can make opaque pointer like typedef struct List *List in list.h. I want to make look like java syntax. List list \$\endgroup\$ – overexchange Jan 4 '17 at 20:16
  • \$\begingroup\$ @overexchange Yes. But that style is frowned upon by many. Could use typedef struct List List[1]. It also depends on how you want to call the functions. Hiding a pointer to a non-const parameter is obfuscation. IAC, recommend staying with typedef struct List *List. \$\endgroup\$ – chux Jan 4 '17 at 20:26
  • 1
    \$\begingroup\$ That style is frowned on by everyone, @over, because C is not a garbage-collected language. If you allocate memory dynamically, you need to explicitly free it. Hiding the fact that something is a pointer is not a good idea, because then you can't tell that it needs to be managed manually. It is, however, perfectly reasonable to add a typedef to make an opaque pointer type, allowing you to hide the implementation details of the struct. \$\endgroup\$ – Cody Gray Jan 5 '17 at 6:12

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.