/* quicksort.c */
/* 
   Author: Joey Lesh, Joe Simonson, Todd Holloway

   Quicksorts nodes in a list according to the lexicographical orderof
   the strings contained in them.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "llistheader.h"

/*
  quicksort(node *) takes a list (represented by any node of the list)
  and sorts it lexicographically.  This function only moves pointers 
  around, it does not create a new list but rather returns the first
  node of the sorted list.
  
  Pre: You exist.
  Post: The node passed in and all of it's connected nodes connections
        may have been rearranged.
  Post: This collection of connected nodes are in lexicographical order.
*/
node *quicksort(node *initial){
  /* A pointer to the first node of the list of nodes with 
	 lexicographically equal contents */
  struct node *equal = NULL;
  /* A pointer to the first node of the list of nodes with 
	 lexicographically lesser contents */
  struct node *lesser = NULL;
  /* A pointer to the first node of the list of nodes with 
   lexicographically greater contents */
  struct node *greater = NULL;
  struct node *pivot;
  struct node *current;
  struct node *nextnode;
  struct node *tmp;
  
  /* Ensure that we are at the front of the list */
  initial = getFirst(initial);

  pivot = initial;
  current = initial; 

  /* While it's not at the end of the list */
  while (current != NULL) {

	nextnode = current->tail;
	/* EQUAL */
	if(strcmp(pivot->contents,current->contents) == 0) {
	  exciseNode(current);
	  if (equal == NULL)
		equal = current;
	  else 
		concat(equal, current);
	}
	/* LESSER */
	else if(strcmp(pivot->contents,current->contents) > 0) {
	 exciseNode(current);
	 if (lesser == NULL)
		lesser = current;
	  else
		concat(lesser, current);
	}
	/* GREATER */
	else if(strcmp(pivot->contents, current->contents) < 0){
	  exciseNode(current);
	  if (greater == NULL)
		greater = current;
	  else
		concat(greater,current);
	}
	/* Point to the next node in the list */
	current = nextnode;
  }

  if ((greater == NULL) && (lesser == NULL))
	return equal;
  else if (greater == NULL)
	return concat(quicksort(lesser),equal);
  else if (lesser == NULL)
	return concat(equal,quicksort(greater));
    else 
      return concat(quicksort(lesser), concat(equal,quicksort(greater)));
  
  /*
	If it makes it past the if statements above, all the lists are
	null (equal, greater, and lesser) and so a NULL node must have 
	been passed in so we return NULL.
  */
  return NULL;
}/*quickSort()*/