home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / graphics / utility / mandlbx1 / stitch.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-11-19  |  11.0 KB  |  396 lines
  1. /* stitch.c 1.0++, with no Rlink
  2. This program maintains a list of squares which define the area on the screen.
  3. Squares are doubly linked, and abutting squares must be 2x, 1x or .5x in size.
  4. Squares which are surrounded by neighbors of the same color do not get split.
  5. /**/
  6.  
  7. #include <define.h>
  8. #include <stdio.h>
  9. #include <debug.h>
  10. #include <osbind.h>
  11.  
  12. #define Nsquares 5000
  13. struct stitches
  14. {    int x, y, lev;        /* in raster coords */
  15.     int queue;
  16.     int count;
  17.     int nrec;
  18. /*    long Zr,Zi;/**/        /*        0 L            */
  19.     int Llink[4];        /*         +-------------+        */
  20. } *stp; /* st[Nsquares];    /*         |   links       |  1 L    */
  21. long nsquares;            /*         |  from this  |        */
  22.                 /*     3 L |   square    |          */
  23.                 /*         +-------------+        */
  24.                 /*            2 L        */
  25. int free_queue;
  26. int point_mode;            /* -1 = first box, 0 = boxes, 1 = point */
  27. #define LEVELS 10
  28. int queue[LEVELS], max_lev;
  29. int cos[5] = {0,0,1,1,0};
  30. int rot[5] = {0,1,0,-1,0};
  31. int xmax, ymax;
  32. int nrec;    /* debug recursive limit */
  33. int no_check;    /* shared with window */
  34.  
  35. st_inz(log_length, x, y)
  36. int log_length, x, y;
  37. {    int i, j;
  38.     register long rqd, got;
  39.     register struct stitches *st1;
  40.     xmax = x; ymax = y;
  41.     if (nsquares == 0)
  42.     {    got = Malloc( (long) -1);
  43.         rqd = 1<<log_length; rqd = rqd * rqd/4* sizeof(struct stitches);
  44.  
  45. /* the /8 below is very heuristic! most screens plot 50%, and the square 
  46.    defined is 1.5x horiz and 2.5x vertical. 2*1.5*2.5 =~ 8 */
  47.  
  48.         if (got < rqd/8)    
  49.         {    /*view_screen();*/
  50.             if (1==form_alert(0, "[1][Need more memory! Otherwise\
  51. |inacurate pictures will be|drawn. Remove RAMDISKS, etc.|and restart]\
  52. [exit|try anyhow]"))        exit();
  53.             /*draw_on_screen();*/
  54.         }
  55.         if (got > rqd) got = rqd;
  56.         stp = Malloc(got);
  57.         if (stp == 0) 
  58.             panic("Error getting memory for BOX data structure\n");
  59.         nsquares = got/sizeof(struct stitches);
  60.     }
  61.     free_queue = 2;            /* form free queue */
  62.     point_mode = -1;
  63.     for (st1=stp, i=0; i<nsquares; i++)
  64.     {    register int *p;
  65.         p = (int *) st1;    /* clear whole structure: */
  66.         for (j=sizeof(struct stitches)/sizeof(int); j>0; j--)
  67.             *p++ = 0;
  68.         if (i>=2)
  69.         {    st1->queue = i+1;
  70.             st1->lev = -1;
  71.         }
  72.         st1++;
  73.     }        
  74.     (stp+nsquares-1)->queue = 0;    /* end of free queue */
  75.  
  76.     stp->count = -1;        /* NULL has don't care color */
  77.     (stp+1)->lev = log_length;    /* starting box defined by args */
  78.     queue[log_length] = 1;        /* put starting box on work queue */
  79.  
  80.     max_lev = log_length;
  81.     for (i=0; i<log_length; i++)     /* all other queues are empty */
  82.         queue[i] = 0;
  83.     st_check("Inz");
  84. }
  85.  
  86. st_do_next()
  87. {   int i, lev, next_sq, count, nr;
  88.     struct stitches *p;
  89.     if (point_mode < 0)
  90.     {    (stp + 1)->count = dr_xy(0, 0, 1 << ((stp+1)->lev) );
  91.     point_mode = 0;
  92.     }
  93.     while (1)
  94.     {    for (lev = max_lev; queue[lev] == 0; )    /* find lowest level */
  95.     {    if (--lev < 0) 
  96.         {    dprintf(stderr, "queues %d-0 empty, returning (0)\n",
  97.                 max_lev);/**/
  98.             return (0);
  99.     }    }
  100.     dprintf(stderr, "dequeueing from queue[%d]: %d\n", lev, queue[lev]);/**/
  101.     next_sq = queue[lev];
  102.     queue[lev] = (stp+next_sq)->queue;        /* dequeue it */
  103.     if (lev >= max_lev -4 ) 
  104.     {    dprintf(stderr, "Too coarse: %d >= %d\n", lev, max_lev-1);/**/
  105.         st_check("C\b");/**/
  106.         st_chop(next_sq, 0);        /* do it if coarse */
  107.         return(1);
  108.     }
  109.     else if (lev != 0)
  110.     {    register int ncount;
  111.         register struct stitches *pl, *pr;
  112.         p = stp + next_sq;
  113.         count = p->count >>2;        /* >>2 is DIRTY */
  114.         dprintf(stderr, "n="); st_print(next_sq);
  115.         for (i = 0; i<4; i++)        /* do it if neighbors differnt*/
  116.         {    dprintf(stderr, "L=");st_print(p->Llink[i]);/**/
  117.             pl = stp + p->Llink[i];
  118.             ncount = pl->count >>2;
  119.             if ((ncount >=0)  && (count != ncount))
  120.             {    dprintf(stderr, "neighbor's color mismatchs\n");/**/
  121.                 st_check("c");
  122.                 st_chop(next_sq, 0);
  123.                 return (1);
  124.             }
  125.             if ((nr = pl->Llink[(i+1)&3]) == 0)
  126.                 continue;
  127.             dprintf(stderr, "R=", nr);/**/
  128.             ncount = (stp + nr)->count >>2;
  129.             if ((ncount >=0)  && (count != ncount))
  130.             {    dprintf(stderr, "neighbor's color mismatchs\n");/**/
  131.                 st_check("e");
  132.                 st_chop(next_sq, 0);
  133.                 return (1);
  134.         }    }
  135.         dprintf(stderr, "colors match, no need to split\n");/**/
  136.     }
  137.     else dprintf(stderr, "can't split -- at lowest level\n");/**/
  138. }   }
  139.        
  140.  
  141. st_chop(square, which)    /* into 4 subsquares, maintaining links, and that    */
  142. int square, which;    /*   all neighbors are within a factor of two in size*/
  143.             /* returns new[which] */
  144. {    /*register*/ struct stitches *p, *p_new[4], *p_neighbor, *p1;
  145.     struct stitches *p_new_i, *p_new_k;
  146.     int new[4], i, j, k, l, neighbor, l_n, lev, len, x, y; 
  147.     int m, qv, mask, *pq;
  148.  
  149.     nrec++;
  150.     p = stp + square;
  151.     if (point_mode)
  152.     {    register int foo;
  153. point__mode:    l = 1 << p->lev;
  154.         x = p->x; y = p->y;
  155.         
  156.         j=1;        /* all boxes except upper left one */
  157.         for (i=0; i<l; i++)
  158.         {    for (; j<l; j++)
  159.                 dr_xy(x+i, y+j, 1);
  160.             j=0;
  161.         }
  162.         return;
  163.     }
  164.     lev = p->lev - 1;
  165. /*    if (lev > max_lev) max_lev = lev;    /* update max level to work on*/
  166.     len = 1 << lev;
  167.     x = p->x;    y = p->y;
  168.  
  169.     for (i = 0; i<4; i++)
  170.     {    register int *pint;
  171.         if ((new[i]=free_queue)==0) 
  172.         {    point_mode = 1;
  173.             goto point__mode;
  174.             panic("Ran out of squares\n",0L,0L);/**/
  175.         }
  176.         p1 = stp + free_queue;
  177.         p_new[i] = p1;
  178.         free_queue = p1->queue;        /* grab new box */
  179.     }
  180.     pq = queue + lev;
  181.     qv = *pq;            /*enqueue "that work needs to be done"*/
  182.     mask = (x+len > xmax)*6 | (y+len > ymax)*12;
  183.     dprintf(stderr,"enqueue[%d]: ", lev);/**/
  184.     for (m=0; m<4; m++, mask >>=1)
  185.     {    if ((mask & 1)==0)    /* enqueue only if within screen */
  186.         {    *pq = new[m];
  187.             pq = &((stp + new[m])->queue);
  188.             dprintf(stderr,"%d#%x, ", new[m], mask);/**/
  189.     }    }
  190.     *pq = qv;            /* finish enqueue */
  191.     dprintf(stderr,"\n");/**/
  192.  
  193.     for (i = 0; i<4; i++)
  194.     {    k = i+1 & 3;
  195.         j = i+2 & 3;
  196.         l = i+3 & 3;
  197. /*        dprintf(stderr,"i=%d",i);/**/
  198.         p_new_i = p_new[i];
  199.         p_new_k = p_new[k];
  200.         p_new_i->x = x + cos[i+1]*len;
  201.         p_new_i->y = y + cos[i]*len;
  202.         p_new_i->lev = lev;
  203.         p_new_i->nrec = nrec;
  204.         p_new_i->Llink[k] = new[k];
  205.         p_new_k->Llink[l] = new[i];
  206.         if ((neighbor = p->Llink[i]) <= 0) 
  207.         {    /*dprintf(stderr,"null links\n");/**/
  208.             p_new_i->Llink[i] = 0;
  209.             p_new_k->Llink[i] = 0;
  210.         }else
  211.         {    p_neighbor = stp + neighbor;
  212.  
  213.             l_n = p->lev - p_neighbor->lev;
  214. /*            dprintf(stderr,"l_n=%d, ",l_n);/**/
  215.             if (l_n > 0)        /* if neighbors were smaller: */
  216.             {    /*dprintf(stderr,"neighbors were smaller\n");/**/
  217.                 p_new_i->Llink[i] = neighbor;    /* link left */
  218.                 p_neighbor->Llink[j] = new[i];
  219.  
  220.                 if (neighbor = p_neighbor->Llink[k])
  221.                 {    p_neighbor = stp + neighbor;
  222.                     p_new_k->Llink[i] = neighbor;    /* link right */
  223.                     p_neighbor->Llink[j] = new[k];
  224.                 }else
  225.                     panic("nei<, but no right one\n");
  226.             }    
  227.             else 
  228.             {        /* if neighbor was bigger, split him! */
  229.                 if (l_n < 0)     /* RECURSIVE CALL */
  230.                 {    m = (p_neighbor->Llink[j]==square)?j:l;
  231.                     neighbor = st_chop(neighbor, m);
  232. /*                    dprintf(stderr,"\ndone split, now neighbor=%d\n"
  233.                         , neighbor);/**/
  234.                     p_neighbor = stp + neighbor;
  235.                 }        /* neighbor was same size: */
  236. /*                dprintf(stderr,"neighbor was same size\n");/**/
  237.                 p_new_i->Llink[i] = neighbor;
  238.                 p_new_k->Llink[i] = neighbor;
  239.                 p_neighbor->Llink[j] = new[k];
  240.         }    }            
  241.         if (i==0)        /*split-up bead to upper-left bead */
  242.             p_new_i->count = p->count; 
  243.         else
  244.             p_new_i->count = dr_xy(p_new_i->x, p_new_i->y,
  245.                          1 << p_new_i->lev);
  246.     }
  247.     p->queue = free_queue;        /* split-up bead to free list */
  248.  
  249. /* diagnostic only */
  250.     p->lev = -1;
  251.     p->x = p->y = p->nrec  =0;
  252.     p->Llink[0] = p->Llink[1] = p->Llink[2] = p->Llink[3] = 0;
  253.  
  254.     free_queue = square;
  255.     return (new[which]);
  256. }
  257.  
  258. int chk, chk_i, chk_n, bchk;
  259. #define bcheck(arg1, arg2) check((bchk=(arg1))>=nsquares, 0, "arg2 > nsquares"); check(bchk<0, 0, "arg2 <0");
  260.  
  261. st_check(label)
  262. char *label;
  263. {   struct stitches *p, *p_I, *p_IJ, *p_IK;
  264.     int          n_I,  n_IJ,  n_IK, n_IKJ, n_IJL;
  265.     int         lev, lev_I; 
  266.     int      len, len_I;
  267.     int i, j, k, l;
  268.     int x, y, x1, y1, vx, vy; 
  269.  
  270.     nrec = 0;
  271.     if (no_check) return;    
  272.     printf(label);    
  273.     chk = free_queue;
  274.     while (chk)
  275.     {    register struct stitches *st1;
  276.     register int *a, b;
  277.     st1 = stp + chk;
  278.     check(st1->x ==0 && st1->y == 0 && st1->nrec ==0, 1, 
  279.                    "free queue clobbered");
  280.     for (a = &(st1->Llink[0]), b=0; b++<4;)
  281.         if (*a++ != 0)
  282.             check (0,1,"free queue link element clobbered");
  283.         check(st1->lev == -1, 1, "free queue element not -1");
  284.     bcheck (chk = st1->queue, free_queue);
  285.     }
  286.     for (chk = 1; chk<nsquares; chk++)
  287.     {    p = stp + chk;
  288.     x = p->x;    y = p->y;
  289.     if ((lev = p->lev) <0)
  290.         continue;        /* don't process if on free queue*/
  291.     len = 1 << lev;
  292.  
  293.     for (i = 0; i<4; i++)
  294.     {    k = i+1 & 3;
  295.         j = i+2 & 3;
  296.         l = i+3 & 3;
  297.         chk_i = i;
  298.         bcheck(    chk_n = n_I = p->Llink[i], Llink);
  299.  
  300.         if (n_I == 0)
  301.             continue;
  302.         p_I = stp + n_I;
  303.  
  304.         lev_I = p_I->lev;
  305.         len_I = 1 << lev_I;
  306.         bcheck(n_IJ= p_I->Llink[j], n_IJ);
  307.         p_IJ = stp + n_IJ;
  308.         switch (lev - lev_I) /* relative size of neighbors */
  309.         {   case (-1):        /* neighbor bigger */
  310.             vy = -6;
  311.             if (n_IJ == chk)            
  312.                 vx = -2;
  313.             else
  314.             {    vx = 2;
  315.                 bcheck(n_IJL = p_IJ->Llink[l], n_IJL);
  316.                 check(n_IJL, chk, "n_IJL != chk");
  317.             }
  318.             break;
  319.             case (0):        /* neighbor same size */
  320.             vy = -4; vx = 0;
  321.             check(n_IJ,chk,"n_IJ != chk");
  322.             break;
  323.             case (1):        /* neighbor smaller */
  324.             vy = -3; vx = -1;
  325.  
  326.             bcheck(n_IK = p_I->Llink[k], n_IK);
  327.             p_IK = stp + n_IK;
  328.             bcheck(n_IKJ = p_IK->Llink[j], n_IKJ);
  329.             check(n_IKJ, chk, "n_IKJ != chk");
  330.             break;    
  331.             default:
  332.             check(1,0, "sizes not within factor of 2");
  333.         }
  334.         x1 = x + ((2 + rot[i+1]*vx - rot[i]*vy)*len-2*len_I)/4;
  335.         y1 = y + ((2 + rot[i]*vx + rot[i+1]*vy)*len-2*len_I)/4;
  336.         check(p_I->x, x1,"x bad");
  337.         check(p_I->y, y1,"y bad");
  338. }   }    }    
  339.  
  340. check(a, b, str)
  341. int a, b;
  342. char *str;
  343. {    if (a == b) return;
  344.     printf("==========\n%d|%d Inconsistent with %d\n", chk, chk_i, chk_n);
  345.     printf("'%s', %d != %d.\n", str, a, b);
  346.     st_pl("base", chk);
  347.     st_pl("neighbor", chk_n);
  348.     st_kbd();
  349. }
  350.  
  351. st_kbd()
  352. {    char input[50], *ip;
  353.     int i;
  354.     while(1)
  355.     {    printf("-* ");
  356.         for (ip=input; (*ip=getchar()) != ' '; ip++);
  357.         *ip = 0;
  358.         switch (input[0])
  359.         {   case ('q'): return;
  360.             case ('c'): no_check = 1-no_check;
  361.             case ('C'): 
  362.             scanf(input+1, "%d", &i);
  363.             printf("Next pass will be %d\n",i);
  364.             chk = i-1;
  365.             return;
  366.             case ('e'): chk = nsquares; break;    
  367.             case ('?'):
  368.             printf("*q*uit, *c*heck off, *e*nd pass\n");
  369.             printf("*C*heck <n>, term with ' '\n");
  370.             break;
  371.             default:
  372.             sscanf(input, "%d",&i);
  373.             st_pl("kbd",i);
  374. }    }    }
  375.  
  376. st_pl(name,s)
  377. char *name;
  378. int s;
  379. {    register struct stitches *stf;
  380.     int i;
  381.     stf = stp + s;
  382.     printf("%s: L%d/%d/%d/%d nr=%d\n (%d) q=%d     (%d,%d)-%d\n",
  383.       name, stf->Llink[0], stf->Llink[1], stf->Llink[2], stf->Llink[3],
  384.       stf->nrec, s, stf->queue,stf->x, stf->y, ((i=stf->lev) >=0)? 1<<i: i);
  385. }
  386.  
  387. st_print(s)
  388. int s;
  389. {    register struct stitches *stf;
  390.     stf = stp + s;
  391.     dprintf(stderr,"%d c%d %d/%d/%d/%d (%d,%d)-%d\n",
  392.       s, stf->count,
  393.       stf->Llink[0], stf->Llink[1], stf->Llink[2], stf->Llink[3],
  394.       stf->x, stf->y, 1<<stf->lev);/**/
  395. }
  396.