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

#define MAX 16

typedef struct node {
	char data[128];
	int next;
} node;

char *os[] = { "AIX", "FreeBSD", "HP-UX", "Linux", "Solaris", "Windows"};

int Free, Head;
node table[MAX];

Init()
{
	int i;

	Free = 0;
	Head = -1;

	for(i = 0; i < MAX - 1; i++) {
		table[i].next = i + 1;
	}
	table[MAX - 1].next = -1;
}

Insert()
{
	char buf[128];
	int i, n, f;

	if( Free == -1 ) {
		printf("There is no sufficient space!\n");
		return;
	}

	for( i = 0; i < sizeof(os) / sizeof(char *); i++) {
		if ( Find( os[i] ) == -1 ) {
			printf("%d: %s\n", i, os[i]);
		}
	}
	printf("\n");

	printf("Choose one to Insert: ");
	fgets(buf, 127, stdin);
	n = atoi(buf);

	if(n < 0 || n >= sizeof(os) / sizeof(char *)) {
		printf("Out of boundary!\n");
		return;
	}

	if( Find(os[n]) != -1 ) {
		printf("The node is already in the list!\n");
		return;
	}

	f = -1;
	if( Head != -1 ) {
		Display();

		printf("Which node to follow: ");
		fgets(buf, 127, stdin);
		f = atoi(buf);

		if( f != -1 ) {
			if( f < 0 || f >= MAX ) {
				printf("Out of boundary!\n");
				return;
			}
			if( isFree(f) ) {
				printf("The node is not been used!\n");
				return;
			}
		}
	}

	if( f == -1 ) {
		i = table[Free].next;
		strcpy( table[Free].data, os[n] );
		table[Free].next = Head;
		Head = Free;
		Free = i;
	} else {
		i = table[Free].next;
		strcpy( table[Free].data, os[n] );
		table[Free].next = table[f].next;
		table[f].next = Free;
		Free = i;
	}

	printf("* The node has been insert!\n");

}

Delete()
{
	int i, d;
	char buf[128];

	if( Head == -1 ) {
		printf("There is no node to delete!\n");
		return;
	}

	Display();
	printf("Which node to delete: ");
	fgets(buf, 127, stdin);
	d = atoi(buf);

	if( d < 0 || d >= MAX ) {
		printf("Out of boundary!\n");
		return;
	}

	if( isFree(d) ) {
		printf("The node is not been used!\n");
		return;
	}

	if ( Head == d ) {
		Head = table[d].next;
		table[d].next = Free;
		strcpy(table[d].data, "");
		Free = d;
	} else {
		i = Head;
		while( i != -1 ) {
			if( table[i].next == d ) {
				table[i].next = table[d].next;
				table[d].next = Free;
				strcpy(table[d].data, "");
				Free = d;
			}
			i = table[i].next;
		}
	}

	printf("* The node has been deleted!\n");
}

Display()
{
	int i;

	printf("--- List ---\n");
	
	if( Head == -1 ) {
		printf("The list is empty!\n\n");
		return;
	}

	printf("-1: Head\n");
	i = Head;
	while( i != -1 ) {
		printf("%d: %s\n", i, table[i].data);
		i = table[i].next;
	}

	printf("\n");
}

DisplayDetail()
{
	int i;

	printf("--- List detail ---\n");
	printf("Head: %d\nFree: %d\n", Head, Free);

	for( i = 0; i < MAX; i++ ) {
		printf("%d\t%s\t%d\n", i, table[i].data, table[i].next);
	}
	printf("\n");
}

int Find(char *s) {
	int i;

	i = Head;
	while( i != -1 ) {
		if( !strcmp( table[i].data, s ) ) {
			return i;
		}
		i = table[i].next;
	}

	return -1;
}

int isFree( int f )
{
	int i;

	i = Free;
	while( i != -1 ) {
		if ( i == f ) {
			return 1;
		}
		i = table[i].next;
	}

	return 0;
}

main()
{
	char buf[128];
	int func;

	Init();
	while(1) {
		printf("Please choose a function (1: Insert 2: Delete 3: Display [4]: Quit): ");
		fgets(buf, 127, stdin);
		func = atoi(buf);

		switch(func) {
			case 1:
				Insert();
				break;
			case 2:
				Delete();
				break;
			case 3:
				Display();
				DisplayDetail();
				break;
			default:
				exit(0);
		};
	}
}