/*
  arrayqueue.c
  Implementation of the queue ADT using an array
  Nadeem Abdul Hamid
  Fall 2006 - Berry College - CSC220
*/

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

#define INITIAL_CAPACITY 2

/* the queue data structure */
struct queue
{
  void **data;  /* array of void* pointers */
  int rear;    /* next index at which to enqueue data */
  int size;     /* number of items in the queue */
  int cap;      /* current capacity of the data array */
  /* front index of queue is ( (rear+(cap-size)) % cap ) */
};


/* return the index of the front element of the queue */
int queueFrontIndex(QUEUE q) 
{
  return ( q->rear + (q->cap - q->size) ) % q->cap;
}


/* creates a new queue with initial capacity */
QUEUE createQueue()
{
  QUEUE q = (QUEUE) malloc(sizeof(struct queue));
  q->cap = INITIAL_CAPACITY;
  q->data = (void**) malloc(q->cap * sizeof(void*));
  q->rear = 0;
  q->size = 0;

  printf("qcap: %d\n", q->cap);
  return q;
}


/* frees all memory associated with the queue data structure,
   (but does not free any of the actual data items) */
void destroyQueue(QUEUE q)
{
  free(q->data);
  free(q);
}


/* returns the size of the queue */
int queueSize(QUEUE q)
{
  return q->size;
}


/* returns whether the queue is empty */
bool isEmptyQueue(QUEUE q)
{
  return !queueSize(q);
}


/* double the capacity of the queue; return true if successful */
bool reallocateQueue(QUEUE q) 
{
    void **newdata;
    int i, j = queueFrontIndex(q);

    newdata = (void**) malloc(2 * q->cap * sizeof(void*));
    if (!newdata)
      return false;
    /* copy the data to position 0 in the new array */
    for (i=0; i<q->size; i++) {
      newdata[i] = q->data[j];
      j = (j + 1) % q->cap;
    }
    q->cap *= 2;
    q->rear = q->size;
    free(q->data);
    q->data = newdata;
    return true;
}


/* adds an item to the rear of the queue; returns true if successful */
bool enqueue(QUEUE q, void* item)
{
  if (q->size == q->cap) { /* out of space -- copy to a bigger array */
    if (!reallocateQueue(q))
      return false;
  }

  q->size++;
  q->data[q->rear] = item;
  q->rear = (q->rear + 1) % q->cap;
  return true;
}


/* removes an item from the front of the queue; returns NULL if error */
void* dequeue(QUEUE q)
{
  void *item;
  int front;
  if (isEmptyQueue(q))
    return NULL;

  front = queueFrontIndex(q);
  item = q->data[front];
  q->data[front] = NULL; /* (not strictly necessary) */
  q->size--;
  return item;
}


/* returns the item at the front of the queue; returns NULL if error */
void* queueFront(QUEUE q)
{
  int front;
  if (isEmptyQueue(q))
    return NULL;

  front = queueFrontIndex(q);
  return q->data[front];
}


/* returns the item at the rear of the queue; returns NULL if error */
void* queueRear(QUEUE q)
{
  if (isEmptyQueue(q))
    return NULL;

  return q->data[q->rear-1];
}