/*
 * Sample program to process list structure
 *
 * Programmed by tnomura@mnet.ne.jp	Jan. 9, 2004
 *
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct listtyp{
	char *name;
	struct listtyp *next;
} list;

list *srch_node(char *name, list *top, list **previous);
list *make_node(char *name);
int add_node(char *name, list *top);
int insert_node(char *src_name, char *dest_name, list *top);
int remove_node(char *name, list *top);
int move_node(char *src_name, char *dest_name, list *top);
void list_print(list *top);

/* search for the node by name */

list *srch_node(char *name, list *top, list **previous)
{
	list *current, *pre_cur;

	pre_cur = top;
	current = top->next;

	while (current != NULL && strcmp(current->name, name) != 0) {
		pre_cur = current;
		current = current->next;
	}
	if (current == NULL) {
		*previous = NULL;
		return NULL;
	} else {
		*previous = pre_cur;
		return current;
	}
}

/* make a new node */

list *make_node(char *name)
{
	list *ptr;

	ptr = (list *)malloc(sizeof(list));
	if (ptr == NULL)
		return NULL;
	ptr->name = (char *)malloc(strlen(name)+1);
	strcpy(ptr->name, name);
	ptr->next = (list *)NULL;
	return ptr;
}

/* make a new node and add it at the end of the list */

int add_node(char *name, list *top)
{
	list *ptr, *cursor;

	ptr = make_node(name);
	if (ptr == NULL)
		return 0;
	cursor = top;
	while(cursor->next != NULL)
		cursor = cursor->next;
	cursor->next = ptr;
	return 1;
}

/* make a new node and insert it before "dest_name" node */

int insert_node(char *src_name, char *dest_name, list *top)
{
	list *ptr, *cursor, *pre_cursor;

	ptr = make_node(src_name);
	if (ptr == NULL)
		return 0;
	cursor = srch_node(dest_name, top, &pre_cursor);
	if (cursor == NULL) {
		free(ptr);
		return 0;
	} else {
		pre_cursor->next = ptr;
		ptr->next = cursor;
		return 1;
	}
}

/* remove the "name" node */

int remove_node(char *name, list *top)
{
	list *cursor, *pre_cursor;

	cursor = srch_node(name, top, &pre_cursor);
	if (cursor == NULL)
		return 0;
	else {
		pre_cursor->next = cursor->next;
		free( cursor );
	}
}

/* move "src_name" node before "dest_name" node */

int move_node(char *src_name, char *dest_name, list *top)
{
	list *src, *pre_src;
	list *dest, *pre_dest;

	src = srch_node(src_name, top, &pre_src);
	dest = srch_node(dest_name, top, &pre_dest);

	if ((src == NULL) || (dest == NULL))
		return 0;
	else {
		pre_src->next = src->next;
		pre_dest->next = src;
		src->next = dest;
		return 1;
	}
}

/* list all node names except (head) node */

void list_print(list *top)
{
	list *cursor;

	cursor = top->next;
	while(cursor != NULL) {
		printf("%s ", cursor->name);
		cursor = cursor->next;
	}
	printf("\n");
}

/*
 * main program
 */

main()
{
	list *top = NULL;
	list *ptr;


	/* Making the (head) node which is located at the top of the list. 
	It is not displayed or processed for convenience of the list 
	processing, e.g. add a new element at the top of the 'visible' list
	elements. 'top' is the address of the (head) node. It must not be 
	changed throughout the main program. */

	top = make_node("(head)");

	add_node("apple", top);			/* make original list */
	add_node("orange", top);
	add_node("banana", top);
	add_node("grape", top);
	printf("original list: \n\t");
	list_print(top);

	remove_node("banana", top);		/* remove an element */
	printf("remove \"banana\": \n\t");
	list_print(top);

	move_node("grape", "apple", top);	/* move an element */
	printf("move \"grape\" before \"apple\": \n\t");
	list_print(top);

	insert_node("plum", "orange", top);	/* insert an element */
	printf("insert \"plum\" before \"orange\": \n\t");
	list_print(top);

	exit(0);
}