/* ========================================================================== */
/*                                                                            */
/*   sortLink.c                                                               */
/*   (c) March 22, 2017 K. J. Rock                                            */
/*                                                                            */
/*   This shows how to sort a doubly linked list                              */
/*      with data node abstraction                                            */
/*                                                                            */
/* ========================================================================== */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct data    // create a structure to hold the data necessary to the problem
	{
	int age;        // min 20  max 70
	int salary;     // min $30,000 max $95,000
	int seniority;  // years of service  0 - 45
	};

struct node    // create a node structure for the linked list
	{
	struct data *data;   // these two data's are not the same.
	struct node *next, *prev;     // for doubly linked list
	//struct node *left, *right;  // for tree in the future
	};

struct node *head, *tail, *ep;  // head, tail, & employee pointers

// allocate the space for the data and then fill each field
// This is a helper function for addNode().
struct data * newData(void)
	{
	struct data *myData;

	myData = (struct data *) malloc(sizeof(struct data));
	myData->age = rand() % 50 + 20;
	myData->salary = rand() % 65000 + 30000;
	myData->seniority = rand() % 45;
	return (myData);
	}

// add a new node to the linked list
// it calls the above function for the problem data.
// This abstraction aids writing code.
// It separates the data from the linked list structure.
// This makes sorting easy because the data is pointed to not part of the list
void addNode(void)
	{
	struct node *myNode;

	myNode = (struct node *) malloc(sizeof(struct node));  // create new node

	myNode->data = newData();     // add data to our new node

	if (head == NULL)   // empty list case
		{
		head = myNode;
		}
	else 	// non-empty list
		{
		tail->next = myNode;
		myNode->prev = tail;
		}
	tail = myNode;
	}

// This is a sort helper function
void swap(struct node *start, struct node *ep)
	{  // notice how only the pointers to the data change
	struct data *temp;

	temp = ep->data;
	ep->data = start->data;
	start->data = temp;
	}

// a simple selection sort, pretty much brute force
// scan the list with two pointers.
// if the second is less than the first then swap them.
void sort(void)
	{
	struct node *start, *ptr; 	// working pointers

	start = head;  // start at the head of the list
	while (start != NULL)
		{   		// find the smallest and move it into the first position
		ptr = start;
		while (ptr != NULL)
			{     // change next line to reflect sort index of choice
			if (ptr->data->age < start->data->age)  // change < to >= for fun
				{
				swap(start, ptr); // swap the pointers, the data stays in place
				}
			ptr = ptr->next; 		// step inner loop
			}
		start = start->next;  // step outer loop, find next smallest list member
		}
	}

int main(void)
	{
	time_t t;
	srand((unsigned) time(&t)); 	// randomize by seeding from time
	int count = 12; 					// number of employees

	int j = 0;
	while (j++ < count)
		{
		addNode();     // add more employees
		}

	// walk the list and print out the data it holds
	ep = head;
	while (ep != NULL)
		{
		printf("age %3d\t\t", ep->data->age);
		printf("salary $%5d\t", ep->data->salary);
		printf("seniority %3d\t", ep->data->seniority);
		printf("data is here %p \n", ep->data);
		ep = ep->next;
		}

	sort();           // sort by age, salary, or seniority

	printf("\n\n\n");	// much needed whitespace

	// walk the sorted list and show the results
	ep = head;
	while (ep != NULL)
		{
		printf("age %3d\t\t", ep->data->age);
		printf("salary $%5d\t", ep->data->salary);
		printf("seniority %3d\t", ep->data->seniority);
		printf("data is here %p \n", ep->data);
		ep = ep->next;
		}

	for (j = 0; j < 5; j++)   // add five more nodes with data
		{
		addNode();
		}

	printf("\n\n\n");	// much needed whitespace

	ep = head;          	// show they are added at the end unsorted
	while (ep != NULL)
		{
		printf("age %3d\t\t", ep->data->age);
		printf("salary $%5d\t", ep->data->salary);
		printf("seniority %3d\t", ep->data->seniority);
		printf("data is here %p \n", ep->data);
		ep = ep->next;
		}
	}

///////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////

// deleteNode is for completeness.  It will be used in the future.
// Notice how you need to free the data node memory
// prior to freeing the node memory.
// If you don't do this in the correct order you'll have a "memory leak".
// That means the memory you allocated is now floating around
// without a pointer to it.  So you can't find it and the OS
// can't put it back into the free memory pool.
// Over time this forces a system crash when there is no more free memory.
void deleteNode(struct node *here)
	{
	if ((here->next == NULL) && (here->prev == NULL))
		{   							// only one left in list case
		free(here->data);       // free data memory space
		free(here);             // free list node memory space
		printf("List is now empty.\n");
		return;
		}

	if (here->prev != NULL)     // you want to delete the first node
		here->prev->next = here->next;
	else
		{
		head = here->next;
		head->prev = NULL;
		}

	if (here->next != NULL)    // you want to delete the last node
		here->next->prev = here->prev;
	else
		{
		tail = here->prev;   // you're deleting node from the middle of the list
		tail->next = NULL;
		}

	free(here->data);       // free data memory space
	free(here);             // free list node memory space
	}