#include "list.h"
#include "strLists.c"

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