home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 1 / ARM_CLUB_CD.iso / contents / education / a / autopcb / !AutoPCB / c / QUEUE < prev    next >
Text File  |  1991-03-23  |  5KB  |  150 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #include "heap.h"
  5.  
  6. #include "cell.h"
  7.  
  8. #define far
  9.  
  10. struct queue { /* search queue structure */
  11.         int Row;        /* current row                                  */
  12.         int Col;        /* current column                               */
  13.         int Side;       /* 0=top, 1=bottom                              */
  14.         int Dist;       /* path distance to this cell so far            */
  15.         int ApxDist;    /* approximate distance to target from here     */
  16.         struct queue far *Next;
  17.         };
  18.  
  19. /* search statistics */
  20. long OpenNodes = 0; /* total number of nodes opened */
  21. long ClosNodes = 0; /* total number of nodes closed */
  22. long MoveNodes = 0; /* total number of nodes moved */
  23. long MaxNodes = 0; /* maximum number of nodes opened at one time */
  24.  
  25. static long qlen = 0; /* current queue length */
  26.  
  27. static struct queue far *Head = NULL;
  28. static struct queue far *Tail = NULL;
  29. static struct queue far *Save = NULL; /* hold empty queue structs */
  30.  
  31. extern void Nomem( void );
  32.  
  33. void InitQueue( void );
  34. void GetQueue( int *, int *, int *, int *, int * );
  35. void SetQueue( int, int, int, int, int, int, int );
  36. void ReSetQueue( int, int, int, int, int, int, int );
  37.  
  38. void InitQueue () { /* initialize the search queue */
  39.         struct queue far *p;
  40.  
  41.         while (p = Head) {
  42.                 Head = p->Next;
  43.                 p->Next = Save;
  44.                 Save = p;
  45.                 }
  46.         Tail = NULL;
  47.         OpenNodes = ClosNodes = MoveNodes = MaxNodes = qlen = 0;
  48.         }
  49.  
  50. void GetQueue ( r, c, s, d, a ) /* get search queue item from list */
  51.         int *r, *c, *s, *d, *a;
  52.         {
  53.         struct queue far *p;
  54.  
  55.         if (p = Head) { /* return first item in list */
  56.                 *r = p->Row;
  57.                 *c = p->Col;
  58.                 *s = p->Side;
  59.                 *d = p->Dist;
  60.                 *a = p->ApxDist;
  61.                 if (!(Head = p->Next))
  62.                         Tail = NULL;
  63.                 /* put node on free list */
  64.                 p->Next = Save;
  65.                 Save = p;
  66.                 ClosNodes++;
  67.                 qlen--;
  68.                 }
  69.         else /* empty list */
  70.                 *r = *c = *s = *d = *a = ILLEGAL;
  71.         }
  72.  
  73. void SetQueue ( r, c, s, d, a, r2, c2 ) /* add a search node to the list */
  74.         int r, c, s, d, a, r2, c2;
  75.         {
  76.         struct queue far *p;
  77.         struct queue far *q;
  78.         struct queue far *t;
  79.         register int i;
  80.         int j;
  81.  
  82.         if (p = Save) /* try free list first */
  83.                 Save = p->Next;
  84.         else if (!(p = (struct queue far *)heap_alloc( sizeof(struct queue) )))
  85.                 Nomem();
  86.         p->Row = r;
  87.         p->Col = c;
  88.         p->Side = s;
  89.         i = (p->Dist = d) + (p->ApxDist = a);
  90.         p->Next = NULL;
  91.         if (q = Head) { /* insert in proper position in list */
  92.                 if (q->Dist + q->ApxDist > i) { /* insert at head */
  93.                         p->Next = q;
  94.                         Head = p;
  95.                         }
  96.                 else { /* search for proper position */
  97.                         for (t = q, q = q->Next;
  98.                                 q && i > (j = q->Dist + q->ApxDist);
  99.                                 t = q, q = q->Next)
  100.                                 ;
  101.                         if (q && i == j && q->Row == r2 && q->Col == c2) {
  102.                                 /* insert after q, which is a goal node */
  103.                                 if (!(p->Next = q->Next))
  104.                                         Tail = p;
  105.                                 q->Next = p;
  106.                                 }
  107.                         else { /* insert in front of q */
  108.                                 if (!(p->Next = q))
  109.                                         Tail = p;
  110.                                 t->Next = p;
  111.                                 }
  112.                         }
  113.                 }
  114.         else /* empty search list */
  115.                 Head = Tail = p;
  116.         OpenNodes++;
  117.         if (++qlen > MaxNodes)
  118.                 MaxNodes = qlen;
  119.         }
  120.  
  121. void ReSetQueue ( r, c, s, d, a, r2, c2 ) /* reposition node in list */
  122.         register int r, c;
  123.         int s, d, a, r2, c2;
  124.         {
  125.         struct queue far *p;
  126.         struct queue far *q;
  127.  
  128.         /* first, see if it is already in the list */
  129.         for (q = NULL, p = Head; p; q = p, p = p->Next) {
  130.                 if (p->Row == r && p->Col == c && p->Side == s) {
  131.                         /* old one to remove */
  132.                         if (q) {
  133.                                 if (!(q->Next = p->Next))
  134.                                         Tail = q;
  135.                                 }
  136.                         else if (!(Head = p->Next))
  137.                                 Tail = NULL;
  138.                         p->Next = Save;
  139.                         Save = p;
  140.                         OpenNodes--;
  141.                         MoveNodes++;
  142.                         qlen--;
  143.                         break;
  144.                         }
  145.                 }
  146.         /* if it was there, it's gone now; insert it at the proper position */
  147.         SetQueue( r, c, s, d, a, r2, c2 );
  148.         }
  149.  
  150.