#include <stdlib.h>		//rand, malloc
#include <stdio.h>		//printf


struct listnode	{

	struct listnode *next;
	long value;
};

//Finds length of list, which is usefull in selecting a random pivot
int ListLength (struct listnode *list)
{
	struct listnode *temp = list;
	
	int i=0;
	while(temp!=NULL)
	{
		i++;
		temp=temp->next;

	}
	return i;
}

// Prints list to help while working on homework
void printList(struct listnode *list)
{	
	struct listnode *node;
	node=list;
	printf("\nList Values\n");
	while(node!=NULL)
	{
		printf("%2lo ", node->value);
    	node=node->next;
	}
}
// Creates a list of desired length
struct listnode *createList(int lengthOfList)
{
	long i; 
    struct listnode *node, *space;
    space =  (struct listnode *) malloc( lengthOfList*sizeof(struct listnode));
    for( i=0; i< lengthOfList; i++ )
    {  (space + i)->value = 2*((17*i+1)%lengthOfList);
       (space + i)->next = space + (i+1);
    }

    (space+(lengthOfList-1))->next = NULL;
    node = space;

    return node;
}

// Prof Brass's test
void Brass_test(struct listnode *list)
{
	int i;
	printf("\nChecking sorted list\n");
	for( i=0; i < 100; i++)
    {  
	    if( list == NULL )
        { 
         	printf("List ended early\n"); exit(0);
        }
        if( list->value != 2*i )
        {  
	        printf("Node contains wrong value\n"); exit(0);
        }
        list = list->next;
   }
   printf("Sort successful\n");
}

// Selects a random pivot point
struct listnode *SelectPivot(struct listnode *list)
{

	int k, n, i = 0;
	n = ListLength(list);


	struct listnode *pivot=list;

	k=rand()%n;

	for (; i < k; ++i)
	{
		pivot=pivot->next;
	}

	return pivot;
}

// Sorts a list using quicksort algo with random pivot point
struct listnode *Quicksort(struct listnode *list)
{
	// Return NULL list
	if (ListLength(list) <= 1) return list;

	struct listnode *less=NULL, *more=NULL, *next, *endl, *temp=list;

	// Select a random pivot point
	struct listnode *pivot = SelectPivot(list);

	printf("Pivot Value = %lo\n", pivot->value);


	
	// Divide & Conquer
	while(temp != NULL)
	{
		
		next = temp->next;

		if(temp->value < pivot->value)
		{
			temp->next = less;
			less = temp;
		}
		else 
		{
			temp->next = more;
			more = temp;
		
		}
		temp = next;
	}
	// printf("\nLess list =\n");
	// printf("List Count %d\n", ListLength(less));
	// printList(less);
	
	// printf("\nMore list =\n");
	// printf("List Count %d\n", ListLength(more));
	// printList(more);


	// printf("\nlist list =\n");
	// printf("List Count %d\n", ListLength(list));
	// printList(list);
	// Recursive Calls


 	// less = Quicksort(less);
    // more = Quicksort(more);

	// Merge
	if(ListLength(less)!=0)
	{		
		while(endl != NULL)
		{
			endl = less->next;
			less->next = more;
			more = less;
			less = endl;
		}

		return more;		
	}
	else 
	{
		
		
		return more;	
	}

}

int main(void)
{
	struct listnode *node;

	node = createList(25);

	printf("Unsorted List\n");
    printList(node);

	printf("\nSorted List\n");
    node =	Quicksort(node);


	printf("\nList Count node %d\n", ListLength(node));
    printList(node);

    // Brass_test(node);




	exit(0);
}
;