home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / X / mit / server / ddx / mi / miregion.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-07-06  |  62.5 KB  |  2,397 lines
  1. /***********************************************************
  2. Copyright 1987, 1988, 1989 by 
  3. Digital Equipment Corporation, Maynard, Massachusetts, and
  4. the Massachusetts Institute of Technology, Cambridge, Massachusetts.
  5.  
  6.                         All Rights Reserved
  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 the above copyright notice appear in all copies and that
  11. both that copyright notice and this permission notice appear in 
  12. supporting documentation, and that the names of Digital or MIT not be
  13. used in advertising or publicity pertaining to distribution of the
  14. software without specific, written prior permission.  
  15.  
  16. DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  17. ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  18. DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  19. ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  20. WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  21. ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  22. SOFTWARE.
  23.  
  24. ******************************************************************/
  25. /* $XConsortium: miregion.c,v 1.55 91/07/06 14:02:29 rws Exp $ */
  26.  
  27. #include <stdio.h>
  28. #include "miscstruct.h"
  29. #include "regionstr.h"
  30. #include "Xprotostr.h"
  31. #include "gc.h"
  32.  
  33. #if defined (__GNUC__) && !defined (NO_INLINES)
  34. #define INLINE    __inline
  35. #else
  36. #define INLINE
  37. #endif
  38.  
  39. /*
  40.  * hack until callers of these functions can deal with out-of-memory
  41.  */
  42.  
  43. extern Bool Must_have_memory;
  44.  
  45. #ifdef DEBUG
  46. #define assert(expr) {if (!(expr)) \
  47.         FatalError("Assertion failed file %s, line %d: expr\n", \
  48.             __FILE__, __LINE__); }
  49. #else
  50. #define assert(expr)
  51. #endif
  52.  
  53. #define good(reg) assert(miValidRegion(reg))
  54.  
  55. /*
  56.  * The functions in this file implement the Region abstraction used extensively
  57.  * throughout the X11 sample server. A Region is simply a set of disjoint
  58.  * (non-overlapping) rectangles, plus an "extent" rectangle which is the
  59.  * smallest single rectangle that contains all the non-overlapping rectangles.
  60.  *
  61.  * A Region is implemented as a "y-x-banded" array of rectangles.  This array
  62.  * imposes two degrees of order.  First, all rectangles are sorted by top side
  63.  * y coordinate first (y1), and then by left side x coordinate (x1).
  64.  *
  65.  * Furthermore, the rectangles are grouped into "bands".  Each rectangle in a
  66.  * band has the same top y coordinate (y1), and each has the same bottom y
  67.  * coordinate (y2).  Thus all rectangles in a band differ only in their left
  68.  * and right side (x1 and x2).  Bands are implicit in the array of rectangles:
  69.  * there is no separate list of band start pointers.
  70.  *
  71.  * The y-x band representation does not minimize rectangles.  In particular,
  72.  * if a rectangle vertically crosses a band (the rectangle has scanlines in 
  73.  * the y1 to y2 area spanned by the band), then the rectangle may be broken
  74.  * down into two or more smaller rectangles stacked one atop the other. 
  75.  *
  76.  *  -----------                    -----------
  77.  *  |         |                    |         |            band 0
  78.  *  |         |  --------            -----------  --------
  79.  *  |         |  |      |  in y-x banded    |         |  |      |   band 1
  80.  *  |         |  |      |  form is        |         |  |      |
  81.  *  -----------  |      |            -----------  --------
  82.  *               |      |                 |      |   band 2
  83.  *               --------                 --------
  84.  *
  85.  * An added constraint on the rectangles is that they must cover as much
  86.  * horizontal area as possible: no two rectangles within a band are allowed
  87.  * to touch.
  88.  *
  89.  * Whenever possible, bands will be merged together to cover a greater vertical
  90.  * distance (and thus reduce the number of rectangles). Two bands can be merged
  91.  * only if the bottom of one touches the top of the other and they have
  92.  * rectangles in the same places (of the same width, of course).
  93.  *
  94.  * Adam de Boor wrote most of the original region code.  Joel McCormack
  95.  * substantially modified or rewrote most of the core arithmetic routines,
  96.  * and added miRegionValidate in order to support several speed improvements
  97.  * to miValidateTree.  Bob Scheifler changed the representation to be more
  98.  * compact when empty or a single rectangle, and did a bunch of gratuitous
  99.  * reformatting.
  100.  */
  101.  
  102. /*  true iff two Boxes overlap */
  103. #define EXTENTCHECK(r1,r2) \
  104.       (!( ((r1)->x2 <= (r2)->x1)  || \
  105.           ((r1)->x1 >= (r2)->x2)  || \
  106.           ((r1)->y2 <= (r2)->y1)  || \
  107.           ((r1)->y1 >= (r2)->y2) ) )
  108.  
  109. /* true iff (x,y) is in Box */
  110. #define INBOX(r,x,y) \
  111.       ( ((r)->x2 >  x) && \
  112.         ((r)->x1 <= x) && \
  113.         ((r)->y2 >  y) && \
  114.         ((r)->y1 <= y) )
  115.  
  116. /* true iff Box r1 contains Box r2 */
  117. #define SUBSUMES(r1,r2) \
  118.       ( ((r1)->x1 <= (r2)->x1) && \
  119.         ((r1)->x2 >= (r2)->x2) && \
  120.         ((r1)->y1 <= (r2)->y1) && \
  121.         ((r1)->y2 >= (r2)->y2) )
  122.  
  123. #define xallocData(n) (RegDataPtr)xalloc(REGION_SZOF(n))
  124. #define xfreeData(reg) if ((reg)->data && (reg)->data->size) xfree((reg)->data)
  125.  
  126. #define RECTALLOC(pReg,n) \
  127. if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
  128.     miRectAlloc(pReg, n)
  129.  
  130. #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2)    \
  131. {                        \
  132.     pNextRect->x1 = nx1;            \
  133.     pNextRect->y1 = ny1;            \
  134.     pNextRect->x2 = nx2;            \
  135.     pNextRect->y2 = ny2;            \
  136.     pNextRect++;                \
  137. }
  138.  
  139. #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2)            \
  140. {                                    \
  141.     if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
  142.     {                                    \
  143.     miRectAlloc(pReg, 1);                        \
  144.     pNextRect = REGION_TOP(pReg);                    \
  145.     }                                    \
  146.     ADDRECT(pNextRect,nx1,ny1,nx2,ny2);                    \
  147.     pReg->data->numRects++;                        \
  148.     assert(pReg->data->numRects<=pReg->data->size);            \
  149. }
  150.  
  151.  
  152. #define DOWNSIZE(reg,numRects)                         \
  153. if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
  154. {                                     \
  155.     RegDataPtr NewData;                             \
  156.     NewData = (RegDataPtr)xrealloc((reg)->data, REGION_SZOF(numRects));     \
  157.     if (NewData)                             \
  158.     {                                     \
  159.     NewData->size = (numRects);                     \
  160.     (reg)->data = NewData;                         \
  161.     }                                     \
  162. }
  163.  
  164.  
  165. static BoxRec EmptyBox = {0, 0, 0, 0};
  166. static RegDataRec EmptyData = {0, 0};
  167.  
  168. #ifdef DEBUG
  169. int
  170. miPrintRegion(rgn)
  171.     RegionPtr rgn;
  172. {
  173.     int num, size;
  174.     register int i;
  175.     BoxPtr rects;
  176.  
  177.     num = REGION_NUM_RECTS(rgn);
  178.     size = REGION_SIZE(rgn);
  179.     rects = REGION_RECTS(rgn);
  180.     ErrorF("num: %d size: %d\n", num, size);
  181.     ErrorF("extents: %d %d %d %d\n",
  182.        rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
  183.     for (i = 0; i < num; i++)
  184.       ErrorF("%d %d %d %d \n",
  185.          rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
  186.     ErrorF("\n");
  187.     return(num);
  188. }
  189.  
  190.  
  191. Bool
  192. miRegionsEqual(reg1, reg2)
  193.     RegionPtr reg1;
  194.     RegionPtr reg2;
  195. {
  196.     int i;
  197.     BoxPtr rects1, rects2;
  198.  
  199.     if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
  200.     if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
  201.     if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
  202.     if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
  203.     if (REGION_NUM_RECTS(reg1) != REGION_NUM_RECTS(reg2)) return FALSE;
  204.     
  205.     rects1 = REGION_RECTS(reg1);
  206.     rects2 = REGION_RECTS(reg2);
  207.     for (i = 0; i != REGION_NUM_RECTS(reg1); i++) {
  208.     if (rects1[i].x1 != rects2[i].x1) return FALSE;
  209.     if (rects1[i].x2 != rects2[i].x2) return FALSE;
  210.     if (rects1[i].y1 != rects2[i].y1) return FALSE;
  211.     if (rects1[i].y2 != rects2[i].y2) return FALSE;
  212.     }
  213.     return TRUE;
  214. }
  215.  
  216. Bool
  217. miValidRegion(reg)
  218.     RegionPtr reg;
  219. {
  220.     register int i, numRects;
  221.  
  222.     if ((reg->extents.x1 > reg->extents.x2) ||
  223.     (reg->extents.y1 > reg->extents.y2))
  224.     return FALSE;
  225.     numRects = REGION_NUM_RECTS(reg);
  226.     if (!numRects)
  227.     return ((reg->extents.x1 == reg->extents.x2) &&
  228.         (reg->extents.y1 == reg->extents.y2) &&
  229.         (reg->data->size || (reg->data == &EmptyData)));
  230.     else if (numRects == 1)
  231.     return (!reg->data);
  232.     else
  233.     {
  234.     register BoxPtr pboxP, pboxN;
  235.     BoxRec box;
  236.  
  237.     pboxP = REGION_RECTS(reg);
  238.     box = *pboxP;
  239.     box.y2 = pboxP[numRects-1].y2;
  240.     pboxN = pboxP + 1;
  241.     for (i = numRects; --i > 0; pboxP++, pboxN++)
  242.     {
  243.         if ((pboxN->x1 >= pboxN->x2) ||
  244.         (pboxN->y1 >= pboxN->y2))
  245.         return FALSE;
  246.         if (pboxN->x1 < box.x1)
  247.             box.x1 = pboxN->x1;
  248.         if (pboxN->x2 > box.x2)
  249.         box.x2 = pboxN->x2;
  250.         if ((pboxN->y1 < pboxP->y1) ||
  251.         ((pboxN->y1 == pboxP->y1) &&
  252.          ((pboxN->x1 < pboxP->x2) || (pboxN->y2 != pboxP->y2))))
  253.         return FALSE;
  254.     }
  255.     return ((box.x1 == reg->extents.x1) &&
  256.         (box.x2 == reg->extents.x2) &&
  257.         (box.y1 == reg->extents.y1) &&
  258.         (box.y2 == reg->extents.y2));
  259.     }
  260. }
  261.  
  262. #endif /* DEBUG */
  263.  
  264.  
  265. /*****************************************************************
  266.  *   RegionCreate(rect, size)
  267.  *     This routine does a simple malloc to make a structure of
  268.  *     REGION of "size" number of rectangles.
  269.  *****************************************************************/
  270.  
  271. RegionPtr
  272. miRegionCreate(rect, size)
  273.     BoxPtr rect;
  274.     int size;
  275. {
  276.     register RegionPtr pReg;
  277.    
  278.     Must_have_memory = TRUE; /* XXX */
  279.     pReg = (RegionPtr)xalloc(sizeof(RegionRec));
  280.     Must_have_memory = FALSE; /* XXX */
  281.     if (rect)
  282.     {
  283.     pReg->extents = *rect;
  284.     pReg->data = (RegDataPtr)NULL;
  285.     }
  286.     else
  287.     {
  288.     pReg->extents = EmptyBox;
  289.     if ((size > 1) && (pReg->data = xallocData(size)))
  290.     {
  291.         pReg->data->size = size;
  292.         pReg->data->numRects = 0;
  293.     }
  294.     else
  295.         pReg->data = &EmptyData;
  296.     }
  297.     return(pReg);
  298. }
  299.  
  300. /*****************************************************************
  301.  *   RegionInit(pReg, rect, size)
  302.  *     Outer region rect is statically allocated.
  303.  *****************************************************************/
  304.  
  305. void
  306. miRegionInit(pReg, rect, size)
  307.     RegionPtr pReg;
  308.     BoxPtr rect;
  309.     int size;
  310. {
  311.     if (rect)
  312.     {
  313.     pReg->extents = *rect;
  314.     pReg->data = (RegDataPtr)NULL;
  315.     }
  316.     else
  317.     {
  318.     pReg->extents = EmptyBox;
  319.     if ((size > 1) && (pReg->data = xallocData(size)))
  320.     {
  321.         pReg->data->size = size;
  322.         pReg->data->numRects = 0;
  323.     }
  324.     else
  325.         pReg->data = &EmptyData;
  326.     }
  327. }
  328.  
  329. void
  330. miRegionDestroy(pReg)
  331.     RegionPtr pReg;
  332. {
  333.     good(pReg);
  334.     xfreeData(pReg);
  335.     xfree(pReg);
  336. }
  337.  
  338. void
  339. miRegionUninit(pReg)
  340.     RegionPtr pReg;
  341. {
  342.     good(pReg);
  343.     xfreeData(pReg);
  344. }
  345.  
  346. Bool
  347. miRectAlloc(pRgn, n)
  348.     register RegionPtr pRgn;
  349.     int n;
  350. {
  351.     Must_have_memory = TRUE; /* XXX */
  352.     if (!pRgn->data)
  353.     {
  354.     n++;
  355.     pRgn->data = xallocData(n);
  356.     pRgn->data->numRects = 1;
  357.     *REGION_BOXPTR(pRgn) = pRgn->extents;
  358.     }
  359.     else if (!pRgn->data->size)
  360.     {
  361.     pRgn->data = xallocData(n);
  362.     pRgn->data->numRects = 0;
  363.     }
  364.     else
  365.     {
  366.     if (n == 1)
  367.     {
  368.         n = pRgn->data->numRects;
  369.         if (n > 500) /* XXX pick numbers out of a hat */
  370.         n = 250;
  371.     }
  372.     n += pRgn->data->numRects;
  373.     pRgn->data = (RegDataPtr)xrealloc(pRgn->data, REGION_SZOF(n));
  374.     }
  375.     Must_have_memory = FALSE; /* XXX */
  376.     pRgn->data->size = n;
  377.     return TRUE;
  378. }
  379.  
  380. Bool
  381. miRegionCopy(dst, src)
  382.     register RegionPtr dst;
  383.     register RegionPtr src;
  384. {
  385.     good(dst);
  386.     good(src);
  387.     if (dst == src)
  388.     return TRUE;
  389.     dst->extents = src->extents;
  390.     if (!src->data || !src->data->numRects)
  391.     {
  392.     xfreeData(dst);
  393.     dst->data = src->data;
  394.     return TRUE;
  395.     }
  396.     if (!dst->data || (dst->data->size < src->data->numRects))
  397.     {
  398.     xfreeData(dst);
  399.     Must_have_memory = TRUE; /* XXX */
  400.     dst->data = xallocData(src->data->numRects);
  401.     Must_have_memory = FALSE; /* XXX */
  402.     dst->data->size = src->data->numRects;
  403.     }
  404.     dst->data->numRects = src->data->numRects;
  405.     bcopy((char *)REGION_BOXPTR(src), (char *)REGION_BOXPTR(dst),
  406.       dst->data->numRects * sizeof(BoxRec));
  407.     return TRUE;
  408. }
  409.  
  410.  
  411. /*======================================================================
  412.  *        Generic Region Operator
  413.  *====================================================================*/
  414.  
  415. /*-
  416.  *-----------------------------------------------------------------------
  417.  * miCoalesce --
  418.  *    Attempt to merge the boxes in the current band with those in the
  419.  *    previous one.  We are guaranteed that the current band extends to
  420.  *      the end of the rects array.  Used only by miRegionOp.
  421.  *
  422.  * Results:
  423.  *    The new index for the previous band.
  424.  *
  425.  * Side Effects:
  426.  *    If coalescing takes place:
  427.  *        - rectangles in the previous band will have their y2 fields
  428.  *          altered.
  429.  *        - pReg->data->numRects will be decreased.
  430.  *
  431.  *-----------------------------------------------------------------------
  432.  */
  433. INLINE static int
  434. miCoalesce (pReg, prevStart, curStart)
  435.     register RegionPtr    pReg;            /* Region to coalesce             */
  436.     int                  prevStart;      /* Index of start of previous band   */
  437.     int                  curStart;       /* Index of start of current band    */
  438. {
  439.     register BoxPtr    pPrevBox;       /* Current box in previous band         */
  440.     register BoxPtr    pCurBox;        /* Current box in current band       */
  441.     register int      numRects;    /* Number rectangles in both bands   */
  442.     register int    y2;        /* Bottom of current band         */
  443.     /*
  444.      * Figure out how many rectangles are in the band.
  445.      */
  446.     numRects = curStart - prevStart;
  447.     assert(numRects == pReg->data->numRects - curStart);
  448.  
  449.     if (!numRects) return curStart;
  450.  
  451.     /*
  452.      * The bands may only be coalesced if the bottom of the previous
  453.      * matches the top scanline of the current.
  454.      */
  455.     pPrevBox = REGION_BOX(pReg, prevStart);
  456.     pCurBox = REGION_BOX(pReg, curStart);
  457.     if (pPrevBox->y2 != pCurBox->y1) return curStart;
  458.  
  459.     /*
  460.      * Make sure the bands have boxes in the same places. This
  461.      * assumes that boxes have been added in such a way that they
  462.      * cover the most area possible. I.e. two boxes in a band must
  463.      * have some horizontal space between them.
  464.      */
  465.     y2 = pCurBox->y2;
  466.  
  467.     do {
  468.     if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) {
  469.         return (curStart);
  470.     }
  471.     pPrevBox++;
  472.     pCurBox++;
  473.     numRects--;
  474.     } while (numRects);
  475.  
  476.     /*
  477.      * The bands may be merged, so set the bottom y of each box
  478.      * in the previous band to the bottom y of the current band.
  479.      */
  480.     numRects = curStart - prevStart;
  481.     pReg->data->numRects -= numRects;
  482.     do {
  483.     pPrevBox--;
  484.     pPrevBox->y2 = y2;
  485.     numRects--;
  486.     } while (numRects);
  487.     return prevStart;
  488. }
  489.  
  490.  
  491. /* Quicky macro to avoid trivial reject procedure calls to miCoalesce */
  492.  
  493. #define Coalesce(newReg, prevBand, curBand)                \
  494.     if (curBand - prevBand == newReg->data->numRects - curBand) {    \
  495.     prevBand = miCoalesce(newReg, prevBand, curBand);        \
  496.     } else {                                \
  497.     prevBand = curBand;                        \
  498.     }
  499.  
  500. /*-
  501.  *-----------------------------------------------------------------------
  502.  * miAppendNonO --
  503.  *    Handle a non-overlapping band for the union and subtract operations.
  504.  *      Just adds the (top/bottom-clipped) rectangles into the region.
  505.  *      Doesn't have to check for subsumption or anything.
  506.  *
  507.  * Results:
  508.  *    None.
  509.  *
  510.  * Side Effects:
  511.  *    pReg->data->numRects is incremented and the rectangles overwritten
  512.  *    with the rectangles we're passed.
  513.  *
  514.  *-----------------------------------------------------------------------
  515.  */
  516.  
  517. INLINE static Bool
  518. miAppendNonO (pReg, r, rEnd, y1, y2)
  519.     register RegionPtr    pReg;
  520.     register BoxPtr    r;
  521.     BoxPtr            rEnd;
  522.     register int      y1;
  523.     register int      y2;
  524. {
  525.     register BoxPtr    pNextRect;
  526.     register int    newRects;
  527.  
  528.     newRects = rEnd - r;
  529.  
  530.     assert(y1 < y2);
  531.     assert(newRects != 0);
  532.  
  533.     /* Make sure we have enough space for all rectangles to be added */
  534.     RECTALLOC(pReg, newRects);
  535.     pNextRect = REGION_TOP(pReg);
  536.     pReg->data->numRects += newRects;
  537.     do {
  538.     assert(r->x1 < r->x2);
  539.     ADDRECT(pNextRect, r->x1, y1, r->x2, y2);
  540.     r++;
  541.     } while (r != rEnd);
  542.  
  543.     return TRUE;
  544. }
  545.  
  546. #define FindBand(r, rBandEnd, rEnd, ry1)            \
  547. {                                \
  548.     ry1 = r->y1;                        \
  549.     rBandEnd = r+1;                        \
  550.     while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) {   \
  551.     rBandEnd++;                        \
  552.     }                                \
  553. }
  554.  
  555. #define    AppendRegions(newReg, r, rEnd)                    \
  556. {                                    \
  557.     int newRects;                            \
  558.     if (newRects = rEnd - r) {                        \
  559.     RECTALLOC(newReg, newRects);                    \
  560.     bcopy((char *)r, (char *)REGION_TOP(newReg),            \
  561.               newRects * sizeof(BoxRec));                \
  562.     newReg->data->numRects += newRects;                \
  563.     }                                    \
  564. }
  565.  
  566. /*-
  567.  *-----------------------------------------------------------------------
  568.  * miRegionOp --
  569.  *    Apply an operation to two regions. Called by miUnion, miInverse,
  570.  *    miSubtract, miIntersect....  Both regions MUST have at least one
  571.  *      rectangle, and cannot be the same object.
  572.  *
  573.  * Results:
  574.  *    TRUE if successful.
  575.  *
  576.  * Side Effects:
  577.  *    The new region is overwritten.
  578.  *    pOverlap set to TRUE if overlapFunc ever returns TRUE.
  579.  *
  580.  * Notes:
  581.  *    The idea behind this function is to view the two regions as sets.
  582.  *    Together they cover a rectangle of area that this function divides
  583.  *    into horizontal bands where points are covered only by one region
  584.  *    or by both. For the first case, the nonOverlapFunc is called with
  585.  *    each the band and the band's upper and lower extents. For the
  586.  *    second, the overlapFunc is called to process the entire band. It
  587.  *    is responsible for clipping the rectangles in the band, though
  588.  *    this function provides the boundaries.
  589.  *    At the end of each band, the new region is coalesced, if possible,
  590.  *    to reduce the number of rectangles in the region.
  591.  *
  592.  *-----------------------------------------------------------------------
  593.  */
  594. static Bool
  595. miRegionOp(newReg, reg1, reg2, overlapFunc, appendNon1, appendNon2, pOverlap)
  596.     RegionPtr       newReg;            /* Place to store result         */
  597.     RegionPtr       reg1;            /* First region in operation     */
  598.     RegionPtr       reg2;            /* 2d region in operation        */
  599.     Bool        (*overlapFunc)();       /* Function to call for over-
  600.                          * lapping bands             */
  601.     Bool        appendNon1;            /* Append non-overlapping bands  */
  602.                         /* in region 1 ? */
  603.     Bool        appendNon2;            /* Append non-overlapping bands  */
  604.                         /* in region 2 ? */
  605.     Bool        *pOverlap;
  606. {
  607.     register BoxPtr r1;                /* Pointer into first region     */
  608.     register BoxPtr r2;                /* Pointer into 2d region         */
  609.     BoxPtr        r1End;            /* End of 1st region         */
  610.     BoxPtr        r2End;            /* End of 2d region             */
  611.     short        ybot;            /* Bottom of intersection         */
  612.     short        ytop;            /* Top of intersection         */
  613.     RegDataPtr        oldData;            /* Old data for newReg         */
  614.     int            prevBand;            /* Index of start of
  615.                          * previous band in newReg       */
  616.     int            curBand;            /* Index of start of current
  617.                          * band in newReg             */
  618.     register BoxPtr r1BandEnd;            /* End of current band in r1     */
  619.     register BoxPtr r2BandEnd;            /* End of current band in r2     */
  620.     short        top;            /* Top of non-overlapping band   */
  621.     short        bot;            /* Bottom of non-overlapping band*/
  622.     register int    r1y1;            /* Temps for r1->y1 and r2->y1   */
  623.     register int    r2y1;
  624.     int            newSize;
  625.     int            numRects;
  626.  
  627.     /*
  628.      * Initialization:
  629.      *    set r1, r2, r1End and r2End appropriately, save the rectangles
  630.      * of the destination region until the end in case it's one of
  631.      * the two source regions, then mark the "new" region empty, allocating
  632.      * another array of rectangles for it to use.
  633.      */
  634.  
  635.     r1 = REGION_RECTS(reg1);
  636.     newSize = REGION_NUM_RECTS(reg1);
  637.     r1End = r1 + newSize;
  638.     numRects = REGION_NUM_RECTS(reg2);
  639.     r2 = REGION_RECTS(reg2);
  640.     r2End = r2 + numRects;
  641.     assert(r1 != r1End);
  642.     assert(r2 != r2End);
  643.  
  644.     oldData = (RegDataPtr)NULL;
  645.     if (((newReg == reg1) && (newSize > 1)) ||
  646.     ((newReg == reg2) && (numRects > 1)))
  647.     {
  648.     oldData = newReg->data;
  649.     newReg->data = &EmptyData;
  650.     }
  651.     /* guess at new size */
  652.     if (numRects > newSize)
  653.     newSize = numRects;
  654.     newSize <<= 1;
  655.     if (!newReg->data)
  656.     newReg->data = &EmptyData;
  657.     else if (newReg->data->size)
  658.     newReg->data->numRects = 0;
  659.     if (newSize > newReg->data->size)
  660.     miRectAlloc(newReg, newSize);
  661.  
  662.     /*
  663.      * Initialize ybot.
  664.      * In the upcoming loop, ybot and ytop serve different functions depending
  665.      * on whether the band being handled is an overlapping or non-overlapping
  666.      * band.
  667.      *     In the case of a non-overlapping band (only one of the regions
  668.      * has points in the band), ybot is the bottom of the most recent
  669.      * intersection and thus clips the top of the rectangles in that band.
  670.      * ytop is the top of the next intersection between the two regions and
  671.      * serves to clip the bottom of the rectangles in the current band.
  672.      *    For an overlapping band (where the two regions intersect), ytop clips
  673.      * the top of the rectangles of both regions and ybot clips the bottoms.
  674.      */
  675.  
  676.     ybot = min(r1->y1, r2->y1);
  677.     
  678.     /*
  679.      * prevBand serves to mark the start of the previous band so rectangles
  680.      * can be coalesced into larger rectangles. qv. miCoalesce, above.
  681.      * In the beginning, there is no previous band, so prevBand == curBand
  682.      * (curBand is set later on, of course, but the first band will always
  683.      * start at index 0). prevBand and curBand must be indices because of
  684.      * the possible expansion, and resultant moving, of the new region's
  685.      * array of rectangles.
  686.      */
  687.     prevBand = 0;
  688.     
  689.     do {
  690.     /*
  691.      * This algorithm proceeds one source-band (as opposed to a
  692.      * destination band, which is determined by where the two regions
  693.      * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
  694.      * rectangle after the last one in the current band for their
  695.      * respective regions.
  696.      */
  697.     assert(r1 != r1End);
  698.     assert(r2 != r2End);
  699.     
  700.     FindBand(r1, r1BandEnd, r1End, r1y1);
  701.     FindBand(r2, r2BandEnd, r2End, r2y1);
  702.  
  703.     /*
  704.      * First handle the band that doesn't intersect, if any.
  705.      *
  706.      * Note that attention is restricted to one band in the
  707.      * non-intersecting region at once, so if a region has n
  708.      * bands between the current position and the next place it overlaps
  709.      * the other, this entire loop will be passed through n times.
  710.      */
  711.     if (r1y1 < r2y1) {
  712.         if (appendNon1) {
  713.         top = max(r1y1, ybot);
  714.         bot = min(r1->y2, r2y1);
  715.         if (top != bot)    {
  716.             curBand = newReg->data->numRects;
  717.             miAppendNonO(newReg, r1, r1BandEnd, top, bot);
  718.             Coalesce(newReg, prevBand, curBand);
  719.         }
  720.         }
  721.         ytop = r2y1;
  722.     } else if (r2y1 < r1y1) {
  723.         if (appendNon2) {
  724.         top = max(r2y1, ybot);
  725.         bot = min(r2->y2, r1y1);
  726.         if (top != bot) {
  727.             curBand = newReg->data->numRects;
  728.             miAppendNonO(newReg, r2, r2BandEnd, top, bot);
  729.             Coalesce(newReg, prevBand, curBand);
  730.         }
  731.         }
  732.         ytop = r1y1;
  733.     } else {
  734.         ytop = r1y1;
  735.     }
  736.  
  737.     /*
  738.      * Now see if we've hit an intersecting band. The two bands only
  739.      * intersect if ybot > ytop
  740.      */
  741.     ybot = min(r1->y2, r2->y2);
  742.     if (ybot > ytop) {
  743.         curBand = newReg->data->numRects;
  744.         (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot,
  745.                 pOverlap);
  746.         Coalesce(newReg, prevBand, curBand);
  747.     }
  748.  
  749.     /*
  750.      * If we've finished with a band (y2 == ybot) we skip forward
  751.      * in the region to the next band.
  752.      */
  753.     if (r1->y2 == ybot) r1 = r1BandEnd;
  754.     if (r2->y2 == ybot) r2 = r2BandEnd;
  755.  
  756.     } while (r1 != r1End && r2 != r2End);
  757.  
  758.     /*
  759.      * Deal with whichever region (if any) still has rectangles left.
  760.      *
  761.      * We only need to worry about banding and coalescing for the very first
  762.      * band left.  After that, we can just group all remaining boxes,
  763.      * regardless of how many bands, into one final append to the list.
  764.      */
  765.  
  766.     if ((r1 != r1End) && appendNon1) {
  767.     /* Do first nonOverlap1Func call, which may be able to coalesce */
  768.     FindBand(r1, r1BandEnd, r1End, r1y1);
  769.     curBand = newReg->data->numRects;
  770.     miAppendNonO(newReg, r1, r1BandEnd, max(r1y1, ybot), r1->y2);
  771.     Coalesce(newReg, prevBand, curBand);
  772.     /* Just append the rest of the boxes  */
  773.     AppendRegions(newReg, r1BandEnd, r1End);
  774.  
  775.     } else if ((r2 != r2End) && appendNon2) {
  776.     /* Do first nonOverlap2Func call, which may be able to coalesce */
  777.     FindBand(r2, r2BandEnd, r2End, r2y1);
  778.     curBand = newReg->data->numRects;
  779.     miAppendNonO(newReg, r2, r2BandEnd, max(r2y1, ybot), r2->y2);
  780.     Coalesce(newReg, prevBand, curBand);
  781.     /* Append rest of boxes */
  782.     AppendRegions(newReg, r2BandEnd, r2End);
  783.     }
  784.  
  785.     if (oldData)
  786.     xfree(oldData);
  787.  
  788.     if (!(numRects = newReg->data->numRects))
  789.     {
  790.     xfreeData(newReg);
  791.     newReg->data = &EmptyData;
  792.     }
  793.     else if (numRects == 1)
  794.     {
  795.     newReg->extents = *REGION_BOXPTR(newReg);
  796.     xfreeData(newReg);
  797.     newReg->data = (RegDataPtr)NULL;
  798.     }
  799.     else
  800.     {
  801.     DOWNSIZE(newReg, numRects);
  802.     }
  803.  
  804.     return TRUE;
  805. }
  806.  
  807. /*-
  808.  *-----------------------------------------------------------------------
  809.  * miSetExtents --
  810.  *    Reset the extents of a region to what they should be. Called by
  811.  *    miSubtract and miIntersect as they can't figure it out along the
  812.  *    way or do so easily, as miUnion can.
  813.  *
  814.  * Results:
  815.  *    None.
  816.  *
  817.  * Side Effects:
  818.  *    The region's 'extents' structure is overwritten.
  819.  *
  820.  *-----------------------------------------------------------------------
  821.  */
  822. void
  823. miSetExtents (pReg)
  824.     register RegionPtr pReg;
  825. {
  826.     register BoxPtr pBox, pBoxEnd;
  827.  
  828.     if (!pReg->data)
  829.     return;
  830.     if (!pReg->data->size)
  831.     {
  832.     pReg->extents.x2 = pReg->extents.x1;
  833.     pReg->extents.y2 = pReg->extents.y1;
  834.     return;
  835.     }
  836.  
  837.     pBox = REGION_BOXPTR(pReg);
  838.     pBoxEnd = REGION_END(pReg);
  839.  
  840.     /*
  841.      * Since pBox is the first rectangle in the region, it must have the
  842.      * smallest y1 and since pBoxEnd is the last rectangle in the region,
  843.      * it must have the largest y2, because of banding. Initialize x1 and
  844.      * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
  845.      * to...
  846.      */
  847.     pReg->extents.x1 = pBox->x1;
  848.     pReg->extents.y1 = pBox->y1;
  849.     pReg->extents.x2 = pBoxEnd->x2;
  850.     pReg->extents.y2 = pBoxEnd->y2;
  851.  
  852.     assert(pReg->extents.y1 < pReg->extents.y2);
  853.     while (pBox <= pBoxEnd) {
  854.     if (pBox->x1 < pReg->extents.x1)
  855.         pReg->extents.x1 = pBox->x1;
  856.     if (pBox->x2 > pReg->extents.x2)
  857.         pReg->extents.x2 = pBox->x2;
  858.     pBox++;
  859.     };
  860.  
  861.     assert(pReg->extents.x1 < pReg->extents.x2);
  862. }
  863.  
  864. /*======================================================================
  865.  *        Region Intersection
  866.  *====================================================================*/
  867. /*-
  868.  *-----------------------------------------------------------------------
  869.  * miIntersectO --
  870.  *    Handle an overlapping band for miIntersect.
  871.  *
  872.  * Results:
  873.  *    TRUE if successful.
  874.  *
  875.  * Side Effects:
  876.  *    Rectangles may be added to the region.
  877.  *
  878.  *-----------------------------------------------------------------------
  879.  */
  880. /*ARGSUSED*/
  881. static Bool
  882. miIntersectO (pReg, r1, r1End, r2, r2End, y1, y2, pOverlap)
  883.     register RegionPtr    pReg;
  884.     register BoxPtr    r1;
  885.     BoxPtr            r1End;
  886.     register BoxPtr    r2;
  887.     BoxPtr            r2End;
  888.     short              y1;
  889.     short              y2;
  890.     Bool        *pOverlap;
  891. {
  892.     register int      x1;
  893.     register int      x2;
  894.     register BoxPtr    pNextRect;
  895.  
  896.     pNextRect = REGION_TOP(pReg);
  897.  
  898.     assert(y1 < y2);
  899.     assert(r1 != r1End && r2 != r2End);
  900.  
  901.     do {
  902.     x1 = max(r1->x1, r2->x1);
  903.     x2 = min(r1->x2, r2->x2);
  904.  
  905.     /*
  906.      * If there's any overlap between the two rectangles, add that
  907.      * overlap to the new region.
  908.      */
  909.     if (x1 < x2)
  910.         NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
  911.  
  912.     /*
  913.      * Advance the pointer(s) with the leftmost right side, since the next
  914.      * rectangle on that list may still overlap the other region's
  915.      * current rectangle.
  916.      */
  917.     if (r1->x2 == x2) {
  918.         r1++;
  919.     }
  920.     if (r2->x2 == x2) {
  921.         r2++;
  922.     }
  923.     } while ((r1 != r1End) && (r2 != r2End));
  924.  
  925.     return TRUE;
  926. }
  927.  
  928.  
  929. Bool
  930. miIntersect(newReg, reg1, reg2)
  931.     register RegionPtr     newReg;     /* destination Region */
  932.     register RegionPtr     reg1;
  933.     register RegionPtr    reg2;       /* source regions     */
  934. {
  935.     good(reg1);
  936.     good(reg2);
  937.     good(newReg);
  938.    /* check for trivial reject */
  939.     if (REGION_NIL(reg1)  || REGION_NIL(reg2) ||
  940.     !EXTENTCHECK(®1->extents, ®2->extents))
  941.     {
  942.     /* Covers about 20% of all cases */
  943.     xfreeData(newReg);
  944.     newReg->extents.x2 = newReg->extents.x1;
  945.     newReg->extents.y2 = newReg->extents.y1;
  946.     newReg->data = &EmptyData;
  947.     }
  948.     else if (!reg1->data && !reg2->data)
  949.     {
  950.     /* Covers about 80% of cases that aren't trivially rejected */
  951.     newReg->extents.x1 = max(reg1->extents.x1, reg2->extents.x1);
  952.     newReg->extents.y1 = max(reg1->extents.y1, reg2->extents.y1);
  953.     newReg->extents.x2 = min(reg1->extents.x2, reg2->extents.x2);
  954.     newReg->extents.y2 = min(reg1->extents.y2, reg2->extents.y2);
  955.     xfreeData(newReg);
  956.     newReg->data = (RegDataPtr)NULL;
  957.     }
  958.     else if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
  959.     {
  960.     return miRegionCopy(newReg, reg1);
  961.     }
  962.     else if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
  963.     {
  964.     return miRegionCopy(newReg, reg2);
  965.     }
  966.     else if (reg1 == reg2)
  967.     {
  968.     return miRegionCopy(newReg, reg1);
  969.     }
  970.     else
  971.     {
  972.     /* General purpose intersection */
  973.     Bool overlap; /* result ignored */
  974.     if (!miRegionOp(newReg, reg1, reg2, miIntersectO, FALSE, FALSE,
  975.             &overlap))
  976.         return FALSE;
  977.     miSetExtents(newReg);
  978.     }
  979.  
  980.     good(newReg);
  981.     return(TRUE);
  982. }
  983.  
  984. #define MERGERECT(r)                        \
  985. {                                \
  986.     if (r->x1 <= x2) {                        \
  987.     /* Merge with current rectangle */            \
  988.     if (r->x1 < x2) *pOverlap = TRUE;                \
  989.     if (x2 < r->x2) x2 = r->x2;                \
  990.     } else {                            \
  991.     /* Add current rectangle, start new one */        \
  992.     NEWRECT(pReg, pNextRect, x1, y1, x2, y2);        \
  993.     x1 = r->x1;                        \
  994.     x2 = r->x2;                        \
  995.     }                                \
  996.     r++;                            \
  997. }
  998.  
  999. /*======================================================================
  1000.  *        Region Union
  1001.  *====================================================================*/
  1002.  
  1003. /*-
  1004.  *-----------------------------------------------------------------------
  1005.  * miUnionO --
  1006.  *    Handle an overlapping band for the union operation. Picks the
  1007.  *    left-most rectangle each time and merges it into the region.
  1008.  *
  1009.  * Results:
  1010.  *    TRUE if successful.
  1011.  *
  1012.  * Side Effects:
  1013.  *    pReg is overwritten.
  1014.  *    pOverlap is set to TRUE if any boxes overlap.
  1015.  *
  1016.  *-----------------------------------------------------------------------
  1017.  */
  1018. static Bool
  1019. miUnionO (pReg, r1, r1End, r2, r2End, y1, y2, pOverlap)
  1020.     register RegionPtr    pReg;
  1021.     register BoxPtr    r1;
  1022.          BoxPtr      r1End;
  1023.     register BoxPtr    r2;
  1024.          BoxPtr      r2End;
  1025.          short    y1;
  1026.          short    y2;
  1027.          Bool    *pOverlap;
  1028. {
  1029.     register BoxPtr     pNextRect;
  1030.     register int        x1;     /* left and right side of current union */
  1031.     register int        x2;
  1032.  
  1033.     assert (y1 < y2);
  1034.     assert(r1 != r1End && r2 != r2End);
  1035.  
  1036.     pNextRect = REGION_TOP(pReg);
  1037.  
  1038.     /* Start off current rectangle */
  1039.     if (r1->x1 < r2->x1)
  1040.     {
  1041.     x1 = r1->x1;
  1042.     x2 = r1->x2;
  1043.     r1++;
  1044.     }
  1045.     else
  1046.     {
  1047.     x1 = r2->x1;
  1048.     x2 = r2->x2;
  1049.     r2++;
  1050.     }
  1051.     while (r1 != r1End && r2 != r2End)
  1052.     {
  1053.     if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
  1054.     }
  1055.  
  1056.     /* Finish off whoever (if any) is left */
  1057.     if (r1 != r1End)
  1058.     {
  1059.     do
  1060.     {
  1061.         MERGERECT(r1);
  1062.     } while (r1 != r1End);
  1063.     }
  1064.     else if (r2 != r2End)
  1065.     {
  1066.     do
  1067.     {
  1068.         MERGERECT(r2);
  1069.     } while (r2 != r2End);
  1070.     }
  1071.     
  1072.     /* Add current rectangle */
  1073.     NEWRECT(pReg, pNextRect, x1, y1, x2, y2);
  1074.  
  1075.     return TRUE;
  1076. }
  1077.  
  1078. Bool 
  1079. miUnion(newReg, reg1, reg2)
  1080.     RegionPtr        newReg;                  /* destination Region */
  1081.     register RegionPtr     reg1;
  1082.     register RegionPtr    reg2;             /* source regions     */
  1083. {
  1084.     Bool overlap; /* result ignored */
  1085.  
  1086.     /* Return TRUE if some overlap between reg1, reg2 */
  1087.     good(reg1);
  1088.     good(reg2);
  1089.     good(newReg);
  1090.     /*  checks all the simple cases */
  1091.  
  1092.     /*
  1093.      * Region 1 and 2 are the same
  1094.      */
  1095.     if (reg1 == reg2)
  1096.     {
  1097.     return miRegionCopy(newReg, reg1);
  1098.     }
  1099.  
  1100.     /*
  1101.      * Region 1 is empty
  1102.      */
  1103.     if (REGION_NIL(reg1))
  1104.     {
  1105.         if (newReg != reg2)
  1106.         return miRegionCopy(newReg, reg2);
  1107.         return TRUE;
  1108.     }
  1109.  
  1110.     /*
  1111.      * Region 2 is empty
  1112.      */
  1113.     if (REGION_NIL(reg2))
  1114.     {
  1115.         if (newReg != reg1)
  1116.         return miRegionCopy(newReg, reg1);
  1117.         return TRUE;
  1118.     }
  1119.  
  1120.     /*
  1121.      * Region 1 completely subsumes region 2
  1122.      */
  1123.     if (!reg1->data && SUBSUMES(®1->extents, ®2->extents))
  1124.     {
  1125.         if (newReg != reg1)
  1126.         return miRegionCopy(newReg, reg1);
  1127.         return TRUE;
  1128.     }
  1129.  
  1130.     /*
  1131.      * Region 2 completely subsumes region 1
  1132.      */
  1133.     if (!reg2->data && SUBSUMES(®2->extents, ®1->extents))
  1134.     {
  1135.         if (newReg != reg2)
  1136.         return miRegionCopy(newReg, reg2);
  1137.         return TRUE;
  1138.     }
  1139.  
  1140.     if (!miRegionOp(newReg, reg1, reg2, miUnionO, TRUE, TRUE, &overlap))
  1141.     return FALSE;
  1142.  
  1143.     newReg->extents.x1 = min(reg1->extents.x1, reg2->extents.x1);
  1144.     newReg->extents.y1 = min(reg1->extents.y1, reg2->extents.y1);
  1145.     newReg->extents.x2 = max(reg1->extents.x2, reg2->extents.x2);
  1146.     newReg->extents.y2 = max(reg1->extents.y2, reg2->extents.y2);
  1147.     good(newReg);
  1148.     return TRUE;
  1149. }
  1150.  
  1151.  
  1152. /*======================================================================
  1153.  *        Batch Rectangle Union
  1154.  *====================================================================*/
  1155.  
  1156. /*-
  1157.  *-----------------------------------------------------------------------
  1158.  * miRegionAppend --
  1159.  * 
  1160.  *      "Append" the rgn rectangles onto the end of dstrgn, maintaining
  1161.  *      knowledge of YX-banding when it's easy.  Otherwise, dstrgn just
  1162.  *      becomes a non-y-x-banded random collection of rectangles, and not
  1163.  *      yet a true region.  After a sequence of appends, the caller must
  1164.  *      call miRegionValidate to ensure that a valid region is constructed.
  1165.  *
  1166.  * Results:
  1167.  *    TRUE if successful.
  1168.  *
  1169.  * Side Effects:
  1170.  *      dstrgn is modified if rgn has rectangles.
  1171.  *
  1172.  */
  1173. Bool
  1174. miRegionAppend(dstrgn, rgn)
  1175.     register RegionPtr dstrgn;
  1176.     register RegionPtr rgn;
  1177. {
  1178.     int numRects, dnumRects, size;
  1179.     BoxPtr new, old;
  1180.     Bool prepend;
  1181.  
  1182.     if (!rgn->data && (dstrgn->data == &EmptyData))
  1183.     {
  1184.     dstrgn->extents = rgn->extents;
  1185.     dstrgn->data = (RegDataPtr)NULL;
  1186.     return TRUE;
  1187.     }
  1188.  
  1189.     numRects = REGION_NUM_RECTS(rgn);
  1190.     if (!numRects)
  1191.     return TRUE;
  1192.     prepend = FALSE;
  1193.     size = numRects;
  1194.     dnumRects = REGION_NUM_RECTS(dstrgn);
  1195.     if (!dnumRects && (size < 200))
  1196.     size = 200; /* XXX pick numbers out of a hat */
  1197.     RECTALLOC(dstrgn, size);
  1198.     old = REGION_RECTS(rgn);
  1199.     if (!dnumRects)
  1200.     dstrgn->extents = rgn->extents;
  1201.     else if (dstrgn->extents.x2 > dstrgn->extents.x1)
  1202.     {
  1203.     register BoxPtr first, last;
  1204.  
  1205.     first = old;
  1206.     last = REGION_BOXPTR(dstrgn) + (dnumRects - 1);
  1207.     if ((first->y1 > last->y2) ||
  1208.         ((first->y1 == last->y1) && (first->y2 == last->y2) &&
  1209.          (first->x1 > last->x2)))
  1210.     {
  1211.         if (rgn->extents.x1 < dstrgn->extents.x1)
  1212.         dstrgn->extents.x1 = rgn->extents.x1;
  1213.         if (rgn->extents.x2 > dstrgn->extents.x2)
  1214.         dstrgn->extents.x2 = rgn->extents.x2;
  1215.         dstrgn->extents.y2 = rgn->extents.y2;
  1216.     }
  1217.     else
  1218.     {
  1219.         first = REGION_BOXPTR(dstrgn);
  1220.         last = old + (numRects - 1);
  1221.         if ((first->y1 > last->y2) ||
  1222.         ((first->y1 == last->y1) && (first->y2 == last->y2) &&
  1223.          (first->x1 > last->x2)))
  1224.         {
  1225.         prepend = TRUE;
  1226.         if (rgn->extents.x1 < dstrgn->extents.x1)
  1227.             dstrgn->extents.x1 = rgn->extents.x1;
  1228.         if (rgn->extents.x2 > dstrgn->extents.x2)
  1229.             dstrgn->extents.x2 = rgn->extents.x2;
  1230.         dstrgn->extents.y1 = rgn->extents.y1;
  1231.         }
  1232.         else
  1233.         dstrgn->extents.x2 = dstrgn->extents.x1;
  1234.     }
  1235.     }
  1236.     if (prepend)
  1237.     {
  1238.     new = REGION_BOX(dstrgn, numRects);
  1239.     if (dnumRects == 1)
  1240.         *new = *REGION_BOXPTR(dstrgn);
  1241.     else
  1242.         bcopy((char *)REGION_BOXPTR(dstrgn), (char *)new,
  1243.           dnumRects * sizeof(BoxRec));
  1244.     new = REGION_BOXPTR(dstrgn);
  1245.     }
  1246.     else
  1247.     new = REGION_BOXPTR(dstrgn) + dnumRects;
  1248.     if (numRects == 1)
  1249.     *new = *old;
  1250.     else
  1251.     bcopy((char *)old, (char *)new, numRects * sizeof(BoxRec));
  1252.     dstrgn->data->numRects += numRects;
  1253.     return TRUE;
  1254. }
  1255.  
  1256.    
  1257. #define ExchangeRects(a, b) \
  1258. {                \
  1259.     BoxRec     t;        \
  1260.     t = rects[a];        \
  1261.     rects[a] = rects[b];    \
  1262.     rects[b] = t;        \
  1263. }
  1264.  
  1265. static void
  1266. QuickSortRects(rects, numRects)
  1267.     register BoxRec     rects[];
  1268.     register int        numRects;
  1269. {
  1270.     register int    y1;
  1271.     register int    x1;
  1272.     register int        i, j;
  1273.     register BoxPtr     r;
  1274.  
  1275.     /* Always called with numRects > 1 */
  1276.  
  1277.     do
  1278.     {
  1279.     if (numRects == 2)
  1280.     {
  1281.         if (rects[0].y1 > rects[1].y1 ||
  1282.             (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
  1283.         ExchangeRects(0, 1);
  1284.         return;
  1285.     }
  1286.  
  1287.     /* Choose partition element, stick in location 0 */
  1288.         ExchangeRects(0, numRects >> 1);
  1289.     y1 = rects[0].y1;
  1290.     x1 = rects[0].x1;
  1291.  
  1292.         /* Partition array */
  1293.         i = 0;
  1294.         j = numRects;
  1295.         do
  1296.     {
  1297.         r = &(rects[i]);
  1298.         do
  1299.         {
  1300.         r++;
  1301.         i++;
  1302.             } while (i != numRects &&
  1303.              (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
  1304.         r = &(rects[j]);
  1305.         do
  1306.         {
  1307.         r--;
  1308.         j--;
  1309.             } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
  1310.             if (i < j)
  1311.         ExchangeRects(i, j);
  1312.         } while (i < j);
  1313.  
  1314.         /* Move partition element back to middle */
  1315.         ExchangeRects(0, j);
  1316.  
  1317.     /* Recurse */
  1318.         if (numRects-j-1 > 1)
  1319.         QuickSortRects(&rects[j+1], numRects-j-1);
  1320.         numRects = j;
  1321.     } while (numRects > 1);
  1322. }
  1323.  
  1324. /*-
  1325.  *-----------------------------------------------------------------------
  1326.  * miRegionValidate --
  1327.  * 
  1328.  *      Take a ``region'' which is a non-y-x-banded random collection of
  1329.  *      rectangles, and compute a nice region which is the union of all the
  1330.  *      rectangles.
  1331.  *
  1332.  * Results:
  1333.  *    TRUE if successful.
  1334.  *
  1335.  * Side Effects:
  1336.  *      The passed-in ``region'' may be modified.
  1337.  *    pOverlap set to TRUE if any retangles overlapped, else FALSE;
  1338.  *
  1339.  * Strategy:
  1340.  *      Step 1. Sort the rectangles into ascending order with primary key y1
  1341.  *        and secondary key x1.
  1342.  *
  1343.  *      Step 2. Split the rectangles into the minimum number of proper y-x
  1344.  *        banded regions.  This may require horizontally merging
  1345.  *        rectangles, and vertically coalescing bands.  With any luck,
  1346.  *        this step in an identity tranformation (ala the Box widget),
  1347.  *        or a coalescing into 1 box (ala Menus).
  1348.  *
  1349.  *    Step 3. Merge the separate regions down to a single region by calling
  1350.  *        miUnion.  Maximize the work each miUnion call does by using
  1351.  *        a binary merge.
  1352.  *
  1353.  *-----------------------------------------------------------------------
  1354.  */
  1355.  
  1356. Bool
  1357. miRegionValidate(badreg, pOverlap)
  1358.     RegionPtr badreg;
  1359.     Bool *pOverlap;
  1360. {
  1361.     /* Descriptor for regions under construction  in Step 2. */
  1362.     typedef struct {
  1363.     RegionRec   reg;
  1364.     int        prevBand;
  1365.     int        curBand;
  1366.     } RegionInfo;
  1367.  
  1368.          int    numRects;   /* Original numRects for badreg        */
  1369.          RegionInfo *ri;        /* Array of current regions            */
  1370.              int    numRI;      /* Number of entries used in ri        */
  1371.          int    sizeRI;        /* Number of entries available in ri    */
  1372.          int    i;        /* Index into rects                */
  1373.     register int    j;        /* Index into ri                */
  1374.     register RegionInfo *rit;       /* &ri[j]                    */
  1375.     register RegionPtr  reg;        /* ri[j].reg                */
  1376.     register BoxPtr    box;        /* Current box in rects            */
  1377.     register BoxPtr    riBox;      /* Last box in ri[j].reg            */
  1378.     register RegionPtr  hreg;       /* ri[j_half].reg                */
  1379.  
  1380.     *pOverlap = FALSE;
  1381.     if (!badreg->data)
  1382.     {
  1383.     good(badreg);
  1384.     return TRUE;
  1385.     }
  1386.     numRects = badreg->data->numRects;
  1387.     if (!numRects)
  1388.     {
  1389.     good(badreg);
  1390.     return TRUE;
  1391.     }
  1392.     if (badreg->extents.x1 < badreg->extents.x2)
  1393.     {
  1394.     if ((numRects) == 1)
  1395.     {
  1396.         xfreeData(badreg);
  1397.         badreg->data = (RegDataPtr) NULL;
  1398.     }
  1399.     else
  1400.     {
  1401.         DOWNSIZE(badreg, numRects);
  1402.     }
  1403.     good(badreg);
  1404.     return TRUE;
  1405.     }
  1406.  
  1407.     /* Step 1: Sort the rects array into ascending (y1, x1) order */
  1408.     QuickSortRects(REGION_BOXPTR(badreg), numRects);
  1409.  
  1410.     /* Step 2: Scatter the sorted array into the minimum number of regions */
  1411.  
  1412.     /* Set up the first region to be the first rectangle in badreg */
  1413.     /* Note that step 2 code will never overflow the ri[0].reg rects array */
  1414.     Must_have_memory = TRUE; /* XXX */
  1415.     ri = (RegionInfo *) xalloc(4 * sizeof(RegionInfo));
  1416.     Must_have_memory = FALSE; /* XXX */
  1417.     sizeRI = 4;
  1418.     numRI = 1;
  1419.     ri[0].prevBand = 0;
  1420.     ri[0].curBand = 0;
  1421.     ri[0].reg = *badreg;
  1422.     box = REGION_BOXPTR(&ri[0].reg);
  1423.     ri[0].reg.extents = *box;
  1424.     ri[0].reg.data->numRects = 1;
  1425.  
  1426.     /* Now scatter rectangles into the minimum set of valid regions.  If the
  1427.        next rectangle to be added to a region would force an existing rectangle
  1428.        in the region to be split up in order to maintain y-x banding, just
  1429.        forget it.  Try the next region.  If it doesn't fit cleanly into any
  1430.        region, make a new one. */
  1431.  
  1432.     for (i = numRects; --i > 0;)
  1433.     {
  1434.     box++;
  1435.     /* Look for a region to append box to */
  1436.     for (j = numRI, rit = ri; --j >= 0; rit++)
  1437.     {
  1438.         reg = &rit->reg;
  1439.         riBox = REGION_END(reg);
  1440.  
  1441.         if (box->y1 == riBox->y1 && box->y2 == riBox->y2)
  1442.         {
  1443.         /* box is in same band as riBox.  Merge or append it */
  1444.         if (box->x1 <= riBox->x2)
  1445.         {
  1446.             /* Merge it with riBox */
  1447.             if (box->x1 < riBox->x2) *pOverlap = TRUE;
  1448.             if (box->x2 > riBox->x2) riBox->x2 = box->x2;
  1449.         }
  1450.         else
  1451.         {
  1452.             RECTALLOC(reg, 1);
  1453.             *REGION_TOP(reg) = *box;
  1454.             reg->data->numRects++;
  1455.         }
  1456.         goto NextRect;   /* So sue me */
  1457.         }
  1458.         else if (box->y1 >= riBox->y2)
  1459.         {
  1460.         /* Put box into new band */
  1461.         if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
  1462.         if (reg->extents.x1 > box->x1)   reg->extents.x1 = box->x1;
  1463.         Coalesce(reg, rit->prevBand, rit->curBand);
  1464.         rit->curBand = reg->data->numRects;
  1465.         RECTALLOC(reg, 1);
  1466.         *REGION_TOP(reg) = *box;
  1467.         reg->data->numRects++;
  1468.         goto NextRect;
  1469.         }
  1470.         /* Well, this region was inappropriate.  Try the next one. */
  1471.     } /* for j */
  1472.  
  1473.     /* Uh-oh.  No regions were appropriate.  Create a new one. */
  1474.     if (sizeRI == numRI)
  1475.     {
  1476.         /* Oops, allocate space for new region information */
  1477.         sizeRI <<= 1;
  1478.         Must_have_memory = TRUE; /* XXX */
  1479.         ri = (RegionInfo *) xrealloc(ri, sizeRI * sizeof(RegionInfo));
  1480.         Must_have_memory = FALSE; /* XXX */
  1481.         rit = &ri[numRI];
  1482.     }
  1483.     numRI++;
  1484.     rit->prevBand = 0;
  1485.     rit->curBand = 0;
  1486.     rit->reg.extents = *box;
  1487.     rit->reg.data = (RegDataPtr)NULL;
  1488.     miRectAlloc(&rit->reg, (i+numRI) / numRI); /* MUST force allocation */
  1489. NextRect: ;
  1490.     } /* for i */
  1491.  
  1492.     /* Make a final pass over each region in order to Coalesce and set
  1493.        extents.x2 and extents.y2 */
  1494.  
  1495.     for (j = numRI, rit = ri; --j >= 0; rit++)
  1496.     {
  1497.     reg = &rit->reg;
  1498.     riBox = REGION_END(reg);
  1499.     reg->extents.y2 = riBox->y2;
  1500.     if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2;
  1501.     Coalesce(reg, rit->prevBand, rit->curBand);
  1502.     if (reg->data->numRects == 1) /* keep unions happy below */
  1503.     {
  1504.         xfreeData(reg);
  1505.         reg->data = (RegDataPtr)NULL;
  1506.     }
  1507.     }
  1508.  
  1509.     /* Step 3: Union all regions into a single region */
  1510.     while (numRI > 1)
  1511.     {
  1512.     int half = numRI/2;
  1513.     for (j = numRI & 1; j < (half + (numRI & 1)); j++)
  1514.     {
  1515.         reg = &ri[j].reg;
  1516.         hreg = &ri[j+half].reg;
  1517.         miRegionOp(reg, reg, hreg, miUnionO, TRUE, TRUE, pOverlap);
  1518.         if (hreg->extents.x1 < reg->extents.x1)
  1519.         reg->extents.x1 = hreg->extents.x1;
  1520.         if (hreg->extents.y1 < reg->extents.y1)
  1521.         reg->extents.y1 = hreg->extents.y1;
  1522.         if (hreg->extents.x2 > reg->extents.x2)
  1523.         reg->extents.x2 = hreg->extents.x2;
  1524.         if (hreg->extents.y2 > reg->extents.y2)
  1525.         reg->extents.y2 = hreg->extents.y2;
  1526.         xfreeData(hreg);
  1527.     }
  1528.     numRI -= half;
  1529.     }
  1530.     *badreg = ri[0].reg;
  1531.     xfree(ri);
  1532.     good(badreg);
  1533.     return TRUE;
  1534. }
  1535.  
  1536. RegionPtr
  1537. miRectsToRegion(nrects, prect, ctype)
  1538.     int            nrects;
  1539.     register xRectangle    *prect;
  1540.     int            ctype;
  1541. {
  1542.     register RegionPtr    pRgn;
  1543.     register RegDataPtr    pData;
  1544.     register BoxPtr    pBox;
  1545.     register int        i;
  1546.     int            x1, y1, x2, y2;
  1547.  
  1548.     pRgn = miRegionCreate(NullBox, 0);
  1549.     if (!nrects)
  1550.     return pRgn;
  1551.     if (nrects == 1)
  1552.     {
  1553.     x1 = prect->x;
  1554.     y1 = prect->y;
  1555.     if ((x2 = x1 + (int) prect->width) > MAXSHORT)
  1556.         x2 = MAXSHORT;
  1557.     if ((y2 = y1 + (int) prect->height) > MAXSHORT)
  1558.         y2 = MAXSHORT;
  1559.     if (x1 != x2 && y1 != y2)
  1560.     {
  1561.         pRgn->extents.x1 = x1;
  1562.         pRgn->extents.y1 = y1;
  1563.         pRgn->extents.x2 = x2;
  1564.         pRgn->extents.y2 = y2;
  1565.         pRgn->data = (RegDataPtr)NULL;
  1566.     }
  1567.     return pRgn;
  1568.     }
  1569.     Must_have_memory = TRUE; /* XXX */
  1570.     pData = xallocData(nrects);
  1571.     pBox = (BoxPtr) (pData + 1);
  1572.     Must_have_memory = FALSE; /* XXX */
  1573.     for (i = nrects; --i >= 0; prect++)
  1574.     {
  1575.     x1 = prect->x;
  1576.     y1 = prect->y;
  1577.     if ((x2 = x1 + (int) prect->width) > MAXSHORT)
  1578.         x2 = MAXSHORT;
  1579.     if ((y2 = y1 + (int) prect->height) > MAXSHORT)
  1580.         y2 = MAXSHORT;
  1581.     if (x1 != x2 && y1 != y2)
  1582.     {
  1583.         pBox->x1 = x1;
  1584.         pBox->y1 = y1;
  1585.         pBox->x2 = x2;
  1586.         pBox->y2 = y2;
  1587.         pBox++;
  1588.     }
  1589.     }
  1590.     if (pBox != (BoxPtr) (pData + 1))
  1591.     {
  1592.     pData->size = nrects;
  1593.     pData->numRects = pBox - (BoxPtr) (pData + 1);
  1594.         pRgn->data = pData;
  1595.         if (ctype != CT_YXBANDED)
  1596.         {
  1597.         Bool overlap; /* result ignored */
  1598.         pRgn->extents.x1 = pRgn->extents.x2 = 0;
  1599.         miRegionValidate(pRgn, &overlap);
  1600.         }
  1601.         else
  1602.         miSetExtents(pRgn);
  1603.         good(pRgn);
  1604.     }
  1605.     else
  1606.     {
  1607.     xfree (pData);
  1608.     }
  1609.     return pRgn;
  1610. }
  1611.  
  1612. /*======================================================================
  1613.  *               Region Subtraction
  1614.  *====================================================================*/
  1615.  
  1616.  
  1617. /*-
  1618.  *-----------------------------------------------------------------------
  1619.  * miSubtractO --
  1620.  *    Overlapping band subtraction. x1 is the left-most point not yet
  1621.  *    checked.
  1622.  *
  1623.  * Results:
  1624.  *    TRUE if successful.
  1625.  *
  1626.  * Side Effects:
  1627.  *    pReg may have rectangles added to it.
  1628.  *
  1629.  *-----------------------------------------------------------------------
  1630.  */
  1631. /*ARGSUSED*/
  1632. static Bool
  1633. miSubtractO (pReg, r1, r1End, r2, r2End, y1, y2, pOverlap)
  1634.     register RegionPtr    pReg;
  1635.     register BoxPtr    r1;
  1636.     BoxPtr            r1End;
  1637.     register BoxPtr    r2;
  1638.     BoxPtr            r2End;
  1639.     register int      y1;
  1640.              int      y2;
  1641.     Bool        *pOverlap;
  1642. {
  1643.     register BoxPtr    pNextRect;
  1644.     register int      x1;
  1645.  
  1646.     x1 = r1->x1;
  1647.     
  1648.     assert(y1<y2);
  1649.     assert(r1 != r1End && r2 != r2End);
  1650.  
  1651.     pNextRect = REGION_TOP(pReg);
  1652.  
  1653.     do
  1654.     {
  1655.     if (r2->x2 <= x1)
  1656.     {
  1657.         /*
  1658.          * Subtrahend entirely to left of minuend: go to next subtrahend.
  1659.          */
  1660.         r2++;
  1661.     }
  1662.     else if (r2->x1 <= x1)
  1663.     {
  1664.         /*
  1665.          * Subtrahend preceeds minuend: nuke left edge of minuend.
  1666.          */
  1667.         x1 = r2->x2;
  1668.         if (x1 >= r1->x2)
  1669.         {
  1670.         /*
  1671.          * Minuend completely covered: advance to next minuend and
  1672.          * reset left fence to edge of new minuend.
  1673.          */
  1674.         r1++;
  1675.         if (r1 != r1End)
  1676.             x1 = r1->x1;
  1677.         }
  1678.         else
  1679.         {
  1680.         /*
  1681.          * Subtrahend now used up since it doesn't extend beyond
  1682.          * minuend
  1683.          */
  1684.         r2++;
  1685.         }
  1686.     }
  1687.     else if (r2->x1 < r1->x2)
  1688.     {
  1689.         /*
  1690.          * Left part of subtrahend covers part of minuend: add uncovered
  1691.          * part of minuend to region and skip to next subtrahend.
  1692.          */
  1693.         assert(x1<r2->x1);
  1694.         NEWRECT(pReg, pNextRect, x1, y1, r2->x1, y2);
  1695.  
  1696.         x1 = r2->x2;
  1697.         if (x1 >= r1->x2)
  1698.         {
  1699.         /*
  1700.          * Minuend used up: advance to new...
  1701.          */
  1702.         r1++;
  1703.         if (r1 != r1End)
  1704.             x1 = r1->x1;
  1705.         }
  1706.         else
  1707.         {
  1708.         /*
  1709.          * Subtrahend used up
  1710.          */
  1711.         r2++;
  1712.         }
  1713.     }
  1714.     else
  1715.     {
  1716.         /*
  1717.          * Minuend used up: add any remaining piece before advancing.
  1718.          */
  1719.         if (r1->x2 > x1)
  1720.         NEWRECT(pReg, pNextRect, x1, y1, r1->x2, y2);
  1721.         r1++;
  1722.         if (r1 != r1End)
  1723.         x1 = r1->x1;
  1724.     }
  1725.     } while ((r1 != r1End) && (r2 != r2End));
  1726.  
  1727.  
  1728.     /*
  1729.      * Add remaining minuend rectangles to region.
  1730.      */
  1731.     while (r1 != r1End)
  1732.     {
  1733.     assert(x1<r1->x2);
  1734.     NEWRECT(pReg, pNextRect, x1, y1, r1->x2, y2);
  1735.     r1++;
  1736.     if (r1 != r1End)
  1737.         x1 = r1->x1;
  1738.     }
  1739.     return TRUE;
  1740. }
  1741.     
  1742. /*-
  1743.  *-----------------------------------------------------------------------
  1744.  * miSubtract --
  1745.  *    Subtract regS from regM and leave the result in regD.
  1746.  *    S stands for subtrahend, M for minuend and D for difference.
  1747.  *
  1748.  * Results:
  1749.  *    TRUE if successful.
  1750.  *
  1751.  * Side Effects:
  1752.  *    regD is overwritten.
  1753.  *
  1754.  *-----------------------------------------------------------------------
  1755.  */
  1756. Bool
  1757. miSubtract(regD, regM, regS)
  1758.     register RegionPtr    regD;               
  1759.     register RegionPtr     regM;
  1760.     register RegionPtr    regS;          
  1761. {
  1762.     Bool overlap; /* result ignored */
  1763.  
  1764.     good(regM);
  1765.     good(regS);
  1766.     good(regD);
  1767.    /* check for trivial rejects */
  1768.     if (REGION_NIL(regM) || REGION_NIL(regS) ||
  1769.     !EXTENTCHECK(®M->extents, ®S->extents))
  1770.     {
  1771.     return miRegionCopy(regD, regM);
  1772.     }
  1773.     else if (regM == regS)
  1774.     {
  1775.     xfreeData(regD);
  1776.     regD->extents.x2 = regD->extents.x1;
  1777.     regD->extents.y2 = regD->extents.y1;
  1778.     regD->data = &EmptyData;
  1779.     return TRUE;
  1780.     }
  1781.  
  1782.     /* Add those rectangles in region 1 that aren't in region 2,
  1783.        do yucky substraction for overlaps, and
  1784.        just throw away rectangles in region 2 that aren't in region 1 */
  1785.     if (!miRegionOp(regD, regM, regS, miSubtractO, TRUE, FALSE, &overlap))
  1786.     return FALSE;
  1787.  
  1788.     /*
  1789.      * Can't alter RegD's extents before we call miRegionOp because
  1790.      * it might be one of the source regions and miRegionOp depends
  1791.      * on the extents of those regions being unaltered. Besides, this
  1792.      * way there's no checking against rectangles that will be nuked
  1793.      * due to coalescing, so we have to examine fewer rectangles.
  1794.      */
  1795.     miSetExtents(regD);
  1796.     good(regD);
  1797.     return TRUE;
  1798. }
  1799.  
  1800. /*======================================================================
  1801.  *        Region Inversion
  1802.  *====================================================================*/
  1803.  
  1804. /*-
  1805.  *-----------------------------------------------------------------------
  1806.  * miInverse --
  1807.  *    Take a region and a box and return a region that is everything
  1808.  *    in the box but not in the region. The careful reader will note
  1809.  *    that this is the same as subtracting the region from the box...
  1810.  *
  1811.  * Results:
  1812.  *    TRUE.
  1813.  *
  1814.  * Side Effects:
  1815.  *    newReg is overwritten.
  1816.  *
  1817.  *-----------------------------------------------------------------------
  1818.  */
  1819. Bool
  1820. miInverse(newReg, reg1, invRect)
  1821.     RegionPtr       newReg;       /* Destination region */
  1822.     RegionPtr       reg1;         /* Region to invert */
  1823.     BoxPtr           invRect;     /* Bounding box for inversion */
  1824. {
  1825.     RegionRec      invReg;       /* Quick and dirty region made from the
  1826.                  * bounding box */
  1827.     Bool      overlap;    /* result ignored */
  1828.  
  1829.     good(reg1);
  1830.     good(newReg);
  1831.    /* check for trivial rejects */
  1832.     if (REGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents))
  1833.     {
  1834.     newReg->extents = *invRect;
  1835.     xfreeData(newReg);
  1836.     newReg->data = (RegDataPtr)NULL;
  1837.         return TRUE;
  1838.     }
  1839.  
  1840.     /* Add those rectangles in region 1 that aren't in region 2,
  1841.        do yucky substraction for overlaps, and
  1842.        just throw away rectangles in region 2 that aren't in region 1 */
  1843.     invReg.extents = *invRect;
  1844.     invReg.data = (RegDataPtr)NULL;
  1845.     if (!miRegionOp(newReg, &invReg, reg1, miSubtractO, TRUE, FALSE, &overlap))
  1846.     return FALSE;
  1847.  
  1848.     /*
  1849.      * Can't alter newReg's extents before we call miRegionOp because
  1850.      * it might be one of the source regions and miRegionOp depends
  1851.      * on the extents of those regions being unaltered. Besides, this
  1852.      * way there's no checking against rectangles that will be nuked
  1853.      * due to coalescing, so we have to examine fewer rectangles.
  1854.      */
  1855.     miSetExtents(newReg);
  1856.     good(newReg);
  1857.     return TRUE;
  1858. }
  1859.  
  1860. /*
  1861.  *   RectIn(region, rect)
  1862.  *   This routine takes a pointer to a region and a pointer to a box
  1863.  *   and determines if the box is outside/inside/partly inside the region.
  1864.  *
  1865.  *   The idea is to travel through the list of rectangles trying to cover the
  1866.  *   passed box with them. Anytime a piece of the rectangle isn't covered
  1867.  *   by a band of rectangles, partOut is set TRUE. Any time a rectangle in
  1868.  *   the region covers part of the box, partIn is set TRUE. The process ends
  1869.  *   when either the box has been completely covered (we reached a band that
  1870.  *   doesn't overlap the box, partIn is TRUE and partOut is false), the
  1871.  *   box has been partially covered (partIn == partOut == TRUE -- because of
  1872.  *   the banding, the first time this is true we know the box is only
  1873.  *   partially in the region) or is outside the region (we reached a band
  1874.  *   that doesn't overlap the box at all and partIn is false)
  1875.  */
  1876.  
  1877. int
  1878. miRectIn(region, prect)
  1879.     register RegionPtr  region;
  1880.     register BoxPtr     prect;
  1881. {
  1882.     register int    x;
  1883.     register int    y;
  1884.     register BoxPtr     pbox;
  1885.     register BoxPtr     pboxEnd;
  1886.     int            partIn, partOut;
  1887.     int            numRects;
  1888.  
  1889.     good(region);
  1890.     numRects = REGION_NUM_RECTS(region);
  1891.     /* useful optimization */
  1892.     if (!numRects || !EXTENTCHECK(®ion->extents, prect))
  1893.         return(rgnOUT);
  1894.  
  1895.     if (numRects == 1)
  1896.     {
  1897.     /* We know that it must be rgnIN or rgnPART */
  1898.     if (SUBSUMES(®ion->extents, prect))
  1899.         return(rgnIN);
  1900.     else
  1901.         return(rgnPART);
  1902.     }
  1903.  
  1904.     partOut = FALSE;
  1905.     partIn = FALSE;
  1906.  
  1907.     /* (x,y) starts at upper left of rect, moving to the right and down */
  1908.     x = prect->x1;
  1909.     y = prect->y1;
  1910.  
  1911.     /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
  1912.     for (pbox = REGION_BOXPTR(region), pboxEnd = pbox + numRects;
  1913.          pbox != pboxEnd;
  1914.          pbox++)
  1915.     {
  1916.  
  1917.         if (pbox->y2 <= y)
  1918.            continue;    /* getting up to speed or skipping remainder of band */
  1919.  
  1920.         if (pbox->y1 > y)
  1921.         {
  1922.            partOut = TRUE;      /* missed part of rectangle above */
  1923.            if (partIn || (pbox->y1 >= prect->y2))
  1924.               break;
  1925.            y = pbox->y1;        /* x guaranteed to be == prect->x1 */
  1926.         }
  1927.  
  1928.         if (pbox->x2 <= x)
  1929.            continue;            /* not far enough over yet */
  1930.  
  1931.         if (pbox->x1 > x)
  1932.         {
  1933.            partOut = TRUE;      /* missed part of rectangle to left */
  1934.            if (partIn)
  1935.               break;
  1936.         }
  1937.  
  1938.         if (pbox->x1 < prect->x2)
  1939.         {
  1940.             partIn = TRUE;      /* definitely overlap */
  1941.             if (partOut)
  1942.                break;
  1943.         }
  1944.  
  1945.         if (pbox->x2 >= prect->x2)
  1946.         {
  1947.            y = pbox->y2;        /* finished with this band */
  1948.            if (y >= prect->y2)
  1949.               break;
  1950.            x = prect->x1;       /* reset x out to left again */
  1951.         }
  1952.     else
  1953.     {
  1954.         /*
  1955.          * Because boxes in a band are maximal width, if the first box
  1956.          * to overlap the rectangle doesn't completely cover it in that
  1957.          * band, the rectangle must be partially out, since some of it
  1958.          * will be uncovered in that band. partIn will have been set true
  1959.          * by now...
  1960.          */
  1961.         partOut = TRUE;
  1962.         break;
  1963.     }
  1964.     }
  1965.  
  1966.     return(partIn ? ((y < prect->y2) ? rgnPART : rgnIN) : rgnOUT);
  1967. }
  1968.  
  1969. /* TranslateRegion(pReg, x, y)
  1970.    translates in place
  1971. */
  1972.  
  1973. void
  1974. miTranslateRegion(pReg, x, y)
  1975.     register RegionPtr pReg;
  1976.     register int x;
  1977.     register int y;
  1978. {
  1979.     int x1, x2, y1, y2;
  1980.     register int nbox;
  1981.     register BoxPtr pbox;
  1982.  
  1983.     good(pReg);
  1984.     pReg->extents.x1 = x1 = pReg->extents.x1 + x;
  1985.     pReg->extents.y1 = y1 = pReg->extents.y1 + y;
  1986.     pReg->extents.x2 = x2 = pReg->extents.x2 + x;
  1987.     pReg->extents.y2 = y2 = pReg->extents.y2 + y;
  1988.     if (((x1 - MINSHORT)|(y1 - MINSHORT)|(MAXSHORT - x2)|(MAXSHORT - y2)) >= 0)
  1989.     {
  1990.     if (pReg->data && (nbox = pReg->data->numRects))
  1991.     {
  1992.         for (pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
  1993.         {
  1994.         pbox->x1 += x;
  1995.         pbox->y1 += y;
  1996.         pbox->x2 += x;
  1997.         pbox->y2 += y;
  1998.         }
  1999.     }
  2000.     return;
  2001.     }
  2002.     if (((x2 - MINSHORT)|(y2 - MINSHORT)|(MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
  2003.     {
  2004.     pReg->extents.x2 = pReg->extents.x1;
  2005.     pReg->extents.y2 = pReg->extents.y1;
  2006.     xfreeData(pReg);
  2007.     pReg->data = &EmptyData;
  2008.     return;
  2009.     }
  2010.     if (x1 < MINSHORT)
  2011.     pReg->extents.x1 = MINSHORT;
  2012.     else if (x2 > MAXSHORT)
  2013.     pReg->extents.x2 = MAXSHORT;
  2014.     if (y1 < MINSHORT)
  2015.     pReg->extents.y1 = MINSHORT;
  2016.     else if (y2 > MAXSHORT)
  2017.     pReg->extents.y2 = MAXSHORT;
  2018.     if (pReg->data && (nbox = pReg->data->numRects))
  2019.     {
  2020.     register BoxPtr pboxout;
  2021.  
  2022.     for (pboxout = pbox = REGION_BOXPTR(pReg); nbox--; pbox++)
  2023.     {
  2024.         pboxout->x1 = x1 = pbox->x1 + x;
  2025.         pboxout->y1 = y1 = pbox->y1 + y;
  2026.         pboxout->x2 = x2 = pbox->x2 + x;
  2027.         pboxout->y2 = y2 = pbox->y2 + y;
  2028.         if (((x2 - MINSHORT)|(y2 - MINSHORT)|
  2029.          (MAXSHORT - x1)|(MAXSHORT - y1)) <= 0)
  2030.         {
  2031.         pReg->data->numRects--;
  2032.         continue;
  2033.         }
  2034.         if (x1 < MINSHORT)
  2035.         pboxout->x1 = MINSHORT;
  2036.         else if (x2 > MAXSHORT)
  2037.         pboxout->x2 = MAXSHORT;
  2038.         if (y1 < MINSHORT)
  2039.         pboxout->y1 = MINSHORT;
  2040.         else if (y2 > MAXSHORT)
  2041.         pboxout->y2 = MAXSHORT;
  2042.         pboxout++;
  2043.     }
  2044.     if (pboxout != pbox)
  2045.     {
  2046.         if (pReg->data->numRects == 1)
  2047.         {
  2048.         pReg->extents = *REGION_BOXPTR(pReg);
  2049.         xfreeData(pReg);
  2050.         pReg->data = (RegDataPtr)NULL;
  2051.         }
  2052.         else
  2053.         miSetExtents(pReg);
  2054.     }
  2055.     }
  2056. }
  2057.  
  2058. void
  2059. miRegionReset(pReg, pBox)
  2060.     RegionPtr pReg;
  2061.     BoxPtr pBox;
  2062. {
  2063.     good(pReg);
  2064.     assert(pBox->x1<=pBox->x2);
  2065.     assert(pBox->y1<=pBox->y2);
  2066.     pReg->extents = *pBox;
  2067.     xfreeData(pReg);
  2068.     pReg->data = (RegDataPtr)NULL;
  2069. }
  2070.  
  2071. Bool
  2072. miPointInRegion(pReg, x, y, box)
  2073.     register RegionPtr pReg;
  2074.     register int x, y;
  2075.     BoxPtr box;     /* "return" value */
  2076. {
  2077.     register BoxPtr pbox, pboxEnd;
  2078.     int numRects;
  2079.  
  2080.     good(pReg);
  2081.     numRects = REGION_NUM_RECTS(pReg);
  2082.     if (!numRects || !INBOX(&pReg->extents, x, y))
  2083.         return(FALSE);
  2084.     if (numRects == 1)
  2085.     {
  2086.     *box = pReg->extents;
  2087.     return(TRUE);
  2088.     }
  2089.     for (pbox = REGION_BOXPTR(pReg), pboxEnd = pbox + numRects;
  2090.      pbox != pboxEnd;
  2091.      pbox++)
  2092.     {
  2093.         if (y >= pbox->y2)
  2094.        continue;        /* not there yet */
  2095.     if ((y < pbox->y1) || (x < pbox->x1))
  2096.        break;        /* missed it */
  2097.     if (x >= pbox->x2)
  2098.        continue;        /* not there yet */
  2099.     *box = *pbox;
  2100.     return(TRUE);
  2101.     }
  2102.     return(FALSE);
  2103. }
  2104.  
  2105. Bool
  2106. miRegionNotEmpty(pReg)
  2107.     RegionPtr pReg;
  2108. {
  2109.     good(pReg);
  2110.     return(!REGION_NIL(pReg));
  2111. }
  2112.  
  2113.  
  2114. void
  2115. miRegionEmpty(pReg)
  2116.     RegionPtr pReg;
  2117. {
  2118.     good(pReg);
  2119.     xfreeData(pReg);
  2120.     pReg->extents.x2 = pReg->extents.x1;
  2121.     pReg->extents.y2 = pReg->extents.y1;
  2122.     pReg->data = &EmptyData;
  2123. }
  2124.  
  2125. BoxPtr
  2126. miRegionExtents(pReg)
  2127.     RegionPtr pReg;
  2128. {
  2129.     good(pReg);
  2130.     return(&pReg->extents);
  2131. }
  2132.  
  2133. #define ExchangeSpans(a, b)                    \
  2134. {                                \
  2135.     DDXPointRec     tpt;                    \
  2136.     register int    tw;                        \
  2137.                                 \
  2138.     tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt;    \
  2139.     tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
  2140. }
  2141.  
  2142. /* ||| I should apply the merge sort code to rectangle sorting above, and see
  2143.    if mapping time can be improved.  But right now I've been at work 12 hours,
  2144.    so forget it.
  2145. */
  2146.  
  2147. static void QuickSortSpans(spans, widths, numSpans)
  2148.     register DDXPointRec    spans[];
  2149.     register int        widths[];
  2150.     register int        numSpans;
  2151. {
  2152.     register int        y;
  2153.     register int        i, j, m;
  2154.     register DDXPointPtr    r;
  2155.  
  2156.     /* Always called with numSpans > 1 */
  2157.     /* Sorts only by y, doesn't bother to sort by x */
  2158.  
  2159.     do
  2160.     {
  2161.     if (numSpans < 9)
  2162.     {
  2163.         /* Do insertion sort */
  2164.         register int yprev;
  2165.  
  2166.         yprev = spans[0].y;
  2167.         i = 1;
  2168.         do
  2169.         { /* while i != numSpans */
  2170.         y = spans[i].y;
  2171.         if (yprev > y)
  2172.         {
  2173.             /* spans[i] is out of order.  Move into proper location. */
  2174.             DDXPointRec tpt;
  2175.             int        tw, k;
  2176.  
  2177.             for (j = 0; y >= spans[j].y; j++) {}
  2178.             tpt = spans[i];
  2179.             tw  = widths[i];
  2180.             for (k = i; k != j; k--)
  2181.             {
  2182.             spans[k] = spans[k-1];
  2183.             widths[k] = widths[k-1];
  2184.             }
  2185.             spans[j] = tpt;
  2186.             widths[j] = tw;
  2187.             y = spans[i].y;
  2188.         } /* if out of order */
  2189.         yprev = y;
  2190.         i++;
  2191.         } while (i != numSpans);
  2192.         return;
  2193.     }
  2194.  
  2195.     /* Choose partition element, stick in location 0 */
  2196.     m = numSpans / 2;
  2197.     if (spans[m].y > spans[0].y)        ExchangeSpans(m, 0);
  2198.     if (spans[m].y > spans[numSpans-1].y)   ExchangeSpans(m, numSpans-1);
  2199.     if (spans[m].y > spans[0].y)        ExchangeSpans(m, 0);
  2200.     y = spans[0].y;
  2201.  
  2202.         /* Partition array */
  2203.         i = 0;
  2204.         j = numSpans;
  2205.         do
  2206.     {
  2207.         r = &(spans[i]);
  2208.         do
  2209.         {
  2210.         r++;
  2211.         i++;
  2212.             } while (i != numSpans && r->y < y);
  2213.         r = &(spans[j]);
  2214.         do
  2215.         {
  2216.         r--;
  2217.         j--;
  2218.             } while (y < r->y);
  2219.             if (i < j)
  2220.         ExchangeSpans(i, j);
  2221.         } while (i < j);
  2222.  
  2223.         /* Move partition element back to middle */
  2224.         ExchangeSpans(0, j);
  2225.  
  2226.     /* Recurse */
  2227.         if (numSpans-j-1 > 1)
  2228.         QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1);
  2229.         numSpans = j;
  2230.     } while (numSpans > 1);
  2231. }
  2232.  
  2233. #define NextBand()                            \
  2234. {                                    \
  2235.     clipy1 = pboxBandStart->y1;                        \
  2236.     clipy2 = pboxBandStart->y2;                        \
  2237.     pboxBandEnd = pboxBandStart + 1;                    \
  2238.     while (pboxBandEnd != pboxLast && pboxBandEnd->y1 == clipy1) {  \
  2239.     pboxBandEnd++;                            \
  2240.     }                                    \
  2241.     for (; ppt != pptLast && ppt->y < clipy1; ppt++, pwidth++) {} \
  2242. }
  2243.  
  2244. /*
  2245.     Clip a list of scanlines to a region.  The caller has allocated the
  2246.     space.  FSorted is non-zero if the scanline origins are in ascending
  2247.     order.
  2248.     returns the number of new, clipped scanlines.
  2249. */
  2250.  
  2251. int
  2252. miClipSpans(prgnDst, ppt, pwidth, nspans, pptNew, pwidthNew, fSorted)
  2253.     RegionPtr            prgnDst;
  2254.     register DDXPointPtr    ppt;
  2255.     register int        *pwidth;
  2256.     int                nspans;
  2257.     register DDXPointPtr    pptNew;
  2258.     int                *pwidthNew;
  2259.     int                fSorted;
  2260. {
  2261.     register DDXPointPtr pptLast;
  2262.     int            *pwidthNewStart;    /* the vengeance of Xerox! */
  2263.     register int    y, x1, x2;
  2264.     register int    numRects;
  2265.  
  2266.     good(prgnDst);
  2267.     pptLast = ppt + nspans;
  2268.     pwidthNewStart = pwidthNew;
  2269.  
  2270.     if (!prgnDst->data)
  2271.     {
  2272.     /* Do special fast code with clip boundaries in registers(?) */
  2273.     /* It doesn't pay much to make use of fSorted in this case, 
  2274.        so we lump everything together. */
  2275.  
  2276.     register    int clipx1, clipx2, clipy1, clipy2;
  2277.  
  2278.     clipx1 = prgnDst->extents.x1;
  2279.     clipy1 = prgnDst->extents.y1;
  2280.     clipx2 = prgnDst->extents.x2;
  2281.     clipy2 = prgnDst->extents.y2;
  2282.         
  2283.     for (; ppt != pptLast; ppt++, pwidth++)
  2284.     {
  2285.         y = ppt->y;
  2286.         x1 = ppt->x;
  2287.         if (clipy1 <= y && y < clipy2)
  2288.         {
  2289.         x2 = x1 + *pwidth;
  2290.         if (x1 < clipx1)    x1 = clipx1;
  2291.         if (x2 > clipx2)    x2 = clipx2;
  2292.         if (x1 < x2)
  2293.         {
  2294.             /* part of span in clip rectangle */
  2295.             pptNew->x = x1;
  2296.             pptNew->y = y;
  2297.             *pwidthNew = x2 - x1;
  2298.             pptNew++;
  2299.             pwidthNew++;
  2300.         }
  2301.         }
  2302.     } /* end for */
  2303.  
  2304.     }
  2305.     else if (numRects = prgnDst->data->numRects)
  2306.     {
  2307.     /* Have to clip against many boxes */
  2308.     BoxPtr        pboxBandStart, pboxBandEnd;
  2309.     register BoxPtr pbox;
  2310.     register BoxPtr pboxLast;
  2311.     register int    clipy1, clipy2;
  2312.  
  2313.     /* In this case, taking advantage of sorted spans gains more than
  2314.        the sorting costs. */
  2315.     if ((! fSorted) && (nspans > 1))
  2316.         QuickSortSpans(ppt, pwidth, nspans);
  2317.  
  2318.     pboxBandStart = REGION_BOXPTR(prgnDst);
  2319.     pboxLast = pboxBandStart + numRects;
  2320.     
  2321.     NextBand();
  2322.  
  2323.     for (; ppt != pptLast; )
  2324.     {
  2325.         y = ppt->y;
  2326.         if (y < clipy2)
  2327.         {
  2328.         /* span is in the current band */
  2329.         pbox = pboxBandStart;
  2330.         x1 = ppt->x;
  2331.         x2 = x1 + *pwidth;
  2332.         do
  2333.         { /* For each box in band */
  2334.             register int    newx1, newx2;
  2335.  
  2336.             newx1 = x1;
  2337.             newx2 = x2;
  2338.             if (newx1 < pbox->x1)   newx1 = pbox->x1;
  2339.             if (newx2 > pbox->x2)   newx2 = pbox->x2;
  2340.             if (newx1 < newx2)
  2341.             {
  2342.             /* Part of span in clip rectangle */
  2343.             pptNew->x = newx1;
  2344.             pptNew->y = y;
  2345.             *pwidthNew = newx2 - newx1;
  2346.             pptNew++;
  2347.             pwidthNew++;
  2348.             }
  2349.             pbox++;
  2350.         } while (pbox != pboxBandEnd);
  2351.         ppt++;
  2352.         pwidth++;
  2353.         }
  2354.         else
  2355.         {
  2356.         /* Move to next band, adjust ppt as needed */
  2357.         pboxBandStart = pboxBandEnd;
  2358.         if (pboxBandStart == pboxLast)
  2359.             break; /* We're completely done */
  2360.         NextBand();
  2361.         }
  2362.     }
  2363.     }
  2364.     return (pwidthNew - pwidthNewStart);
  2365. }
  2366.  
  2367. /* find the band in a region with the most rectangles */
  2368. int
  2369. miFindMaxBand(prgn)
  2370.     RegionPtr prgn;
  2371. {
  2372.     register int nbox;
  2373.     register BoxPtr pbox;
  2374.     register int nThisBand;
  2375.     register int nMaxBand = 0;
  2376.     short yThisBand;
  2377.  
  2378.     good(prgn);
  2379.     nbox = REGION_NUM_RECTS(prgn);
  2380.     pbox = REGION_RECTS(prgn);
  2381.  
  2382.     while(nbox > 0)
  2383.     {
  2384.     yThisBand = pbox->y1;
  2385.     nThisBand = 0;
  2386.     while((nbox > 0) && (pbox->y1 == yThisBand))
  2387.     {
  2388.         nbox--;
  2389.         pbox++;
  2390.         nThisBand++;
  2391.     }
  2392.     if (nThisBand > nMaxBand)
  2393.         nMaxBand = nThisBand;
  2394.     }
  2395.     return (nMaxBand);
  2396. }
  2397.