//=========================================================================
#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   "linklist.c"
//=========================================================================

// 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 <conio.h> // gotoxy(), kbhit(), getch()
#include <malloc.h> // malloc()
#include <stdlib.h> // rand(), RAND_MAX

//== MACRO DEFINITIONS ====================================================
#define FALSE (0)
#define TRUE  (!FALSE)

//== STRUCTURE DEFINITIONS ================================================
typedef struct LINK LINK;

struct LINK
{
	LINK *prev;
	LINK *next;
	void *item;
};

#define NottaLINK(link) (NULL == (link))
#define IsaLINK(link)   (NULL != (link))

//-------------------------------------------------------------------------
// LINK functions - primitives
LINK *CreateLINK(void);
int   DestroyLINK(LINK *link);
LINK *SetNextLINK(LINK *link, LINK *nextlink);
LINK *SetPrevLINK(LINK *link, LINK *prevlink);
void *SetLINKItem(LINK *link, void *item);
void *GetLINKItem(LINK *link);
LINK *GetNextLINK(LINK *link);
LINK *GetPrevLINK(LINK *link);
//-------------------------------------------------------------------------
// LINK functions - manipulatives
#define BEFORE (0)
#define AFTER  (1)

LINK *NewLINK(void *item);
int   IsFirstLINK(LINK *link);
int   IsLastLINK(LINK *link);
LINK *GetFirstLINK(LINK *link);
LINK *GetLastLINK(LINK *link);
LINK *ConnectLINKs(LINK *first, LINK *second);
LINK *InsertLINK(LINK *looselink, int where, LINK *link, void *item);
int   SwapLINKs(LINK *first, LINK *second);
//-------------------------------------------------------------------------
typedef struct PT PT;

struct PT
{
	double x;
	double y;
};

#define NottaPT(pt) (NULL == (pt))
#define IsaPT(pt)   (NULL != (pt))

//-------------------------------------------------------------------------
// PT functions - primitives
PT *CreatePT(void);
int DestroyPT(PT *pt);
double SetPTx(PT *pt, double x);
double SetPTy(PT *pt, double y);
double GetPTx(PT *pt);
double GetPTy(PT *pt);
//-------------------------------------------------------------------------
PT *NewPT(double x, double y);
int IsLessThan(PT *a, PT *b);


//== TOP LEVEL SUPPORT FUNCTION PROTOTYPES ================================
void PrintHeader(void);
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);

//== MAIN FUNCTION ========================================================
int main(void)
{
	int i,j;
	int exitflag;

	LINK *TheList;
	LINK *ThisLink;
	LINK *StartLink, *SmallestLink;  // Used to sort links

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

	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));

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

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

	// 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((PT *)GetLINKItem(ThisLink),
			              (PT *)GetLINKItem(SmallestLink)))
				SmallestLink = ThisLink;
		}
		i++;
		SwapLINKs(StartLink, SmallestLink);
		StartLink = GetNextLINK(StartLink);
	}

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

	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 ======================================
//== TOP 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());
}

//== LOWER LEVEL SUPPORT FUNCTION DEFINITIONS =============================
//== LINK functions =======================================================

//-------------------------------------------------------------------------
// LINK functions - primitives
//-------------------------------------------------------------------------
#define NottaLINK(link) (NULL == (link))

LINK *CreateLINK(void)
{
	LINK *newLINK;
	newLINK = (LINK *) malloc(sizeof(LINK));
	return(newLINK);
}

int DestroyLINK(LINK *link)
{
	if(NottaLINK(link))
		return(FALSE);

	if(NULL == GetLINKItem(link))   // Link still has item attached
		return(FALSE);

	free(link);
	return(TRUE);
}

LINK *SetNextLINK(LINK *link, LINK *nextlink)
{
	link->next = nextlink;
	return(GetNextLINK(link));
}

LINK *SetPrevLINK(LINK *link, LINK *prevlink)
{
	link->prev = prevlink;
	return(GetPrevLINK(link));
}

void *SetLINKItem(LINK *link, void *item)
{
	if(NottaLINK(link))
		return(NULL);

	link->item = item;
	return(GetLINKItem(link));
}

LINK *GetNextLINK(LINK *link)
{
	if(NottaLINK(link))
		return(NULL);

	return(link->next);
}

LINK *GetPrevLINK(LINK *link)
{
	if(NottaLINK(link))
		return(NULL);

	return(link->prev);
}

void *GetLINKItem(LINK *link)
{
	if(NottaLINK(link))
		return(NULL);

	return(link->item);
}

//-------------------------------------------------------------------------
// LINK functions - manipulatives
//-------------------------------------------------------------------------

LINK *NewLINK(void *item)
{
	LINK *newLINK;
	newLINK = CreateLINK();
	SetLINKItem(newLINK, item);
	SetNextLINK(newLINK, NULL);
	SetPrevLINK(newLINK, NULL);
	return(newLINK);
}

int IsFirstLINK(LINK *link)
{
	if(NottaLINK(link))
		return(FALSE);

	if(NottaLINK(GetPrevLINK(link)))
		return(TRUE);

	return(FALSE);
}

int IsLastLINK(LINK *link)
{
	if(NottaLINK(link))
		return(FALSE);

	if(NottaLINK(GetNextLINK(link)))
		return(TRUE);

	return(FALSE);
}

LINK *GetFirstLINK(LINK *link)
{
	if(NottaLINK(link))
		return(NULL);

	while(!IsFirstLINK(link))
		link = GetPrevLINK(link);

	return(link);
}

LINK *GetLastLINK(LINK *link)
{
	if(NottaLINK(link))
		return(NULL);

	while(!IsLastLINK(link))
		link = GetNextLINK(link);

	return(link);
}

LINK *ConnectLINKs(LINK *first, LINK *second)
{
	if( NottaLINK(first) || NottaLINK(second) )
		return( NULL );

	SetNextLINK(first, second);
	SetPrevLINK(second, first);

	return( first );
}

LINK *InsertLINK(LINK *looselink, int where, LINK *link, void *item)
{
	if(NottaLINK(link))
		return( looselink );

	if(NottaLINK(looselink))
		return( InsertLINK(NewLINK(item), where, link, NULL ));

	switch(where)
	{
		case BEFORE:
			ConnectLINKs(GetPrevLINK(link), looselink);
			ConnectLINKs(looselink, link);
			break;
		case AFTER:
			ConnectLINKs(looselink, GetNextLINK(link));
			ConnectLINKs(link, looselink);
			break;
	}

	return(looselink);
}

int   SwapLINKs(LINK *first, LINK *second)
{
	void *temp;

	if( NottaLINK(first) || NottaLINK(second) )
		return(FALSE);

	temp = GetLINKItem(first);
	SetLINKItem(first, GetLINKItem(second));
	SetLINKItem(second, temp);

	return(TRUE);
}

//-------------------------------------------------------------------------
// PT functions - primitives
//-------------------------------------------------------------------------
PT *CreatePT(void)
{
	PT *newPT;
	newPT = (PT *) malloc(sizeof(PT));
	SetPTx(newPT, 0.0);
	SetPTy(newPT, 0.0);
	return(newPT);
}

int DestroyPT(PT *pt)
{
	if(NULL == pt)                  // pt doesn't exist
		return(FALSE);

	free(pt);
	return(TRUE);
}

double SetPTx(PT *pt, double x)
{
	if(NULL == pt)
		return(0.0);

	pt->x = x;

	return(GetPTx(pt));
}

double SetPTy(PT *pt, double y)
{
	if(NULL == pt)
		return(0.0);

	pt->y = y;

	return(GetPTy(pt));
}

double GetPTx(PT *pt)
{
	if(NULL == pt)
		return(0.0);

	return(pt->x);
}

double GetPTy(PT *pt)
{
	if(NULL == pt)
		return(0.0);

	return(pt->y);
}
//-------------------------------------------------------------------------

//-------------------------------------------------------------------------
// PT functions - manipulatives
//-------------------------------------------------------------------------
PT *NewPT(double x, double y)
{
	PT *newPT;
	newPT = CreatePT();
	SetPTx(newPT, x);
	SetPTy(newPT, y);
	return(newPT);
}

int IsLessThan(PT *a, PT *b)
{
	// Primary sort on x-value
	if(GetPTx(a) < GetPTx(b))
		return(TRUE);

	if(GetPTx(a) > GetPTx(b))
		return(FALSE);

	// x-values equal - Secondary sort on y-value
	if(GetPTy(a) < GetPTy(b))
		return(TRUE);

	return(FALSE);
}