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