/* Goal: An implementation of doubly linked lists using pointers.
 *
 * List are implemented using two structures: a node and a list.
 * A node contains pointers to two other nodes, nextNode and previousNode
 * A list contains the length of the list and three pointers to nodes: startNode, endNode, and CursorNode
 *
 * Functions provided for list manipulation:
 *   list *createList()
 *   node *createNode(char *value, node *nextNode, node *previousNode)
 *   int advanceCursor(int forward, list *dataList)
 *   int regressCursor(int backward, list *dataList)
 *   int deleteList(list *dataList)
 *   int deleteCursorNode(list *dataList)
 *   int addToStart(node *newNode, list *dataList)
 *   int addToEnd(node *newNode, list *dataList)
 *   int addAfterCursor(node *newNode, list *dataList)
 *   int addBeforeCursor(node *newNode, list *dataList)
 *   int clearList(list *dataList)
 *   int *concatenateLists(list *dataList1, list *dataList2)
 *   int compareNode(node *node1, node *node2)
 *   int quicksort(list *dataList)
 *   int readList(char *inputFileName, list *dataList)
 *   int displayList(list *dataList)
 *   int fdisplayList(FILE *outputFile, list *dataList)
 * Full descriptions of these functions are given below
 *
 * Author: Nathan Corvino
 * 
 * Created 2/9/00
 * First fully working version 2/22/99
 * Code cleaned up and additional comments added 2/23/99
 *
 */

#include <stdio.h>
#include "list.h"

/**************************************************************
 * Purpose: instantiates a linked list                        *
 * Postconditions: memory is allocated for a list new list    *
 * Problems: memory may not be able to be allocated           *
 * Returns: a pointer to a list                               *
 **************************************************************/
list *createList() {

  list *newList;

  /* Attempt to allocate memory for the new list */
  if (newList = (list *) malloc(sizeof(list))) {
     /* allocation was successful, so initialize components */
     newList->length = 0;
     newList->startNode = NULL;
     newList->endNode = NULL;
     newList->cursorNode = NULL;
  }

  /*return the address of the new list */
  return(newList);
}



/**************************************************************
 * Purpose: instantiates a node                               *
 * Postconditions: memory is allocated for a list new list    *
 * Problems: memory may not be able to be allocated           *
 * Returns: a pointer to a node if successful                 *
 *          the null pointer if unsuccessful                  *
 **************************************************************/
node *createNode(char *value, node *nextNode, node *previousNode) { 
  node *newNode;
  char *newData;

  /* Attempt to allocate memory for the new node */
  if (newNode = (node *) malloc(sizeof(node))) {
    if (newData = (char *) malloc(1+strlen(value)*sizeof(char))) {
      /* allocation was successful, so initialize components */
      strcpy(newData, value);
      newNode->data = newData;
      newNode->next = nextNode;
      newNode->previous = previousNode;
    }
  }

  /* return the address of the new node */
  return(newNode);
}



/************************************************************************************************
 * Purpose: moves a lists cursor forward a given number of nodes                                *
 * Parameters: int forward: the number of nodes to move forward                                 *
 *             list *dataList: the pointer to the list in which to move the cursor              *
 * Preconditions: forward must be a positive integer; otherwise, cursor will not be moved       *
 * Postconditions: the cursor is advanced the appropriate number of nodes                       *
 *                 if forward indicates the cursor should move past the last node in dataList,  *
 *                 the cursor will point to the last node                                       *
 * Returns: returns 0 after successful execution                                                *
 ************************************************************************************************/ 
int advanceCursor(int forward, list *dataList) {
  int i;

  for (i=0; i < forward; i++) {
    if (dataList->cursorNode == dataList->endNode) {
        return(0); 
    }
    else {
        dataList->cursorNode = dataList->cursorNode->next;
    }
  }
  return(0);
}



/*************************************************************************************************
 * Purpose: moves a lists cursor backward a given number of nodes                                *
 * Parameters: int backward: the number of nodes to move backword                                *
 *             list *dataList: the pointer to the list in which to move the cursor               *
 * Preconditions: backward must be a positive integer; otherwise, cursor will not be moved       *
 * Postconditions: the cursor is regressed the appropriate number of nodes                       *
 *                 if backward indicates the cursor should move past the first node in dataList, *
 *                 the cursor will point to the starting node                                    *
 * Returns: returns 0 after successful execution                                                 *
 *************************************************************************************************/
int regressCursor(int backward, list *dataList) {
  int i;

  for (i=0; i < backward; i++) {
    if (dataList->cursorNode == dataList->startNode) {
        return(1);
    }
    else {
        dataList->cursorNode = dataList->cursorNode->previous;
    }
  }
  return(0);
}



/********************************************************************
 * Purpose: too free the memory used by a list and all of its nodes *
 * Parameters: list *dataList: the list to be deleted               *
 * returns: 0 after successful execution                            *
 ********************************************************************/
int deleteList(list *dataList) {
  clearList(dataList);
  free(dataList);
  return(0);
}



/*******************************************************************************************************************
 * Purpose: to remove the cursorNode from the current list and free the memory associated with this node           *
 * Parameters: list *dataList: the list from which the cursor node should be removed                               *
 * Preconditions: the list is non-empty                                                                            *
 * Postconditions: The cursorNode of *dataList i deleted and the memory associated with it is freed                *
 *                 The cursor node is left pointing to the next element in the list, which is the same distance    *
 *                 from the startNode that the original cursorNode was.  The exception is when the cursorNode is   *
 *                 at the end of the list, in which case the cursorNode still points to the end of the list.       *
 * Returns: 0 if successful                                                                                        *
 *          1 if list was all ready empty                                                                          *
 *          -1 if anything else, unforseen, happens (should not)                                                   *
 *******************************************************************************************************************/
int deleteCursorNode(list *dataList) {
  node *deletedNode;
  /* if the list is all ready empty, nothing can be deleted.  Return 1 to indicate list was all ready empty */
  if (dataList->cursorNode == NULL) {
     return(1);
  } 
  /* if there is only 1 element in the list, then return an empty list */
  else if (dataList->length <= 1) {
     deletedNode = dataList->cursorNode;
     dataList->cursorNode = NULL;
     dataList->startNode = NULL;
     dataList->endNode = NULL;
     free(deletedNode->data);
     free(deletedNode);
     dataList->length = 0;
     return(0);
  }
  /* if cursorNode points to end ot list, then remove the last node */
  else if (dataList->cursorNode->next == NULL) {
    deletedNode = dataList->cursorNode;
    dataList->endNode = dataList->cursorNode = dataList->cursorNode->previous;
    dataList->endNode->next = NULL;
    free(deletedNode->data);
    free(deletedNode);
    dataList->length--;
    return(0);
  } 
  /* if cursorNode is at the beginning of the list, then remove the first node */
  else if (dataList->cursorNode->previous == NULL) {
    deletedNode = dataList->cursorNode;
    dataList->startNode = dataList->cursorNode = dataList->cursorNode->next;
    dataList->startNode->previous = NULL;
    free(deletedNode->data);
    free(deletedNode);
    dataList->length--;
    return(0);
  }
  /* otherwise, the list is a list of length greater than three with the cursorNode pointed somewhere in the
     middle of the list.  Remove the current node */
  else if (dataList->length > 1) {
    deletedNode = dataList->cursorNode;
    dataList->cursorNode = dataList->cursorNode->next;
    deletedNode->previous->next = deletedNode->next;
    deletedNode->next->previous = deletedNode->previous;
    dataList->length--;
    free(deletedNode->data);
    free(deletedNode);
    return(0);
  }
  /* if one of the above options was not executed, something has gone wrong.  Return -1 to indicate an error. */
  else return(-1);
}



/****************************************************************
 * Purose: to add a new node at the beginning of a list         *
 * Parameters: node *newNode: node to be added                  *
               list *dataList: list to which to add node        *
 * Preconditions: newNode and dataList are properly initialized *
 * Postconditions: newNode is added to beginning of dataList    *
 * Returns: 0 for successful operation                          *
 ****************************************************************/
int addToStart(node *newNode, list *dataList) {
  /* if dataList is empty, then newNode is the only node */
  if (dataList->length == 0) {
     dataList->startNode = dataList->endNode = dataList->cursorNode = newNode;
     dataList->length = 1;
     return(0);
  }
  /* otherwise, add dataList to the start */
  else {
     newNode->previous = NULL;
     newNode->next = dataList->startNode;
     dataList->startNode->previous = newNode;
     dataList->startNode = newNode;
     dataList->length++;
     return(0);
  }
}



/****************************************************************
 * Purose: to add a new node at the end of a list               *
 * Parameters: node *newNode: node to be added                  *
               list *dataList: list to which to add node        *
 * Preconditions: newNode and dataList are properly initialized *
 * Postconditions: newNode is added to end of dataList          *
 * Returns: 0 for successful operation                          *
 ****************************************************************/
int addToEnd(node *newNode, list *dataList) {
  /* if dataList is empty, then newNode is the only node */
  if (dataList->length == 0) {
     dataList->startNode = newNode;
     dataList->endNode = newNode;
     dataList->cursorNode = newNode;
     dataList->length++;
     return(0);
  }
  /* otherwise, add newNode to the end */
  else {
     newNode->next = NULL;
     newNode->previous = dataList->endNode;
     dataList->endNode->next = newNode;
     dataList->endNode = newNode;
     dataList->length++;
     return(0);
  }
}




/********************************************************************
 * Purose: to add a new node after the cursor of a list             *
 * Parameters: node *newNode: node to be added                      *
               list *dataList: list to which to add node            *
 * Preconditions: newNode and dataList are properly initialized     *
 * Postconditions: newNode is added after the cursor of dataList    *
 * Returns: 0 for successful operation                              *
 ********************************************************************/
int addAfterCursor(node *newNode, list *dataList) {
  /* if dataList is empty, then newNode is the only node */
  if (dataList->length == 0) {
     dataList->startNode = newNode;
     dataList->endNode = newNode;
     dataList->cursorNode = newNode;
     dataList->length++;
     return(0);
  } 
  /* if the cursor is at the end of  dataList, then newNode is the endNode */
  else if (dataList->cursorNode->next == NULL) {
     return(addToEnd(newNode,dataList));
  }
  /* otherwise, add newNode to the middle of dataList after the cursor */
  else
  {
     newNode->previous = dataList->cursorNode;
     newNode->next = dataList->cursorNode->next;
     dataList->cursorNode->next = newNode;
     newNode->next->previous = newNode;
     dataList->length++;
     return(0);
  }
}




/********************************************************************
 * Purose: to add a new node before the cursor of a list            *
 * Parameters: node *newNode: node to be added                      *
               list *dataList: list to which to add node            *
 * Preconditions: newNode and dataList are properly initialized     *
 * Postconditions: newNode is added before the cursor of dataList   *
 * Returns: 0 for successful operation                              *
 ********************************************************************/
int addBeforeCursor(node *newNode, list *dataList) {
  /* if dataList is empty, the newNode is the only node */
  if (dataList->length == 0) {
     dataList->startNode = newNode;
     dataList->endNode = newNode;
     dataList->cursorNode = newNode;
     dataList->length++;
     return(0);
  }
  /* if the cursor is at the start of dataList, then newNode is the startNode */
  else if (dataList->cursorNode->previous == NULL) {
     return(addToStart(newNode,dataList));
  }
  /* otherwise, add newNode to the end of dataList */
  else {
     newNode->next = dataList->cursorNode;
     newNode->previous = dataList->cursorNode->previous;
     dataList->cursorNode->previous = newNode;
     newNode->previous->next = newNode;
     dataList->length++;
     return(0);
  }
}


/*****************************************************************************
 * Purpose: to delete all the nodes in a list                                *
 * Parameters: list *dataList: the list to be cleared                        *
 * Postconditions: dataList is empty                                         *
 * Returns: 0 for successful operation                                       *
 *          -1 if all nodes have been deleted and there list length is not 0 *
 *               (should not happen                                          *
 *****************************************************************************/
int clearList(list *dataList) {
  dataList->cursorNode = dataList->startNode;
  /* remove the nodes one by one */
  while (dataList->cursorNode != NULL) {
    deleteCursorNode(dataList);
  }
  /* check to see if length of list is 0 */
  if (dataList->length == 0) {
    return(0);
  }
  /* if length of list is not 0, signal an error */
  else {
    return(-1);
  }
 }


/********************************************************************************
 * Purpose: to combine two lists                                                *
 * Parameters: list *dataList1: the list to appear at the start of the new list *
 *             list *dataList2: the list to follow dataList1                    *
 * Postconditions: *dataList1 points to dataList1 followed by dataList2         *
 *                 datatList2 is empty                                          *
 * Returns: 0 after successful operation                                        *
 ********************************************************************************/
int *concatenateLists(list *dataList1, list *dataList2) {
  node *cursorNode;

  if (dataList1->length < 1) {
    *dataList1 = *dataList2;
  }
  else if (dataList2->length > 0) {
  dataList1->endNode->next = dataList2->startNode;
  dataList2->startNode->previous = dataList1->endNode;
  dataList1->endNode = dataList2->endNode;
  dataList1->length = dataList1->length + dataList2->length;
  dataList2->startNode = NULL;
  dataList2->endNode = NULL;
  dataList2->cursorNode = NULL;
  dataList2->length = 0;
  }
  return(0);
}


/******************************************************
 * Purpose: to compare the data in two nodes          *
 * Parameters: node *node1: a node to be compared     *
 *             node *node2: a node to be compared     *
 * Preconditions: node1 and node2 are not NULL        *
 * Postconditions: nothing changed                    *
 * Returns: <0 if node1's data < node2's data         *
 *           0 if node1's data == node2's data        *
 *          >0 if node1's data > node2's data.        *
 ******************************************************/
int compareNode(node *node1, node *node2) {
  return(strcmp(node1->data, node2->data));
}  


/***************************************************************************************************
 * Purpose: To sort the list given based on string comparisons using the quicksort algorithm.      *
 * Parameters: list *dataList: list to be sorted                                                   *
 * Preconditions: dataList is not NULL                                                             *
 * Postconditions: dataList is sorted                                                              *
 * Returns: 0 for successful operation                                                             *
 ***************************************************************************************************/
int quicksort(list *dataList) {

  int pivotNumber;
  list *smallerList;
  list *equalList;
  list *greaterList;
  node *pivot;
  node *nodeCopy;

  /* Check to see that list has more than 1 element */
  if (dataList->length < 2) {
    return(0);
  }
  /* List has elements needing sorting */
  else {
    /* Pick a pivot - randomly */
    srand(clock());
    pivotNumber = (rand() % dataList->length);
    dataList->cursorNode = dataList->startNode;
    advanceCursor(pivotNumber, dataList);
    pivot = createNode(dataList->cursorNode->data, NULL, NULL);
    /* Usefull code - a line to see what random number is being selected for the pivot.  Verifies that the pivot
       is being choosen Randomly.  Also a line that sets the pivot to the start of the node - pivot is selected
       faster, although not randomly. */
          /* printf("PivotNumber = %d   Pivot: %s\n", pivotNumber, pivot->data); */
          /* pivot = createNode(dataList->startNode->data, NULL, NULL); */

    /* Create three lists for three categories of values */
    smallerList = createList();
    equalList = createList();
    greaterList = createList();
    /* set the cursor node to the start of the list */
    dataList->cursorNode = dataList->startNode;
    /* While there are still elements in the list to be sorted, sort these elements into the appropriate lists */
    while (dataList->length > 0) {
      /* Copy cursor node and then delete the cursor node */
      nodeCopy = createNode(dataList->cursorNode->data, NULL, NULL);
      deleteCursorNode(dataList);
      /* add the copied node to the appropriate list */
      /* see if curosr node is less than pivot */
      if (compareNode(pivot, nodeCopy) > 0) {
	addToEnd(nodeCopy, smallerList);
      }
      /* see if cursor node is greater than pivot */
      else if (compareNode(pivot, nodeCopy) < 0) {
	addToEnd(nodeCopy, greaterList);
      }
      /* if neither less than or greater than pivot, must be equal to pivot */
      else {
	addToEnd(nodeCopy, equalList);
      }
    }
    /* sort the smaller and greater lists */
    quicksort(smallerList);
    quicksort(greaterList);
    /* add the three lists together in the appropriate order */
    concatenateLists(smallerList, equalList);
    concatenateLists(smallerList, greaterList);
    /* copy the sorted list structure to the original list address */
    *dataList = *smallerList;
    /* free up memory and return 0 for a successful sort */
    free(equalList);
    free(smallerList);
    free(greaterList);
    free(pivot->data);
    free(pivot);
    return(0);
  }
}



/**************************************************************************************
 * Purpose: to read a list from a file                                                *
 * Parameters: char * inputFileName: the name of the file from which to read the list *
 *             dataList: the list to be read                                          *
 * Preconditions: dataList is not empty                                               *
 *                the file indicated exists and is in the proper formate to be read   *
 *                  as a list                                                         *
 * Postconditions: dataList contains the list contained in the indicated file         *
 * Problems: if input file is not in the proper format, problems may be encountered   *
 *             first line of file should be an integer with the number of nodes in    *
 *                  the list being read                                               *
 *             each successive line of the file should contain a string representing  *
 *                  the data on a node in the list.  There should be at least as many *
 *                  such lines as the integer on the first line indicates             *
 * Returns: 0 for successful operation                                                *
 *          -1 if dataList is non-empty                                               *
 *          -2 if inputFileName does not exist                                        *
 **************************************************************************************/
int readList(char *inputFileName, list *dataList) {
  if (dataList->length > 0) {
    return(-1);
  }
  else {
    FILE *inputFile;
    int numberOfNodes, i;
    char buffer[255];
    node *newNode;

    inputFile = fopen(inputFileName, "r");
    /* if file was opened successfully, read the list */
    if (inputFile != NULL) {
      /* get the number of nodes in the list */
      fgets(buffer, sizeof(buffer), inputFile);
      sscanf(buffer, "%d", &numberOfNodes);
      /* read the appropriate number of nodes */
      for (i = 0; i < numberOfNodes; i++) {
	fgets(buffer, sizeof(buffer), inputFile);
	/* remove the newline character */
	buffer[strlen(buffer)-1] = '\0';
	newNode = createNode(buffer, NULL, NULL);
	addToEnd(newNode, dataList);
	}
      /* clost the inputFile */
      fclose(inputFile);
      return(0);
    }
    else return(-2);
  }
}



/********************************************************
 * Purpose: to display a list to the screen             *
 * Parameters: list *dataList: the list to be displayed *
 * Returns: 0 for successful operation                  *
 ********************************************************/
int displayList(list *dataList) {
     int len;
     node *cursor;
     len = 0;
     /* display the number of nodes the list indicates it should contain */
     printf("Displaying List\nExpected Length: %i\n", dataList->length);
     cursor = dataList->startNode;
     /* display each node in the list */
     while (cursor != NULL) {
        len++;
        /* check to see if the node is the cursor node */
        if (cursor == dataList->cursorNode) {
	   printf("-->");
	}
        else {
           printf("   ");
        }
	/* display the nodes data */
        printf("%i:  %s", len, cursor->data);
	/* display the previous nodes data if it exists */
	if (cursor->previous != NULL) {
	   printf("   Prev: %s", (cursor->previous)->data);
	}
	/* display the next nodes data if it exists */
	if (cursor->next != NULL) {
	   printf("   Next: %s", (cursor->next)->data);
	}
	printf("\n");
        cursor = cursor->next;
     }
     /* display the number of nodes the list contained */
     printf("Actual Length: %i\n",len);
     return(0);
}



/***********************************************************
 * Purpose: to write a list to a file                      *
 * Parameters: File *outputFile: the file to be written to *
 *             list *dataList: the list to be written      *
 * Returns: 0 for successful operation                     *
 ***********************************************************/
int fdisplayList(FILE *outputFile, list *dataList) {

     int len;
     node *cursor;
     len = 0;

     /* display the number of nodes the list indicates it should contain */
     fprintf(outputFile, "Displaying List\nExpected Length: %i\n", dataList->length);
     cursor = dataList->startNode;
     /* display each node in the list */
     while (cursor != NULL) {
        len++;
        /* check to see if the node is the cursor node */
        if (cursor == dataList->cursorNode) {
	   fprintf(outputFile, "-->");
	}
        else {
           fprintf(outputFile, "   ");
        }
	/* display the nodes data */
        fprintf(outputFile, "%i:  %s", len, cursor->data);
	/* display the previous nodes data if it exists */
	if (cursor->previous != NULL) {
	   fprintf(outputFile, "   Prev: %s", (cursor->previous)->data);
	}
	else {
	   fprintf(outputFile, "   No Prev");
	}
        /* display the next nodes data if it exists */
	if (cursor->next != NULL) {
	   fprintf(outputFile, "   Next: %s", (cursor->next)->data);
	}
	else {
	   fprintf(outputFile, "   No Next");
	}
	fprintf(outputFile, "\n");
        cursor = cursor->next;
     }
     fprintf(outputFile, "Actual Length: %i\n",len);
     return(0);
}