/* quicksort.c 
 *
 * Chris Kern
 * This file contains the quicksort function, which quicksorts linked lists. */

#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"


struct list *quicksort(struct list *list) {

  /* Declare lists and pivot. */
  struct list *smaller = malloc(sizeof(struct list));
  struct list *equal = malloc(sizeof(struct list));
  struct list *greater = malloc(sizeof(struct list));
  struct list *final = malloc(sizeof(struct list));

  char *pivot = list->first->item;

  /* Declare a temporary integer. */
  int temp;

  /* Blank the lists. */
  smaller->first = NULL;
  smaller->last = NULL;
  equal->first = NULL;
  equal->last = NULL;
  greater->first = NULL;
  greater->last = NULL;

  /* If the list has only one element, it is already sorted. */
  if (list->first == list->last) {

    return list;

  }

  /* If all the elements in the list are the same, it is already sorted. 
   * Step through the list, comparing the pivot to each element. 
   */
  Reset(list);
  do {
    if (strcmp(list->cursor->item, pivot)) break;
    list->cursor = list->cursor->next;
  } while (list->cursor->next);
  
  /* If the cursor ran off the end of the list, then the list is sorted. */
  if (!list->cursor->next) return list;

  /* Otherwise, place the elements in the appropriate lists. */
  Reset(list);

  /* Step through each element, and place it in one of the three lists depending
   * on whether it is greater than, smaller than, or equal to the pivot.
   */
  do {
    
    temp = strcmp(list->cursor->item, pivot);
    if (!temp) AddToFront(list->cursor->item, equal);
    else if (temp < 0) AddToFront(list->cursor->item, smaller);
    else if (temp > 0) AddToFront(list->cursor->item, greater);
    
  } while (Advance(list));
  

  /* Recurse on the non-null lists. */
  if (smaller->first) smaller = quicksort(smaller);
  if (equal->first) equal = quicksort(equal);
  if (greater->first) greater = quicksort(greater);

  /* Combine the lists. The combination works by linking the smaller, equal, and greater
   * lists, and then setting the "final" list equal to smaller (or equal is smaller is
   * null).  The final->last and final->first fields and then initialized.
   */

  /* If the smaller list is not null, link it to the equal list. */
  if (smaller->first) {
    smaller->last->next = equal->first;
    equal->first->previous = smaller->last;
  }
  
  /* The equal list will always contain at least one element (the pivot), so no test is
   * necessary.  Link equal to greater. */
  equal->last->next = greater->first;

  /* If the greater list exists, link it to the equal list. */
  if (greater->first) greater->first->previous = equal->last;

  /* If the smaller list exists, make "final" point to that. */
  if (smaller->first) {
    final = smaller;
    final->first = smaller->first;
  }
  
  /* Otherwise, make "final" point to the equal list. */
  else {
    final = equal;
    final->first = equal->first;
  }

  /* Set final->last to either the "greater" or "equal" field, depending on the
   * existence of "greater". */
  if (greater->first) final->last = greater->last;
  else final->last = equal->last;

  /* Return the sorted, combined list. */
  return final;

} /* quicksort */