/* quicksort.c
 * Authors: Pete Broadwell
 *          Josh Vickery
 * sort lists using the quicksort algorithm, it frees up unused memory, 
 * returning a new sorted list.
 * NOTE: uses a randomly-selected pivot on each sort.
 * ALSO NOTE: only works with strings of numbers as we use atoi to
 *            get the values of the numbers.
 * This program is called from the main interactive loop of fun_with_lists.
 * It takes a pointer to a list as its argument.
 */

#include "ll_defs.h"

llist *quicksort(llist *clist) {
  
  /* variable declarations */
  llist *equal = NULL;
  llist *greater = NULL;
  llist *smaller = NULL;
  node *cnode;
  int pivot_value;
  llist *slist;
  int i;
  int times;
  int count=1;
  double list_size;
  time_t seed; /* variable to initialize random number generator */   
  int random_pivot;

  time(&seed); /* store current system time in seed */
  srand(seed); /* initialize random generator with the system time */

  if (clist==NULL) {
    printf("List is currently empty. Nothing done.\n");
    return NULL;
  }

  /* base case--returns a list with one element */
  
  if (clist->first == clist->last) {
    return clist;
  }
 
  /* initial set up */

  /* determine the size of the list */
  list_size=count_nodes(clist); 
  
  clist->current=(node *)tofront(clist);

  /* randomly choose a number within the range of the list size as a pivot */ 
  random_pivot = 1 + (int) (list_size * rand() / (RAND_MAX + 1.0));

  /* move the the randomly selected pivot position */
  while(count < random_pivot){
    clist->current=(node *)advance_cursor(clist);
    count++;
  }
 
  /* record the pivot value */ 
  pivot_value = atoi(clist->current->contents);

  clist->current=(node *)tofront(clist);

  /* go through the list and put each element in one of the three new lists */
  times=1;

  while(times <= list_size) {
    /* puts elements in the equal list */ 
    if (atoi(clist->current->contents) == pivot_value) {
      if (equal == NULL) { 
        cnode = (node *)create_n(clist->current->contents);
        equal = (llist *)create_l(cnode);
      }
      else {
        cnode = (node *)create_n(clist->current->contents);
        equal = (llist *)add_to_end(equal, cnode);
      }
    }
    /* puts elements in the greater list */
    else if(atoi(clist->current->contents) > pivot_value) {
      if (greater == NULL) {
        cnode = (node *)create_n(clist->current->contents);
        greater = (llist *)create_l(cnode);
      }
      else {
        cnode = (node *)create_n(clist->current->contents);
        greater = (llist *)add_to_end(greater, cnode);
      }    
    }
    /* puts elements in the smaller list */
    else if (atoi(clist->current->contents) < pivot_value) {
      if (smaller == NULL) {
        cnode = (node *)create_n(clist->current->contents);
        smaller = (llist *)create_l(cnode);
      }
      else {
        cnode = (node *)create_n(clist->current->contents);
        smaller = (llist *)add_to_front(smaller, cnode);
       
      } 
    }
    times++;
    if (times <= list_size)
      clist->current = (node *)advance_cursor(clist);
  }

  /* recurse */

  /* case 1:  both greater and smaller have elements, recurse on both */
  if ((greater != NULL) && (smaller != NULL)) {
  
    /* add the elements of equals to front of quicksort(greater)
     * this should result in a sorted greater list, with the original
     * elements in equals
     */
     greater = (llist *)conclists(equal,(llist *)quicksort(greater));

    /* add quicksort(smaller) to the beginning of greater.
     * recursively, this should result in a sorted smaller element that
     * is connected to the larger list. The entire list is then stored as
     * slist, and the original greater is freed.
    */
    slist = (llist *)conclists((llist *)quicksort(smaller), greater);
//    delete_l(greater);
   
  }
  
  /* the following cases follow the same priciple, but only perform one part */
 
  /* case2: there are elements in greater, but not smaller */
  else if (greater != NULL) {
   
    slist = (llist *)conclists(equal,(llist *)quicksort(greater));
  }
  
  /* case 3: there are elements in smaller, but not greater */
  else if (smaller != NULL) {
     
    slist = (llist *)conclists((llist *)quicksort(smaller), equal);
  } 
  /* case 4: only elements in equal, return it */
  else {
    
    return equal;
  }
  
  return slist;
}