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

#include "queue.h"

struct qitem
{
	struct qitem *prev,*next;
	void * data;
};

struct queue
{
	int size;
	struct qitem *head,*tail;
};


/*------------*/
/* new_queue  */
/*            *----------------------------------------------------*/
/*                                             */
/*-----------------------------------------------------------------*/
queue_t
new_queue()
{
	queue_t q ;
	if (NULL != (q = malloc(sizeof(struct queue))))
		queue_init(q);
		
	return q;
}



/*------------*/
/* queue_init */
/*            *----------------------------------------------------*/
/* initialize the queue                                            */
/*-----------------------------------------------------------------*/
void
queue_init(queue_t q)
{
	assert(q!=NULL);
	
	q->size = 0;
	q->head = NULL;
	q->tail = NULL;
	
}

/*------------*/
/* queue_init */
/*            *----------------------------------------------------*/
/* add a new item into the queue                                   */
/*-----------------------------------------------------------------*/
void 
queue_push( queue_t q, void * data)
{
	struct qitem *new_item;
	
	assert(q!=NULL);
	assert(data!= NULL);
	
	new_item = malloc(sizeof(struct qitem));
	assert (new_item != NULL);
	
	new_item->data = data;
	
	if (queue_empty(q))
	{
		/* add the first item into the queue */
		q->head = new_item;
		q->tail = new_item;
		new_item->prev = NULL;
		new_item->next = NULL;
	}
	else
	{
		/* append the item at the tail of the queue */
		q->tail->next = new_item;
		new_item->prev = q->tail;
		new_item->next = NULL;
		q->tail = new_item;
	}
	
	++q->size;
	
}

/*------------*/
/* queue_top  */
/*            *----------------------------------------------------*/
/* get the first item in the queue                                 */
/*-----------------------------------------------------------------*/
void * 
queue_top(queue_t q)
{
	if (queue_empty(q))
		return NULL;
	else
		return q->head->data;
}


/*------------*/
/* queue_pop  */
/*            *----------------------------------------------------*/
/* remove the first item in the queue                              */
/*-----------------------------------------------------------------*/
void 
queue_pop(queue_t q)
{
	struct qitem *item;
	
	if (!queue_empty(q))
	{
		item = q->head;
		q->head = item->next;
		if (q->head)
			q->head->prev = NULL;
		else
			q->tail = NULL;
		--q->size;
		free(item);
	}
}

/*------------*/
/* queue_size */
/*            *----------------------------------------------------*/
/* get the size of the queue                                       */
/*-----------------------------------------------------------------*/
int 
queue_size(queue_t q)
{
	return q->size;
}

/*--------------*/
/* queue_empty  */
/*              *--------------------------------------------------*/
/* check if the queue is empty                                     */
/*-----------------------------------------------------------------*/
int	
queue_empty(queue_t q)
{
	return !q->size;
}


/*--------------*/
/* queue_clear  */
/*              *--------------------------------------------------*/
/* clear queue, all items in queue are not destoryed,              */
/* then the objects will still be valid.                           */
/*-----------------------------------------------------------------*/
void queue_clear( queue_t q)
{
	while (!queue_empty(q))
	{
		queue_pop(q);
	}
	return;
}


/*---------------*/
/* destory_queue */
/*               *-------------------------------------------------*/
/* clear queue, all items in the queue are also destoryed          */
/*-----------------------------------------------------------------*/
void destory_queue ( queue_t q)
{
	while (!queue_empty(q))
	{
		free(queue_top(q));
		queue_pop(q);
	}
	return;
}