#include <stdio.h>

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

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

extern char *Alloc();

struct work { /* a unit of work is a hole-pair to connect */
	int FromRow;		/* source row		*/
	int FromCol;		/* source column	*/
	char *FromName;	/* source name		*/
	int ToRow;		/* target row		*/
	int ToCol;		/* target column	*/
	char *ToName;	/* target name		*/
	int ApxDist;		/* approximate distance	*/
	int Priority;		/* 0=no, 1=yes		*/
	struct work *Next;
	};

/* pointers to the first and last item of work to do */
static struct work *Head = NULL;
static struct work *Tail = NULL;

extern int Ntotal;

extern int GetApxDist();
extern void Nomem();

void InitWork();
void SetWork();
void GetWork();
void SortWork();

void InitWork () { /* initialize the work list */
	struct work *p;

	while (p = Head) {
		Head = p->Next;
		Free( p );
		}
	Tail = NULL;
	}

void SetWork ( r1, c1, n1, r2, c2, n2, pri )
	/* add a unit of work to the work list */
	int r1, c1, r2, c2, pri;
	char *n1;
	char *n2;
	{
	struct work *p;

	if (p = (struct work *)Alloc( (long)sizeof(struct work) )) {
		p->FromRow = r1;
		p->FromCol = c1;
		p->FromName = n1;
		p->ToRow = r2;
		p->ToCol = c2;
		p->ToName = n2;
		p->ApxDist = GetApxDist( r1, c1, r2, c2 );
		p->Priority = pri;
		p->Next = NULL;
		if (Head) /* attach at end */
			Tail->Next = p;
		else /* first in list */
			Head = p;
		Tail = p;
		Ntotal++;
		}
	else /* can't get any more memory */
		Nomem();
	}

void GetWork ( r1, c1, n1, r2, c2, n2 )
	/* fetch a unit of work from the work list */
	int *r1, *c1, *r2, *c2;
	char **n1;
	char **n2;
	{
	struct work *p;

	if (p = Head) {
		*r1 = p->FromRow;
		*c1 = p->FromCol;
		*n1 = p->FromName;
		*r2 = p->ToRow;
		*c2 = p->ToCol;
		*n2 = p->ToName;
		if (!(Head = p->Next))
			Tail = NULL;
		Free( p );
		}
	else { /* none left */
		*r1 = *c1 = *r2 = *c2 = ILLEGAL;
		*n1 = *n2 = NULL;
		}
	}

void SortWork () { /* order the work items; shortest first */
	struct work *p;
	struct work *q0; /* put PRIORITY CONNECTs in q0 */
	struct work *q1; /* sort other CONNECTs in q1 */
	struct work *r;

	q0 = q1 = NULL;
	while (p = Head) { /* prioritize each work item */
		Head = Head->Next;
		if (p->Priority) {
			if (!(r = q0)) {
				p->Next = q0;
				q0 = p;
				}
			else {
				while (r->Next)
					r = r->Next;
				p->Next = r->Next;
				r->Next = p;
				}
			}
		else if (!(r = q1) || p->ApxDist < q1->ApxDist) {
			p->Next = q1;
			q1 = p;
			}
		else { /* find proper position in list */
			while (r->Next && p->ApxDist >= r->ApxDist)
				r = r->Next;
			p->Next = r->Next;
			r->Next = p;
			}
		}
	if (p = q0) {
		while (q0->Next)
			q0 = q0->Next;
		q0->Next = q1;
		}
	else
		p = q1;
	/* reposition Head and Tail */
	for (Tail = Head = p; Tail && Tail->Next; Tail = Tail->Next)
		;
	}