src/generic/regiong.cpp

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