#include <stdio.h>

/*
#ifndef M_XENIX
#include <stdlib.h>
#endif
*/

/*
#include <malloc.h>
*/
#include "cell.h"

extern char *Alloc();

struct queue { /* search queue structure */
	int Row;	/* current row					*/
	int Col;	/* current column				*/
	int Side;	/* 0=top, 1=bottom				*/
	int Dist;	/* path distance to this cell so far		*/
	int ApxDist;	/* approximate distance to target from here	*/
	struct queue *Next;
	};

/* search statistics */
long OpenNodes = 0; /* total number of nodes opened */
long ClosNodes = 0; /* total number of nodes closed */
long MoveNodes = 0; /* total number of nodes moved */
long MaxNodes = 0; /* maximum number of nodes opened at one time */

static long qlen = 0; /* current queue length */

static struct queue *Head = NULL;
static struct queue *Tail = NULL;
static struct queue *Save = NULL; /* hold empty queue structs */

extern void Nomem();

void InitQueue();
void GetQueue();
void SetQueue();
void ReSetQueue();

void InitQueue () { /* initialize the search queue */
	struct queue *p;

	while (p = Head) {
		Head = p->Next;
		p->Next = Save;
		Save = p;
		}
	Tail = NULL;
	OpenNodes = ClosNodes = MoveNodes = MaxNodes = qlen = 0;
	}

void GetQueue ( r, c, s, d, a ) /* get search queue item from list */
	int *r, *c, *s, *d, *a;
	{
	struct queue *p;

	if (p = Head) { /* return first item in list */
		*r = p->Row;
		*c = p->Col;
		*s = p->Side;
		*d = p->Dist;
		*a = p->ApxDist;
		if (!(Head = p->Next))
			Tail = NULL;
		/* put node on free list */
		p->Next = Save;
		Save = p;
		ClosNodes++;
		qlen--;
		}
	else /* empty list */
		*r = *c = *s = *d = *a = ILLEGAL;
	}

void SetQueue ( r, c, s, d, a, r2, c2 ) /* add a search node to the list */
	int r, c, s, d, a, r2, c2;
	{
	struct queue *p;
	struct queue *q;
	struct queue *t;
	register int i;
	int j;

	if (p = Save) /* try free list first */
		Save = p->Next;
	else if (!(p = (struct queue *)Alloc( (long)sizeof(struct queue) )))
		Nomem();
	p->Row = r;
	p->Col = c;
	p->Side = s;
	i = (p->Dist = d) + (p->ApxDist = a);
	p->Next = NULL;
	if (q = Head) { /* insert in proper position in list */
		if (q->Dist + q->ApxDist > i) { /* insert at head */
			p->Next = q;
			Head = p;
			}
		else { /* search for proper position */
			for (t = q, q = q->Next;
				q && i > (j = q->Dist + q->ApxDist);
				t = q, q = q->Next)
				;
			if (q && i == j && q->Row == r2 && q->Col == c2) {
				/* insert after q, which is a goal node */
				if (!(p->Next = q->Next))
					Tail = p;
				q->Next = p;
				}
			else { /* insert in front of q */
				if (!(p->Next = q))
					Tail = p;
				t->Next = p;
				}
			}
		}
	else /* empty search list */
		Head = Tail = p;
	OpenNodes++;
	if (++qlen > MaxNodes)
		MaxNodes = qlen;
	}

void ReSetQueue ( r, c, s, d, a, r2, c2 ) /* reposition node in list */
	register int r, c;
	int s, d, a, r2, c2;
	{
	struct queue *p;
	struct queue *q;

	/* first, see if it is already in the list */
	for (q = NULL, p = Head; p; q = p, p = p->Next) {
		if (p->Row == r && p->Col == c && p->Side == s) {
			/* old one to remove */
			if (q) {
				if (!(q->Next = p->Next))
					Tail = q;
				}
			else if (!(Head = p->Next))
				Tail = NULL;
			p->Next = Save;
			Save = p;
			OpenNodes--;
			MoveNodes++;
			qlen--;
			break;
			}
		}
	/* if it was there, it's gone now; insert it at the proper position */
	SetQueue( r, c, s, d, a, r2, c2 );
	}