/* strLists.c provides the following functions declared in list.h
 * @author Wanlin Liu, Dorene Mboya, Eric Otoo
 * Version 2.0 of February 18, 2000
 */

#include "list.h"
/* Construct a doubly linked  node that has 3 parts: a word,
   pointer to the previous and the next node.
*/
struct lnode{
  char word[MAX]; /* points to text */
  struct lnode *pre; /* previous node */
  struct lnode *next; /* next node */
};



/*---------------------------FUNCTIONS------------------------*/

/* initialize(): Initialize a linked list.
 * Parameters  : none
 * Return      : a pointer to an empty doubly linked list.  The first
 *               and only node of the list is a dummy.
 */
list initialize() {
  /* Allocate space for the dummy node of the list and the list. */
  nodep dummy;
  list lst;
  if((dummy = (nodep)malloc(sizeof(struct lnode))) &&
     (lst = (list)malloc(sizeof(struct linkedlist))))  {
    /* The dummy node has not predecessor or successor.*/
    dummy->pre = null;
    dummy->next = null;
    /* The dummy node contains no string value.*/
    strcpy(dummy->word, "");
    /* The head, tail, and current node of the list all point to the dummy.*/
    lst->head = dummy;
    lst->tail = dummy;
    lst->current = dummy;
    
    return lst;
  }
  else
    exit(1);
}/*initialize() */


/* reset(list ls) : sets the current of a given list to the node after dummy
 * Parameters     : a pointer to the list.
 * Returns        : none.
 */
void reset(list ls) {
  ls->current = ls->head->next;
}/*reset(list) */


/* isempty(list ls) : tests whether a given list is empty or not.
 * Parameters       : a pointer to the list.
 * Returns          : 0 if the list is not empty, 1 if empty.
 */
int isempty(list ls) {
  return (ls->head == ls->tail);
}/*isempty(list ls)


/* advance(list ls) : moves the current node forward by one step.
 * Parameters       : the pointer to the list.
 * Returns          : 1 if adavnce succeeds, 0 if it fails.
 */
int advance(list ls) {
  /* If the current pointer is at the end of the file, keep it there.*/
  if (ls->current == ls->tail) {
    printf("Cannot advance, already at the end of the list.\n");
    return 0;
  }
  else {
    ls->current = ls->current->next;
    return 1;
  }
}/*advance(list)*/


/* backoff(list ls) : moves the current node backward by one step.
 * Parameters       : the pointer to the list.
 * Returns          : 1 if backoff succeeds, 0 if it fails.
 */
int  backoff(list ls) {
  if(ls->current == ls->head) {
    printf("Cannot backoff, already at the head of the list.\n");
    return 0;
  }
  else { 
    ls->current = ls->current->pre;
    return 1;
  }
}/*backoff(list)*/


/* getcurrent(list ls) : returns the content of the current node.
 * Parameters          : a pointer to the list.
 * Pre                 : the current cannot be the dummy node.
 * Returns             : the content of the current node.
 */
char *getcurrent(list ls) {
  if(!isempty(ls))
    return ls->current->word;
  else
    return null;
}/*getcurrent(list ls)*/


/* addtoend(list ls, char *w) : add a node to the end of a given list. 
 * Parameters                 : a pointer to the list, and 
 *                              the string to be added.
 * Return                     : none
 */
void addtoend(list ls, char *w){
  /* Allocate space for the new node. */
  nodep newnode;
  if(newnode = (nodep)malloc(sizeof(struct lnode))){
    /* The new node is add to the end, it has no successor.*/
    newnode->next = null;
    /* Let the string value of the new node be w.*/
    strcpy(newnode->word, w);
    /* The original tail of the list now has the new node as its successor.*/
    ls->tail->next = newnode;
    /* And the predecessor of the new node is the original tail node.*/
    newnode->pre = ls->tail;
    /* Advance the tail pointer to the new node.*/
    ls->tail = newnode;
  }
  else
    printf("Unable to allocate memory for the new node.\n");
}/* addtoend(list, char*) */



/* insert(list ls, char *w) : Insert a node after the current node. 
 * Parameters               : a pointer to the list, the string to be added.
 * Return                   : none.
 * Post                     : The current node will be the new node.
                              All other nodes remain in the original order.
*/
void insert(list ls, char *w) {
  nodep newnode;
  /* If the current node does not point to the tail of the list, insert.*/
  if(ls->current != ls->tail) {
    /* Allocate space for the new node.*/
    if (newnode = (nodep)malloc(sizeof(struct lnode))){ 
      /* Copy the string.*/
      strcpy(newnode->word, w);  
      /* Insert the new node between current and the node after current.*/
      newnode->next = ls->current->next;
      newnode->pre = ls->current;
      newnode->next->pre = newnode;
      ls->current->next = newnode;    
      ls->current = newnode;
    }
    else
      printf("Unable to allocate memory for the new node.\n");
  }/*if*/
  /* Otherwise, we can simply call addtoend to accomplish the task.*/
  else {
    addtoend(ls, w);
    advance(ls);
  }/*else*/  
}/*insert(list, char*)*/


/* printcurrent(list ls): prints the content of the current node.
 * Parameters           : the pointer to the list.
 * Returns              : 1 if pritncurrent succeeds, 0 if it fails..
 */ 
int printcurrent(list ls) {
  /* If the current points to the dummy node, do nothing.*/
  if(ls->current == ls->head) {
    printf("No content in the current node.\n");
    return 0;
  }
  else {
    printf("%s", ls->current->word);
    return 1;
  }
}/* printcurent(list)*/


/* listwrite(list ls, char* filename) : write the content of the list to
 *                                      a designated file.
 * Parameters                         : a pointer to the list,
 *                                      the name of a file
 * Return                             : 1 if listwrite succeeds,
 *                                      0 if it fails..
 */
int listwrite(list ls, char *fileName){
  /* A pointer to the file.*/
  FILE *fp;
  /* Let the current point to the head in the beginning. */
  ls->current = ls->head;
  /* If the file is opened successfully, write to the file.*/
  if((fp = fopen(fileName, "w")) != null) {    
    /*While the end of the list is not reached yet.*/
    while (ls->current != ls->tail){
      advance(ls);
      fputs(ls->current->word, fp);
    }/*if*/
    /*fputs(q->word, fp);*/
    fclose(fp);
    printf("File %s is successfully written.\n", fileName);
    return 1;
  }
  else {
    printf("Unable to open file %s.\n", fileName);
    return 0;
  }
}/* listwrite(list, char*) */


/* listprint(list ls) : prints out all the strings in the list in order. 
 * Parameters         : a pointer to the list.
 * Returns            : none
 */
void listprint(list ls) {
  ls->current = ls->head;
  while(ls->current != ls->tail) {
    advance(ls);
    printcurrent(ls);
    printf("\n");
  }/*while*/
  /*printf("%s", q->word);*/
  printf("\nEnd of list.\n");
}/*listprint*/


/* printfile(char *filename)   : prints a file to the screen.
 * Parameters                  : the name of the file.
 */
void printfile(char *filename) {
  FILE *fp;
  char ch;
  if((fp = fopen(filename, "r")) != null){
    /*While the end of file is not reached, read a character and print it.*/
    while((ch = fgetc(fp)) != EOF) {
      putchar(ch);
    } /*while*/    
    fclose(fp);
  }
  else
    printf("File %s cannot be opened.\n", filename);
}/*printfile(char*)*/


/* readline(FILE *fp) : read one line of characters from the given pointer
 * Parameters         : the pointer to a file.
 * pre                : The first character cannot be EOF
 * Returns            : a string containing the line read.
 */
char *readline(FILE *fp) {
  /* A buffer to store the characters read. */
  char *buf;
  char c;
  int i = 0;
  /* Read until the '\n' or EOF is encourntered.  */
  while(((c = fgetc(fp)) != '\n') && (c != EOF))
    buf[i++] = c;
  /*Put the'\n' or EOF into the buffer.*/
  buf[i++] = c;
  /*Put the end of string sign into the buffer.*/
  buf[i] = '\0';
  
  return buf;
}/* readline(FILE*) */


/* listread(char *filename) : read a file into a list of strings
 * Parameters               : the name of a file 
 * Returns                  : pointer to the list. 
 */
list listread(char *filename) {
  FILE *fp;
  char *str;
  list ls;
  char c;
  /* If the file is opened successfully, read. */
  if ((fp = fopen(filename, "r")) != null){ 
    ls = initialize();
    /* While the end of file has not been reached. */
    while ((c = fgetc(fp)) != EOF) {
      /* Because we have already read in the character, 
       * we should back off the pointer by one character.
       */
      fseek(fp, -1, SEEK_CUR);
      str = readline(fp);
      addtoend(ls, str);     
    }
    fclose(fp);
    printf("File %s is read.\n", filename);
    return ls;
  }
  else {
    printf("Unable to open file %s.\n", filename);
    return ls;
  }
  
}/*listread(char*)*/


/*The function concatenates sorted lists containing 
 *elements less than the pivot, elements equals to the
 *pivot and elements greater than the pivot
 *Parameters:Three lists to be concatenated
 *PreConditions: All three lists are initialized
 *PostConditions:The concatenated list contains all the 
 *elements in the three lists
 *Produces: A sorted list containing all the elements 
 *of the concatenated lists
 */

list concatenate(list smaller, list eql, list greater) {
  list lst;
  lst = (list)initialize();

  /* Concatenate the first list */

  lst->head = smaller->head; 
  lst->current = smaller->tail; 
  lst->tail= smaller->tail;
  free(smaller); /* deleting smaller wrapper node*/

  /*Concatenating the second list to the first */

  if (!isempty(eql)){/* Checking if the eql list is empty 
                              *i.e., contains the dummy node only.*/
    lst->tail = eql->tail;
    lst->current->next = eql->head->next;
    lst->current->next->pre = lst->current;
    lst->current = lst->tail;  
    free(eql->head); /* deleting eql's dummy node */
    free(eql);/* deleting eql wrapper node*/
  }
  else {/*list is empty */
    free(eql->head); /* deleting eql's dummy node */
    free(eql);/* deleting eql wrapper node*/
  }

  /*Concatenating the third list to the first two */

  if (greater->head->next != null){/* Checking if the greater list is empty 
                              *i.e., contains the dummy node only.*/
    lst->tail = greater->tail;
    lst->current->next = greater->head->next;
    lst->current->next->pre = lst->current;
    lst->current = lst->tail;  
    free(greater->head); /* deleting greater dummy node */
    free(greater);/* deleting greater wrapper node*/
  }
  else {/*list is empty */
    free(greater->head); /* deleting greater dummy node */
    free(greater);/* deleting greater wrapper node*/
  }
  return lst;
}/* concatenate*/ 

/*The function sorts a list using quicksort method 
 *Parameters:The list to be sorted
 *PreConditions: The list is initialized
 *PostConditions:The sorted list has all the elements in the initial list
 *Produces: A sorted list  
 */

list quicksort(list lst) {
  char str[128];
  list smaller, greater, eql;
  /*Basis: the list has less than two elements */
  if ((lst->head->next == null) || (lst->head->next->next == null)) {
    return lst;
  }
  else {
    /* skip the dummy node. */
    lst->current = lst->head->next;
    /* pick a pivot. */    
    strcpy(str,lst->current->word);
      
    /* partition the list into 3 lists.
     * smaller is the list with strings smaller than the pivot.
     * greater is the list with strings greater than the pivot.
     * eql is the list with strings equal to the pivot.
     */
    smaller = (list)initialize();
    greater = (list)initialize();
    eql = (list)initialize();

    while(lst->current != null) {
      /* If the string is greater than the pivot, add it to greater.*/ 
      if((strcmp(lst->current->word, str)) > 0) {
        addtoend(greater, lst->current->word);
      }
      /* If the string is equal to the pivot, add it to eql.*/      
      else if((strcmp(lst->current->word,str)) == 0) {
        addtoend(eql, lst->current->word);
      }
      /* If the string is smaller than the pivot, add it to smaller.*/
      else {
        addtoend(smaller, lst->current->word);
      }
     /* advance the pointer to the next node.*/
      if (lst->head->next->next != null){
        lst->head->next->next->pre = lst->head;
        lst->head->next = lst->head->next->next;
        free(lst->current);/*delete the node containing compared string */
        lst->current = lst->head->next;
      }
      else {
        free(lst->current);/*delete the node containing compared string */
        lst->head->next = null;
        lst->tail = lst->head;
        lst->current = null;
      }
    }/*while*/
    
    free(lst->head); /*delete the list dummy node */
    /*lst = concatenate(smaller, eql, greater); */ 
    lst = concatenate(quicksort(smaller), eql, quicksort(greater)); 
    return lst;
  }/*else*/
}/*quicksort*/


/* listDeletions.c provides functions to delete nodes from a linked list.
 * @authro Eric Otoo, Wanlin Liu
 * Version 2.0 of February, 19, 2000
 */

/* deletecurrent(list ls) : deletes the current node of the list
 * Parmaeters             : a pointer to the list.
 * Pre                    : the current node cannot be the head
 * Post                   : current points to the next node if current is 
 *                          not the tail, otherwise current points to tail.
 * Returns                : 1 if current is successfully deleted, else 0.
 */                                                       
int deletecurrent(list ls) {
  /* A pointer to save current, so we can free it later.*/
  nodep p;
  /* If the current node is the dummy node, we cannot delete it.*/
  if(ls->head == ls->tail) {  
    printf("Cannot delete current, list is empty.\n");
    return 0;
  }
  /*If the current is the tail, delete it and update tail and current.*/
  else if (ls->current == ls->tail) {
    ls->tail = ls->tail->pre;
    free(ls->tail->next);
    ls->tail->next = null;
  }
  /*Otherwise, delete and update current.*/
  else {
    p = ls->current;
    p->pre->next = p->next;
    p->next->pre = p->pre;
    advance(ls);
    free(p);    
  }
  return 1;
}/*deletecurrent(list)*/


/* find_nth_node(list ls, int n) : finds the nth node in a given list.
 * Parameters                    : the pointer to the list, a positive
 *                                 integer indicating the position the node.
 * Returns                       : 1 if the node is found, 0 if not
 * Pre                           : n cannot exceed the length of the node
 * Post                          : current points to the nth node if found
 *                               : otherwise, current position is unknown.
 */
int find_nth_node(list ls, int n){
  if (n<1)
    return 0;
  reset(ls);
  n--;
  while (n--) {
    /*If the end of the list has not been reached, move forward.*/
    if((advance(ls)) == 0)
      return 0;
  }
  return 1;
}/* find_nth_node */


/* delete_nth_node(list ls, int n) : deletes the nth node in ls.
 * Parameters                      : a pointer to the list, 
 * Pre                             : n cannot exceed the length of the list.
 * Returns                         : 1 if node is successfully deleted,
 *                                   0 if the task fails.
 */
int delete_nth_node(list ls, int n){
  /* If the nth node cannot be located, return 0.*/
  if (find_nth_node(ls, n) == 0){
      printf("Unable to delete.\n");
      return 0;
  }
  /* If the nth node is found, delete it.*/
  else{
    deletecurrent(ls);
  }
}/*delete_nth_node(list, int) 


/* delete_elements(list ls, char[] str) : deletes all occurrences of the 
 *                                        string from the list
 * Parameters                           : a pointer to the list and a string
 * Returns                              : number of nodes deleted.
 */
int delete_elements(list ls, char *str) {
  int count = 0;
  /* set the current to the first "real" node of the list.*/
  reset(ls);
  /* Go through the list and delete the strings.*/
  do
    {
      if((strcmp(getcurrent(ls), str)) == 0) {
        deletecurrent(ls);      
        count++;
      }
      else
        advance(ls);
  }
  while(ls->current != ls->tail);/* while */
  if((strcmp(ls->current->word, str)) == 0) {
    deletecurrent(ls);      
    count++;
  }
   if(count==0)
    printf("String %s not found in list.\n", str);
   return count;
}/* delete_ elements */


/* delete_element(list ls, char *str) : deletes the first occurence of str
 * Parameters                         : a pointer to the list and the
 *                                      string to be deleted.
 * returns                            : 1 if the string is deleted,else 0.
 */
int delete_element(list ls, char str[]){
  int count = 0;
  reset(ls);
  /* Go through the list and delete the strings.*/
  do
    {
      if((strcmp(getcurrent(ls), str)) == 0) {
        deletecurrent(ls);
        count++;
        return count;
      }
      else
        advance(ls);
    }
  while(ls->current != ls->tail);/* while */
  if((strcmp(getcurrent(ls), str)) == 0) {
    deletecurrent(ls);
    count++;
  }
  if(count==0)
    printf("String %s not found in list.\n", str);
  return count;
}