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