src/generic/regiong.cpp

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