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

#include "llist.h"

/* Prints the keys of a linked list in order  */
void print_listp(llist *L)
{
    elist *x;
    x = L->head;
    while (x != NULL && x-> next != NULL) x = x -> next;
    printf("|-");
    while (x != NULL) {
	printf("%d-", x->key);
	x = x->prev;
    }
    printf("\n");
}

void print_list(llist L)
{
    elist *x;
    x = L.head;
    while (x != NULL && x-> next != NULL) x = x -> next;
    printf("|-");
    while (x != NULL) {
	printf("%d-", x->key);
	x = x->prev;
    }
    printf("\n");
}

void push(llist *S, elist *x)
{
    if (S->head != NULL) S->head->prev = x;
    x->next = S->head;
    S->head = x;
} 

int stack_empty(llist *S)
{
    return (S->head == NULL);
} 

elist *pop(llist *S) 
{
    elist *x;
    if (!stack_empty(S)) {
	x = S->head;
	if (x->next != NULL) x->next->prev = (elist*) NULL;
	S->head = x->next;
	return x;
    }
    else { 
	printf("Error: underflow");
	exit(1);
    }
}

/* elist make_elist(int key)   /\* WILL NOT WORK *\/ */
/* { */
/*     elist e; */
/*     e.key = key; */
/*     return e; */
/* } */
elist *make_elist(int key)
{
    elist *e = (elist*) malloc(sizeof(elist));
    e->key = key;
    return e;
}

void shift(llist *S, int from, int to)
{
    int i;
    printf("\nPUSH(S%d, POP(S%d))\n", to, from);
    push(S + to, pop(S + from));
    for (i = 0; i < 3; i++) {printf("S%d ", i); print_list(S[i]);}
}

int main()
{
    llist S[3];
    int i, n;
    elist *e;
    for (i = 0; i < 3; i++) S[i].head = (elist *) NULL;
    for (i = 5; i >= 1; i--) {
	e = make_elist(i);
    	push(&S[0], e);
    }
    /* printf("%ld\n", (long int) S[0].head); */
    /* printf("%ld\n", (long int) S[0].head->next); */
    for (i = 0; i < 3; i++) {printf("S%d ", i); print_list(S[i]);}
    shift(S, 0, 1);
    shift(S, 0, 2);
    shift(S, 1, 2);
    shift(S, 0, 1);
    shift(S, 2, 0);
    shift(S, 2, 1);
    shift(S, 0, 1);
    shift(S, 0, 2);
    shift(S, 1, 2);
    shift(S, 1, 0);
    shift(S, 2, 0);
    shift(S, 1, 2);
    shift(S, 0, 1);
    shift(S, 0, 2);
    shift(S, 1, 2);
    shift(S, 0, 1);
    shift(S, 2, 0);
    shift(S, 2, 1);
    shift(S, 0, 1);
    shift(S, 2, 0);
    shift(S, 1, 2);
    shift(S, 1, 0);
    shift(S, 2, 0);
    shift(S, 2, 1);
    shift(S, 0, 1);
    shift(S, 0, 2);
    shift(S, 1, 2);
    shift(S, 0, 1);
    shift(S, 2, 0);
    shift(S, 2, 1);
    shift(S, 0, 1);
}

/* int main(int argc, char **argv)  */
/* { */
/*     int i, n; */
/*     elist *e; */
/*     llist *S; */
/*     if (argc != 2) {  */
/* 	printf("\nUsage: %s <n>\n\n", argv[0]); */
/* 	return 1; */
/*     } */
/*     n = atoi(argv[1]); */
/*     S->head = (elist *) NULL; */
/*     for (i = n; i >= 1; i--) { */
/*     	e = make_elist(i); */
/*     	push(S, e); */
/*     } */
/*     print_listp(S); */
/* } */