/* Program to track the assembly of a train from loose boxcars.
   Cars are added or removed at either end of the train with the
   AH, AT (add head or tail), and RH, RT (remove head or tail) commands.
   AH & AT are followed by the serial number of the boxcar being added.
   The D (departure) command causes the program to list the numbers of
   the boxcars and then quit.
*/

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

typedef struct train train;     /* This is an 'incomplete' type, because
                                   we have not yet said what a struct train
                                   is.  We are allowed to declare pointers
                                   to such a type but not variables of the
                                   type itself. */

train *newtrain(void);          /* Creates an 'empty' train. */
void addboxcar(train *t, char end);
void dropboxcar(train *t, char end);
void list_train(train *t);

main () {
    char cmd, end;              /* cmd: A, R or D; end: H or T. */
    train * atrain;

    atrain = newtrain();        /* Create a new, empty train. */

    printf(
        "Enter train assembly commands:\n"
        "    AH nnn           Add boxcar nnn to head of train.\n"
        "    AT nnn           Add boxcar nnn to tail of train.\n"
        "    RH               Remove boxcar from head of train.\n"
        "    RT               Remove boxcar from tail of train.\n"
        "    D                Departure; boxcars in train are listed.\n\n"
    );

    /* Process assembly commands: */
    while (scanf(" %c", &cmd), cmd != 'D') {
        scanf(" %c", &end);     /* which end to process */
        switch (cmd) {
        case 'A':
            addboxcar(atrain, end);  /* Add a car to the specified end. */
            break;
        case 'R':
            dropboxcar(atrain, end); /* Drop a car from the specified end. */
            break;
        default:
            printf("Invalid command\n");
            exit(1);
        }
    }

    /* List the boxcars in the departing train: */
    list_train(atrain);
    exit(0);
}

/******************************
   Now to implement the train as a doubly-linked list.  We need pointers
   to the head and tail of the list, so type train can simply be a
   structure of two pointers.  The nodes in the list must have pointers
   to the adjacent nodes, and an int for the boxcar serial number.
   You should trace the steps in the following functions by hand, drawing
   pictures with arrows for pointers, etc., as in the text.  Make sure you
   understand exactly what each step in the logic does.
*/

typedef struct train_node {
    struct train_node *next, *prev;
    int number;
} node;

struct train {
    node *first, *last;
};


train *newtrain(void) {
    /* Creates an 'empty' train, or exits on failure. */
    train *t;
    t = malloc(sizeof(train));
    if (t == NULL) {
        printf("No memory for train.\n");
        exit(1);
    }
    t->first = t->last = NULL;  /* No boxcars */
    return t;
}


void addboxcar(train *t, char end) {
    /* Inputs the serial no., adds the boxcar to the specified end, or
       exits on failure.
    */
    node *nod;

    /* Get space for the boxcar node, and check success. */
    nod = malloc(sizeof(node));
    if (nod == NULL) {
        printf("No memory for boxcar.\n");
        exit(1);
    }

    /* Load the boxcar number: */
    scanf("%d", &nod->number);

    /* Now connect to the appropriate end.  Four cases: which end, and
       whether the train already has any boxcars.
    */
    if (t->first == NULL) {
        /* Train empty; this is the first boxcar; which end doesn't matter. */
        nod->next = nod->prev = NULL;     /* no boxcars either side */
        t->first = t->last = nod;         /* This is both the first and last
                                             boxcar. */
    } else {
        /* Train already has boxcars: add to appropriate end. */
        if (end == 'H') {
            /* Head: this becomes new head node. */
            nod->next = t->first;     /* Car that was first is now second. */
            t->first->prev = nod;     /* This car precedes that car. */
            nod->prev = NULL;         /* No cars before this one. */
            t->first = nod;           /* This car is first. */
        } else {
            /* Tail: this becomes last node; logic is inverse of the above. */
            nod->prev = t->last;
            t->last->next = nod;
            nod->next = NULL;
            t->last = nod;
        }
    }
}


void dropboxcar(train *t, char end) {
    /* Drops a boxcar from the train, and prints its number. */
    node *nod;

    /* Drop a car from the train: */
    if (t->first == NULL) {             /* Train already empty? */
        printf("No boxcars to remove.\n");
        return;
    } else if (t->first == t->last) {   /* Train has just one boxcar? */
        nod = t->first;                 /* Remember the boxcar node */
        t->first = t->last = NULL;      /* Make the train empty. */
    } else if (end == 'H') {            /* head? */
        nod = t->first;
        t->first = nod->next;           /* 2nd car becomes first */
        t->first->prev = NULL;          /* no preceding car now */
    } else {                            /* tail */
        nod = t->last;
        t->last = nod->prev;           /* 2nd-last car becomes last */
        t->last->next = NULL;          /* no following car now */
    }

    printf("Dropped boxcar %d from train.\n", nod->number);
    free(nod);
}


void list_train(train *t) {
    node *nod;
    printf("\nBoxcars in the train are:\n");
    for (nod = t->first; nod != NULL; nod = nod->next) {
        printf("%d ", nod->number);
    }
}