//=========================================================================
#define PROGRAMMER "SOLUTIONS, NoFrills"
#define PROG_CODE  "soln"
#define COURSE     "ECE-1021"
#define YEAR       (2003)
#define TERM       "Fall"
#define SECTION    (0)
#define ASSIGNMENT "DEMO"
#define REVISION   (0)
#define TITLE      "Linked List"
#define SUBTITLE   "Demo Program"
#define EMAIL      "wbahn@eas.uccs.edu"
#define FILENAME   "lnklst_2.c"
//=========================================================================

// NOTE: This is the same program as linklist.c except that it hides the
// details of main() into user subfunctions. The thing to notice is that
// the ONLY information that has to be passed to ANY of these functions
// from main() is a pointer to the first link in the list. The only other
// difference is that the NavigateList() function now removes the 'X' at
// the current point when it finishes.

// PROBLEM:
//
// This program demonstrates the features of linked lists.
//
// SOLUTION:
//
// We will create a flexible structure that allows us to link items
// together and manipulate them.
//
// The basic idea is that you have a chain of links. Each link connects
// to up to two other links. In addition, you can hang objects from
// each link.
//
// For out demo program, we will create a list of links that have
// structures attached to them that represent randomly picked points
// on the screen. We will then traverse the list and plot the points and
// then we will use the '+' and '-' keys to navigate back and forth
// through the points. After we are done with that, we will sort the
// list so that the points go from left to right across the screen when
// they are traversed in order a second time.

//== INCLUDE FILES ========================================================
#include <stdio.h>    // printf()
#include "lnklst_2.h" // LINK and PT structures and functions

//== MACRO DEFINITIONS ====================================================

//== TOP LEVEL SUPPORT FUNCTION PROTOTYPES ================================
void PrintHeader(void);
LINK *CreateList(void);
void DrawList(LINK *TheList);
void NavigateList(LINK *TheList);
void SortList(LINK *TheList);

//== MAIN FUNCTION ========================================================
int main(void)
{
	LINK *TheList;

	PrintHeader();
	printf("\n"); // Print a blank line

	TheList = CreateList();
	DrawList(TheList);
	NavigateList(TheList);
	SortList(TheList);
	NavigateList(TheList);

	return(0);
}
//== SUPPORT FUNCTIONS ====================================================
void PrintHeader(void)
{
	printf("========================================"
			 "=======================================\n");
	printf("Course....... %s-%i (%s %i)\n", COURSE, SECTION, TERM, YEAR);
	printf("Programmer... %s (%s)\n", PROGRAMMER, PROG_CODE);
	printf("Assignment... %s (Rev %i) (Source Code in %s)\n",
		ASSIGNMENT, REVISION, FILENAME);
	printf("Description.. %s\n", TITLE);
	printf("              %s\n", SUBTITLE);
	printf("========================================"
			 "=======================================\n");

	return;
}

//== LOWER LEVEL FUNCTION PROTOTYPES ======================================
PT *RandomPT(double xmin, double xmax, double ymin, double ymax);
double rand_fp(double xmin, double xmax);
double randnorm(void);
void Draw(PT *pt, char symbol);
char CatchKey(void);

//== TOP LEVEL SUPPORT FUNCTION DEFINITIONS ===============================

LINK *CreateList(void)
{
	int i;
	LINK *TheList;

	TheList = NewLINK(NewPT(20.0, 20.0));

	// Generate a linked list of random screen points
	for(i = 0; i < 100; i++)
		InsertLINK(NULL, AFTER, GetLastLINK(TheList), RandomPT(2.0,79.0,10.0,24.0));

	return(TheList);
}

void DrawList(LINK *TheList)
{
	LINK *ThisLink;

	// Draw the points on the screen
	ThisLink = GetFirstLINK(TheList);
	while(IsaPT(GetLINKItem(ThisLink)))
	{
		Draw(GetLINKItem(ThisLink), '*');
		ThisLink = GetNextLINK(ThisLink);
	}

	return;
}

void NavigateList(LINK *TheList)
{
	LINK *ThisLink;
	int exitflag;

	// Navigate through the points in the order they are in the list
	ThisLink = GetFirstLINK(TheList);
	Draw(GetLINKItem(ThisLink), 'X');
	exitflag = FALSE;
	while(!exitflag)
	{
		switch(CatchKey())
		{
			case '-':
				Draw(GetLINKItem(ThisLink), '*');
				if(!IsFirstLINK(ThisLink))
					ThisLink = GetPrevLINK(ThisLink);
				Draw(GetLINKItem(ThisLink), 'X');
				break;
			case '+':
				Draw(GetLINKItem(ThisLink), '*');
				if(!IsLastLINK(ThisLink))
					ThisLink = GetNextLINK(ThisLink);
				Draw(GetLINKItem(ThisLink), 'X');
				break;
			case 'x':
			case 'X':
				Draw(GetLINKItem(ThisLink), '*');
				exitflag = TRUE;
				break;
		}
	}

	return;
}

void SortList(LINK *TheList)
{
	LINK *ThisLink;
	LINK *StartLink, *SmallestLink;  // Used to sort links
	int i, j;

	// Sort the list
	StartLink = GetFirstLINK(TheList);
	i = 0;
	while(!IsLastLINK(StartLink))
	{
		gotoxy(10,25); printf("StartLink #%3i", i);
		SmallestLink = ThisLink = StartLink;
		j = i;
		while(!IsLastLINK(ThisLink))
		{
			gotoxy(50,25); printf("Link #%3i", j);
			ThisLink = GetNextLINK(ThisLink);
			if(IsLessThan(GetLINKItem(ThisLink), GetLINKItem(SmallestLink)))
				SmallestLink = ThisLink;
		}
		i++;
		SwapLINKs(StartLink, SmallestLink);
		StartLink = GetNextLINK(StartLink);
	}

	return;
}

//== LOWER LEVEL SUPPORT FUNCTION DEFINITIONS =============================
PT *RandomPT(double xmin, double xmax, double ymin, double ymax)
{
	return(NewPT(rand_fp(xmin, xmax), rand_fp(ymin, ymax)));
}

double rand_fp(double xmin, double xmax)
{
	return(xmin + randnorm()*(xmax-xmin));
}

double randnorm(void)
{
	return( (double)rand()/(double)RAND_MAX );
}

void Draw(PT *pt, char symbol)
{
	gotoxy((int) GetPTx(pt), (int) GetPTy(pt));
	putch(symbol);
	return;
}

char CatchKey(void)
{
	while(kbhit())
		getch();       // Clear out buffer
	while(!kbhit());  // Stall until key hit
	return(getch());
}