home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programming
/
powerprogramming1994.iso
/
progtool
/
cad
/
pcb.arc
/
QUEUE.C
< prev
next >
Wrap
C/C++ Source or Header
|
1989-02-08
|
4KB
|
145 lines
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include "cell.h"
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 far *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 far *Head = NULL;
static struct queue far *Tail = NULL;
static struct queue far *Save = NULL; /* hold empty queue structs */
extern void Nomem( void );
void InitQueue( void );
void GetQueue( int *, int *, int *, int *, int * );
void SetQueue( int, int, int, int, int, int, int );
void ReSetQueue( int, int, int, int, int, int, int );
void InitQueue () { /* initialize the search queue */
struct queue far *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 far *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 far *p;
struct queue far *q;
struct queue far *t;
register int i;
int j;
if (p = Save) /* try free list first */
Save = p->Next;
else if (!(p = (struct queue far *)_fmalloc( 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 far *p;
struct queue far *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 );
}