/* dllfuncs.c - Doubly-Linked-List functions
 * Author: Amit Nangalia
 * Last modified: 17th February, 2000
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "listfunc.h"

/*Creates a doubly-linked-list*/
NODE *create(void) 
{

  NODE *list;
  
  /* Create a block of memory for header dummy node */
  if ((list = (NODE *) malloc(sizeof(NODE))) == NULL) {
    printf("Fatal malloc error in main!\n");
    exit(1);
  }
  /* Store constant HEADER into dummy head node */
  list->str[0] = HEADER;

  /* Create a block of memory for trailer dummy node */
  if( (list->forward = (NODE *) malloc(sizeof(NODE))) == NULL) {
    printf("Fatal error in malloc\n");
    exit(2);
  }
  /* Store constant DUMMY_TRAILER into dummy head node */
  list->forward->str[0] = DUMMY_TRAILER;
  list->forward->forward = NULL;
  list->forward->backward = list;
  return list;
}/* create */

/*********************************************/
/* deletes a node in a list, given the string to delete */

void delete(NODE *list, char *str)
{
  /* skip over dummy header */
  NODE *current = list->forward, *previous = list;
  list = list->forward;
 
  /* traverse through list till NULL pointer to find node to delete */
  while (list->forward != NULL) {
    /* compare the two strings */
    if (strncmp(str, current->str, sizeof(str)) == 0) {
      previous->forward = current->forward;
      current->forward->backward = previous;
      free(current);
      printf("deleted the element\n");
      break;
    }/* if */
    /* move onto next node */
    previous = current;
    current = current->forward;
    list = list->forward;
  }/* while */
  printf("no matching node found!\n");
}/* delete/

/*****************************************************/
/* insert an element into a list */

void insert(NODE *list, char *str)
{
  int num = 0;
  NODE *new, *previous = list;
  /* skip over dummy header */
  NODE *current = list->forward;

  /* allocate memory for new node */
  if ((new = (NODE *) malloc(sizeof(NODE))) == NULL)
    {
      printf("Fatal malloc error in insert!\n");
      exit(1);
    }
  /* copy the string data to new node */
  strcpy(new->str, str);

  /* Check the number of elements in the list, since we are inserting at the 
     end of the list.  If the list is empty, our current, and previous pointers
     are as defined above.  If the list already has a few elements in it, then
     we traverse the list to the end, and then define our current and previous 
     pointers. */
  num = num_elements(list);
  if (num >= 1) {
    while (current->str[0] != DUMMY_TRAILER) {
      current = current->forward;
    }
    previous = current->backward;
  }  

  /* update pointers */
  new->forward = current;
  new->backward = previous;
  previous->forward = new;
  current->backward = new;
}/* insert */

/****************************************************/
/* print out contents of each node */

void toFile(NODE *list, FILE *fp)
{
  /* skip over dummy header */
  list = list->forward; 
  
  /* Loop through till end of the list */
  while (list->str[0] != DUMMY_TRAILER)
    {
      fprintf(fp, list->str);
      printf("written to file %s", list->str);
      list = list->forward;
    }
}/* toFile */

/*************************************************/
/* print out contents of each node */

void traverse(NODE *list)
{
  /* skip over dummy header */
  list = list->forward; 
  /* This loop traverses the list and prints the string in each node - i.e FIFO order */
  while (list->str[0] != DUMMY_TRAILER) { 
    printf("%s", list->str);
    list = list->forward;
  }
  printf("\n");
}/* traverse */

/***************************************************/
/* counts the number of nodes in the list, excluding the dummy nodes */

int num_elements(NODE *list)
{
  int count= 0;
  
  /* skip over dummy header*/
  list = list->forward; 
  /* This loop traverses the list and keeps count of the number of elements*/
  while (list->str[0] != DUMMY_TRAILER) { 
    list = list->forward;
    count++;
  }
  return count;
}/* num_elements */

/*************************************************/
/* concatenates three smaller lists into one larger list, which is sorted 
   in alphabetical order */

NODE *join(NODE *smaller, NODE *equal, NODE *larger)
{

  NODE *linked, *small, *eq, *large;
  /* skip the dummy headers for each of the three lists */
  small = smaller->forward;
  eq = equal->forward;
  large = larger->forward;
  linked = create();
  
  while (small->str[0] != DUMMY_TRAILER) {
    insert(linked, small->str);
    small = small->forward;
  }
  while (eq->str[0] != DUMMY_TRAILER) {
    insert(linked, eq->str);
    eq = eq->forward;
  }
  while (large->str[0] != DUMMY_TRAILER) {
    insert(linked, large->str);
    large = large->forward;
  }
  return linked;
}/* join */

/************************************************************/
/*sort the list using a quick-sort */

NODE *sort(NODE *list) 
{
  int num_of_elements = 0;
  char *pivot;
  NODE *smaller, *equal, *larger, *all;
  /* skip over dummy header */
  list = list->forward;

  /* the pivot is the string stored in the first node */
  pivot = list->str;
  smaller = create();
  equal = create();
  larger = create();
  
  while (list->str[0] != DUMMY_TRAILER) { 
    /* compare the strings against the pivot - either smaller, larger or equal */
    if (strcmp(pivot, list->str) < 0)
      insert(larger, list->str);
    else if (strcmp(pivot, list->str) > 0)
      insert(smaller, list->str);
    else
      insert(equal, list->str);
    list = list->forward;
  }
 
  /* Base case for recursive sort. Check to see if list size is one or less */
  num_of_elements = num_elements(smaller);
  if (num_of_elements > 1)
    smaller = sort(smaller);

  num_of_elements = num_elements(larger);
  if (num_of_elements > 1)
    larger = sort(larger); 
  
  /* concatenate all three lists together */
  all = join(smaller, equal, larger);
  traverse(all);
  return all;
}/* sort */