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