home *** CD-ROM | disk | FTP | other *** search
/ Hacker Chronicles 2 / HACKER2.BIN / 686.WORK.C < prev    next >
C/C++ Source or Header  |  1989-02-16  |  3KB  |  139 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4. #include "cell.h"
  5.  
  6. struct work { /* a unit of work is a hole-pair to connect */
  7.     int FromRow;        /* source row        */
  8.     int FromCol;        /* source column    */
  9.     char far *FromName;    /* source name        */
  10.     int ToRow;        /* target row        */
  11.     int ToCol;        /* target column    */
  12.     char far *ToName;    /* target name        */
  13.     int ApxDist;        /* approximate distance    */
  14.     int Priority;        /* 0=no, 1=yes        */
  15.     struct work far *Next;
  16.     };
  17.  
  18. /* pointers to the first and last item of work to do */
  19. static struct work far *Head = NULL;
  20. static struct work far *Tail = NULL;
  21.  
  22. extern int Ntotal;
  23.  
  24. extern int GetApxDist( int, int, int, int );
  25. extern void Nomem( void );
  26.  
  27. void InitWork( void );
  28. void SetWork( int, int, char far *, int, int, char far *, int );
  29. void GetWork( int *, int *, char far * far *, int *, int *, char far * far * );
  30. void SortWork( void );
  31.  
  32. void InitWork () { /* initialize the work list */
  33.     struct work far *p;
  34.  
  35.     while (p = Head) {
  36.         Head = p->Next;
  37.         _ffree( p );
  38.         }
  39.     Tail = NULL;
  40.     }
  41.  
  42. void SetWork ( r1, c1, n1, r2, c2, n2, pri )
  43.     /* add a unit of work to the work list */
  44.     int r1, c1, r2, c2, pri;
  45.     char far *n1;
  46.     char far *n2;
  47.     {
  48.     struct work far *p;
  49.  
  50.     if (p = (struct work far *)_fmalloc( sizeof(struct work) )) {
  51.         p->FromRow = r1;
  52.         p->FromCol = c1;
  53.         p->FromName = n1;
  54.         p->ToRow = r2;
  55.         p->ToCol = c2;
  56.         p->ToName = n2;
  57.         p->ApxDist = GetApxDist( r1, c1, r2, c2 );
  58.         p->Priority = pri;
  59.         p->Next = NULL;
  60.         if (Head) /* attach at end */
  61.             Tail->Next = p;
  62.         else /* first in list */
  63.             Head = p;
  64.         Tail = p;
  65.         Ntotal++;
  66.         }
  67.     else /* can't get any more memory */
  68.         Nomem();
  69.     }
  70.  
  71. void GetWork ( r1, c1, n1, r2, c2, n2 )
  72.     /* fetch a unit of work from the work list */
  73.     int *r1, *c1, *r2, *c2;
  74.     char far * far *n1;
  75.     char far * far *n2;
  76.     {
  77.     struct work far *p;
  78.  
  79.     if (p = Head) {
  80.         *r1 = p->FromRow;
  81.         *c1 = p->FromCol;
  82.         *n1 = p->FromName;
  83.         *r2 = p->ToRow;
  84.         *c2 = p->ToCol;
  85.         *n2 = p->ToName;
  86.         if (!(Head = p->Next))
  87.             Tail = NULL;
  88.         _ffree( p );
  89.         }
  90.     else { /* none left */
  91.         *r1 = *c1 = *r2 = *c2 = ILLEGAL;
  92.         *n1 = *n2 = NULL;
  93.         }
  94.     }
  95.  
  96. void SortWork () { /* order the work items; shortest first */
  97.     struct work far *p;
  98.     struct work far *q0; /* put PRIORITY CONNECTs in q0 */
  99.     struct work far *q1; /* sort other CONNECTs in q1 */
  100.     struct work far *r;
  101.  
  102.     q0 = q1 = NULL;
  103.     while (p = Head) { /* prioritize each work item */
  104.         Head = Head->Next;
  105.         if (p->Priority) {
  106.             if (!(r = q0)) {
  107.                 p->Next = q0;
  108.                 q0 = p;
  109.                 }
  110.             else {
  111.                 while (r->Next)
  112.                     r = r->Next;
  113.                 p->Next = r->Next;
  114.                 r->Next = p;
  115.                 }
  116.             }
  117.         else if (!(r = q1) || p->ApxDist < q1->ApxDist) {
  118.             p->Next = q1;
  119.             q1 = p;
  120.             }
  121.         else { /* find proper position in list */
  122.             while (r->Next && p->ApxDist >= r->ApxDist)
  123.                 r = r->Next;
  124.             p->Next = r->Next;
  125.             r->Next = p;
  126.             }
  127.         }
  128.     if (p = q0) {
  129.         while (q0->Next)
  130.             q0 = q0->Next;
  131.         q0->Next = q1;
  132.         }
  133.     else
  134.         p = q1;
  135.     /* reposition Head and Tail */
  136.     for (Tail = Head = p; Tail && Tail->Next; Tail = Tail->Next)
  137.         ;
  138.     }
  139.