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