/* Steven Andrews, 4/16/95 */
/* operates a queue with a circular array */
/* modified 4/20/95, modified substantially 1/20/02 */
/* See documentation called queue doc */
/* Copyright 2003 by Steven Andrews.  Permission is granted
   for non-commercial use of and modifications to the code. */

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

queue qalloc(int n,int (*keycmp)(void *,void *)) {
	queue q;
	int i;

	if(n<0) return NULL;
	q=(queue) malloc(sizeof(struct qstruct));
	if(!q) return NULL;
	q->f=q->b=0;
	q->n=++n;
	q->keycmp=keycmp;
	q->x=(void **) calloc(n,sizeof(void *));
	q->k=(void **) calloc(n,sizeof(void *));
	if(!q->x||!q->k) {qfree(q,0,0);return 0;}
	for(i=0;i<n;i++)
		q->x[i]=q->k[i]=NULL;
	return q; }


int qexpand(queue q,int addspace) {
	int i,j,nnew;
	void **xnew,**knew;

	nnew=q->n+addspace;
	if(nnew<1) return 2;
	xnew=(void**)calloc(nnew,sizeof(void*));
	if(!xnew) return 1;
	knew=(void**)calloc(nnew,sizeof(void*));
	if(!knew) {free(xnew);return 1;}
	j=0;
	for(i=q->f;i!=q->b&&j<nnew;i=(i+1)%q->n) {
		xnew[j]=q->x[i];
		knew[j]=q->k[i];
		j++; }
	free(q->x);
	free(q->k);
	q->x=xnew;
	q->k=knew;
	q->n=nnew;
	q->f=0;
	q->b=j%nnew;
	for(;j<nnew;j++) xnew[j]=knew[j]=NULL;
	return 0; }


void qfree(queue q,int freek,int freex) {
	int i;

	if(!q) return;
	if(q->x) {
		if(freex)
			for(i=q->f;i!=q->b;i=(i+1)%q->n)
				if(q->x[i]) free(q->x[i]);
		free(q->x); }
	if(q->k) {
		if(freek)
			for(i=q->f;i!=q->b;i=(i+1)%q->n)
				if(q->k[i]) free(q->k[i]);
		free(q->k); }
	free(q); }


void qnull(queue q) {
	q->f=q->b=0; }


int enqueue(void *k,void *x,queue q) {
	int sp;

	q->k[q->b]=k;
	q->x[q->b]=x;
	q->b=(q->b+1)%q->n;
	sp=(q->n+q->f-q->b)%q->n-1;
	if(q->b==q->f) q->f=(q->f+1)%q->n;
	return sp; }


int qpush(void *k,void *x,queue q) {
	int sp;

	q->f=(q->n+q->f-1)%q->n;
	q->k[q->f]=k;
	q->x[q->f]=x;
	sp=(q->n+q->f-q->b)%q->n-1;
	if(q->b==q->f) q->b=(q->n+q->b-1)%q->n;
	return sp; }


int qinsert(void *k,void *x,queue q) {
	int i,n,sp,im1;

	n=q->n;
	for(im1=(n+(i=q->b)-1)%n;i!=q->f&&(q->keycmp)(k,q->k[im1])<0;im1=(n+(i=im1)-1)%n) {
		q->k[i]=q->k[im1];
		q->x[i]=q->x[im1]; }
	q->k[i]=k;
	q->x[i]=x;
	q->b=(q->b+1)%n;
	sp=(q->n+q->f-q->b)%q->n-1;
	if(q->b==q->f) q->b=(q->n+q->b-1)%q->n;
	return sp; }


void *qfront(queue q,void **kptr) {
	if(q->f==q->b) {
		if(kptr) *kptr=NULL;
		return NULL; }
	if(kptr) *kptr=q->k[q->f];
	return q->x[q->f]; }


void *qpop(queue q,void **kptr) {
	void *x;

	if(q->f==q->b) {
		if(kptr) *kptr=NULL;
		return NULL; }
	if(kptr) *kptr=q->k[q->f];
	x=q->x[q->f];
	q->f=(q->f+1)%q->n;
	return x; }


int qlength(queue q) {
	return (q->n+q->b-q->f)%q->n; }


int qmaxlength(queue q) {
	return q->n-1; }


int qnext(int i,void **kptr,void **xptr,queue q) {
	int f,b;

	f=q->f;
	b=q->b;
	if(i<0) i=f;
	else if(i>=q->n||(b<f&&i<f&&i>=b)||i<f||i>=b) return -1;
	else i=(i+1)%q->n;
	if((b<f&&i<f&&i>=b)||i<f||i>=b) return -1;
	if(kptr) *kptr=q->k[i];
	if(xptr) *xptr=q->x[i];
	return i; }