/* File: queues.c
 * Author: Jim Mayfield
 */

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

typedef void *queue_item_type;

#include "queues.h"

typedef struct queue_node_tag *queue_node_ptr;
typedef struct queue_node_tag {
  queue_item_type data;
  queue_node_ptr next;
} queue_node_struct;
typedef struct queue_tag {
  queue_node_ptr front;
  queue_node_ptr rear;
  /* This field is used to allow full_queue to work properly.
     A queue_node_struct may be cached here.  When full_queue is
     called, it will make sure that it can cache such a struct
     here.  Enqueue will look here first for a queue_node_struct,
     and if one is found, enqueue will use it. */
  queue_node_ptr full_queue_store;
} queue_struct_type;

queue_type
create_queue(void)
{
  queue_type result;

  result = malloc(sizeof(queue_struct_type));
  assert(result != NULL);
  result->front = NULL;  /* This indicates an empty queue. */
  result->rear = NULL;   /* Just for neatness */
  result->full_queue_store = NULL;
  return(result);
}

void
enqueue(queue_item_type item, queue_type q)
{
  queue_node_ptr temp;

  if (q->full_queue_store == NULL)
    q->full_queue_store = malloc(sizeof(queue_node_struct));
  temp = q->full_queue_store;
  assert(temp != NULL);
  q->full_queue_store = NULL;
  temp->data = item;
  temp->next = NULL;
  if (q->front == NULL)
    q->front = temp;
  else q->rear->next = temp;
  q->rear = temp;
}

queue_item_type
dequeue(queue_type q)
{
  queue_node_ptr temp;
  queue_item_type result;

  assert(q->front != NULL);
  temp = q->front;
  q->front = q->front->next;
  result = temp->data;
  if (q->front == NULL)
    q->rear = NULL;    /* Again, just for neatness. */
  free(temp);          /* Free up the space used by the removed item. */
  return(result);
}

BOOL
empty_queue(queue_type q)
{
  return(q->front == NULL);
}

BOOL
full_queue(queue_type q)
{
  /* Try to get space for the next call to enqueue. */
  if (q->full_queue_store == NULL)
    q->full_queue_store = malloc(sizeof(queue_node_struct));
  return(q->full_queue_store == NULL);
}