/***********************************************************************
* linkedlist.cpp
*
* A simple inplementation of an expandable queue, based on a linked list
*
* Written by Paul Bonamy - 23 May 2010
* Rewritten in pure C - 20 July 2010
************************************************************************/

#include <stdlib.h>
#include "equeue.h"

/***********************************************************************
 * void equeue_init(EQUEUE *queue)
 *
 * Serves the same purpose as a class constructor, initalizing
 * the head and tail pointers to known values.
 *
 * queue -> pointer to an EQUEUE struct
 * no return
 ***********************************************************************/
void equeue_init(EQUEUE *queue) {    
    queue->head = 0; // set head to 0 so we can detect empty queues
    queue->tail = 0; // ditto
    return;
}

/***********************************************************************
 * void equeue_cleanup(EQUEUE *queue)
 *
 * Serves the same purpose as a class destructor.
 * Delete all nodes in the queue and return
 *
 * queue -> pointer to an EQUEUE struct
 * no return
 ***********************************************************************/
void equeue_cleanup(EQUEUE *queue) {
    equeue_empty(queue); // we could code a delete here, instead
    return;
}

/***********************************************************************
 * int equeue_enqueue(EQUEUE *queue, int v)
 *
 * Enqueue a given value by inserting it at the head of the list
 *
 * queue -> pointer to an EQUEUE struct
 * v -> value to add to list
 * returns 1 for successful dequeue, 0 otherwise
 ***********************************************************************/
int equeue_enqueue(EQUEUE *queue, int v) {
    // set up the new node, assign it the correct value, place at head
    NODE * newbie = (NODE *)malloc(sizeof(NODE));
    if(!newbie) { return 0; }
    newbie->value = v;
    newbie->next = queue->head;
    newbie->prev = 0;
    queue->head = newbie;
    
    if (queue->tail == 0) {
        // the queue is empty, so we have to set the tail pointer, too
        queue->tail = newbie;
    }
    else {
        // queue is non-empty, so old head needs to know about new head
        queue->head->next->prev = queue->head;
    }
    
    return 1;
}

/***********************************************************************
 * int equeue_dequeue(EQUEUE *queue, int &v)
 *
 * Dequeue one value from the queue, and return it to the user.
 * Also returns a status values so we know if dequeue succeeded.
 *
 * queue -> pointer to an EQUEUE struct
 * v -> reference to variable to receive dequeued value
 * returns 1 for successful dequeue, 0 otherwise
 ***********************************************************************/
int equeue_dequeue(EQUEUE *queue, int *v) {
    NODE * temp; // temporary handle for last node
    
    if(queue->tail == 0) {
        // queue is empty, return suitable status
        return 0;
    }
    
    *v = queue->tail->value;    // get ready to return value
    temp = queue->tail;    // get a pointer to the last element
    
    if(queue->tail == queue->head) {
        // equeue had one entry and is now empty
        queue->head = 0;
    }
    else {
        // equeue will not be emptied, so cope with loss of end
        queue->tail->prev->next = 0;
    }
    queue->tail = queue->tail->prev;
    
    free(temp);    // free memory associated with the value
    
    return 1;
}

/***********************************************************************
 * void equeue_empty(EQUEUE *queue)
 *
 * Delete all nodes in the equeue and return
 *
 * queue -> pointer to an EQUEUE struct
 * no return
 ***********************************************************************/
void equeue_empty(EQUEUE *queue) {
    NODE * curr = queue->head; // start from the beginning of the list
    queue->head = 0;           // no need for the head pointer any more
    NODE * next;        // use this to not get lost in the list
    
    // start at the beginning of the list and delete to the end
    while (curr != 0) {     // note that while (curr) would also work here
        next = curr->next;  // figure out the next node
        free(curr);        // delete the current node
        curr = next;        // make the next node the current node
    }
    
    queue->tail = 0;           // no need for the tail pointer, either
    
    return;
}