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