/* stringlist.c
 * 
 * Library of functions to create and manipulate a doubly linked
 * list of nodes containing strings.
 *
 * AUTHORS:
 *
 * Rackham Hoke and Ashfaqur Rahman
 *
 * REVISION HISTORY:
 *
 * 2/17/00 by Rackham Hoke
 * - Renamed node and list types to reflect that nodes contain
 *   strings (stringList and stringListNode).
 * - Moved node struct and definition back to stringlist.c
 *   (shouldn't be visible outside of where it's needed).
 * - Revised comments in functions to state purpose, preconditions,
 *   postconditions, problems, parameters, and return values.
 * - Replaced NO_NODE with NULL -- more standard.
 * - Changed addToFront() and addToEnd() to create their own nodes,
 *   rather than take preexisting nodes. This allows for node
 *   primitives to be completely hidden from outside users.
 * - Included checks for success in calls to malloc().
 * - Revised concatenateLists() to take handles rather than
 *   pointers, so that both list pointers actually access the same
 *   location in memory when done.
 * - Renamed printToScreen() and printToScreenBackwards() to
 *   listToScreen() and listToScreenReversed().
 * - Moved list iterator functionality to the list structure itself;
 *   Replaced deleteNodes() and deleteCurrent() with a new
 *   deleteCurrent() that deletes the current node in the list.
 * - Updated quicksortList() to reflect changes in addToFront(),
 *   addToEnd(), and concatenateLists().
 * - Moved function documentation to stringlist.h.
 * - Implemented the following functions:
 *     freeList()
 *     reverseList()
 *     appendNode() - helper for common list manipulations
 *     currentValue()
 *     resetCurrent()
 *
 * 2/10/00 by Rackham Hoke and Ashfaqur Rahman
 * - Implemented listFromFile().
 * - Implemented listToFile().
 * - Implemented resetIterator().
 * - Replaced isDone() with atEnd() and atFront().
 *
 * 2/10/00 by Rackham Hoke
 * - Added #define NO_NODE to eliminate explicit comparisons
 *   against '\0'.
 * - Moved function declarations to linkedlist.h.
 * - Implemented isEmpty().
 * - Created Makefile.
 * - Removed test code from this library.
 * - Implemented listIterator structure (see linkedlist.h).
 * - Implemented the following iterator functions:
 *     newListIterator()
 *     moveNext()
 *     deleteCurrent()
 *     isDone()
 * - Bug fix: listNode and newNode() pointer problem - listNodes
 *   need to store their own copies of strings, or their contents
 *   may change unexpectedly. listNodes now store a string of
 *   length VALUE_LENGTH, and newNode() uses strcpy() to store
 *   values.
 *
 * 2/9/00 by Rackham Hoke
 * - Implemented concatenateLists().
 *   Previously, concatenation code was located in quicksort().
 * - Bug fix: quicksortList() pointer problem - the given
 *   list pointer was not being changed to point to the
 *   newly sorted list, causing most lists to be corrupted.
 *
 * 2/9/00 by Rackham Hoke and Ashfaqur Rahman
 * - Implemeted quicksortList()
 * - Modified addToFront() so that nodes preceding
 *   the given node are lost.
 * - Modified addToEnd() so that nodes trailing the
 *   given node are lost.
 *
 * 2/8/00 by Rackham Hoke and Ashfaqur Rahman
 * - Implemented linkedList and listNode structs.
 * - Implemented the following functions:
 *     newList()
 *     newNode()
 *     addToFront()
 *     addToEnd()
 *     printToScreen()
 *     printToScreenBackwards()
 *     deleteNodes()
 */


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

/*********************/
/* STRUCTS AND TYPES */
/********************/


/* Structure and type definition for a node in the list. */
typedef struct stringListNode {
  struct stringListNode* left;   /* The predecessor in the list */
  struct stringListNode* right;  /* The successor in the list */
  char value[MAX_VALUE_LENGTH];  /* A string value */
} stringListNode;


/* Structure for a doubly linked list.
 * Type declaration is in stringlist.h. */
struct stringList {
  stringListNode* front;    /* The first node in the list */
  stringListNode* end;      /* The last node in the list */
  stringListNode* current;  /* The current node in a list iteration */
  int length;               /* The number of nodes in the list */
};


/*****************************************/
/* HELPER FUNCTIONS (for this file only) */
/*****************************************/


/* Creates a new list node with the given string value.
 * Preconditions: value is no longer than MAX_VALUE_LENGTH.
 * Postconditions: memory allocated for the returned node.
 * Problems: none.
 * Parameters:
 *   value - the string value to place in the node.
 * Return: a pointer to a new node,
 *   NULL if value is too long or memory allocation fails.
 */
stringListNode* newStringListNode(char* value);


/* Appends the given node to the end of the given list.
 * Preconditions: the node and list have been initialized.
 * Postconditions: the node is appended to the list,
 *   nodes trailing the appended node are "cut off".
 * Problems: none.
 * Parameters:
 *   list - the list to append to.
 *   node - the node to append.
 * Return: nothing.
 *
 * NOTE: To concatenate lists, use concatenateLists().
 */
void appendNode(stringList* list, stringListNode* node);


/* BEGIN newStringListNode() */
stringListNode* newStringListNode(char* value) {
  /* Local variables */
  stringListNode* node;

  /* Verify the length of the value. */
  if (strlen(value) > MAX_VALUE_LENGTH)
    return NULL;

  /* Allocate memory for the node.
   * Return NULL if allocation fails. */
  if (!(node = (stringListNode*) malloc(sizeof(stringListNode))))
    return NULL;

  /* Initialize node members. */
  node->left = NULL;
  node->right = NULL;
  strcpy(node->value,value);

  /* Return a pointer to the node. */
  return node;
}
/* END newStringListNode() */


/* BEGIN appendNode() */
void appendNode(stringList* list, stringListNode* node) {
  /* Local variables */
  stringListNode* oldEndNode;

  /* Update the old end node, if there is one. */
  oldEndNode = list->end;
  if (oldEndNode != NULL)
    oldEndNode->right = node;

  /* Update the new node. */
  node->left = oldEndNode;

  /* Make sure it's really the end node. */
  node->right = NULL;

  /* Update the list. */
  list->end = node;
  if (list->front == NULL)
    list->front = node;
  list->length += 1;
}
/* END appendNode() */


/*************************************************/
/* LIBRARY FUNCTIONS (available in stringlist.h) */
/*************************************************/


/* BEGIN newList() */
stringList* newList() {
  /* Local variables */
  stringList* list;

  /* Allocate memory for the list.
   * Return NULL if allocation fails. */
  if (!(list = (stringList*) malloc(sizeof(stringList))))
    return NULL;

  /* Initialize list members. */
  list->front = NULL;
  list->end = NULL;
  list->current = NULL;
  list->length = 0;

  /* Return a pointer to the list. */
  return list;
}
/* END newList() */


/* BEGIN addToFront() */
int addToFront(stringList* list, char* value) {
  /* Local variables */
  stringListNode* node;
  stringListNode* oldFrontNode;

  /* Attempt to create the node. */
  if (!(node = newStringListNode(value)))
    return 0;

  /* Update the old front node, if there is one. */
  oldFrontNode = list->front;
  if (oldFrontNode != NULL)
    oldFrontNode->left = node;

  /* Update the new node. */
  node->right = oldFrontNode;

  /* Update the list. */
  list->front = node;
  if (list->end == NULL) {
    list->end = node;
    list->current = node;
  }
  list->length += 1;

  /* Indicate success. */
  return 1;
}
/* END addToFront() */


/* BEGIN addToEnd() */
int addToEnd(stringList* list, char* value) {
  /* Local variables */
  stringListNode* node;

  /* Attempt to create the node. */
  if (!(node = newStringListNode(value)))
    return 0;

  /* Update current node in the list, if needed. */
  if (isEmpty(list))
    list->current = node;

  /* Add the node to the list. */
  appendNode(list,node);

  /* Indicate success. */
  return 1;
}
/* END addToEnd() */


/* BEGIN concatenateLists() */
void concatenateLists(stringList** listA, stringList** listB) {
  /* If either list is empty, point it at the other one and return. */
  if ((*listA)->front == NULL) {
    free(*listA);
    *listA = *listB;
    return;
  }
  if ((*listB)->front == NULL) {
    free(*listB);
    *listB = *listA;
    return;
  }

  /* Point the end of listA at the front of listB, and vice versa. */
  (*listA)->end->right = (*listB)->front;
  (*listB)->front->left = (*listA)->end;

  /* Update list fields. */
  (*listA)->end = (*listB)->end;
  (*listA)->length += (*listB)->length;

  /* Point both lists at the full list and return. */
  free(*listB);
  *listB = *listA;
  return;
}
/* END concatenateLists() */


/* BEGIN listToScreen() */
void listToScreen(stringList* list) {
  /* Local variables */
  stringListNode* current;

  for (current = list->front; current != NULL; current = current->right) {
    printf("%s",current->value);
    if (current != list->end)
      printf(", ");
  }
  printf("\n");
}
/* END listToScreen() */


/* BEGIN listToScreenReversed() */
void listToScreenReversed(stringList* list) {
  /* Local variables */
  stringListNode* current;

  for (current = list->end; current != NULL; current = current->left) {
    printf("%s",current->value);
    if (current != list->front)
      printf(", ");
  }
  printf("\n");
}
/* END listToScreenReversed() */


/* BEGIN deleteCurrent() */
int deleteCurrent(stringList* list) {
  /* Local variables */
  stringListNode* current = list->current;

  /* Indicate failure if current node is NULL. */
  if (current == NULL)
    return 0;

  /* Update the node's predecessor and successor. */
  if (current->right != NULL)
    current->right->left = current->left;
  if (current->left != NULL)
    current->left->right = current->right;

  /* Update the list. */
  if (current == list->front)
    list->front = current->right;
  if (current == list->end)
    list->end = current->left;

  list->length -= 1;
  list->current = current->right;

  /* Free the node from memory. */
  free(current);

  /* Indicate success. */
  return 1;
}
/* END deleteCurrent() */


/* BEGIN quicksortList() */
int quicksortList(stringList* list) {
  /* Local variables */
  stringList* lessThanPivot;  /* Stores nodes with values less than the pivot value. */
  stringList* equalToPivot;   /* Stores nodes with values equal to the pivot value. */
  stringList* moreThanPivot;  /* Stores nodes with values greater than the pivot value. */
  int pivotIndex;             /* The "index" of the pivot node. */
  char* pivotValue;           /* The value in the pivot node. */
  stringListNode* current;    /* Used for iterating the list. */
  stringListNode* nextRight;  /* Backs up the next node when iterating. */
  int cmpResult;              /* Stores the result when comparing values. */

  /* Don't sort lists with 0 or 1 nodes. */
  if (list->length <= 1)
    return 1;

  /* Create the temporary lists.
   * Indicate failure if list creation fails. */
  if (!((lessThanPivot = newList()) &&
	(equalToPivot = newList()) &&
	(moreThanPivot = newList())))
    return 0;

  /* Choose a random pivot node and retrieve its value. */
  pivotIndex = abs(rand() % list->length);
  current = list->front;
  for ( ; pivotIndex > 0; pivotIndex--)
    current = current->right;
  pivotValue = current->value;

  /* Place each node in the appropriate list, based on its stored value. */
  for (current = list->front; current != NULL; current = nextRight) {
    /* Store the next node to check. */
    nextRight = current->right;

    /* Compare and move the node. */
    cmpResult = strcmp(current->value,pivotValue);
    if (cmpResult < 0)
      appendNode(lessThanPivot,current);
    else if (cmpResult == 0)
      appendNode(equalToPivot,current);
    else
      appendNode(moreThanPivot,current);
  }

  /* Quicksort new lists as needed.
   * Indicate failure if either sort fails.*/
  if (lessThanPivot->length > 1)
    if (!quicksortList(lessThanPivot))
      return 0;
  if (moreThanPivot->length > 1)
    if (!quicksortList(moreThanPivot))
      return 0;
  
  /* Concatenate the three lists. */
  concatenateLists(&lessThanPivot,&equalToPivot);
  concatenateLists(&lessThanPivot,&moreThanPivot);

  /* Restore the pointer to the current node. */
  lessThanPivot->current = list->current;
  
  /* Point the actual list to the sorted result. */
  *list = *lessThanPivot;
  
  /* Free the temporary lists (they all point to the
   * same location in memory due to concatenation). */
  free(lessThanPivot);

  /* Indicate success. */
  return 1;
}
/* END quicksortList() */


/* BEGIN isEmpty() */
int isEmpty(stringList* list) {
  return (list->front == NULL);
}
/* END isEmpty() */


/* BEGIN moveNext() */
int moveNext(stringList* list) {
  /* Indicate failure if current node is NULL or the end node. */
  if (list->current == NULL || atEnd(list))
    return 0;

  /* Advance and indicate success. */
  list->current = list->current->right;
  return 1;
}
/* END moveNext() */


/* BEGIN moveBack() */
int moveBack(stringList* list) {
  /* Indicate failure if current node is NULL or the front node. */
  if (list->current == NULL || atFront(list))
    return 0;

  /* Move back and indicate success. */
  list->current = list->current->left;
  return 1;
}
/* END moveBack() */


/* BEGIN atEnd() */
int atEnd(stringList* list) {
  return (list->current == list->end);
}
/* END atEnd() */


/* BEGIN atFront() */
int atFront(stringList* list) {
  return (list->current == list->front);
}
/* END atFront() */


/* BEGIN listFromFile() */
stringList* listFromFile(char* fileName) {
  /* Local variables */
  stringList* list;                 /* The list to be returned. */
  stringListNode* node;             /* Used to build individual nodes. */
  FILE* file;                       /* The file handle. */
  int readStatus;                   /* Used to determine EOF. */
  char value[MAX_VALUE_LENGTH + 1]; /* Stores values being read. */

  /* Indicate failure if the file doesn't open. */
  if (!(file = fopen(fileName,"r")))
    return NULL;

  /* Attempt to create a new list. */
  if (!(list = newList()))
    return NULL;

  /* Create a node from each line in the file. MAX_VALUE_LENGTH + 1
   * is used because fgets() includes a trailing newline. */
  while (fgets(value,MAX_VALUE_LENGTH + 1,file) != NULL) {
    /* Remove the newline. */
    value[strlen(value) - 1] = '\0';

    /* Attempt to add the new node. */
    if (!addToEnd(list,value)) {
      freeList(list);
      return NULL;
    }
  }
  
  /* Close the file and return the list. */
  fclose(file);
  return list;
}
/* END listFromFile() */


/* BEGIN listToFile() */
int listToFile(stringList* list, char* fileName) {
  /* Local variables */
  FILE* file;              /* The file handle. */
  int writeStatus;         /* Monitors write progress. */
  stringListNode* current; /* The current node being written. */

  /* Indicate failure if the file can't be opened. */
  if (!(file = fopen(fileName,"w")))
    return 0;

  /* Iterate the list. */
  for (current = list->front; current != NULL; current = current->right) {
    /* Write the node's value.
     * Indicate failure if write fails. */
    if ((writeStatus = fputs(current->value,file)) > 0)
      return 0;

    /* Add a newline unless at the end of the list.
     * Indicate failure if write fails. */
    /* if (current != list->end) */
      if ((writeStatus = fputs("\n",file)) > 0)
	return 0;
  }

  /* Close the file and indicate success. */
  fclose(file);
  return 1;
}
/* END listToFile() */


/* BEGIN freeList() */
void freeList(stringList* list) {
  /* Local variables */
  stringListNode* current;  /* The current node being looked at. */
  stringListNode* nextNode; /* Points to the next node to free. */

  /* Loop through all the nodes, freeing them. */
  for (current = list->front; current != NULL; current = nextNode) {
    nextNode = current->right;
    free(current);
  }

  /* Free the list. */
  free(list);
}
/* END freeList() */


/* BEGIN currentValue() */
char* currentValue(stringList* list) {
  if (list->current != NULL)
    return list->current->value;
  else
    return NULL;
}
/* END currentValue() */


/* BEGIN reverseList() */
void reverseList(stringList* list) {
  /* Local variables */
  stringList* reverseList = newList();
  stringListNode* current;  /* The current node in iterating. */
  stringListNode* nextNode; /* The next node to move to. */

  /* Iterate the original list BACKWARDS,
   * appending each node to the end of the new list. */
  for (current = list->end; current != NULL; current = nextNode) {
    nextNode = current->left;
    appendNode(reverseList,current);
  }

  /* Update the original list. */
  list->front = reverseList->front;
  list->end = reverseList->end;
  free(reverseList);
}
/* END reverseList() */


/* BEGIN resetCurrent() */
void resetCurrent(stringList* list) {
  list->current = list->front;
}