#ifndef CA_UWATERLOO_ALUMNI_DWHARDER_QUEUE
#define CA_UWATERLOO_ALUMNI_DWHARDER_QUEUE

// Author:  Douglas Wilhelm Harder
// Copyright (c) 2012 by Douglas Wilhelm Harder.  All rights reserved.

/***********************************************************************
 * *********************************************************************
 * * Queue
 * *
 * * A circular queue of pointers
 * *
 * *  void init( struct Queue *, int n )
 * *     Initialize the queue and allocate n memory locations.
 * *            
 * *  void deinit( struct Queue * )
 * *     Clean up the allocated memory.
 * *
 * *   int size( struct Queue * )
 * *     Return the number of entries in the queue.
 * *
 * *   int empty( struct Queue * )
 * *     Return 1 if the queue is empty, and 0 otherwise.
 * *
 * *   void *front( struct Queue * )
 * *     Return the front of the queue; NULL if empty.
 * *
 * *   void push( struct Queue *, void * )
 * *      Push the second argument onto the queue.
 * *      Double the allocated memory if the queue is full.
 * *
 * *   void pop( struct Queue * )
 * *      Remove the head of the queue.
 * *
 * * There is one helper function:
 * *
 * *   void double_capacity( struct Queue * )
 * *      Double the memory allocated for the circular queue.
 * *      While it is only called if the queue is full,
 * *      its functionality does not depend on the queue being full.
 * *********************************************************************
 ***********************************************************************/

#include <stdlib.h>

struct Queue {
	void **array;
	int head;
	int tail;
	int array_capacity;
	int initial_capacity;
	int queue_size;
};

/*****************************************************
 * void init( struct Queue * )
 *
 * This function should only be called once and
 * before the queue is ever used.  Calling any other
 * function on an uninitialized queue will result
 * in undefined behaviour.
 *
 * The argument represents the initial capacity of
 * the array
 *    - if the user passes a value < 1, we set the
 *      inital capacity to 1
 *
 * Then, we allocate an array with an initial capacity
 * number of entries.  These entries do not have to
 * be initialized.
 *
 * In our scheme, we will leave it to push(...) to
 * initialize 'head' and 'tail' if the queue is
 * empty, so we will simply set the queue size to 0.
 *****************************************************/

void init( struct Queue *q, int n ) {
	// Make sure the array capacity is at least 1 and allocate the memory
	q->initial_capacity = (n > 0) ? n : 1;
	q->array_capacity = q->initial_capacity;

	q->array = malloc( (q->initial_capacity)*sizeof( void * ) );

	// Set the queue size to zero.  If queue_size == 0 in push(),
	// both head and tail will be set to 0.
	q->queue_size = 0;
}

/*****************************************************
 * void deinit( struct Queue * )
 *
 * Free the memory allocated for the array.
 * The queue should not be used after this point.
 *
 * Calling any function other than another init(...)
 * on a de-initialized queue will result in undefined
 * behaviour.
 *****************************************************/

void deinit( struct Queue *q ) {
	free( q->array );
}

/*****************************************************
 * void double_capacity( struct Queue * )
 *
 * Double the capacity of the array allocated to the
 * circular queue.
 *
 * This requires us to make sure that the head and
 * tail are in the appropriate places when this
 * function exits.
 *****************************************************/

void double_capacity( struct Queue *q ) {
	// Create a new array twice the current capacity
	void **tmp = q->array;
	q->array = malloc( 2*(q->array_capacity)*sizeof( void * ) );

	int i;

	if ( q->head <= q->tail ) {
		// Scenario 1: 
		//  ...H*******T... => ...H*******T..................

		for ( i = q->head; i <= q->tail; ++i ) {
			q->array[i] = tmp[i];
		}
	} else {
		// Scenario 2:
		//  ***T......H**** => ***T.....................H****

		for ( i = 0; i <= q->tail; ++i ) {
			q->array[i] = tmp[i];
		}

		for ( i = q->head; i < q->array_capacity; ++i ) {
			q->array[q->array_capacity + i] = tmp[i];
		}

		q->head += q->array_capacity;
	}

	// Free up the old memory and double the capacity
	free( tmp );
	q->array_capacity *= 2;
}

/*****************************************************
 * int size( struct Queue * )
 *
 * Return the queue size.
 *****************************************************/

int size( struct Queue *q ) {
	return q->queue_size;
}

/*****************************************************
 * int empty( struct Queue * )
 *
 * Return 1 if the queue is empty, and 0 otherwise.
 *****************************************************/

int empty( struct Queue *q ) {
	return ( q->queue_size == 0 );
}

/*****************************************************
 * void *front( struct Queue * )
 *
 * If the circular queue is empty, return NULL;
 * Otherwise, return the entry at location 'head'.
 *****************************************************/

void *front( struct Queue *q ) {
	return ( q->queue_size == 0 ) ? NULL : q->array[q->head];
}

/*****************************************************
 * void push( struct Queue *, void * )
 *
 * Push the second argument onto the queue.
 *****************************************************/

void push( struct Queue *q, void *ptr ) {
	// If the queue is empty, just set head = tail = 0
        // and place the first pointer there.

	if ( q->queue_size == 0 ) {
		q->queue_size = 1;
		q->head = 0;
		q->tail = 0;
		q->array[0] = ptr;

		return;
	}

	// If the queue is full, double the capacity
	if ( q->queue_size == q->array_capacity ) {
		double_capacity( q );
	}

	// Increment the tail and place the new pointer there.
	// Increment the queue size.

	q->tail = (q->tail + 1) % q->array_capacity;
	q->array[q->tail] = ptr;
	++(q->queue_size);
}

/*****************************************************
 * void pop( struct Queue *, void * )
 *
 * Remove the front from the queue.
 * Decrement the queue size if the queue is not empty.
 *****************************************************/

void pop( struct Queue *q ) {
	if ( q->queue_size != 0 ) {
		q->head = (q->head + 1) % q->array_capacity;
		--(q->queue_size);
	}
}

#endif