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