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