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