home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / games / volume8 / mgt / part01 / tree.c < prev   
C/C++ Source or Header  |  1990-02-23  |  6KB  |  371 lines
  1.  
  2. /*
  3.  
  4.         "mgt" Copyright 1990 Shodan
  5.         All Rights Reserved.
  6.         Program by Greg Hale
  7.  
  8. Permission to use, copy, modify, and distribute this software and its
  9. documentation for any purpose and without fee is hereby granted,
  10. provided that this entire comment and copyright notice appear in all
  11. copies and that both that copyright notice and this permission notice
  12. appear in supporting documentation.  No representations are made about
  13. the suitability of this software for any purpose.  It is provided "as
  14. is" without express or implied warranty.
  15.  
  16. Please send copies of extensions to:
  17.  
  18. hale@scam.berkeley.edu
  19. 128.32.138.4    scam.berkeley.edu sting sting.Berkeley.EDU
  20.  
  21. Donations for the 'From My Go Teacher' series may be sent to:
  22.     Shodan
  23.     P.O. Box 4456
  24.     Berkeley, CA 94704
  25.     (415) 849-9475
  26.  
  27. */
  28.  
  29. #include "mgt.h"
  30. #include "var.h"
  31. #include "file.h"
  32.  
  33.  
  34. #define MAXNODE (65536/sizeof(node))
  35.  
  36. static char bitmask[] = {1<<0,1<<1,1<<2,1<<3,1<<4,1<<5,1<<6,1<<7,1<<8};
  37.  
  38.  
  39. #define byteNumXY(x,y) (((x)+(y)*19)/8)
  40. #define bitNumXY(x,y) (((x)+(y)*19)%8)
  41.  
  42.  
  43. static depthrec d;
  44. static int newNodeNum;
  45.  
  46.  
  47.  
  48. FUNCTION void clearCoordList(c)
  49. coordListP c;
  50. {
  51.     int i;
  52.     for (i=8; i--;)
  53.         c->b[i]=0;
  54. }
  55.  
  56. FUNCTION boolean getCoord(x,y,c)
  57. int x,y;
  58. coordListP c;
  59. {
  60.     return c->b[byteNumXY(x,y)] & bitmask[bitNumXY(x,y)];
  61. }
  62.  
  63. FUNCTION void setCoord(x,y,c)
  64. int x,y;
  65. coordListP c;
  66. {
  67.     int bytenum,bitnum;
  68.     bytenum = byteNumXY(x,y);
  69.     bitnum = bitNumXY(x,y);
  70.     c->b[bytenum] |= bitmask[bitnum];
  71. }
  72.  
  73. FUNCTION void clearCoord(x,y,c)
  74. int x,y;
  75. coordListP c;
  76. {
  77.     int bytenum;
  78.     bytenum = byteNumXY(x,y);
  79.     c->b[bytenum] &= (~bitmask[bitNumXY(x,y)]);
  80. }
  81.  
  82. FUNCTION void initNodes()
  83. {
  84.     newNodeNum = 1;
  85. }
  86.  
  87. FUNCTION nodep newNode()
  88. {
  89.     nodep new;
  90.     new =  (nodep)calloc(1,sizeof(node));
  91.     if (!new)
  92.         barf("Memory allocation failure (newnode)");
  93.     new->nodeNum = newNodeNum++;
  94.     return new;
  95. }
  96.  
  97. FUNCTION void freeNode(n)
  98. nodep n;
  99. {
  100.     if (n) {
  101.         delNode(n->nextSibling);
  102.         delNode(n->child);
  103.         free(n);
  104.     }
  105. }
  106.  
  107. FUNCTION char *dupStr(s)
  108. char *s;
  109. {
  110.     char *c;
  111.     c = (char *)malloc((unsigned)strlen(s)+1);
  112.     if (!c)
  113.         barf("Memory allocation failure (dupstr)");
  114.     strcpy(c,s);
  115.     return c;
  116. }
  117.  
  118. /* not done yet */
  119. FUNCTION void freeProps(n)
  120. nodep n;
  121. {
  122.     switch (n->p->t) {
  123.     }
  124. }
  125.  
  126. FUNCTION void delNode(n)
  127. nodep n;
  128. {
  129.     freeProps(n);
  130.     free(n);
  131. }
  132.  
  133. FUNCTION void addprop(n,p)
  134. nodep n;
  135. property *p;
  136. {
  137.     p->next = n->p;
  138.     n->p = p;
  139. }
  140.  
  141. FUNCTION property *getprop(n,t)
  142. nodep n;
  143. token t;
  144. {
  145.     property *p;
  146.     p = n->p;
  147.     while (p && p->t != t)
  148.         p = p->next;
  149.     return p;
  150. }
  151.  
  152. FUNCTION int treeCountSiblings(n)
  153. {
  154.     int i;
  155.     nodep n1;
  156.     n1 = child(n,false);
  157.     i = 0;
  158.     while (n1) {
  159.         n1 = nextSibling(n1,false);
  160.         i++;
  161.     }
  162.     return i;
  163. }
  164.  
  165. FUNCTION nodep nthChild(n,c,bSearch) /* nodep, int, boolean */
  166. nodep n;
  167. int c;
  168. boolean bSearch;
  169. {
  170.     if (n->child) {
  171.         n = child(n,bSearch);
  172.         while (c-- && n)
  173.             n = nextSibling(n,bSearch);
  174.     } else {
  175.         n = 0;
  176.     }
  177.     return n;
  178. }
  179.  
  180. /*
  181. *
  182. *
  183. * TREE WALK functions
  184. * KEEP TRACK OF DEPTH AS WELL
  185. *
  186. *
  187. *
  188. */
  189. FUNCTION nodep parent(n,bSearch)
  190. nodep n;
  191. boolean bSearch;
  192. {
  193.     if (bSearch && n->parent)
  194.         --d.depth;
  195.     return n->parent;
  196. }
  197.  
  198. FUNCTION nodep child(n,bSearch)
  199. nodep n;
  200. boolean bSearch;
  201. {
  202.     if (bSearch && n->child)
  203.         d.d[++d.depth]=0;
  204.     return n->child;
  205. }
  206.  
  207. FUNCTION nodep lastSibling(n,bSearch)
  208. nodep n;
  209. boolean bSearch;
  210. {
  211.     if (bSearch && n->lastSibling)
  212.         d.d[d.depth]--;
  213.     return n->lastSibling;
  214. }
  215.  
  216. FUNCTION nodep nextSibling(n,bSearch)
  217. nodep n;
  218. boolean bSearch;
  219. {
  220.     if (bSearch && n->nextSibling)
  221.         d.d[d.depth]++;
  222.     return n->nextSibling;
  223. }
  224.  
  225. FUNCTION nodep treeLastSibling(n,bSearch)
  226. nodep n;
  227. boolean bSearch;
  228. {
  229.     /* n = treeFirstSibling(n,bSearch); */
  230.     while (n->nextSibling) {
  231.         if (bSearch)
  232.             d.d[d.depth]++;
  233.         n = n->nextSibling;
  234.     }
  235.     return n;
  236. }
  237.  
  238. FUNCTION nodep treeFirstSibling(n,bSearch)
  239. nodep n;
  240. boolean bSearch;
  241. {
  242.     if (bSearch)
  243.         d.d[d.depth] = 0;
  244.     while(n->lastSibling)
  245.         n = n->lastSibling;
  246. }
  247.  
  248. /* go to next node down the tree. Stop if at bottom. */
  249. FUNCTION nodep treeDown(n,bSearch)
  250. nodep n;
  251. boolean bSearch;
  252. {
  253.     if (n->child) {
  254.         BUG("treeDown: going down\n");
  255.         return child(n,bSearch);
  256.     } else {
  257.         BUG("treeDown: stop\n");
  258.         return n;
  259.     }
  260. }
  261.  
  262. /* backup, stop if at top */
  263. FUNCTION nodep treeUp(n,bSearch)
  264. nodep n;
  265. boolean bSearch;
  266. {
  267.     if (n->parent) {
  268.         BUG("treeUp: going up\n");
  269.         return parent(n,bSearch);
  270.     } else {
  271.         BUG("treeUp: staying\n");
  272.         return n;
  273.     }
  274. }
  275.  
  276.  
  277. /* go to next node backing up the tree only */
  278. FUNCTION nodep treeNextUp(n,bSearch)
  279. nodep n;
  280. boolean bSearch;
  281. {
  282.     if (n->nextSibling) {
  283.         BUG("nextSibling ");
  284.         return nextSibling(n,bSearch);
  285.     } else if (n->parent) {
  286.         BUG("nextup-parent ");
  287.         while (n->parent && !n->nextSibling)
  288.             n = parent(n,bSearch);
  289.         if (n->nextSibling)
  290.             return nextSibling(n,bSearch);
  291.         else return n;
  292.     } else if (n->child) {
  293.         BUG("child ");
  294.         return child(n,bSearch);
  295.     } else {
  296.         BUG("current ");
  297.         return n;
  298.     }
  299. }
  300.  
  301.  
  302. /* go to next node, backup if neccessary */
  303. FUNCTION nodep treeNext(n,bSearch)
  304. nodep n;
  305. boolean bSearch;
  306. {
  307.     nodep r;
  308.     BUG("treeNext:");
  309.     if (n != (r = treeDown(n,bSearch))) {
  310.         BUG("going down ");
  311.     } else {
  312.         BUG("going up ");
  313.         r = treeNextUp(n,bSearch);
  314.     }
  315.     BUG("\n");
  316.     return r;
  317. }
  318.  
  319.  
  320.  
  321. FUNCTION nodep lastChildOfLastSibling(n,bSearch)
  322. nodep n;
  323. boolean bSearch;
  324. {
  325.     while(n->nextSibling)
  326.         n = nextSibling(n,bSearch);
  327.     if (n->child)
  328.         return lastChildOfLastSibling(child(n,bSearch),bSearch);
  329.     else return n;
  330. }
  331.  
  332. /* go to next node, backup if neccessary */
  333. FUNCTION nodep treeLast(n,bSearch)
  334. nodep n;
  335. boolean bSearch;
  336. {
  337.     nodep r;
  338.     if (n->lastSibling) {
  339.         n = lastSibling(n,bSearch);
  340.         if (n->child)
  341.             r = lastChildOfLastSibling(child(n,bSearch),bSearch);
  342.         else
  343.             r = n;
  344.     } else if (n->parent) {
  345.         /* r = treeLast(parent(n,bSearch),bSearch); */
  346.         r = parent(n,bSearch);
  347.     } else if (n->child) {
  348.         r = lastChildOfLastSibling(child(n,bSearch),bSearch);
  349.     } else {
  350.         r = n;
  351.     }
  352.     return r;
  353. }
  354.  
  355. FUNCTION int treeWillBranch(n)
  356. nodep n;
  357. {
  358.     return n->child && n->child->nextSibling;
  359. }
  360.  
  361. FUNCTION void initDepth()
  362. {
  363.     d.depth = 0;
  364.     d.d[0] = 0;
  365. }
  366.  
  367. FUNCTION void updateDepth()
  368. {
  369.     /* (*io->printDepth)(&d); */
  370. }
  371.