/* 
queue4.c 
An implementation of a queue ADT using a linked list.

Jessica Cao
December 5, 2008
*/

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

/* Types and constants */

typedef int nat;

typedef struct {
    char * data;
    nat id;
} element_rec;

typedef element_rec * element;

typedef struct q_node {
    element contents;
    struct q_node * next;
} node_rec;

typedef node_rec * node;

typedef struct {
    node back;
    node front;
    nat length;
} queue_rec;

typedef queue_rec * queue;

node make_new_node(element e, node n) {
    node new = malloc(sizeof(node_rec));
    new->contents = e;
    new->next = n;
    return new;
}

/* Primitive operators */

queue bottom() {
    queue new = malloc(sizeof(queue_rec));
    new->front = NULL;
    new->back = NULL;
    new->length = 0;
    return new;
}

nat length(queue q) {
    return q->length;
}

element front(queue q) {
    if (length(q) == 0) {
        printf("Error in front: queue is empty.\n");
        return;
    } else {
        return (q->front)->contents;
    }
}

void push(element e, queue q) {
    node new = make_new_node(e, NULL);
    if (length(q) == 0) {
        q->front = new;
    } else {
        (q->back)->next = new;
    }
    q->back = new;
    q->length = q->length + 1;
}

void pop (queue q) {
    nat len = length(q);
    if (len == 0) {
        printf("Error in pop: queue is empty.\n");
    } else if (len == 1) {
        q->back = NULL;
        q->front = NULL;
        q->length = 0;
    } else {
        node front = q->front;
        q->front = (q->front)->next;
        q->length = len - 1;
        free(front);
    }
}

/* Derived operators */

void print(queue q) {
    nat len = q->length;
    if (len == 0) {
        printf("Queue is empty.\n");
        return;
    }

    node n = q->front;
    printf("Queue contents: [{%s, %d}", (n->contents)->data, (n->contents)->id);
    n = n->next;
    while (n!=NULL) {
        printf(", {%s, %d}", (n->contents)->data, (n->contents)->id);
        n = n->next;
    }
    printf("].\n");
    free(n);
}