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