/*
Let the user type in positive numbers, not necessarily unique.  Store them in
ascending order in a dynamically allocated doubly linked list.  The smallest
number will be at the head of the list, and the biggest number at the tail.
Then print the list from head to tail and from tail to head.

Each number is stored in a structure called a node_t.  Each node is malloc'ed
separately.  head is the first node, tail is always the last.

The next field of each node holds the address of the next node, or is NULL if
there is no next node.  The prev field of each node holds the address of the
previous node, or is NULL if there is no previous node.  The 0 that the user
types in to terminate the input is not stored in the list.
*/

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>	/* for INT_MAX */

typedef struct node_t {
	int n;                 /* the payload */
	struct node_t *prev;   /* the address of the previous node */
	struct node_t *next;   /* the address of the next node */
} node_t;

int main()
{
	node_t head = {      0, NULL, NULL};
	node_t tail = {INT_MAX, NULL, NULL};

	node_t *p, *q;   /* for looping through the list */
	int n;           /* each number that the user types in */

	head.next = &tail;
	tail.prev = &head;

	printf(
		"Please type positive numbers less than %d.\n"
		"Press RETURN after each number.\n"
		"Type a negative number to delete the corresponding positive number.\n"
		"Type 0 when done.\n", INT_MAX);

	for (;;) {
		scanf("%d", &n);
		if (n == 0) {
			break;
		}

		if (n > 0) {	/* Insert a new node. */
			node_t *new = malloc(sizeof(node_t));
			if (new == NULL) {
				fprintf(stderr, "Can't allocate %lu bytes.\n", sizeof(node_t));
				return EXIT_FAILURE;
			}
			new->n = n;

			/*
			Search the list to find the insertion point.
			The insertion point will always be between head and tail. 
			*/
			for (p = &head; (q = p->next) != &tail; p = q) {
				if (q->n >= n) {
					break;
				}
			}

			/* Insert the new node between the ones that p and q point to. */
			printf("Found the insertion point.\n");
			new->next = q;
			new->prev = p;
			p->next = new;
			q->prev = new;
		}

		else {	/* Delete an existing node. */
			n = -n;

			/* Let p point to the node to be deleted. */
			for (p = head.next; p != &tail; p = p->next) {
				if (p->n == n) {
					goto found;
				}
			}
			fprintf(stderr, "The number %d is not on the list.\n", n);
			continue;

			found:;
			p->prev->next = p->next;
			p->next->prev = p->prev;
			free(p);
		}
	}

	printf("Print the list from head to tail:\n");
	for (p = head.next; p != &tail; p = p->next) {
		printf("%d\n", p->n);
	}

	printf("\nPrint the list from tail to head:\n");
	for (p = tail.prev; p != &head; p = p->prev) {
		printf("%d\n", p->n);
	}

	return EXIT_SUCCESS;
}