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_region.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_region.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_region.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_region.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_region.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 (Region pReg)
 655 {
 656     register BoxPtr pBox,
 657                     pBoxEnd,
 658                     pExtents;
 659
 660     if (pReg->numRects == 0)
 661     {
 662         pReg->extents.x1 = 0;
 663         pReg->extents.y1 = 0;
 664         pReg->extents.x2 = 0;
 665         pReg->extents.y2 = 0;
 666         return;
 667     }
 668
 669     pExtents = &pReg->extents;
 670     pBox = pReg->rects;
 671     pBoxEnd = &pBox[pReg->numRects - 1];
 672
 673     /*
 674      * Since pBox is the first rectangle in the region, it must have the
 675      * smallest y1 and since pBoxEnd is the last rectangle in the region,
 676      * it must have the largest y2, because of banding. Initialize x1 and
 677      * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
 678      * to...
 679      */
 680     pExtents->x1 = pBox->x1;
 681     pExtents->y1 = pBox->y1;
 682     pExtents->x2 = pBoxEnd->x2;
 683     pExtents->y2 = pBoxEnd->y2;
 684
 685     assert(pExtents->y1 < pExtents->y2);
 686     while (pBox <= pBoxEnd)
 687     {
 688         if (pBox->x1 < pExtents->x1)
 689         {
 690             pExtents->x1 = pBox->x1;
 691         }
 692         if (pBox->x2 > pExtents->x2)
 693         {
 694             pExtents->x2 = pBox->x2;
 695         }
 696         pBox++;
 697     }
 698     assert(pExtents->x1 < pExtents->x2);
 699 }
 700
 701 bool REGION::
 702 XDestroyRegion(
 703     Region r)
 704 {
 705     free( (char *) r->rects );
 706     delete r;
 707     return true;
 708 }
 709
 710 /* TranslateRegion(pRegion, x, y)
 711    translates in place
 712    added by raymond
 713 */
 714
 715 bool REGION::
 716 XOffsetRegion(
 717     register Region pRegion,
 718     register int x,
 719     register int y)
 720 {
 721     register int nbox;
 722     register BOX *pbox;
 723
 724     pbox = pRegion->rects;
 725     nbox = pRegion->numRects;
 726
 727     while(nbox--)
 728     {
 729         pbox->x1 += x;
 730         pbox->x2 += x;
 731         pbox->y1 += y;
 732         pbox->y2 += y;
 733         pbox++;
 734     }
 735     pRegion->extents.x1 += x;
 736     pRegion->extents.x2 += x;
 737     pRegion->extents.y1 += y;
 738     pRegion->extents.y2 += y;
 739     return 1;
 740 }
 741
 742 /*======================================================================
 743  *  Region Intersection
 744  *====================================================================*/
 745 /*-
 746  *-----------------------------------------------------------------------
 747  * miIntersectO --
 748  *    Handle an overlapping band for miIntersect.
 749  *
 750  * Results:
 751  *    None.
 752  *
 753  * Side Effects:
 754  *    Rectangles may be added to the region.
 755  *
 756  *-----------------------------------------------------------------------
 757  */
 758 /* static void*/
 759 int REGION::
 760 miIntersectO (
 761     register Region     pReg,
 762     register BoxPtr     r1,
 763     BoxPtr              r1End,
 764     register BoxPtr     r2,
 765     BoxPtr              r2End,
 766     wxCoord             y1,
 767     wxCoord             y2)
 768 {
 769     register wxCoord    x1;
 770     register wxCoord    x2;
 771     register BoxPtr     pNextRect;
 772
 773     pNextRect = &pReg->rects[pReg->numRects];
 774
 775     while ((r1 != r1End) && (r2 != r2End))
 776     {
 777         x1 = wxMax(r1->x1,r2->x1);
 778         x2 = wxMin(r1->x2,r2->x2);
 779
 780         /*
 781          * If there's any overlap between the two rectangles, add that
 782          * overlap to the new region.
 783          * There's no need to check for subsumption because the only way
 784          * such a need could arise is if some region has two rectangles
 785          * right next to each other. Since that should never happen...
 786          */
 787         if (x1 < x2)
 788         {
 789             assert(y1<y2);
 790
 791             MEMCHECK(pReg, pNextRect, pReg->rects);
 792             pNextRect->x1 = x1;
 793             pNextRect->y1 = y1;
 794             pNextRect->x2 = x2;
 795             pNextRect->y2 = y2;
 796             pReg->numRects += 1;
 797             pNextRect++;
 798             assert(pReg->numRects <= pReg->size);
 799         }
 800
 801         /*
 802          * Need to advance the pointers. Shift the one that extends
 803          * to the right the least, since the other still has a chance to
 804          * overlap with that region's next rectangle, if you see what I mean.
 805          */
 806         if (r1->x2 < r2->x2)
 807         {
 808             r1++;
 809         }
 810         else if (r2->x2 < r1->x2)
 811         {
 812             r2++;
 813         }
 814         else
 815         {
 816             r1++;
 817             r2++;
 818         }
 819     }
 820     return 0; /* lint */
 821 }
 822
 823 bool REGION::
 824 XIntersectRegion(
 825     Region reg1,
 826     Region reg2, /* source regions     */
 827     register Region newReg) /* destination Region */
 828 {
 829    /* check for trivial reject */
 830     if ( (!(reg1->numRects)) || (!(reg2->numRects))  ||
 831         (!EXTENTCHECK(&reg1->extents, &reg2->extents)))
 832         newReg->numRects = 0;
 833     else
 834         miRegionOp (newReg, reg1, reg2,
 835                     miIntersectO, NULL, NULL);
 836
 837     /*
 838      * Can't alter newReg's extents before we call miRegionOp because
 839      * it might be one of the source regions and miRegionOp depends
 840      * on the extents of those regions being the same. Besides, this
 841      * way there's no checking against rectangles that will be nuked
 842      * due to coalescing, so we have to examine fewer rectangles.
 843      */
 844     miSetExtents(newReg);
 845     return 1;
 846 }
 847
 848 void REGION::
 849 miRegionCopy(
 850     register Region dstrgn,
 851     register Region rgn)
 852
 853 {
 854     if (dstrgn != rgn) /*  don't want to copy to itself */
 855     {
 856         if (dstrgn->size < rgn->numRects)
 857         {
 858             if (dstrgn->rects)
 859             {
 860                 BOX *prevRects = dstrgn->rects;
 861
 862                 if (! (dstrgn->rects = (BOX *)
 863                        realloc((char *) dstrgn->rects,
 864                                (unsigned) rgn->numRects * (sizeof(BOX)))))
 865                 {
 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     {
 958         pCurBox -= curNumRects;
 959         /*
 960          * The bands may only be coalesced if the bottom of the previous
 961          * matches the top scanline of the current.
 962          */
 963         if (pPrevBox->y2 == pCurBox->y1)
 964         {
 965         /*
 966          * Make sure the bands have boxes in the same places. This
 967          * assumes that boxes have been added in such a way that they
 968          * cover the most area possible. I.e. two boxes in a band must
 969          * have some horizontal space between them.
 970          */
 971             do
 972             {
 973                 if ((pPrevBox->x1 != pCurBox->x1) ||
 974                     (pPrevBox->x2 != pCurBox->x2))
 975                 {
 976                     /*
 977                      * The bands don't line up so they can't be coalesced.
 978                      */
 979                     return (curStart);
 980                 }
 981                 pPrevBox++;
 982                 pCurBox++;
 983                 prevNumRects -= 1;
 984             } while (prevNumRects != 0);
 985
 986             pReg->numRects -= curNumRects;
 987             pCurBox -= curNumRects;
 988             pPrevBox -= curNumRects;
 989
 990             /*
 991              * The bands may be merged, so set the bottom y of each box
 992              * in the previous band to that of the corresponding box in
 993              * the current band.
 994              */
 995             do
 996             {
 997                 pPrevBox->y2 = pCurBox->y2;
 998                 pPrevBox++;
 999                 pCurBox++;
1000                 curNumRects -= 1;
1001             } while (curNumRects != 0);
1002
1003             /*
1004              * If only one band was added to the region, we have to backup
1005              * curStart to the start of the previous band.
1006              *
1007              * If more than one band was added to the region, copy the
1008              * other bands down. The assumption here is that the other bands
1009              * came from the same region as the current one and no further
1010              * coalescing can be done on them since it's all been done
1011              * already... curStart is already in the right place.
1012              */
1013             if (pCurBox == pRegEnd)
1014             {
1015                 curStart = prevStart;
1016             }
1017             else
1018             {
1019                 do
1020                 {
1021                     *pPrevBox++ = *pCurBox++;
1022                 } while (pCurBox != pRegEnd);
1023             }
1024
1025         }
1026     }
1027     return (curStart);
1028 }
1029
1030 /*-
1031  *-----------------------------------------------------------------------
1032  * miRegionOp --
1033  *        Apply an operation to two regions. Called by miUnion, miInverse,
1034  *        miSubtract, miIntersect...
1035  *
1036  * Results:
1037  *        None.
1038  *
1039  * Side Effects:
1040  *        The new region is overwritten.
1041  *
1042  * Notes:
1043  *        The idea behind this function is to view the two regions as sets.
1044  *        Together they cover a rectangle of area that this function divides
1045  *        into horizontal bands where points are covered only by one region
1046  *        or by both. For the first case, the nonOverlapFunc is called with
1047  *        each the band and the band's upper and lower extents. For the
1048  *        second, the overlapFunc is called to process the entire band. It
1049  *        is responsible for clipping the rectangles in the band, though
1050  *        this function provides the boundaries.
1051  *        At the end of each band, the new region is coalesced, if possible,
1052  *        to reduce the number of rectangles in the region.
1053  *
1054  *-----------------------------------------------------------------------
1055  */
1056 /* static void*/
1057 void REGION::
1058 miRegionOp(
1059     register Region         newReg,                              /* Place to store result */
1060     Region                  reg1,                                /* First region in operation */
1061     Region                  reg2,                                /* 2d region in operation */
1062     int                      (*overlapFunc)(
1063         register Region     pReg,
1064         register BoxPtr     r1,
1065         BoxPtr              r1End,
1066         register BoxPtr     r2,
1067         BoxPtr              r2End,
1068         wxCoord               y1,
1069         wxCoord               y2),              /* Function to call for over-
1070                                                  * lapping bands */
1071     int                      (*nonOverlap1Func)(
1072         register Region     pReg,
1073         register BoxPtr     r,
1074         BoxPtr              rEnd,
1075         register wxCoord      y1,
1076         register wxCoord      y2),              /* Function to call for non-
1077                                                  * overlapping bands in region
1078                                                  * 1 */
1079     int                      (*nonOverlap2Func)(
1080         register Region     pReg,
1081         register BoxPtr     r,
1082         BoxPtr              rEnd,
1083         register wxCoord      y1,
1084         register wxCoord      y2))              /* Function to call for non-
1085                                                  * overlapping bands in region
1086                                                  * 2 */
1087 {
1088     register BoxPtr        r1; /* Pointer into first region */
1089     register BoxPtr        r2; /* Pointer into 2d region */
1090     BoxPtr              r1End; /* End of 1st region */
1091     BoxPtr              r2End; /* End of 2d region */
1092     register wxCoord     ybot; /* Bottom of intersection */
1093     register wxCoord     ytop; /* Top of intersection */
1094     BoxPtr           oldRects; /* Old rects for newReg */
1095     int              prevBand; /* Index of start of
1096                                 * previous band in newReg */
1097     int               curBand; /* Index of start of current
1098                                 * band in newReg */
1099     register BoxPtr r1BandEnd; /* End of current band in r1 */
1100     register BoxPtr r2BandEnd; /* End of current band in r2 */
1101     wxCoord               top; /* Top of non-overlapping
1102                                 * band */
1103     wxCoord               bot; /* Bottom of non-overlapping
1104                                 * band */
1105
1106     /*
1107      * Initialization:
1108      *        set r1, r2, r1End and r2End appropriately, preserve the important
1109      * parts of the destination region until the end in case it's one of
1110      * the two source regions, then mark the "new" region empty, allocating
1111      * another array of rectangles for it to use.
1112      */
1113     r1 = reg1->rects;
1114     r2 = reg2->rects;
1115     r1End = r1 + reg1->numRects;
1116     r2End = r2 + reg2->numRects;
1117
1118     oldRects = newReg->rects;
1119
1120     EMPTY_REGION(newReg);
1121
1122     /*
1123      * Allocate a reasonable number of rectangles for the new region. The idea
1124      * is to allocate enough so the individual functions don't need to
1125      * reallocate and copy the array, which is time consuming, yet we don't
1126      * have to worry about using too much memory. I hope to be able to
1127      * nuke the realloc() at the end of this function eventually.
1128      */
1129     newReg->size = wxMax(reg1->numRects,reg2->numRects) * 2;
1130
1131     if (! (newReg->rects = (BoxPtr)
1132            malloc ((unsigned) (sizeof(BoxRec) * newReg->size)))) {
1133         newReg->size = 0;
1134         return;
1135     }
1136
1137     /*
1138      * Initialize ybot and ytop.
1139      * In the upcoming loop, ybot and ytop serve different functions depending
1140      * on whether the band being handled is an overlapping or non-overlapping
1141      * band.
1142      *         In the case of a non-overlapping band (only one of the regions
1143      * has points in the band), ybot is the bottom of the most recent
1144      * intersection and thus clips the top of the rectangles in that band.
1145      * ytop is the top of the next intersection between the two regions and
1146      * serves to clip the bottom of the rectangles in the current band.
1147      *        For an overlapping band (where the two regions intersect), ytop clips
1148      * the top of the rectangles of both regions and ybot clips the bottoms.
1149      */
1150     if (reg1->extents.y1 < reg2->extents.y1)
1151         ybot = reg1->extents.y1;
1152     else
1153         ybot = reg2->extents.y1;
1154
1155     /*
1156      * prevBand serves to mark the start of the previous band so rectangles
1157      * can be coalesced into larger rectangles. qv. miCoalesce, above.
1158      * In the beginning, there is no previous band, so prevBand == curBand
1159      * (curBand is set later on, of course, but the first band will always
1160      * start at index 0). prevBand and curBand must be indices because of
1161      * the possible expansion, and resultant moving, of the new region's
1162      * array of rectangles.
1163      */
1164     prevBand = 0;
1165
1166     do
1167     {
1168         curBand = newReg->numRects;
1169
1170         /*
1171          * This algorithm proceeds one source-band (as opposed to a
1172          * destination band, which is determined by where the two regions
1173          * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1174          * rectangle after the last one in the current band for their
1175          * respective regions.
1176          */
1177         r1BandEnd = r1;
1178         while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
1179         {
1180             r1BandEnd++;
1181         }
1182
1183         r2BandEnd = r2;
1184         while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
1185         {
1186             r2BandEnd++;
1187         }
1188
1189         /*
1190          * First handle the band that doesn't intersect, if any.
1191          *
1192          * Note that attention is restricted to one band in the
1193          * non-intersecting region at once, so if a region has n
1194          * bands between the current position and the next place it overlaps
1195          * the other, this entire loop will be passed through n times.
1196          */
1197         if (r1->y1 < r2->y1)
1198         {
1199             top = wxMax(r1->y1,ybot);
1200             bot = wxMin(r1->y2,r2->y1);
1201
1202             if ((top != bot) && (nonOverlap1Func != NULL))
1203             {
1204                 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1205             }
1206
1207             ytop = r2->y1;
1208         }
1209         else if (r2->y1 < r1->y1)
1210         {
1211             top = wxMax(r2->y1,ybot);
1212             bot = wxMin(r2->y2,r1->y1);
1213
1214             if ((top != bot) && (nonOverlap2Func != NULL))
1215             {
1216                 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1217             }
1218
1219             ytop = r1->y1;
1220         }
1221         else
1222         {
1223             ytop = r1->y1;
1224         }
1225
1226         /*
1227          * If any rectangles got added to the region, try and coalesce them
1228          * with rectangles from the previous band. Note we could just do
1229          * this test in miCoalesce, but some machines incur a not
1230          * inconsiderable cost for function calls, so...
1231          */
1232         if (newReg->numRects != curBand)
1233         {
1234             prevBand = miCoalesce (newReg, prevBand, curBand);
1235         }
1236
1237         /*
1238          * Now see if we've hit an intersecting band. The two bands only
1239          * intersect if ybot > ytop
1240          */
1241         ybot = wxMin(r1->y2, r2->y2);
1242         curBand = newReg->numRects;
1243         if (ybot > ytop)
1244         {
1245             (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1246
1247         }
1248
1249         if (newReg->numRects != curBand)
1250         {
1251             prevBand = miCoalesce (newReg, prevBand, curBand);
1252         }
1253
1254         /*
1255          * If we've finished with a band (y2 == ybot) we skip forward
1256          * in the region to the next band.
1257          */
1258         if (r1->y2 == ybot)
1259         {
1260             r1 = r1BandEnd;
1261         }
1262         if (r2->y2 == ybot)
1263         {
1264             r2 = r2BandEnd;
1265         }
1266     } while ((r1 != r1End) && (r2 != r2End));
1267
1268     /*
1269      * Deal with whichever region still has rectangles left.
1270      */
1271     curBand = newReg->numRects;
1272     if (r1 != r1End)
1273     {
1274         if (nonOverlap1Func != NULL)
1275         {
1276             do
1277             {
1278                 r1BandEnd = r1;
1279                 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
1280                 {
1281                     r1BandEnd++;
1282                 }
1283                 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1284                                      wxMax(r1->y1,ybot), r1->y2);
1285                 r1 = r1BandEnd;
1286             } while (r1 != r1End);
1287         }
1288     }
1289     else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1290     {
1291         do
1292         {
1293             r2BandEnd = r2;
1294             while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
1295             {
1296                  r2BandEnd++;
1297             }
1298             (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1299                                 wxMax(r2->y1,ybot), r2->y2);
1300             r2 = r2BandEnd;
1301         } while (r2 != r2End);
1302     }
1303
1304     if (newReg->numRects != curBand)
1305     {
1306         (void) miCoalesce (newReg, prevBand, curBand);
1307     }
1308
1309     /*
1310      * A bit of cleanup. To keep regions from growing without bound,
1311      * we shrink the array of rectangles to match the new number of
1312      * rectangles in the region. This never goes to 0, however...
1313      *
1314      * Only do this stuff if the number of rectangles allocated is more than
1315      * twice the number of rectangles in the region (a simple optimization...).
1316      */
1317     if (newReg->numRects < (newReg->size >> 1))
1318     {
1319         if (REGION_NOT_EMPTY(newReg))
1320         {
1321             BoxPtr prev_rects = newReg->rects;
1322             newReg->size = newReg->numRects;
1323             newReg->rects = (BoxPtr) realloc ((char *) newReg->rects,
1324                                    (unsigned) (sizeof(BoxRec) * newReg->size));
1325             if (! newReg->rects)
1326                 newReg->rects = prev_rects;
1327         }
1328         else
1329         {
1330             /*
1331              * No point in doing the extra work involved in an realloc if
1332              * the region is empty
1333              */
1334             newReg->size = 1;
1335             free((char *) newReg->rects);
1336             newReg->rects = (BoxPtr) malloc(sizeof(BoxRec));
1337         }
1338     }
1339     free ((char *) oldRects);
1340     return;
1341 }
1342
1343 /*======================================================================
1344  *            Region Union
1345  *====================================================================*/
1346
1347 /*-
1348  *-----------------------------------------------------------------------
1349  * miUnionNonO --
1350  *        Handle a non-overlapping band for the union operation. Just
1351  *        Adds the rectangles into the region. Doesn't have to check for
1352  *        subsumption or anything.
1353  *
1354  * Results:
1355  *        None.
1356  *
1357  * Side Effects:
1358  *        pReg->numRects is incremented and the final rectangles overwritten
1359  *        with the rectangles we're passed.
1360  *
1361  *-----------------------------------------------------------------------
1362  */
1363 /* static void*/
1364 int REGION::
1365 miUnionNonO (
1366     register Region        pReg,
1367     register BoxPtr        r,
1368     BoxPtr                 rEnd,
1369     register wxCoord       y1,
1370     register wxCoord       y2)
1371 {
1372     register BoxPtr        pNextRect;
1373
1374     pNextRect = &pReg->rects[pReg->numRects];
1375
1376     assert(y1 < y2);
1377
1378     while (r != rEnd)
1379     {
1380         assert(r->x1 < r->x2);
1381         MEMCHECK(pReg, pNextRect, pReg->rects);
1382         pNextRect->x1 = r->x1;
1383         pNextRect->y1 = y1;
1384         pNextRect->x2 = r->x2;
1385         pNextRect->y2 = y2;
1386         pReg->numRects += 1;
1387         pNextRect++;
1388
1389         assert(pReg->numRects<=pReg->size);
1390         r++;
1391     }
1392     return 0;        /* lint */
1393 }
1394
1395
1396 /*-
1397  *-----------------------------------------------------------------------
1398  * miUnionO --
1399  *        Handle an overlapping band for the union operation. Picks the
1400  *        left-most rectangle each time and merges it into the region.
1401  *
1402  * Results:
1403  *        None.
1404  *
1405  * Side Effects:
1406  *        Rectangles are overwritten in pReg->rects and pReg->numRects will
1407  *        be changed.
1408  *
1409  *-----------------------------------------------------------------------
1410  */
1411
1412 /* static void*/
1413 int REGION::
1414 miUnionO (
1415     register Region        pReg,
1416     register BoxPtr        r1,
1417     BoxPtr                 r1End,
1418     register BoxPtr        r2,
1419     BoxPtr                 r2End,
1420     register wxCoord       y1,
1421     register wxCoord       y2)
1422 {
1423     register BoxPtr        pNextRect;
1424
1425     pNextRect = &pReg->rects[pReg->numRects];
1426
1427 #define MERGERECT(r) \
1428     if ((pReg->numRects != 0) &&  \
1429         (pNextRect[-1].y1 == y1) &&  \
1430         (pNextRect[-1].y2 == y2) &&  \
1431         (pNextRect[-1].x2 >= r->x1))  \
1432     {  \
1433         if (pNextRect[-1].x2 < r->x2)  \
1434         {  \
1435             pNextRect[-1].x2 = r->x2;  \
1436             assert(pNextRect[-1].x1<pNextRect[-1].x2); \
1437         }  \
1438     }  \
1439     else  \
1440     {  \
1441         MEMCHECK(pReg, pNextRect, pReg->rects);  \
1442         pNextRect->y1 = y1;  \
1443         pNextRect->y2 = y2;  \
1444         pNextRect->x1 = r->x1;  \
1445         pNextRect->x2 = r->x2;  \
1446         pReg->numRects += 1;  \
1447         pNextRect += 1;  \
1448     }  \
1449     assert(pReg->numRects<=pReg->size);\
1450     r++;
1451
1452     assert (y1<y2);
1453     while ((r1 != r1End) && (r2 != r2End))
1454     {
1455         if (r1->x1 < r2->x1)
1456         {
1457             MERGERECT(r1);
1458         }
1459         else
1460         {
1461             MERGERECT(r2);
1462         }
1463     }
1464
1465     if (r1 != r1End)
1466     {
1467         do
1468         {
1469             MERGERECT(r1);
1470         } while (r1 != r1End);
1471     }
1472     else while (r2 != r2End)
1473     {
1474         MERGERECT(r2);
1475     }
1476     return 0;        /* lint */
1477 }
1478
1479 bool REGION::
1480 XUnionRegion(
1481     Region           reg1,
1482     Region          reg2,             /* source regions     */
1483     Region           newReg)                  /* destination Region */
1484 {
1485     /*  checks all the simple cases */
1486
1487     /*
1488      * Region 1 and 2 are the same or region 1 is empty
1489      */
1490     if ( (reg1 == reg2) || (!(reg1->numRects)) )
1491     {
1492         if (newReg != reg2)
1493             miRegionCopy(newReg, reg2);
1494         return 1;
1495     }
1496
1497     /*
1498      * if nothing to union (region 2 empty)
1499      */
1500     if (!(reg2->numRects))
1501     {
1502         if (newReg != reg1)
1503             miRegionCopy(newReg, reg1);
1504         return 1;
1505     }
1506
1507     /*
1508      * Region 1 completely subsumes region 2
1509      */
1510     if ((reg1->numRects == 1) &&
1511         (reg1->extents.x1 <= reg2->extents.x1) &&
1512         (reg1->extents.y1 <= reg2->extents.y1) &&
1513         (reg1->extents.x2 >= reg2->extents.x2) &&
1514         (reg1->extents.y2 >= reg2->extents.y2))
1515     {
1516         if (newReg != reg1)
1517             miRegionCopy(newReg, reg1);
1518         return 1;
1519     }
1520
1521     /*
1522      * Region 2 completely subsumes region 1
1523      */
1524     if ((reg2->numRects == 1) &&
1525         (reg2->extents.x1 <= reg1->extents.x1) &&
1526         (reg2->extents.y1 <= reg1->extents.y1) &&
1527         (reg2->extents.x2 >= reg1->extents.x2) &&
1528         (reg2->extents.y2 >= reg1->extents.y2))
1529     {
1530         if (newReg != reg2)
1531             miRegionCopy(newReg, reg2);
1532         return 1;
1533     }
1534
1535     miRegionOp (newReg, reg1, reg2, miUnionO,
1536                     miUnionNonO, miUnionNonO);
1537
1538     newReg->extents.x1 = wxMin(reg1->extents.x1, reg2->extents.x1);
1539     newReg->extents.y1 = wxMin(reg1->extents.y1, reg2->extents.y1);
1540     newReg->extents.x2 = wxMax(reg1->extents.x2, reg2->extents.x2);
1541     newReg->extents.y2 = wxMax(reg1->extents.y2, reg2->extents.y2);
1542
1543     return 1;
1544 }
1545
1546 /*======================================================================
1547  *                       Region Subtraction
1548  *====================================================================*/
1549
1550 /*-
1551  *-----------------------------------------------------------------------
1552  * miSubtractNonO --
1553  *        Deal with non-overlapping band for subtraction. Any parts from
1554  *        region 2 we discard. Anything from region 1 we add to the region.
1555  *
1556  * Results:
1557  *        None.
1558  *
1559  * Side Effects:
1560  *        pReg may be affected.
1561  *
1562  *-----------------------------------------------------------------------
1563  */
1564 /* static void*/
1565 int REGION::
1566 miSubtractNonO1 (
1567     register Region        pReg,
1568     register BoxPtr        r,
1569     BoxPtr                    rEnd,
1570     register wxCoord          y1,
1571     register wxCoord           y2)
1572 {
1573     register BoxPtr        pNextRect;
1574
1575     pNextRect = &pReg->rects[pReg->numRects];
1576
1577     assert(y1<y2);
1578
1579     while (r != rEnd)
1580     {
1581         assert(r->x1<r->x2);
1582         MEMCHECK(pReg, pNextRect, pReg->rects);
1583         pNextRect->x1 = r->x1;
1584         pNextRect->y1 = y1;
1585         pNextRect->x2 = r->x2;
1586         pNextRect->y2 = y2;
1587         pReg->numRects += 1;
1588         pNextRect++;
1589
1590         assert(pReg->numRects <= pReg->size);
1591
1592         r++;
1593     }
1594     return 0;        /* lint */
1595 }
1596
1597 /*-
1598  *-----------------------------------------------------------------------
1599  * miSubtractO --
1600  *        Overlapping band subtraction. x1 is the left-most point not yet
1601  *        checked.
1602  *
1603  * Results:
1604  *        None.
1605  *
1606  * Side Effects:
1607  *        pReg may have rectangles added to it.
1608  *
1609  *-----------------------------------------------------------------------
1610  */
1611 /* static void*/
1612 int REGION::
1613 miSubtractO (
1614     register Region        pReg,
1615     register BoxPtr        r1,
1616     BoxPtr                    r1End,
1617     register BoxPtr        r2,
1618     BoxPtr                    r2End,
1619     register wxCoord          y1,
1620     register wxCoord          y2)
1621 {
1622     register BoxPtr        pNextRect;
1623     register int          x1;
1624
1625     x1 = r1->x1;
1626
1627     assert(y1<y2);
1628     pNextRect = &pReg->rects[pReg->numRects];
1629
1630     while ((r1 != r1End) && (r2 != r2End))
1631     {
1632         if (r2->x2 <= x1)
1633         {
1634             /*
1635              * Subtrahend missed the boat: go to next subtrahend.
1636              */
1637             r2++;
1638         }
1639         else if (r2->x1 <= x1)
1640         {
1641             /*
1642              * Subtrahend preceeds minuend: nuke left edge of minuend.
1643              */
1644             x1 = r2->x2;
1645             if (x1 >= r1->x2)
1646             {
1647                 /*
1648                  * Minuend completely covered: advance to next minuend and
1649                  * reset left fence to edge of new minuend.
1650                  */
1651                 r1++;
1652                 if (r1 != r1End)
1653                     x1 = r1->x1;
1654             }
1655             else
1656             {
1657                 /*
1658                  * Subtrahend now used up since it doesn't extend beyond
1659                  * minuend
1660                  */
1661                 r2++;
1662             }
1663         }
1664         else if (r2->x1 < r1->x2)
1665         {
1666             /*
1667              * Left part of subtrahend covers part of minuend: add uncovered
1668              * part of minuend to region and skip to next subtrahend.
1669              */
1670             assert(x1<r2->x1);
1671             MEMCHECK(pReg, pNextRect, pReg->rects);
1672             pNextRect->x1 = x1;
1673             pNextRect->y1 = y1;
1674             pNextRect->x2 = r2->x1;
1675             pNextRect->y2 = y2;
1676             pReg->numRects += 1;
1677             pNextRect++;
1678
1679             assert(pReg->numRects<=pReg->size);
1680
1681             x1 = r2->x2;
1682             if (x1 >= r1->x2)
1683             {
1684                 /*
1685                  * Minuend used up: advance to new...
1686                  */
1687                 r1++;
1688                 if (r1 != r1End)
1689                     x1 = r1->x1;
1690             }
1691             else
1692             {
1693                 /*
1694                  * Subtrahend used up
1695                  */
1696                 r2++;
1697             }
1698         }
1699         else
1700         {
1701             /*
1702              * Minuend used up: add any remaining piece before advancing.
1703              */
1704             if (r1->x2 > x1)
1705             {
1706                 MEMCHECK(pReg, pNextRect, pReg->rects);
1707                 pNextRect->x1 = x1;
1708                 pNextRect->y1 = y1;
1709                 pNextRect->x2 = r1->x2;
1710                 pNextRect->y2 = y2;
1711                 pReg->numRects += 1;
1712                 pNextRect++;
1713                 assert(pReg->numRects<=pReg->size);
1714             }
1715             r1++;
1716             if (r1 != r1End)
1717                 x1 = r1->x1;
1718         }
1719     }
1720
1721     /*
1722      * Add remaining minuend rectangles to region.
1723      */
1724     while (r1 != r1End)
1725     {
1726         assert(x1<r1->x2);
1727         MEMCHECK(pReg, pNextRect, pReg->rects);
1728         pNextRect->x1 = x1;
1729         pNextRect->y1 = y1;
1730         pNextRect->x2 = r1->x2;
1731         pNextRect->y2 = y2;
1732         pReg->numRects += 1;
1733         pNextRect++;
1734
1735         assert(pReg->numRects<=pReg->size);
1736
1737         r1++;
1738         if (r1 != r1End)
1739         {
1740             x1 = r1->x1;
1741         }
1742     }
1743     return 0;        /* lint */
1744 }
1745
1746 /*-
1747  *-----------------------------------------------------------------------
1748  * miSubtract --
1749  *        Subtract regS from regM and leave the result in regD.
1750  *        S stands for subtrahend, M for minuend and D for difference.
1751  *
1752  * Results:
1753  *        true.
1754  *
1755  * Side Effects:
1756  *        regD is overwritten.
1757  *
1758  *-----------------------------------------------------------------------
1759  */
1760
1761 bool REGION::
1762 XSubtractRegion(
1763     Region                   regM,
1764     Region                  regS,
1765     register Region        regD)
1766 {
1767    /* check for trivial reject */
1768     if ( (!(regM->numRects)) || (!(regS->numRects))  ||
1769         (!EXTENTCHECK(&regM->extents, &regS->extents)) )
1770     {
1771         miRegionCopy(regD, regM);
1772         return true;
1773     }
1774
1775     miRegionOp (regD, regM, regS, miSubtractO,
1776                     miSubtractNonO1, NULL);
1777
1778     /*
1779      * Can't alter newReg's extents before we call miRegionOp because
1780      * it might be one of the source regions and miRegionOp depends
1781      * on the extents of those regions being the unaltered. Besides, this
1782      * way there's no checking against rectangles that will be nuked
1783      * due to coalescing, so we have to examine fewer rectangles.
1784      */
1785     miSetExtents (regD);
1786     return true;
1787 }
1788
1789 bool REGION::
1790 XXorRegion(Region sra, Region srb, Region dr)
1791 {
1792     Region tra, trb;
1793
1794     if ((! (tra = XCreateRegion())) || (! (trb = XCreateRegion())))
1795         return 0;
1796     (void) XSubtractRegion(sra,srb,tra);
1797     (void) XSubtractRegion(srb,sra,trb);
1798     (void) XUnionRegion(tra,trb,dr);
1799     XDestroyRegion(tra);
1800     XDestroyRegion(trb);
1801     return 0;
1802 }
1803
1804 /*
1805  * Check to see if the region is empty.  Assumes a region is passed
1806  * as a parameter
1807  */
1808 bool REGION::
1809 XEmptyRegion(
1810     Region r)
1811 {
1812     if( r->numRects == 0 ) return true;
1813     else  return false;
1814 }
1815
1816 /*
1817  *        Check to see if two regions are equal
1818  */
1819 bool REGION::
1820 XEqualRegion(Region r1, Region r2)
1821 {
1822     int i;
1823
1824     if( r1->numRects != r2->numRects ) return false;
1825     else if( r1->numRects == 0 ) return true;
1826     else if ( r1->extents.x1 != r2->extents.x1 ) return false;
1827     else if ( r1->extents.x2 != r2->extents.x2 ) return false;
1828     else if ( r1->extents.y1 != r2->extents.y1 ) return false;
1829     else if ( r1->extents.y2 != r2->extents.y2 ) return false;
1830     else for( i=0; i < r1->numRects; i++ ) {
1831             if ( r1->rects[i].x1 != r2->rects[i].x1 ) return false;
1832             else if ( r1->rects[i].x2 != r2->rects[i].x2 ) return false;
1833             else if ( r1->rects[i].y1 != r2->rects[i].y1 ) return false;
1834             else if ( r1->rects[i].y2 != r2->rects[i].y2 ) return false;
1835     }
1836     return true;
1837 }
1838
1839 bool REGION::
1840 XPointInRegion(
1841     Region pRegion,
1842     int x, int y)
1843 {
1844     int i;
1845
1846     if (pRegion->numRects == 0)
1847         return false;
1848     if (!INBOX(pRegion->extents, x, y))
1849         return false;
1850     for (i=0; i<pRegion->numRects; i++)
1851     {
1852         if (INBOX (pRegion->rects[i], x, y))
1853             return true;
1854     }
1855     return false;
1856 }
1857
1858 wxRegionContain REGION::
1859 XRectInRegion(
1860     register Region        region,
1861     int rx, int ry,
1862     unsigned int rwidth, unsigned int rheight)
1863 {
1864     register BoxPtr pbox;
1865     register BoxPtr pboxEnd;
1866     Box rect;
1867     register BoxPtr prect = &rect;
1868     int      partIn, partOut;
1869
1870     prect->x1 = rx;
1871     prect->y1 = ry;
1872     prect->x2 = rwidth + rx;
1873     prect->y2 = rheight + ry;
1874
1875     /* this is (just) a useful optimization */
1876     if ((region->numRects == 0) || !EXTENTCHECK(&region->extents, prect))
1877         return(wxOutRegion);
1878
1879     partOut = false;
1880     partIn = false;
1881
1882     /* can stop when both partOut and partIn are true, or we reach prect->y2 */
1883     for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1884          pbox < pboxEnd;
1885          pbox++)
1886     {
1887
1888         if (pbox->y2 <= ry)
1889            continue;        /* getting up to speed or skipping remainder of band */
1890
1891         if (pbox->y1 > ry)
1892         {
1893            partOut = true;        /* missed part of rectangle above */
1894            if (partIn || (pbox->y1 >= prect->y2))
1895               break;
1896            ry = pbox->y1;        /* x guaranteed to be == prect->x1 */
1897         }
1898
1899         if (pbox->x2 <= rx)
1900            continue;                /* not far enough over yet */
1901
1902         if (pbox->x1 > rx)
1903         {
1904            partOut = true;        /* missed part of rectangle to left */
1905            if (partIn)
1906               break;
1907         }
1908
1909         if (pbox->x1 < prect->x2)
1910         {
1911             partIn = true;        /* definitely overlap */
1912             if (partOut)
1913                break;
1914         }
1915
1916         if (pbox->x2 >= prect->x2)
1917         {
1918            ry = pbox->y2;        /* finished with this band */
1919            if (ry >= prect->y2)
1920               break;
1921            rx = prect->x1;        /* reset x out to left again */
1922         } else
1923         {
1924             /*
1925              * Because boxes in a band are maximal width, if the first box
1926              * to overlap the rectangle doesn't completely cover it in that
1927              * band, the rectangle must be partially out, since some of it
1928              * will be uncovered in that band. partIn will have been set true
1929              * by now...
1930              */
1931             break;
1932         }
1933
1934     }
1935
1936     return(partIn ? ((ry < prect->y2) ? wxPartRegion : wxInRegion) :
1937                 wxOutRegion);
1938 }
1939