home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / struct / 3.reach.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  3.6 KB  |  144 lines

  1. #include <stdio.h>
  2. #
  3. /*
  4. set REACH[v] = w if w is only node outside subtree of v which is reached from within
  5.     subtree of v, REACH[v] = UNDEFINED otherwise
  6. */
  7. #include "def.h"
  8.  
  9. /* strategy in obtaining REACH(v) for each node v:
  10. Since only need to know whether there is exactly one exit from subtree of v,
  11. need keep track only of 2 farthest exits from each subtree rather than all exits.
  12. The first may be the unique exit, while the second is used when the children
  13. of a node has the same first exit.
  14. To obtain 2 farthest exits of v, look at 2 farthest exits of children of v and
  15. the nodes entered by arcs from v.  Farthest exits are identified by numbering
  16. the nodes from -2 to -(accessnum-2) starting at the bottom left corner of tree
  17. using procedure number().  The farthest exit from the subtree of v is the one
  18. with the least number according NUM to this numbering.  If a node w is an exit from the
  19. subtree of v, then NUM(w) < NUM(v).  The negative numbers allow NUM(v) to be stored
  20. in the same location as REACH(v).  REACH(w) may already be set when an arc (v,w) to a child
  21. is searched, but the negative numbering is consistent, i.e. NUM(v) < NUM(w) in this case
  22. as in other cases where w is not an exit from the subtree of v.
  23. */
  24.  
  25. struct pair {
  26.     int smallest;
  27.     int second;
  28.     };
  29.  
  30.  
  31. getreach()        /* obtain REACH(v) for each node v */
  32.     {
  33.     VERT v;
  34.     struct pair *pr;
  35.     for (v = 0; v < nodenum; ++v)
  36.         REACH(v) = UNDEFINED;
  37.     number(START);
  38.     for (v = START; DEFINED(v); v = RSIB(v))
  39.         {
  40.         pr = exits(v);    /* need to free the space for pr */
  41.         chfree(pr,sizeof(*pr));
  42.         }
  43.     }
  44.  
  45.  
  46. exits(v)    /* set REACH(v) = w if w is only node outside subtree of v which is reached from within
  47.             subtree of v, leave REACH(v) UNDEFINED otherwise */
  48. VERT v;
  49.     {
  50.     struct pair *vpair, *chpair;
  51.     VERT w,t;
  52.     int i;
  53.     vpair = challoc(sizeof(*vpair));
  54.     vpair ->smallest = vpair ->second = UNDEFINED;
  55.     for (i = 0; i < CHILDNUM(v); ++i)
  56.         {
  57.         w = LCHILD(v,i);
  58.         if (!DEFINED(w)) continue;
  59.         for (t = w; DEFINED(t); t = RSIB(t))
  60.             {
  61.             chpair = exits(t);
  62.  
  63.             /* set vpair->smallest,second to two smallest of vpair->smallest,second,
  64.                 chpair->smallest,second */
  65.             if (inspr(chpair->smallest,vpair))
  66.                 inspr(chpair->second,vpair);
  67.             chfree(chpair, sizeof(*chpair));
  68.             }
  69.         }
  70.     for (i = 0; i < ARCNUM(v); ++i)
  71.         {
  72.         w = ARC(v,i);
  73.         if (!DEFINED(w)) continue;
  74.             inspr(w,vpair);
  75.         }
  76.     /* throw out nodes in subtree of  v */
  77.     if (NUM(vpair->second) >= NUM(v))
  78.         {
  79.         vpair->second = UNDEFINED;
  80.         if (NUM(vpair->smallest) >= NUM(v))
  81.             vpair->smallest = UNDEFINED;
  82.         }
  83.     if (vpair->second == UNDEFINED)
  84.          REACH(v) = vpair->smallest;    /* vpair->smallest possibly UNDEFINED */
  85.     else
  86.         REACH(v) = UNDEFINED;
  87.     return(vpair);
  88.     }
  89.  
  90.  
  91.     /* number nodes from -2 to -(accessnum+2) starting at bottom left corner of tree */
  92. number(v)
  93. VERT v;
  94.     {
  95.     int i;
  96.     VERT w;
  97.     static int count;
  98.     for (i = 0; i < CHILDNUM(v); ++i)
  99.         {
  100.         w = LCHILD(v,i);
  101.         if (DEFINED(w))
  102.             number(w);
  103.         }
  104.     SETNUM(v,count-2);
  105.     --count;
  106.     if (DEFINED(RSIB(v)))
  107.         number(RSIB(v));
  108.     }
  109.  
  110.  
  111. NUM(v)
  112. VERT v;
  113.     {
  114.     if (!DEFINED(v)) return(UNDEFINED);
  115.     return(REACH(v));
  116.     }
  117.  
  118. SETNUM(v,count)
  119. VERT v; int count;
  120.     {
  121.     /* this reuses REACH to save space;
  122.     /* appears to be no conflict with setting true value of REACH later */
  123.     REACH(v) = count;
  124.     }
  125.  
  126.  
  127. LOGICAL inspr(w,pr)        /* insert w in order in pr, return TRUE if <= smaller of pr */
  128.                     /* don't insert duplicates */
  129. VERT w;
  130. struct pair *pr;
  131.     {
  132.     if (w == pr-> smallest) return(TRUE);
  133.     if (NUM(w) < NUM(pr->smallest))
  134.         {
  135.         pr->second = pr->smallest;
  136.         pr->smallest = w;
  137.         return(TRUE);
  138.         }
  139.     if (w == pr->second) return(FALSE);
  140.     if (NUM(w) < NUM(pr->second))
  141.         pr->second = w;
  142.     return(FALSE);
  143.     }
  144.