/* ========================================================================== */
/*                                                                            */
/*   search.c                                                                 */
/*   (c) April 8, 2017 K. J. Rock                                             */
/*                                                                            */
/*   Description:                                                             */
/*    create a linked list of random data.                                    */
/*	   save list to a disk file.                                               */
/*	   read list back into a tree.                                             */
/*	   walk the tree and put into an array                                     */
/*	   search array with a binary search using scanf                           */
/*                                                                            */
/* ========================================================================== */

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

#define COUNT 51		// size of the employee list

struct data		// create a structure to hold the data necessary to the problem
	{
	int id;        	// sequential upon instantiation id number
	int age;       	// min 20  max 70
	long salary;  		// min $30,000 max $115,000
	int seniority;		// years of service  0 - 45
	// xxx???      	// other fields ??
	};

struct node		// create a hybrid node structure for a list and a tree
	{
	struct data *data;   		// data pointer.
	struct node *next;         // singly linked list pointer
	struct node *left, *right; // tree structure pointers
	};

struct node *nodes[COUNT];    // array required for binary search routine

struct data * newData(void)
	{
	static int id = 0;  			// static makes this persistent
	struct data *myData;

	myData = (struct data *) malloc (sizeof(struct data));
	myData->id = id++;
	myData->age = rand() % 50 + 20;     // age from 20 to 70
	myData->salary = rand() % 65000 + 50000;  // income from 50000 to 115000
	myData->seniority = rand() % 45;
	return(myData);
	}

struct node * newNode(void)
	{
	struct node *myNode;

   myNode = (struct node *) malloc (sizeof(struct node));  // create new node
	myNode->data = newData();     // add data to our new node
	myNode->next = NULL;
   myNode->left = NULL;
	myNode->right = NULL;
	return(myNode);
	}

struct node * addNode(struct node *head)
	{
	struct node *ptr, *temp;

	if (head == NULL)
		{
		head = newNode();
		}
	else
		{
		ptr = head;
		while (ptr != NULL)    		// find the end of the list
			{
			temp = ptr;       		// remember the one before me
			ptr = ptr->next;
			}
	   temp->next = newNode();    // add new node at the end
		}
	return head;
	}

void printData(struct node *node)
	{
	printf("id %2d \t", node->data->id);
   printf("age %3d  ", node->data->age);
	printf("salary $%6ld  ", node->data->salary);
	printf("seniority %2d  ", node->data->seniority);
	printf("data at %p \n", node->data);
	}

   // insert myNode into tree
struct node * treeInsert(struct node *root, struct node *myNode)
	{
	if (root == NULL)  				// empty tree
		{
		//printf("node\n");          // sanity check
		root = myNode;
		}
	else
		{
		int isLeft = 0;            // direction flag
		struct node *ptr = root;
		struct node *prev = NULL;

		// walk the tree until there is space for a new node
		while (ptr != NULL)
			{
			prev = ptr;
											// change for different sort order
         if (myNode->data->age < ptr->data->age)
         //if (myNode->data->salary < ptr->data->salary)
         //if (myNode->data->seniority < ptr->data->seniority)
				{
				//printf("left\n");    // sanity check
				isLeft = 1;         	// set left flag
				ptr = ptr->left;
				}
			else
				{
            //printf("right\n");   // sanity check
				isLeft = 0;  			// set right flag
				ptr = ptr->right;
				}
			}
		// fill space at leaf with new node
		if (isLeft)
			prev->left = myNode;    // set new node as left leaf
		else
			prev->right = myNode;   // set new node as right leaf
		}
	return root;
	}

void printInorder(struct node *node)
	{
	if (node == NULL)   return;            // the tree is empty

		// First recurse on left child
	printInorder(node->left);

		// Print the data of node
	printData(node);

		// Then recurse on right child
	printInorder(node->right);
	}

void putInArray(struct node *node)
	{
	static int i=0;

	if (node == NULL)  return;
	putInArray(node->left);
   nodes[i++] = node;
	putInArray(node->right);
	}

// Binary searching requires an indexed list i.e. an array
// In this case it is fed an array of pointers to nodes
// which then point to data.  This is why I put our faithful
// nodes into an array.  The data is still located at the
// same memory location it started at which is the beauty
// of abstracting the data away from the structure holding it.

struct node * binSearch(struct node **nodes, int start, int end, int index)
	{
	if (start > end)    return (NULL);  // not found

	int middle = (start + end) / 2;
		// using age as the index value
	int midValue = nodes[middle]->data->age;

	if (midValue > index)
		{
		//printf("greater than, midValue %d, index %d\n", midValue, index);
		return binSearch(nodes, start, middle-1, index);
		}
	if (midValue < index)
		{
		//printf("less than, midValue %d, index %d\n", midValue, index);
		return binSearch(nodes, middle+1, end, index);
		}
	if (midValue == index)
		{
		//printf("node ptr %p\n", nodes[middle]);
		return nodes[middle];
		}
	}

void writeData(struct node *head)
	{
	FILE *fp;
	struct node *ptr;

	fp = fopen("search.dat", "w+"); // will overwrite any previous search.dat file
	fprintf(fp, "%d", COUNT);  	// save the size of the list
	ptr = head;
	while (ptr != NULL)
		{
		fprintf(fp, "%4d %2d %5ld %2d\n", ptr->data->id, ptr->data->age, ptr->data->salary, ptr->data->seniority);
		ptr = ptr->next;
		}
	fclose(fp);
	}

struct node * addXNode(struct node *head, struct node *node)
	{
	struct node *ptr, *temp;

	//printf("here is node %p\n", node);
   //printf("here is head %p\n", head);
	if (head == NULL)					// empty list case
		{
		head = node;
		//printf("filled head node\n");
		}
	else									// non-empty list case
		{
		ptr = head;
		while (ptr != NULL)    		// find the end of the list
			{
			temp = ptr;       		// remember the one before me
			ptr = ptr->next;
			}
	   temp->next = node;    		// add new node at the end
		}
   //printf("here is head %p\n", head);
	return head;
	}

struct node * readData(void)
	{
	FILE *fp;
   struct data *myData;
   struct node *myNode;
	struct node *head = NULL, *ptr;
	int number;
	int id, age, salary, seniority;

   fp = fopen("search.dat", "r"); 	// open a saved file
	fscanf(fp, "%d", &number);      	// retrieve size of list

	for (int i=0; i<number; i++)
		{
		fscanf(fp, "%4d%2d%5d%2d", &id, &age, &salary, &seniority);

      myData = (struct data *) malloc (sizeof(struct data));
		myData->id = id;
		myData->age = age;
		myData->salary = salary;
		myData->seniority = seniority;

	   myNode = (struct node *) malloc (sizeof(struct node));  // create new node
		myNode->data = myData;     // add data to our new node
		myNode->next = NULL;			// set all the pointers to guard value
	   myNode->left = NULL;
		myNode->right = NULL;

		head = addXNode(head, myNode);
		}
	fclose(fp);
	return head;
	}

int main()
	{
	srand((unsigned) time(NULL)); // randomize by seeding from time
	struct node *head = NULL;   	// start with an empty list
	struct node *root = NULL;   	// start with an empty tree
	struct node *headTwo = NULL;  // start with a second empty list for reading file
	struct node *ptr;					// our handy working pointer

	for (int i=0; i<COUNT; i++)	// create a singly linked list
		{
		head = addNode(head);      // use random data for each field
		}

	ptr = head;
	while(ptr != NULL)          	// walk the list and print it out
		{
      printData(ptr);
		ptr = ptr->next;
		}

	writeData(head);              // save original list of data to search.dat

	ptr = head;
	while (ptr != NULL)        	// walk the list and build a tree from it
		{
      root = treeInsert(root, ptr);
		ptr = ptr->next;
		}

	printf("\n\n");
	printInorder(root);        	// print the tree inorder

	putInArray(root);          	// walk tree and build array

	// search for age of your choice
	int seeker = 0;					// Not a beater nor a chaser
	while (seeker != -1)
		{
		printf("\n\nWhat is your number?? ");
		printf("\n-1 to quit ");
		scanf("%2d", &seeker);
		if (seeker > 69)  continue; // skip to next iteration
											 // age limit in company is 69
	   ptr = binSearch(nodes, 0, COUNT, seeker);  // search for employee aged ?? years

		if (ptr != NULL)
			printData(ptr);
		else
			printf("Index not found");
		}
   printf("\n\n");          		// obligatory white space

	// read the saved data from the disk file and print it out
	// memory addresses will have changed when the new list was
	// formed from the stored data.
	headTwo = readData();    		// read data into a new linked list

	ptr = headTwo;
	while (ptr != NULL)
		{
		printData(ptr);
		ptr = ptr->next;
		}
	}