Pileus Git - ~andy/gtk/blob - gdk/gdkregion-generic.c

   1 /* $TOG: Region.c /main/31 1998/02/06 17:50:22 kaleb $ */
   2 /************************************************************************
   3
   4 Copyright 1987, 1988, 1998  The Open Group
   5
   6 All Rights Reserved.
   7
   8 The above copyright notice and this permission notice shall be included in
   9 all copies or substantial portions of the Software.
  10
  11 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  12 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  13 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  14 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  15 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  16 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  17
  18 Except as contained in this notice, the name of The Open Group shall not be
  19 used in advertising or otherwise to promote the sale, use or other dealings
  20 in this Software without prior written authorization from The Open Group.
  21
  22
  23 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
  24
  25                         All Rights Reserved
  26
  27 Permission to use, copy, modify, and distribute this software and its
  28 documentation for any purpose and without fee is hereby granted,
  29 provided that the above copyright notice appear in all copies and that
  30 both that copyright notice and this permission notice appear in
  31 supporting documentation, and that the name of Digital not be
  32 used in advertising or publicity pertaining to distribution of the
  33 software without specific, written prior permission.
  34
  35 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  36 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  37 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  38 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  39 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  40 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  41 SOFTWARE.
  42
  43 ************************************************************************/
  44 /* $XFree86: xc/lib/X11/Region.c,v 1.5 1999/05/09 10:50:01 dawes Exp $ */
  45 /*
  46  * The functions in this file implement the Region abstraction, similar to one
  47  * used in the X11 sample server. A Region is simply an area, as the name
  48  * implies, and is implemented as a "y-x-banded" array of rectangles. To
  49  * explain: Each Region is made up of a certain number of rectangles sorted
  50  * by y coordinate first, and then by x coordinate.
  51  *
  52  * Furthermore, the rectangles are banded such that every rectangle with a
  53  * given upper-left y coordinate (y1) will have the same lower-right y
  54  * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
  55  * will span the entire vertical distance of the band. This means that some
  56  * areas that could be merged into a taller rectangle will be represented as
  57  * several shorter rectangles to account for shorter rectangles to its left
  58  * or right but within its "vertical scope".
  59  *
  60  * An added constraint on the rectangles is that they must cover as much
  61  * horizontal area as possible. E.g. no two rectangles in a band are allowed
  62  * to touch.
  63  *
  64  * Whenever possible, bands will be merged together to cover a greater vertical
  65  * distance (and thus reduce the number of rectangles). Two bands can be merged
  66  * only if the bottom of one touches the top of the other and they have
  67  * rectangles in the same places (of the same width, of course). This maintains
  68  * the y-x-banding that's so nice to have...
  69  */
  70
  71 #include <stdlib.h>
  72 #include <string.h>
  73 #include <gdkregion.h>
  74 #include "gdkregion-generic.h"
  75
  76 #ifdef DEBUG
  77 #include <stdio.h>
  78 #define assert(expr) {if (!(expr)) fprintf(stderr,\
  79 "Assertion failed file %s, line %d: expr\n", __FILE__, __LINE__); }
  80 #else
  81 #define assert(expr)
  82 #endif
  83
  84 typedef void (*overlapFunc) (GdkRegion    *pReg,
  85                              GdkRegionBox *r1,
  86                              GdkRegionBox *r1End,
  87                              GdkRegionBox *r2,
  88                              GdkRegionBox *r2End,
  89                              gint          y1,
  90                              gint          y2);
  91 typedef void (*nonOverlapFunc) (GdkRegion    *pReg,
  92                                 GdkRegionBox *r,
  93                                 GdkRegionBox *rEnd,
  94                                 gint          y1,
  95                                 gint          y2);
  96
  97 static void miRegionCopy (GdkRegion      *dstrgn,
  98                           GdkRegion      *rgn);
  99 static void miRegionOp   (GdkRegion      *newReg,
 100                           GdkRegion      *reg1,
 101                           GdkRegion      *reg2,
 102                           overlapFunc     overlapFn,
 103                           nonOverlapFunc  nonOverlap1Fn,
 104                           nonOverlapFunc  nonOverlap2Fn);
 105
 106 /*      Create a new empty region       */
 107
 108 GdkRegion *
 109 gdk_region_new ()
 110 {
 111   GdkRegion *temp;
 112
 113   temp = g_new (GdkRegion, 1);
 114   temp->rects = g_new (GdkRegionBox, 1);
 115
 116   temp->numRects = 0;
 117   temp->extents.x1 = 0;
 118   temp->extents.y1 = 0;
 119   temp->extents.x2 = 0;
 120   temp->extents.y2 = 0;
 121   temp->size = 1;
 122
 123   return temp;
 124 }
 125
 126 /**
 127  * gdk_region_rectangle:
 128  * @rectangle: a #GdkRectangle
 129  *
 130  * Creates a new region containing the area @rectangle.
 131  *
 132  * Return value: a new region
 133  **/
 134 GdkRegion *
 135 gdk_region_rectangle (GdkRectangle *rectangle)
 136 {
 137   GdkRegion *temp;
 138
 139   g_return_val_if_fail (rectangle != NULL, NULL);
 140
 141   if (rectangle->width <= 0 || rectangle->height <= 0)
 142     return gdk_region_new();
 143
 144   temp = g_new (GdkRegion, 1);
 145   temp->rects = g_new (GdkRegionBox, 1);
 146
 147   temp->numRects = 1;
 148   temp->extents.x1 = temp->rects[0].x1 = rectangle->x;
 149   temp->extents.y1 = temp->rects[0].y1 = rectangle->y;
 150   temp->extents.x2 = temp->rects[0].x2 = rectangle->x + rectangle->width;
 151   temp->extents.y2 = temp->rects[0].y2 = rectangle->y + rectangle->height;
 152   temp->size = 1;
 153
 154   return temp;
 155 }
 156
 157 /**
 158  * gdk_region_copy:
 159  * @region: a #GdkRegion
 160  *
 161  * Copies @region, creating an identical new region.
 162  *
 163  * Return value: a new region identical to @region
 164  **/
 165 GdkRegion *
 166 gdk_region_copy (GdkRegion *region)
 167 {
 168   GdkRegion *temp;
 169
 170   g_return_val_if_fail (region != NULL, NULL);
 171
 172   temp = g_new (GdkRegion, 1);
 173   temp->rects = g_new (GdkRegionBox, region->numRects);
 174
 175   temp->numRects = region->numRects;
 176   temp->extents = region->extents;
 177   temp->size = region->numRects;
 178
 179   memcpy (temp->rects, region->rects, region->numRects * sizeof (GdkRegionBox));
 180
 181   return temp;
 182 }
 183
 184 void
 185 gdk_region_get_clipbox (GdkRegion *r, GdkRectangle *rect)
 186 {
 187   g_return_if_fail (r != NULL);
 188   g_return_if_fail (rect != NULL);
 189
 190   rect->x = r->extents.x1;
 191   rect->y = r->extents.y1;
 192   rect->width = r->extents.x2 - r->extents.x1;
 193   rect->height = r->extents.y2 - r->extents.y1;
 194 }
 195
 196
 197 /**
 198  * gdk_region_get_rectangles:
 199  * @region: a #GdkRegion
 200  * @rectangles: return location for an array of rectangles
 201  * @n_rectangles: length of returned array
 202  *
 203  * Obtains the area covered by the region as a list of rectangles.
 204  * The array returned in @rectangles must be freed with g_free().
 205  *
 206  **/
 207 void
 208 gdk_region_get_rectangles (GdkRegion     *region,
 209                            GdkRectangle **rectangles,
 210                            gint          *n_rectangles)
 211 {
 212   gint i;
 213
 214   g_return_if_fail (region != NULL);
 215   g_return_if_fail (rectangles != NULL);
 216   g_return_if_fail (n_rectangles != NULL);
 217
 218   *n_rectangles = region->numRects;
 219   *rectangles = g_new (GdkRectangle, region->numRects);
 220
 221   for (i = 0; i < region->numRects; i++)
 222     {
 223       GdkRegionBox rect;
 224       rect = region->rects[i];
 225       (*rectangles)[i].x = rect.x1;
 226       (*rectangles)[i].y = rect.y1;
 227       (*rectangles)[i].width = rect.x2 - rect.x1;
 228       (*rectangles)[i].height = rect.y2 - rect.y1;
 229     }
 230 }
 231
 232 /**
 233  * gdk_region_union_with_rect:
 234  * @region: a #GdkRegion.
 235  * @rect: a #GdkRectangle.
 236  *
 237  * Sets the area of @region to the union of the areas of @region and
 238  * @rect. The resulting area is the set of pixels contained in
 239  * either @region or @rect.
 240  **/
 241 void
 242 gdk_region_union_with_rect (GdkRegion    *region,
 243                             GdkRectangle *rect)
 244 {
 245   GdkRegion tmp_region;
 246
 247   g_return_if_fail (region != NULL);
 248   g_return_if_fail (rect != NULL);
 249
 250   if (!rect->width || !rect->height)
 251     return;
 252
 253   tmp_region.rects = &tmp_region.extents;
 254   tmp_region.numRects = 1;
 255   tmp_region.extents.x1 = rect->x;
 256   tmp_region.extents.y1 = rect->y;
 257   tmp_region.extents.x2 = rect->x + rect->width;
 258   tmp_region.extents.y2 = rect->y + rect->height;
 259   tmp_region.size = 1;
 260
 261   gdk_region_union (region, &tmp_region);
 262 }
 263
 264 /*-
 265  *-----------------------------------------------------------------------
 266  * miSetExtents --
 267  *      Reset the extents of a region to what they should be. Called by
 268  *      miSubtract and miIntersect b/c they can't figure it out along the
 269  *      way or do so easily, as miUnion can.
 270  *
 271  * Results:
 272  *      None.
 273  *
 274  * Side Effects:
 275  *      The region's 'extents' structure is overwritten.
 276  *
 277  *-----------------------------------------------------------------------
 278  */
 279 static void
 280 miSetExtents (GdkRegion *pReg)
 281 {
 282   GdkRegionBox *pBox, *pBoxEnd, *pExtents;
 283
 284   if (pReg->numRects == 0)
 285     {
 286       pReg->extents.x1 = 0;
 287       pReg->extents.y1 = 0;
 288       pReg->extents.x2 = 0;
 289       pReg->extents.y2 = 0;
 290       return;
 291     }
 292
 293   pExtents = &pReg->extents;
 294   pBox = pReg->rects;
 295   pBoxEnd = &pBox[pReg->numRects - 1];
 296
 297     /*
 298      * Since pBox is the first rectangle in the region, it must have the
 299      * smallest y1 and since pBoxEnd is the last rectangle in the region,
 300      * it must have the largest y2, because of banding. Initialize x1 and
 301      * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
 302      * to...
 303      */
 304   pExtents->x1 = pBox->x1;
 305   pExtents->y1 = pBox->y1;
 306   pExtents->x2 = pBoxEnd->x2;
 307   pExtents->y2 = pBoxEnd->y2;
 308
 309   assert(pExtents->y1 < pExtents->y2);
 310   while (pBox <= pBoxEnd)
 311     {
 312       if (pBox->x1 < pExtents->x1)
 313         {
 314           pExtents->x1 = pBox->x1;
 315         }
 316       if (pBox->x2 > pExtents->x2)
 317         {
 318           pExtents->x2 = pBox->x2;
 319         }
 320       pBox++;
 321     }
 322   assert(pExtents->x1 < pExtents->x2);
 323 }
 324
 325 void
 326 gdk_region_destroy (GdkRegion *r)
 327 {
 328   g_return_if_fail (r != NULL);
 329
 330   g_free (r->rects);
 331   g_free (r);
 332 }
 333
 334
 335 /* TranslateRegion(pRegion, x, y)
 336    translates in place
 337    added by raymond
 338 */
 339
 340 void
 341 gdk_region_offset (GdkRegion *region,
 342                    gint       x,
 343                    gint       y)
 344 {
 345   int nbox;
 346   GdkRegionBox *pbox;
 347
 348   g_return_if_fail (region != NULL);
 349
 350   pbox = region->rects;
 351   nbox = region->numRects;
 352
 353   while(nbox--)
 354     {
 355       pbox->x1 += x;
 356       pbox->x2 += x;
 357       pbox->y1 += y;
 358       pbox->y2 += y;
 359       pbox++;
 360     }
 361   region->extents.x1 += x;
 362   region->extents.x2 += x;
 363   region->extents.y1 += y;
 364   region->extents.y2 += y;
 365 }
 366
 367 /*
 368    Utility procedure Compress:
 369    Replace r by the region r', where
 370      p in r' iff (Quantifer m <= dx) (p + m in r), and
 371      Quantifier is Exists if grow is TRUE, For all if grow is FALSE, and
 372      (x,y) + m = (x+m,y) if xdir is TRUE; (x,y+m) if xdir is FALSE.
 373
 374    Thus, if xdir is TRUE and grow is FALSE, r is replaced by the region
 375    of all points p such that p and the next dx points on the same
 376    horizontal scan line are all in r.  We do this using by noting
 377    that p is the head of a run of length 2^i + k iff p is the head
 378    of a run of length 2^i and p+2^i is the head of a run of length
 379    k. Thus, the loop invariant: s contains the region corresponding
 380    to the runs of length shift.  r contains the region corresponding
 381    to the runs of length 1 + dxo & (shift-1), where dxo is the original
 382    value of dx.  dx = dxo & ~(shift-1).  As parameters, s and t are
 383    scratch regions, so that we don't have to allocate them on every
 384    call.
 385 */
 386
 387 #define ZOpRegion(a,b) if (grow) gdk_region_union (a, b); \
 388                          else gdk_region_intersect (a,b)
 389 #define ZShiftRegion(a,b) if (xdir) gdk_region_offset (a,b,0); \
 390                           else gdk_region_offset (a,0,b)
 391
 392 static void
 393 Compress(GdkRegion *r,
 394          GdkRegion *s,
 395          GdkRegion *t,
 396          guint      dx,
 397          int        xdir,
 398          int        grow)
 399 {
 400   guint shift = 1;
 401
 402   miRegionCopy (s, r);
 403   while (dx)
 404     {
 405       if (dx & shift)
 406         {
 407           ZShiftRegion(r, -(int)shift);
 408           ZOpRegion(r, s);
 409           dx -= shift;
 410           if (!dx) break;
 411         }
 412       miRegionCopy (t, s);
 413       ZShiftRegion(s, -(int)shift);
 414       ZOpRegion(s, t);
 415       shift <<= 1;
 416     }
 417 }
 418
 419 #undef ZOpRegion
 420 #undef ZShiftRegion
 421 #undef ZCopyRegion
 422
 423 void
 424 gdk_region_shrink (GdkRegion *r,
 425                    int        dx,
 426                    int        dy)
 427 {
 428   GdkRegion *s, *t;
 429   int grow;
 430
 431   g_return_if_fail (r != NULL);
 432
 433   if (!dx && !dy)
 434     return;
 435
 436   s = gdk_region_new ();
 437   t = gdk_region_new ();
 438
 439   grow = (dx < 0);
 440   if (grow)
 441     dx = -dx;
 442   if (dx)
 443      Compress(r, s, t, (unsigned) 2*dx, TRUE, grow);
 444
 445   grow = (dy < 0);
 446   if (grow)
 447     dy = -dy;
 448   if (dy)
 449      Compress(r, s, t, (unsigned) 2*dy, FALSE, grow);
 450
 451   gdk_region_offset (r, dx, dy);
 452   gdk_region_destroy (s);
 453   gdk_region_destroy (t);
 454 }
 455
 456 \f
 457 /*======================================================================
 458  *          Region Intersection
 459  *====================================================================*/
 460 /*-
 461  *-----------------------------------------------------------------------
 462  * miIntersectO --
 463  *      Handle an overlapping band for miIntersect.
 464  *
 465  * Results:
 466  *      None.
 467  *
 468  * Side Effects:
 469  *      Rectangles may be added to the region.
 470  *
 471  *-----------------------------------------------------------------------
 472  */
 473 /* static void*/
 474 static void
 475 miIntersectO (GdkRegion    *pReg,
 476               GdkRegionBox *r1,
 477               GdkRegionBox *r1End,
 478               GdkRegionBox *r2,
 479               GdkRegionBox *r2End,
 480               gint          y1,
 481               gint          y2)
 482 {
 483   int   x1;
 484   int   x2;
 485   GdkRegionBox *pNextRect;
 486
 487   pNextRect = &pReg->rects[pReg->numRects];
 488
 489   while ((r1 != r1End) && (r2 != r2End))
 490     {
 491       x1 = MAX (r1->x1,r2->x1);
 492       x2 = MIN (r1->x2,r2->x2);
 493
 494       /*
 495        * If there's any overlap between the two rectangles, add that
 496        * overlap to the new region.
 497        * There's no need to check for subsumption because the only way
 498        * such a need could arise is if some region has two rectangles
 499        * right next to each other. Since that should never happen...
 500        */
 501       if (x1 < x2)
 502         {
 503           assert (y1<y2);
 504
 505           MEMCHECK (pReg, pNextRect, pReg->rects);
 506           pNextRect->x1 = x1;
 507           pNextRect->y1 = y1;
 508           pNextRect->x2 = x2;
 509           pNextRect->y2 = y2;
 510           pReg->numRects += 1;
 511           pNextRect++;
 512           assert (pReg->numRects <= pReg->size);
 513         }
 514
 515       /*
 516        * Need to advance the pointers. Shift the one that extends
 517        * to the right the least, since the other still has a chance to
 518        * overlap with that region's next rectangle, if you see what I mean.
 519        */
 520       if (r1->x2 < r2->x2)
 521         {
 522           r1++;
 523         }
 524       else if (r2->x2 < r1->x2)
 525         {
 526           r2++;
 527         }
 528       else
 529         {
 530           r1++;
 531           r2++;
 532         }
 533     }
 534 }
 535
 536 /**
 537  * gdk_region_intersect:
 538  * @source1: a #GdkRegion
 539  * @source2: another #GdkRegion
 540  *
 541  * Sets the area of @source1 to the intersection of the areas of @source1
 542  * and @source2. The resulting area is the set of pixels contained in
 543  * both @source1 and @source2.
 544  **/
 545 void
 546 gdk_region_intersect (GdkRegion *region,
 547                       GdkRegion *other)
 548 {
 549   g_return_if_fail (region != NULL);
 550   g_return_if_fail (other != NULL);
 551
 552   /* check for trivial reject */
 553   if ((!(region->numRects)) || (!(other->numRects))  ||
 554       (!EXTENTCHECK(&region->extents, &other->extents)))
 555     region->numRects = 0;
 556   else
 557     miRegionOp (region, region, other,
 558                 miIntersectO, (nonOverlapFunc) NULL, (nonOverlapFunc) NULL);
 559
 560   /*
 561    * Can't alter region's extents before miRegionOp depends on the
 562    * extents of the regions being unchanged. Besides, this way there's
 563    * no checking against rectangles that will be nuked due to
 564    * coalescing, so we have to examine fewer rectangles.
 565    */
 566   miSetExtents(region);
 567 }
 568
 569 static void
 570 miRegionCopy(GdkRegion *dstrgn, GdkRegion *rgn)
 571 {
 572   if (dstrgn != rgn) /*  don't want to copy to itself */
 573     {
 574       if (dstrgn->size < rgn->numRects)
 575         {
 576           dstrgn->rects = g_renew (GdkRegionBox, dstrgn->rects, rgn->numRects);
 577           dstrgn->size = rgn->numRects;
 578         }
 579       dstrgn->numRects = rgn->numRects;
 580       dstrgn->extents.x1 = rgn->extents.x1;
 581       dstrgn->extents.y1 = rgn->extents.y1;
 582       dstrgn->extents.x2 = rgn->extents.x2;
 583       dstrgn->extents.y2 = rgn->extents.y2;
 584
 585       memcpy (dstrgn->rects, rgn->rects, rgn->numRects * sizeof (GdkRegionBox));
 586     }
 587 }
 588
 589
 590 /*======================================================================
 591  *          Generic Region Operator
 592  *====================================================================*/
 593
 594 /*-
 595  *-----------------------------------------------------------------------
 596  * miCoalesce --
 597  *      Attempt to merge the boxes in the current band with those in the
 598  *      previous one. Used only by miRegionOp.
 599  *
 600  * Results:
 601  *      The new index for the previous band.
 602  *
 603  * Side Effects:
 604  *      If coalescing takes place:
 605  *          - rectangles in the previous band will have their y2 fields
 606  *            altered.
 607  *          - pReg->numRects will be decreased.
 608  *
 609  *-----------------------------------------------------------------------
 610  */
 611 /* static int*/
 612 static int
 613 miCoalesce (GdkRegion *pReg,         /* Region to coalesce */
 614             gint       prevStart,    /* Index of start of previous band */
 615             gint       curStart)     /* Index of start of current band */
 616 {
 617   GdkRegionBox *pPrevBox;       /* Current box in previous band */
 618   GdkRegionBox *pCurBox;        /* Current box in current band */
 619   GdkRegionBox *pRegEnd;        /* End of region */
 620   int           curNumRects;    /* Number of rectangles in current
 621                                  * band */
 622   int           prevNumRects;   /* Number of rectangles in previous
 623                                  * band */
 624   int           bandY1;         /* Y1 coordinate for current band */
 625
 626   pRegEnd = &pReg->rects[pReg->numRects];
 627
 628   pPrevBox = &pReg->rects[prevStart];
 629   prevNumRects = curStart - prevStart;
 630
 631     /*
 632      * Figure out how many rectangles are in the current band. Have to do
 633      * this because multiple bands could have been added in miRegionOp
 634      * at the end when one region has been exhausted.
 635      */
 636   pCurBox = &pReg->rects[curStart];
 637   bandY1 = pCurBox->y1;
 638   for (curNumRects = 0;
 639        (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
 640        curNumRects++)
 641     {
 642       pCurBox++;
 643     }
 644
 645   if (pCurBox != pRegEnd)
 646     {
 647       /*
 648        * If more than one band was added, we have to find the start
 649        * of the last band added so the next coalescing job can start
 650        * at the right place... (given when multiple bands are added,
 651        * this may be pointless -- see above).
 652        */
 653       pRegEnd--;
 654       while (pRegEnd[-1].y1 == pRegEnd->y1)
 655         {
 656           pRegEnd--;
 657         }
 658       curStart = pRegEnd - pReg->rects;
 659       pRegEnd = pReg->rects + pReg->numRects;
 660     }
 661
 662   if ((curNumRects == prevNumRects) && (curNumRects != 0)) {
 663     pCurBox -= curNumRects;
 664     /*
 665      * The bands may only be coalesced if the bottom of the previous
 666      * matches the top scanline of the current.
 667      */
 668     if (pPrevBox->y2 == pCurBox->y1)
 669       {
 670         /*
 671          * Make sure the bands have boxes in the same places. This
 672          * assumes that boxes have been added in such a way that they
 673          * cover the most area possible. I.e. two boxes in a band must
 674          * have some horizontal space between them.
 675          */
 676         do
 677           {
 678             if ((pPrevBox->x1 != pCurBox->x1) ||
 679                 (pPrevBox->x2 != pCurBox->x2))
 680               {
 681                 /*
 682                  * The bands don't line up so they can't be coalesced.
 683                  */
 684                 return (curStart);
 685               }
 686             pPrevBox++;
 687             pCurBox++;
 688             prevNumRects -= 1;
 689           } while (prevNumRects != 0);
 690
 691         pReg->numRects -= curNumRects;
 692         pCurBox -= curNumRects;
 693         pPrevBox -= curNumRects;
 694
 695         /*
 696          * The bands may be merged, so set the bottom y of each box
 697          * in the previous band to that of the corresponding box in
 698          * the current band.
 699          */
 700         do
 701           {
 702             pPrevBox->y2 = pCurBox->y2;
 703             pPrevBox++;
 704             pCurBox++;
 705             curNumRects -= 1;
 706           }
 707         while (curNumRects != 0);
 708
 709         /*
 710          * If only one band was added to the region, we have to backup
 711          * curStart to the start of the previous band.
 712          *
 713          * If more than one band was added to the region, copy the
 714          * other bands down. The assumption here is that the other bands
 715          * came from the same region as the current one and no further
 716          * coalescing can be done on them since it's all been done
 717          * already... curStart is already in the right place.
 718          */
 719         if (pCurBox == pRegEnd)
 720           {
 721             curStart = prevStart;
 722           }
 723         else
 724           {
 725             do
 726               {
 727                 *pPrevBox++ = *pCurBox++;
 728               }
 729             while (pCurBox != pRegEnd);
 730           }
 731
 732       }
 733   }
 734   return curStart;
 735 }
 736
 737 /*-
 738  *-----------------------------------------------------------------------
 739  * miRegionOp --
 740  *      Apply an operation to two regions. Called by miUnion, miInverse,
 741  *      miSubtract, miIntersect...
 742  *
 743  * Results:
 744  *      None.
 745  *
 746  * Side Effects:
 747  *      The new region is overwritten.
 748  *
 749  * Notes:
 750  *      The idea behind this function is to view the two regions as sets.
 751  *      Together they cover a rectangle of area that this function divides
 752  *      into horizontal bands where points are covered only by one region
 753  *      or by both. For the first case, the nonOverlapFunc is called with
 754  *      each the band and the band's upper and lower extents. For the
 755  *      second, the overlapFunc is called to process the entire band. It
 756  *      is responsible for clipping the rectangles in the band, though
 757  *      this function provides the boundaries.
 758  *      At the end of each band, the new region is coalesced, if possible,
 759  *      to reduce the number of rectangles in the region.
 760  *
 761  *-----------------------------------------------------------------------
 762  */
 763 /* static void*/
 764 static void
 765 miRegionOp(GdkRegion *newReg,
 766            GdkRegion *reg1,
 767            GdkRegion *reg2,
 768            overlapFunc    overlapFn,            /* Function to call for over-
 769                                                  * lapping bands */
 770            nonOverlapFunc nonOverlap1Fn,        /* Function to call for non-
 771                                                  * overlapping bands in region
 772                                                  * 1 */
 773            nonOverlapFunc nonOverlap2Fn)        /* Function to call for non-
 774                                                  * overlapping bands in region
 775                                                  * 2 */
 776 {
 777     GdkRegionBox *r1;                   /* Pointer into first region */
 778     GdkRegionBox *r2;                   /* Pointer into 2d region */
 779     GdkRegionBox *r1End;                /* End of 1st region */
 780     GdkRegionBox *r2End;                /* End of 2d region */
 781     int           ybot;                 /* Bottom of intersection */
 782     int           ytop;                 /* Top of intersection */
 783     GdkRegionBox *oldRects;             /* Old rects for newReg */
 784     int           prevBand;             /* Index of start of
 785                                          * previous band in newReg */
 786     int           curBand;              /* Index of start of current
 787                                          * band in newReg */
 788     GdkRegionBox *r1BandEnd;            /* End of current band in r1 */
 789     GdkRegionBox *r2BandEnd;            /* End of current band in r2 */
 790     int           top;                  /* Top of non-overlapping
 791                                          * band */
 792     int           bot;                  /* Bottom of non-overlapping
 793                                          * band */
 794
 795     /*
 796      * Initialization:
 797      *  set r1, r2, r1End and r2End appropriately, preserve the important
 798      * parts of the destination region until the end in case it's one of
 799      * the two source regions, then mark the "new" region empty, allocating
 800      * another array of rectangles for it to use.
 801      */
 802     r1 = reg1->rects;
 803     r2 = reg2->rects;
 804     r1End = r1 + reg1->numRects;
 805     r2End = r2 + reg2->numRects;
 806
 807     oldRects = newReg->rects;
 808
 809     EMPTY_REGION(newReg);
 810
 811     /*
 812      * Allocate a reasonable number of rectangles for the new region. The idea
 813      * is to allocate enough so the individual functions don't need to
 814      * reallocate and copy the array, which is time consuming, yet we don't
 815      * have to worry about using too much memory. I hope to be able to
 816      * nuke the Xrealloc() at the end of this function eventually.
 817      */
 818     newReg->size = MAX (reg1->numRects, reg2->numRects) * 2;
 819     newReg->rects = g_new (GdkRegionBox, newReg->size);
 820
 821     /*
 822      * Initialize ybot and ytop.
 823      * In the upcoming loop, ybot and ytop serve different functions depending
 824      * on whether the band being handled is an overlapping or non-overlapping
 825      * band.
 826      *  In the case of a non-overlapping band (only one of the regions
 827      * has points in the band), ybot is the bottom of the most recent
 828      * intersection and thus clips the top of the rectangles in that band.
 829      * ytop is the top of the next intersection between the two regions and
 830      * serves to clip the bottom of the rectangles in the current band.
 831      *  For an overlapping band (where the two regions intersect), ytop clips
 832      * the top of the rectangles of both regions and ybot clips the bottoms.
 833      */
 834     if (reg1->extents.y1 < reg2->extents.y1)
 835       ybot = reg1->extents.y1;
 836     else
 837       ybot = reg2->extents.y1;
 838
 839     /*
 840      * prevBand serves to mark the start of the previous band so rectangles
 841      * can be coalesced into larger rectangles. qv. miCoalesce, above.
 842      * In the beginning, there is no previous band, so prevBand == curBand
 843      * (curBand is set later on, of course, but the first band will always
 844      * start at index 0). prevBand and curBand must be indices because of
 845      * the possible expansion, and resultant moving, of the new region's
 846      * array of rectangles.
 847      */
 848     prevBand = 0;
 849
 850     do
 851       {
 852         curBand = newReg->numRects;
 853
 854         /*
 855          * This algorithm proceeds one source-band (as opposed to a
 856          * destination band, which is determined by where the two regions
 857          * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
 858          * rectangle after the last one in the current band for their
 859          * respective regions.
 860          */
 861         r1BandEnd = r1;
 862         while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
 863           {
 864             r1BandEnd++;
 865           }
 866
 867         r2BandEnd = r2;
 868         while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
 869           {
 870             r2BandEnd++;
 871           }
 872
 873         /*
 874          * First handle the band that doesn't intersect, if any.
 875          *
 876          * Note that attention is restricted to one band in the
 877          * non-intersecting region at once, so if a region has n
 878          * bands between the current position and the next place it overlaps
 879          * the other, this entire loop will be passed through n times.
 880          */
 881         if (r1->y1 < r2->y1)
 882           {
 883             top = MAX (r1->y1,ybot);
 884             bot = MIN (r1->y2,r2->y1);
 885
 886             if ((top != bot) && (nonOverlap1Fn != (void (*)())NULL))
 887               {
 888                 (* nonOverlap1Fn) (newReg, r1, r1BandEnd, top, bot);
 889               }
 890
 891             ytop = r2->y1;
 892           }
 893         else if (r2->y1 < r1->y1)
 894           {
 895             top = MAX (r2->y1,ybot);
 896             bot = MIN (r2->y2,r1->y1);
 897
 898             if ((top != bot) && (nonOverlap2Fn != (void (*)())NULL))
 899               {
 900                 (* nonOverlap2Fn) (newReg, r2, r2BandEnd, top, bot);
 901               }
 902
 903             ytop = r1->y1;
 904           }
 905         else
 906           {
 907             ytop = r1->y1;
 908           }
 909
 910         /*
 911          * If any rectangles got added to the region, try and coalesce them
 912          * with rectangles from the previous band. Note we could just do
 913          * this test in miCoalesce, but some machines incur a not
 914          * inconsiderable cost for function calls, so...
 915          */
 916         if (newReg->numRects != curBand)
 917           {
 918             prevBand = miCoalesce (newReg, prevBand, curBand);
 919           }
 920
 921         /*
 922          * Now see if we've hit an intersecting band. The two bands only
 923          * intersect if ybot > ytop
 924          */
 925         ybot = MIN (r1->y2, r2->y2);
 926         curBand = newReg->numRects;
 927         if (ybot > ytop)
 928           {
 929             (* overlapFn) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
 930
 931           }
 932
 933         if (newReg->numRects != curBand)
 934           {
 935             prevBand = miCoalesce (newReg, prevBand, curBand);
 936           }
 937
 938         /*
 939          * If we've finished with a band (y2 == ybot) we skip forward
 940          * in the region to the next band.
 941          */
 942         if (r1->y2 == ybot)
 943           {
 944             r1 = r1BandEnd;
 945           }
 946         if (r2->y2 == ybot)
 947           {
 948             r2 = r2BandEnd;
 949           }
 950       } while ((r1 != r1End) && (r2 != r2End));
 951
 952     /*
 953      * Deal with whichever region still has rectangles left.
 954      */
 955     curBand = newReg->numRects;
 956     if (r1 != r1End)
 957       {
 958         if (nonOverlap1Fn != (nonOverlapFunc )NULL)
 959           {
 960             do
 961               {
 962                 r1BandEnd = r1;
 963                 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
 964                   {
 965                     r1BandEnd++;
 966                   }
 967                 (* nonOverlap1Fn) (newReg, r1, r1BandEnd,
 968                                      MAX (r1->y1,ybot), r1->y2);
 969                 r1 = r1BandEnd;
 970               } while (r1 != r1End);
 971           }
 972       }
 973     else if ((r2 != r2End) && (nonOverlap2Fn != (nonOverlapFunc) NULL))
 974       {
 975         do
 976           {
 977             r2BandEnd = r2;
 978             while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
 979               {
 980                 r2BandEnd++;
 981               }
 982             (* nonOverlap2Fn) (newReg, r2, r2BandEnd,
 983                                MAX (r2->y1,ybot), r2->y2);
 984             r2 = r2BandEnd;
 985           } while (r2 != r2End);
 986       }
 987
 988     if (newReg->numRects != curBand)
 989     {
 990       (void) miCoalesce (newReg, prevBand, curBand);
 991     }
 992
 993     /*
 994      * A bit of cleanup. To keep regions from growing without bound,
 995      * we shrink the array of rectangles to match the new number of
 996      * rectangles in the region. This never goes to 0, however...
 997      *
 998      * Only do this stuff if the number of rectangles allocated is more than
 999      * twice the number of rectangles in the region (a simple optimization...).
1000      */
1001     if (newReg->numRects < (newReg->size >> 1))
1002       {
1003         if (REGION_NOT_EMPTY (newReg))
1004           {
1005             newReg->size = newReg->numRects;
1006             newReg->rects = g_renew (GdkRegionBox, newReg->rects, newReg->size);
1007           }
1008         else
1009           {
1010             /*
1011              * No point in doing the extra work involved in an Xrealloc if
1012              * the region is empty
1013              */
1014             newReg->size = 1;
1015             g_free (newReg->rects);
1016             newReg->rects = g_new (GdkRegionBox, 1);
1017           }
1018       }
1019     g_free (oldRects);
1020 }
1021
1022 \f
1023 /*======================================================================
1024  *          Region Union
1025  *====================================================================*/
1026
1027 /*-
1028  *-----------------------------------------------------------------------
1029  * miUnionNonO --
1030  *      Handle a non-overlapping band for the union operation. Just
1031  *      Adds the rectangles into the region. Doesn't have to check for
1032  *      subsumption or anything.
1033  *
1034  * Results:
1035  *      None.
1036  *
1037  * Side Effects:
1038  *      pReg->numRects is incremented and the final rectangles overwritten
1039  *      with the rectangles we're passed.
1040  *
1041  *-----------------------------------------------------------------------
1042  */
1043 static void
1044 miUnionNonO (GdkRegion    *pReg,
1045              GdkRegionBox *r,
1046              GdkRegionBox *rEnd,
1047              gint          y1,
1048              gint          y2)
1049 {
1050   GdkRegionBox *pNextRect;
1051
1052   pNextRect = &pReg->rects[pReg->numRects];
1053
1054   assert(y1 < y2);
1055
1056   while (r != rEnd)
1057     {
1058       assert(r->x1 < r->x2);
1059       MEMCHECK(pReg, pNextRect, pReg->rects);
1060       pNextRect->x1 = r->x1;
1061       pNextRect->y1 = y1;
1062       pNextRect->x2 = r->x2;
1063       pNextRect->y2 = y2;
1064       pReg->numRects += 1;
1065       pNextRect++;
1066
1067       assert(pReg->numRects<=pReg->size);
1068       r++;
1069     }
1070 }
1071
1072
1073 /*-
1074  *-----------------------------------------------------------------------
1075  * miUnionO --
1076  *      Handle an overlapping band for the union operation. Picks the
1077  *      left-most rectangle each time and merges it into the region.
1078  *
1079  * Results:
1080  *      None.
1081  *
1082  * Side Effects:
1083  *      Rectangles are overwritten in pReg->rects and pReg->numRects will
1084  *      be changed.
1085  *
1086  *-----------------------------------------------------------------------
1087  */
1088
1089 /* static void*/
1090 static void
1091 miUnionO (GdkRegion *pReg,
1092           GdkRegionBox *r1,
1093           GdkRegionBox *r1End,
1094           GdkRegionBox *r2,
1095           GdkRegionBox *r2End,
1096           gint          y1,
1097           gint          y2)
1098 {
1099   GdkRegionBox *        pNextRect;
1100
1101   pNextRect = &pReg->rects[pReg->numRects];
1102
1103 #define MERGERECT(r)                                    \
1104     if ((pReg->numRects != 0) &&                        \
1105         (pNextRect[-1].y1 == y1) &&                     \
1106         (pNextRect[-1].y2 == y2) &&                     \
1107         (pNextRect[-1].x2 >= r->x1))                    \
1108       {                                                 \
1109         if (pNextRect[-1].x2 < r->x2)                   \
1110           {                                             \
1111             pNextRect[-1].x2 = r->x2;                   \
1112             assert(pNextRect[-1].x1<pNextRect[-1].x2);  \
1113           }                                             \
1114       }                                                 \
1115     else                                                \
1116       {                                                 \
1117         MEMCHECK(pReg, pNextRect, pReg->rects);         \
1118         pNextRect->y1 = y1;                             \
1119         pNextRect->y2 = y2;                             \
1120         pNextRect->x1 = r->x1;                          \
1121         pNextRect->x2 = r->x2;                          \
1122         pReg->numRects += 1;                            \
1123         pNextRect += 1;                                 \
1124       }                                                 \
1125     assert(pReg->numRects<=pReg->size);                 \
1126     r++;
1127
1128     assert (y1<y2);
1129     while ((r1 != r1End) && (r2 != r2End))
1130     {
1131         if (r1->x1 < r2->x1)
1132         {
1133             MERGERECT(r1);
1134         }
1135         else
1136         {
1137             MERGERECT(r2);
1138         }
1139     }
1140
1141     if (r1 != r1End)
1142     {
1143         do
1144         {
1145             MERGERECT(r1);
1146         } while (r1 != r1End);
1147     }
1148     else while (r2 != r2End)
1149     {
1150         MERGERECT(r2);
1151     }
1152 }
1153
1154 /**
1155  * gdk_region_union:
1156  * @source1:  a #GdkRegion
1157  * @source2: a #GdkRegion
1158  *
1159  * Sets the area of @source1 to the union of the areas of @source1 and
1160  * @source2. The resulting area is the set of pixels contained in
1161  * either @source1 or @source2.
1162  **/
1163 void
1164 gdk_region_union (GdkRegion *region,
1165                   GdkRegion *other)
1166 {
1167   g_return_if_fail (region != NULL);
1168   g_return_if_fail (other != NULL);
1169
1170   /*  checks all the simple cases */
1171
1172     /*
1173      * region and other are the same or other is empty
1174      */
1175   if ((region == other) || (!(other->numRects)))
1176     return;
1177
1178     /*
1179      * region is empty
1180      */
1181   if (!(region->numRects))
1182     {
1183       miRegionCopy (region, other);
1184       return;
1185     }
1186
1187   /*
1188      * region completely subsumes otehr
1189      */
1190   if ((region->numRects == 1) &&
1191       (region->extents.x1 <= other->extents.x1) &&
1192       (region->extents.y1 <= other->extents.y1) &&
1193       (region->extents.x2 >= other->extents.x2) &&
1194       (region->extents.y2 >= other->extents.y2))
1195     return;
1196
1197   /*
1198      * other completely subsumes region
1199      */
1200   if ((other->numRects == 1) &&
1201       (other->extents.x1 <= region->extents.x1) &&
1202       (other->extents.y1 <= region->extents.y1) &&
1203       (other->extents.x2 >= region->extents.x2) &&
1204       (other->extents.y2 >= region->extents.y2))
1205     {
1206       miRegionCopy(region, other);
1207       return;
1208     }
1209
1210   miRegionOp (region, region, other, miUnionO,
1211               miUnionNonO, miUnionNonO);
1212
1213   region->extents.x1 = MIN (region->extents.x1, other->extents.x1);
1214   region->extents.y1 = MIN (region->extents.y1, other->extents.y1);
1215   region->extents.x2 = MAX (region->extents.x2, other->extents.x2);
1216   region->extents.y2 = MAX (region->extents.y2, other->extents.y2);
1217 }
1218
1219 \f
1220 /*======================================================================
1221  *                Region Subtraction
1222  *====================================================================*/
1223
1224 /*-
1225  *-----------------------------------------------------------------------
1226  * miSubtractNonO --
1227  *      Deal with non-overlapping band for subtraction. Any parts from
1228  *      region 2 we discard. Anything from region 1 we add to the region.
1229  *
1230  * Results:
1231  *      None.
1232  *
1233  * Side Effects:
1234  *      pReg may be affected.
1235  *
1236  *-----------------------------------------------------------------------
1237  */
1238 /* static void*/
1239 static void
1240 miSubtractNonO1 (GdkRegion    *pReg,
1241                  GdkRegionBox *r,
1242                  GdkRegionBox *rEnd,
1243                  gint          y1,
1244                  gint          y2)
1245 {
1246   GdkRegionBox *        pNextRect;
1247
1248   pNextRect = &pReg->rects[pReg->numRects];
1249
1250   assert(y1<y2);
1251
1252   while (r != rEnd)
1253     {
1254       assert (r->x1<r->x2);
1255       MEMCHECK (pReg, pNextRect, pReg->rects);
1256       pNextRect->x1 = r->x1;
1257       pNextRect->y1 = y1;
1258       pNextRect->x2 = r->x2;
1259       pNextRect->y2 = y2;
1260       pReg->numRects += 1;
1261       pNextRect++;
1262
1263       assert (pReg->numRects <= pReg->size);
1264
1265       r++;
1266     }
1267 }
1268
1269 /*-
1270  *-----------------------------------------------------------------------
1271  * miSubtractO --
1272  *      Overlapping band subtraction. x1 is the left-most point not yet
1273  *      checked.
1274  *
1275  * Results:
1276  *      None.
1277  *
1278  * Side Effects:
1279  *      pReg may have rectangles added to it.
1280  *
1281  *-----------------------------------------------------------------------
1282  */
1283 /* static void*/
1284 static void
1285 miSubtractO (GdkRegion    *pReg,
1286              GdkRegionBox *r1,
1287              GdkRegionBox *r1End,
1288              GdkRegionBox *r2,
1289              GdkRegionBox *r2End,
1290              gint          y1,
1291              gint          y2)
1292 {
1293   GdkRegionBox *        pNextRect;
1294   int   x1;
1295
1296   x1 = r1->x1;
1297
1298   assert(y1<y2);
1299   pNextRect = &pReg->rects[pReg->numRects];
1300
1301   while ((r1 != r1End) && (r2 != r2End))
1302     {
1303       if (r2->x2 <= x1)
1304         {
1305           /*
1306            * Subtrahend missed the boat: go to next subtrahend.
1307            */
1308           r2++;
1309         }
1310       else if (r2->x1 <= x1)
1311         {
1312           /*
1313            * Subtrahend preceeds minuend: nuke left edge of minuend.
1314            */
1315           x1 = r2->x2;
1316           if (x1 >= r1->x2)
1317             {
1318               /*
1319                * Minuend completely covered: advance to next minuend and
1320                * reset left fence to edge of new minuend.
1321                */
1322               r1++;
1323               if (r1 != r1End)
1324                 x1 = r1->x1;
1325             }
1326           else
1327             {
1328               /*
1329                * Subtrahend now used up since it doesn't extend beyond
1330                * minuend
1331                */
1332               r2++;
1333             }
1334         }
1335       else if (r2->x1 < r1->x2)
1336         {
1337           /*
1338            * Left part of subtrahend covers part of minuend: add uncovered
1339            * part of minuend to region and skip to next subtrahend.
1340            */
1341           assert(x1<r2->x1);
1342           MEMCHECK(pReg, pNextRect, pReg->rects);
1343           pNextRect->x1 = x1;
1344           pNextRect->y1 = y1;
1345           pNextRect->x2 = r2->x1;
1346           pNextRect->y2 = y2;
1347           pReg->numRects += 1;
1348           pNextRect++;
1349
1350           assert(pReg->numRects<=pReg->size);
1351
1352           x1 = r2->x2;
1353           if (x1 >= r1->x2)
1354             {
1355               /*
1356                * Minuend used up: advance to new...
1357                */
1358               r1++;
1359               if (r1 != r1End)
1360                 x1 = r1->x1;
1361             }
1362           else
1363             {
1364               /*
1365                * Subtrahend used up
1366                */
1367               r2++;
1368             }
1369         }
1370       else
1371         {
1372           /*
1373            * Minuend used up: add any remaining piece before advancing.
1374            */
1375           if (r1->x2 > x1)
1376             {
1377               MEMCHECK(pReg, pNextRect, pReg->rects);
1378               pNextRect->x1 = x1;
1379               pNextRect->y1 = y1;
1380               pNextRect->x2 = r1->x2;
1381               pNextRect->y2 = y2;
1382               pReg->numRects += 1;
1383               pNextRect++;
1384               assert(pReg->numRects<=pReg->size);
1385             }
1386           r1++;
1387           if (r1 != r1End)
1388             x1 = r1->x1;
1389         }
1390     }
1391
1392   /*
1393      * Add remaining minuend rectangles to region.
1394      */
1395   while (r1 != r1End)
1396     {
1397       assert(x1<r1->x2);
1398       MEMCHECK(pReg, pNextRect, pReg->rects);
1399       pNextRect->x1 = x1;
1400       pNextRect->y1 = y1;
1401       pNextRect->x2 = r1->x2;
1402       pNextRect->y2 = y2;
1403       pReg->numRects += 1;
1404       pNextRect++;
1405
1406       assert(pReg->numRects<=pReg->size);
1407
1408       r1++;
1409       if (r1 != r1End)
1410         {
1411           x1 = r1->x1;
1412         }
1413     }
1414 }
1415
1416 /**
1417  * gdk_region_subtract:
1418  * @source1: a #GdkRegion
1419  * @source2: another #GdkRegion
1420  *
1421  * Subtracts the area of @source2 from the area @source1. The resulting
1422  * area is the set of pixels contained in @source1 but not in @source2.
1423  **/
1424 void
1425 gdk_region_subtract (GdkRegion *region,
1426                      GdkRegion *other)
1427 {
1428   g_return_if_fail (region != NULL);
1429   g_return_if_fail (other != NULL);
1430
1431   /* check for trivial reject */
1432   if ((!(region->numRects)) || (!(other->numRects)) ||
1433       (!EXTENTCHECK(&region->extents, &other->extents)))
1434     return;
1435
1436   miRegionOp (region, region, other, miSubtractO,
1437               miSubtractNonO1, (nonOverlapFunc) NULL);
1438
1439   /*
1440    * Can't alter region's extents before we call miRegionOp because miRegionOp
1441    * depends on the extents of those regions being the unaltered. Besides, this
1442    * way there's no checking against rectangles that will be nuked
1443    * due to coalescing, so we have to examine fewer rectangles.
1444    */
1445   miSetExtents (region);
1446 }
1447
1448 /**
1449  * gdk_region_xor:
1450  * @source1: a #GdkRegion
1451  * @source2: another #GdkRegion
1452  *
1453  * Sets the area of @source1 to the exclusive-OR of the areas of @source1
1454  * and @source2. The resulting area is the set of pixels contained in one
1455  * or the other of the two sources but not in both.
1456  **/
1457 void
1458 gdk_region_xor (GdkRegion *sra,
1459                 GdkRegion *srb)
1460 {
1461   GdkRegion *trb;
1462
1463   g_return_if_fail (sra != NULL);
1464   g_return_if_fail (srb != NULL);
1465
1466   trb = gdk_region_copy (srb);
1467
1468   gdk_region_subtract (trb, sra);
1469   gdk_region_subtract (sra, srb);
1470
1471   gdk_region_union (sra,trb);
1472
1473   gdk_region_destroy (trb);
1474 }
1475
1476 /*
1477  * Check to see if the region is empty.  Assumes a region is passed
1478  * as a parameter
1479  */
1480 gboolean
1481 gdk_region_empty (GdkRegion *r)
1482 {
1483   g_return_val_if_fail (r != NULL, FALSE);
1484
1485   if (r->numRects == 0)
1486     return TRUE;
1487   else
1488     return FALSE;
1489 }
1490
1491 /*
1492  *      Check to see if two regions are equal
1493  */
1494 gboolean
1495 gdk_region_equal (GdkRegion *r1,
1496                   GdkRegion *r2)
1497 {
1498   int i;
1499
1500   g_return_val_if_fail (r1 != NULL, FALSE);
1501   g_return_val_if_fail (r2 != NULL, FALSE);
1502
1503   if (r1->numRects != r2->numRects) return FALSE;
1504   else if (r1->numRects == 0) return TRUE;
1505   else if (r1->extents.x1 != r2->extents.x1) return FALSE;
1506   else if (r1->extents.x2 != r2->extents.x2) return FALSE;
1507   else if (r1->extents.y1 != r2->extents.y1) return FALSE;
1508   else if (r1->extents.y2 != r2->extents.y2) return FALSE;
1509   else
1510     for(i=0; i < r1->numRects; i++ )
1511       {
1512         if (r1->rects[i].x1 != r2->rects[i].x1) return FALSE;
1513         else if (r1->rects[i].x2 != r2->rects[i].x2) return FALSE;
1514         else if (r1->rects[i].y1 != r2->rects[i].y1) return FALSE;
1515         else if (r1->rects[i].y2 != r2->rects[i].y2) return FALSE;
1516       }
1517   return TRUE;
1518 }
1519
1520 gboolean
1521 gdk_region_point_in (GdkRegion *region,
1522                      int        x,
1523                      int        y)
1524 {
1525   int i;
1526
1527   g_return_val_if_fail (region != NULL, FALSE);
1528
1529   if (region->numRects == 0)
1530     return FALSE;
1531   if (!INBOX(region->extents, x, y))
1532     return FALSE;
1533   for (i=0; i<region->numRects; i++)
1534     {
1535       if (INBOX (region->rects[i], x, y))
1536         return TRUE;
1537     }
1538   return FALSE;
1539 }
1540
1541 GdkOverlapType
1542 gdk_region_rect_in (GdkRegion    *region,
1543                     GdkRectangle *rectangle)
1544 {
1545   GdkRegionBox *pbox;
1546   GdkRegionBox *pboxEnd;
1547   GdkRegionBox  rect;
1548   GdkRegionBox *prect = &rect;
1549   gboolean      partIn, partOut;
1550   gint rx, ry;
1551
1552   g_return_val_if_fail (region != NULL, GDK_OVERLAP_RECTANGLE_OUT);
1553   g_return_val_if_fail (rectangle != NULL, GDK_OVERLAP_RECTANGLE_OUT);
1554
1555   rx = rectangle->x;
1556   ry = rectangle->y;
1557
1558   prect->x1 = rx;
1559   prect->y1 = ry;
1560   prect->x2 = rx + rectangle->width;
1561   prect->y2 = ry + rectangle->height;
1562
1563     /* this is (just) a useful optimization */
1564   if ((region->numRects == 0) || !EXTENTCHECK (&region->extents, prect))
1565     return GDK_OVERLAP_RECTANGLE_OUT;
1566
1567   partOut = FALSE;
1568   partIn = FALSE;
1569
1570     /* can stop when both partOut and partIn are TRUE, or we reach prect->y2 */
1571   for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1572        pbox < pboxEnd;
1573        pbox++)
1574     {
1575
1576       if (pbox->y2 <= ry)
1577         continue;       /* getting up to speed or skipping remainder of band */
1578
1579       if (pbox->y1 > ry)
1580         {
1581           partOut = TRUE;       /* missed part of rectangle above */
1582           if (partIn || (pbox->y1 >= prect->y2))
1583             break;
1584           ry = pbox->y1;        /* x guaranteed to be == prect->x1 */
1585         }
1586
1587       if (pbox->x2 <= rx)
1588         continue;               /* not far enough over yet */
1589
1590       if (pbox->x1 > rx)
1591         {
1592           partOut = TRUE;       /* missed part of rectangle to left */
1593           if (partIn)
1594             break;
1595         }
1596
1597       if (pbox->x1 < prect->x2)
1598         {
1599           partIn = TRUE;        /* definitely overlap */
1600           if (partOut)
1601             break;
1602         }
1603
1604       if (pbox->x2 >= prect->x2)
1605         {
1606           ry = pbox->y2;        /* finished with this band */
1607           if (ry >= prect->y2)
1608             break;
1609           rx = prect->x1;       /* reset x out to left again */
1610         }
1611       else
1612         {
1613           /*
1614            * Because boxes in a band are maximal width, if the first box
1615            * to overlap the rectangle doesn't completely cover it in that
1616            * band, the rectangle must be partially out, since some of it
1617            * will be uncovered in that band. partIn will have been set true
1618            * by now...
1619            */
1620           break;
1621         }
1622
1623     }
1624
1625   return (partIn ?
1626              ((ry < prect->y2) ?
1627               GDK_OVERLAP_RECTANGLE_PART : GDK_OVERLAP_RECTANGLE_IN) :
1628           GDK_OVERLAP_RECTANGLE_OUT);
1629 }
1630
1631
1632 static void
1633 gdk_region_unsorted_spans_intersect_foreach (GdkRegion *region,
1634                                              GdkSpan   *spans,
1635                                              int        n_spans,
1636                                              GdkSpanFunc function,
1637                                              gpointer data)
1638 {
1639   gint i, left, right, y;
1640   gint clipped_left, clipped_right;
1641   GdkRegionBox *pbox;
1642   GdkRegionBox *pboxEnd;
1643   GdkSpan out_span;
1644
1645   if (!region->numRects)
1646     return;
1647
1648   for (i=0;i<n_spans;i++)
1649     {
1650       y = spans[i].y;
1651       left = spans[i].x;
1652       right = left + spans[i].width; /* right is not in the span! */
1653
1654       if (! ((region->extents.y1 <= y) &&
1655              (region->extents.y2 > y) &&
1656              (region->extents.x1 < right) &&
1657              (region->extents.x2 > left)) )
1658         continue;
1659
1660       /* can stop when we passed y */
1661       for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1662            pbox < pboxEnd;
1663            pbox++)
1664         {
1665           if (pbox->y2 <= y)
1666             continue; /* Not quite there yet */
1667
1668           if (pbox->y1 > y)
1669             break; /* passed the spanline */
1670
1671           if ((right > pbox->x1) && (left < pbox->x2))
1672             {
1673               clipped_left = MAX (left, pbox->x1);
1674               clipped_right = MIN (right, pbox->x2);
1675
1676               out_span.y = y;
1677               out_span.x = clipped_left;
1678               out_span.width = clipped_right - clipped_left;
1679               (*function) (&out_span, data);
1680             }
1681         }
1682     }
1683 }
1684
1685
1686 void
1687 gdk_region_spans_intersect_foreach (GdkRegion  *region,
1688                                     GdkSpan    *spans,
1689                                     int         n_spans,
1690                                     gboolean    sorted,
1691                                     GdkSpanFunc function,
1692                                     gpointer    data)
1693 {
1694   gint left, right, y;
1695   gint clipped_left, clipped_right;
1696   GdkRegionBox *pbox;
1697   GdkRegionBox *pboxEnd;
1698   GdkSpan *span, *tmpspan;
1699   GdkSpan *end_span;
1700   GdkSpan out_span;
1701
1702   g_return_if_fail (region != NULL);
1703   g_return_if_fail (spans != NULL);
1704
1705   if (!sorted)
1706     {
1707       gdk_region_unsorted_spans_intersect_foreach (region,
1708                                                    spans,
1709                                                    n_spans,
1710                                                    function,
1711                                                    data);
1712       return;
1713     }
1714
1715   if ((!region->numRects) || (n_spans == 0))
1716     return;
1717
1718   y = span->y;
1719   left = span->x;
1720   right = span->x + span->width; /* right is not in the span! */
1721
1722   /* The main method here is to step along the
1723    * sorted rectangles and spans in lock step, and
1724    * clipping the spans that are in the current
1725    * rectangle before going on to the next rectangle.
1726    */
1727
1728   span = spans;
1729   end_span = spans + n_spans;
1730   pbox = region->rects;
1731   pboxEnd = pbox + region->numRects;
1732   while (pbox < pboxEnd)
1733     {
1734       while ((pbox->y2 < span->y) || (span->y < pbox->y1))
1735         {
1736           /* Skip any rectangles that are above the current span */
1737           if (pbox->y2 < span->y)
1738             {
1739               pbox++;
1740               if (pbox == pboxEnd)
1741                 return;
1742             }
1743           /* Skip any spans that are above the current rectangle */
1744           if (span->y < pbox->y1)
1745             {
1746               span++;
1747               if (span == end_span)
1748                 return;
1749             }
1750         }
1751
1752       /* Ok, we got at least one span that might intersect this rectangle. */
1753       tmpspan = span;
1754       while ((tmpspan < end_span) &&
1755              (tmpspan->y < pbox->y2))
1756         {
1757           y = tmpspan->y;
1758           left = tmpspan->x;
1759           right = left + tmpspan->width; /* right is not in the span! */
1760
1761           if ((right > pbox->x1) && (left < pbox->x2))
1762             {
1763               clipped_left = MAX (left, pbox->x1);
1764               clipped_right = MIN (right, pbox->x2);
1765
1766               out_span.y = y;
1767               out_span.x = clipped_left;
1768               out_span.width = clipped_right - clipped_left;
1769               (*function) (&out_span, data);
1770             }
1771
1772           tmpspan++;
1773         }
1774
1775       /* Finished this rectangle.
1776        * The spans could still intersect the next one
1777        */
1778       pbox++;
1779     }
1780 }