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

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