home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume11 / quadtree / part01 / quadtree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-04-03  |  7.5 KB  |  346 lines
  1. #include <stdio.h>
  2. #include <quadtree.h>
  3.  
  4. #define ColorsAgree(c1,c2) ((c1)?(c2):(!(c2)))
  5.  
  6. static char     BitBuffer;
  7. static int      BitPos;
  8.  
  9. extern char    *malloc();
  10.  
  11. int             QT_Bitmap_Bit(b, x, y)
  12. QT_Bitmap_t    *b;
  13. int             x, y;
  14. {
  15.     int             index, byte, offset;
  16.  
  17.     index = (y + b->y) * b->fullwidth + (x + b->x);
  18.     byte = index / 8;
  19.     offset = index % 8;
  20.     return (b->bits[byte] & (1 << offset));
  21. }
  22.  
  23. void            QT_Bitmap_SetBit(b, x, y, val)
  24. QT_Bitmap_t    *b;
  25. int             x, y, val;
  26. {
  27.     int             index, byte, offset;
  28.  
  29.     index = (y + b->y) * b->fullwidth + (x + b->x);
  30.     byte = index / 8;
  31.     offset = index % 8;
  32.     if (val)
  33.     b->bits[byte] |= (1 << offset);
  34.     else
  35.     b->bits[byte] &= ~(1 << offset);
  36. }
  37.  
  38. int             QT_Bitmap_Init(b, x, y, width, height, ref)
  39. QT_Bitmap_t    *b;
  40. int             width, height;
  41. QT_Bitmap_t    *ref;
  42. {
  43.     b->x = x;
  44.     b->y = y;
  45.     b->width = width;
  46.     b->height = height;
  47.     if (ref) {
  48.     b->x += ref->x;
  49.     b->y += ref->y;
  50.     b->bits = ref->bits;
  51.     b->fullwidth = ref->fullwidth;
  52.     b->fullheight = ref->fullheight;
  53.     return (0);
  54.     }
  55.     b->fullwidth = width;
  56.     b->fullheight = height;
  57.     if (b->bits = malloc(width * height / 8 + 1)) {
  58.     bzero(b->bits, width * height / 8 + 1);
  59.     return (0);
  60.     }
  61.     return (1);
  62. }
  63.  
  64. QT_TreeNode_t  *QT_TreeNode_New(color, ul, ur, ll, lr)
  65. int             color;
  66. QT_TreeNode_t  *ul, *ur, *ll, *lr;
  67. {
  68.     QT_TreeNode_t  *result = (QT_TreeNode_t *) malloc(sizeof(QT_TreeNode_t));
  69.  
  70.     if (result) {
  71.     result->color = color;
  72.     result->children[0] = ul;
  73.     result->children[1] = ur;
  74.     result->children[2] = ll;
  75.     result->children[3] = lr;
  76.     }
  77.     return (result);
  78. }
  79.  
  80. void            QT_TreeNode_Destroy(node)
  81. QT_TreeNode_t  *node;
  82. {
  83.     int             i;
  84.     QT_TreeNode_t  *child;
  85.  
  86.     for (i = 0; i < 4; ++i) {
  87.     if (child = QT_TreeNode_Child(node, i))
  88.         QT_TreeNode_Destroy(child);
  89.     }
  90.     free(node);
  91. }
  92.  
  93. static int      TreeAgrees(color, node)
  94. int             color;
  95. QT_TreeNode_t  *node;
  96. {
  97.     return ((ColorsAgree(color, QT_TreeNode_Color(node)))
  98.         && ((!(QT_TreeNode_Child(node, 0)))
  99.         || TreeAgrees(color, QT_TreeNode_Child(node, 0)))
  100.         && ((!(QT_TreeNode_Child(node, 1)))
  101.         || TreeAgrees(color, QT_TreeNode_Child(node, 1)))
  102.         && ((!(QT_TreeNode_Child(node, 2)))
  103.         || TreeAgrees(color, QT_TreeNode_Child(node, 2)))
  104.         && ((!(QT_TreeNode_Child(node, 3)))
  105.         || TreeAgrees(color,
  106.                   QT_TreeNode_Child(node, 3))));
  107. }
  108.  
  109. QT_TreeNode_t  *QT_BitmapToTree(b)
  110. QT_Bitmap_t    *b;
  111. {
  112.     QT_Bitmap_t     ulbm, urbm, llbm, lrbm;
  113.     QT_TreeNode_t  *ulqt, *urqt, *llqt, *lrqt;
  114.     int             h = QT_Bitmap_Height(b), w = QT_Bitmap_Width(b), h2, w2;
  115.     int             ones = 0, zeroes = 0, color;
  116.  
  117.     switch (w * h) {
  118.     case 0:
  119.         return 0;
  120.     case 1:
  121.         return (QT_TreeNode_New(QT_Bitmap_Bit(b, 0, 0),
  122.                     0, 0, 0, 0));
  123.     }
  124.     /* It's a non-trivial bitmap */
  125.     h2 = h >> 1;
  126.     w2 = w >> 1;
  127.     (void) QT_Bitmap_Init(&ulbm, 0, 0, w2, h2, b);
  128.     (void) QT_Bitmap_Init(&urbm, w2, 0, w - w2, h2, b);
  129.     (void) QT_Bitmap_Init(&llbm, 0, h2, w2, h - h2, b);
  130.     (void) QT_Bitmap_Init(&lrbm, w2, h2, w - w2, h - h2, b);
  131.     ulqt = QT_BitmapToTree(&ulbm);
  132.     urqt = QT_BitmapToTree(&urbm);
  133.     llqt = QT_BitmapToTree(&llbm);
  134.     lrqt = QT_BitmapToTree(&lrbm);
  135.     if (ulqt) {
  136.     if (QT_TreeNode_Color(ulqt))
  137.         ++ones;
  138.     else
  139.         ++zeroes;
  140.     }
  141.     if (urqt) {
  142.     if (QT_TreeNode_Color(urqt))
  143.         ++ones;
  144.     else
  145.         ++zeroes;
  146.     }
  147.     if (llqt) {
  148.     if (QT_TreeNode_Color(llqt))
  149.         ++ones;
  150.     else
  151.         ++zeroes;
  152.     }
  153.     if (lrqt) {
  154.     if (QT_TreeNode_Color(lrqt))
  155.         ++ones;
  156.     else
  157.         ++zeroes;
  158.     }
  159.     color = (ones > zeroes) ? 1 : 0;
  160.     if (ulqt) {
  161.     if (TreeAgrees(color, ulqt)) {
  162.         QT_TreeNode_Destroy(ulqt);
  163.         ulqt = 0;
  164.     }
  165.     }
  166.     if (urqt) {
  167.     if (TreeAgrees(color, urqt)) {
  168.         QT_TreeNode_Destroy(urqt);
  169.         urqt = 0;
  170.     }
  171.     }
  172.     if (llqt) {
  173.     if (TreeAgrees(color, llqt)) {
  174.         QT_TreeNode_Destroy(llqt);
  175.         llqt = 0;
  176.     }
  177.     }
  178.     if (lrqt) {
  179.     if (TreeAgrees(color, lrqt)) {
  180.         QT_TreeNode_Destroy(lrqt);
  181.         lrqt = 0;
  182.     }
  183.     }
  184.     return (QT_TreeNode_New(color, ulqt, urqt, llqt, lrqt));
  185. }
  186.  
  187. static void     BitWrite(bit, fp)
  188. int             bit;
  189. FILE           *fp;
  190. {
  191.     if (bit)
  192.     BitBuffer |= (1 << BitPos);
  193.     else
  194.     BitBuffer &= ~(1 << BitPos);
  195.     if ((--BitPos) < 0) {
  196.     BitPos = 7;
  197.     fputc(BitBuffer, fp);
  198.     }
  199. }
  200.  
  201. #define BitFlush(fp) (fputc(BitBuffer,(fp)))
  202.  
  203. static void     QT_TreeNode_Write(fp, node, fmt)
  204. FILE           *fp;
  205. QT_TreeNode_t  *node;
  206. char            fmt;
  207. {
  208.     int             i;
  209.     QT_TreeNode_t  *child;
  210.  
  211.     switch (fmt) {
  212.     case 0:
  213.         BitWrite(0, fp);
  214.         BitWrite(QT_TreeNode_Color(node), fp);
  215.         for (i = 0; i < 4; ++i) {
  216.         if (child = QT_TreeNode_Child(node, i))
  217.             QT_TreeNode_Write(fp, child, fmt);
  218.         else
  219.             BitWrite(1, fp);
  220.         }
  221.         break;
  222.     case 1:
  223.         BitWrite(0, fp);
  224.         BitWrite(QT_TreeNode_Color(node), fp);
  225.         if (QT_TreeNode_Child(node, 0)
  226.         || QT_TreeNode_Child(node, 1)
  227.         || QT_TreeNode_Child(node, 2)
  228.         || QT_TreeNode_Child(node, 3)) {
  229.         for (i = 0; i < 4; ++i) {
  230.             if (child = QT_TreeNode_Child(node, i))
  231.             QT_TreeNode_Write(fp, child, fmt);
  232.             else {
  233.             BitWrite(1, fp);
  234.             BitWrite(0, fp);
  235.             }
  236.         }
  237.         }
  238.         else {
  239.         BitWrite(1, fp);
  240.         BitWrite(1, fp);
  241.         }
  242.         break;
  243.     }
  244. }
  245.  
  246. void            QT_Tree_Write(fp, node, fmt, w, h)
  247. FILE           *fp;
  248. QT_TreeNode_t  *node;
  249. char            fmt;
  250. short           w, h;
  251. {
  252.     BitPos = 7;
  253.     fputc(fmt, fp);
  254.     fputc(w % 256, fp);
  255.     fputc(w / 256, fp);
  256.     fputc(h % 256, fp);
  257.     fputc(h / 256, fp);
  258.     QT_TreeNode_Write(fp, node, fmt);
  259.     BitFlush(fp);
  260. }
  261.  
  262. static int      BitRead(fp)
  263. FILE           *fp;
  264. {
  265.     if ((--BitPos) < 0) {
  266.     BitPos = 7;
  267.     BitBuffer = fgetc(fp);
  268.     }
  269.     return (BitBuffer & (1 << BitPos));
  270. }
  271.  
  272. static QT_TreeNode_t *QT_TreeNode_Read(fp, fmt, extra)
  273. FILE           *fp;
  274. char            fmt;
  275. int            *extra;
  276. {
  277.     int             bit = BitRead(fp), bit2, nochildren, dummy;
  278.     QT_TreeNode_t  *ul, *ur, *ll, *lr;
  279.  
  280.     switch (fmt) {
  281.     case 0:
  282.         if (bit) {
  283.         return (0);
  284.         }
  285.         bit = BitRead(fp);
  286.         ul = QT_TreeNode_Read(fp, fmt, &dummy);
  287.         ur = QT_TreeNode_Read(fp, fmt, &dummy);
  288.         ll = QT_TreeNode_Read(fp, fmt, &dummy);
  289.         lr = QT_TreeNode_Read(fp, fmt, &dummy);
  290.         return (QT_TreeNode_New(bit, ul, ur, ll, lr));
  291.     case 1:
  292.         bit2 = BitRead(fp);
  293.         if (bit) {
  294.         *extra = bit2;
  295.         return (0);
  296.         }
  297.         ul = QT_TreeNode_Read(fp, fmt, &nochildren);
  298.         if ((!ul) && nochildren)
  299.         return (QT_TreeNode_New(bit2, 0, 0, 0, 0));
  300.         ur = QT_TreeNode_Read(fp, fmt, &dummy);
  301.         ll = QT_TreeNode_Read(fp, fmt, &dummy);
  302.         lr = QT_TreeNode_Read(fp, fmt, &dummy);
  303.         return (QT_TreeNode_New(bit2, ul, ur, ll, lr));
  304.     }
  305. }
  306.  
  307. QT_TreeNode_t  *QT_Tree_Read(fp, w, h)
  308. FILE           *fp;
  309. short          *w, *h;
  310. {
  311.     char            fmt = fgetc(fp);
  312.     int             dummy;
  313.  
  314.     BitPos = 0;
  315.     *w = fgetc(fp);
  316.     *w += fgetc(fp) * 256;
  317.     *h = fgetc(fp);
  318.     *h += fgetc(fp) * 256;
  319.     return (QT_TreeNode_Read(fp, fmt, &dummy));
  320. }
  321.  
  322. int             QT_Bitmap_Read(b, fp)  /* B is an *uninitialized* bitmap */
  323. QT_Bitmap_t    *b;
  324. FILE           *fp;
  325. {
  326.     int             x, y, c;
  327.     char            buf[4];
  328.     long            w, h;
  329.  
  330.     fread(buf, 4, 1, fp);
  331.     fread(&w, 4, 1, fp);
  332.     fread(&h, 4, 1, fp);
  333.     fread(buf, 2, 1, fp);
  334.     if (QT_Bitmap_Init(b, 0, 0, (int) w, (int) h, 0))
  335.     return (1);
  336.     BitPos = -1;
  337.     for (y = 0; y < h; ++y) {
  338.     for (x = 0; x < w; ++x) {
  339.         c = BitRead(fp);
  340.         QT_Bitmap_SetBit(b, x, y, !c);
  341.     }
  342.     BitPos = -1;
  343.     }
  344.     return (0);
  345. }
  346.