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