src/generic/regiong.cpp

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