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/generic/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::
 635 XCreateRegion(void)
 636 {
 637     Region temp;
 638
 639     if (! (temp = new REGION))
 640         return (Region) NULL;
 641     if (! (temp->rects = ( BOX * )malloc( (unsigned) sizeof( BOX )))) {
 642         free((char *) temp);
 643         return (Region) NULL;
 644     }
 645     temp->numRects = 0;
 646     temp->extents.x1 = 0;
 647     temp->extents.y1 = 0;
 648     temp->extents.x2 = 0;
 649     temp->extents.y2 = 0;
 650     temp->size = 1;
 651     return( temp );
 652 }
 653
 654 bool REGION::
 655 XClipBox(
 656     Region r,
 657     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                 if (! (dstrgn->rects = (BOX *)
 891                        realloc((char *) dstrgn->rects,
 892                                (unsigned) rgn->numRects * (sizeof(BOX)))))
 893                 {
 894                     free(prevRects);
 895                     return;
 896                 }
 897             }
 898             dstrgn->size = rgn->numRects;
 899         }
 900         dstrgn->numRects = rgn->numRects;
 901         dstrgn->extents.x1 = rgn->extents.x1;
 902         dstrgn->extents.y1 = rgn->extents.y1;
 903         dstrgn->extents.x2 = rgn->extents.x2;
 904         dstrgn->extents.y2 = rgn->extents.y2;
 905
 906         memcpy((char *) dstrgn->rects, (char *) rgn->rects,
 907                 (int) (rgn->numRects * sizeof(BOX)));
 908     }
 909 }
 910
 911 /*======================================================================
 912  * Generic Region Operator
 913  *====================================================================*/
 914
 915 /*-
 916  *-----------------------------------------------------------------------
 917  * miCoalesce --
 918  *    Attempt to merge the boxes in the current band with those in the
 919  *    previous one. Used only by miRegionOp.
 920  *
 921  * Results:
 922  *    The new index for the previous band.
 923  *
 924  * Side Effects:
 925  *    If coalescing takes place:
 926  *        - rectangles in the previous band will have their y2 fields
 927  *          altered.
 928  *        - pReg->numRects will be decreased.
 929  *
 930  *-----------------------------------------------------------------------
 931  */
 932 /* static int*/
 933 int REGION::
 934 miCoalesce(
 935     register Region pReg,     /* Region to coalesce */
 936     int prevStart,            /* Index of start of previous band */
 937     int curStart)             /* Index of start of current band */
 938 {
 939     register BoxPtr pPrevBox; /* Current box in previous band */
 940     register BoxPtr pCurBox;  /* Current box in current band */
 941     register BoxPtr pRegEnd;  /* End of region */
 942     int         curNumRects;  /* Number of rectangles in current
 943                                * band */
 944     int        prevNumRects;  /* Number of rectangles in previous
 945                                * band */
 946     int              bandY1;  /* Y1 coordinate for current band */
 947
 948     pRegEnd = &pReg->rects[pReg->numRects];
 949
 950     pPrevBox = &pReg->rects[prevStart];
 951     prevNumRects = curStart - prevStart;
 952
 953     /*
 954      * Figure out how many rectangles are in the current band. Have to do
 955      * this because multiple bands could have been added in miRegionOp
 956      * at the end when one region has been exhausted.
 957      */
 958     pCurBox = &pReg->rects[curStart];
 959     bandY1 = pCurBox->y1;
 960     for (curNumRects = 0;
 961          (pCurBox != pRegEnd) && (pCurBox->y1 == bandY1);
 962          curNumRects++)
 963     {
 964         pCurBox++;
 965     }
 966
 967     if (pCurBox != pRegEnd)
 968     {
 969         /*
 970          * If more than one band was added, we have to find the start
 971          * of the last band added so the next coalescing job can start
 972          * at the right place... (given when multiple bands are added,
 973          * this may be pointless -- see above).
 974          */
 975         pRegEnd--;
 976         while (pRegEnd[-1].y1 == pRegEnd->y1)
 977         {
 978             pRegEnd--;
 979         }
 980         curStart = pRegEnd - pReg->rects;
 981         pRegEnd = pReg->rects + pReg->numRects;
 982     }
 983
 984     if ((curNumRects == prevNumRects) && (curNumRects != 0))
 985     {
 986         pCurBox -= curNumRects;
 987         /*
 988          * The bands may only be coalesced if the bottom of the previous
 989          * matches the top scanline of the current.
 990          */
 991         if (pPrevBox->y2 == pCurBox->y1)
 992         {
 993         /*
 994          * Make sure the bands have boxes in the same places. This
 995          * assumes that boxes have been added in such a way that they
 996          * cover the most area possible. I.e. two boxes in a band must
 997          * have some horizontal space between them.
 998          */
 999             do
1000             {
1001                 if ((pPrevBox->x1 != pCurBox->x1) ||
1002                     (pPrevBox->x2 != pCurBox->x2))
1003                 {
1004                     /*
1005                      * The bands don't line up so they can't be coalesced.
1006                      */
1007                     return (curStart);
1008                 }
1009                 pPrevBox++;
1010                 pCurBox++;
1011                 prevNumRects -= 1;
1012             } while (prevNumRects != 0);
1013
1014             pReg->numRects -= curNumRects;
1015             pCurBox -= curNumRects;
1016             pPrevBox -= curNumRects;
1017
1018             /*
1019              * The bands may be merged, so set the bottom y of each box
1020              * in the previous band to that of the corresponding box in
1021              * the current band.
1022              */
1023             do
1024             {
1025                 pPrevBox->y2 = pCurBox->y2;
1026                 pPrevBox++;
1027                 pCurBox++;
1028                 curNumRects -= 1;
1029             } while (curNumRects != 0);
1030
1031             /*
1032              * If only one band was added to the region, we have to backup
1033              * curStart to the start of the previous band.
1034              *
1035              * If more than one band was added to the region, copy the
1036              * other bands down. The assumption here is that the other bands
1037              * came from the same region as the current one and no further
1038              * coalescing can be done on them since it's all been done
1039              * already... curStart is already in the right place.
1040              */
1041             if (pCurBox == pRegEnd)
1042             {
1043                 curStart = prevStart;
1044             }
1045             else
1046             {
1047                 do
1048                 {
1049                     *pPrevBox++ = *pCurBox++;
1050                 } while (pCurBox != pRegEnd);
1051             }
1052
1053         }
1054     }
1055     return (curStart);
1056 }
1057
1058 /*-
1059  *-----------------------------------------------------------------------
1060  * miRegionOp --
1061  *        Apply an operation to two regions. Called by miUnion, miInverse,
1062  *        miSubtract, miIntersect...
1063  *
1064  * Results:
1065  *        None.
1066  *
1067  * Side Effects:
1068  *        The new region is overwritten.
1069  *
1070  * Notes:
1071  *        The idea behind this function is to view the two regions as sets.
1072  *        Together they cover a rectangle of area that this function divides
1073  *        into horizontal bands where points are covered only by one region
1074  *        or by both. For the first case, the nonOverlapFunc is called with
1075  *        each the band and the band's upper and lower extents. For the
1076  *        second, the overlapFunc is called to process the entire band. It
1077  *        is responsible for clipping the rectangles in the band, though
1078  *        this function provides the boundaries.
1079  *        At the end of each band, the new region is coalesced, if possible,
1080  *        to reduce the number of rectangles in the region.
1081  *
1082  *-----------------------------------------------------------------------
1083  */
1084 /* static void*/
1085 void REGION::
1086 miRegionOp(
1087     register Region         newReg,                              /* Place to store result */
1088     Region                  reg1,                                /* First region in operation */
1089     Region                  reg2,                                /* 2d region in operation */
1090     int                      (*overlapFunc)(
1091         register Region     pReg,
1092         register BoxPtr     r1,
1093         BoxPtr              r1End,
1094         register BoxPtr     r2,
1095         BoxPtr              r2End,
1096         wxCoord               y1,
1097         wxCoord               y2),              /* Function to call for over-
1098                                                  * lapping bands */
1099     int                      (*nonOverlap1Func)(
1100         register Region     pReg,
1101         register BoxPtr     r,
1102         BoxPtr              rEnd,
1103         register wxCoord      y1,
1104         register wxCoord      y2),              /* Function to call for non-
1105                                                  * overlapping bands in region
1106                                                  * 1 */
1107     int                      (*nonOverlap2Func)(
1108         register Region     pReg,
1109         register BoxPtr     r,
1110         BoxPtr              rEnd,
1111         register wxCoord      y1,
1112         register wxCoord      y2))              /* Function to call for non-
1113                                                  * overlapping bands in region
1114                                                  * 2 */
1115 {
1116     register BoxPtr        r1; /* Pointer into first region */
1117     register BoxPtr        r2; /* Pointer into 2d region */
1118     BoxPtr              r1End; /* End of 1st region */
1119     BoxPtr              r2End; /* End of 2d region */
1120     register wxCoord     ybot; /* Bottom of intersection */
1121     register wxCoord     ytop; /* Top of intersection */
1122     BoxPtr           oldRects; /* Old rects for newReg */
1123     int              prevBand; /* Index of start of
1124                                 * previous band in newReg */
1125     int               curBand; /* Index of start of current
1126                                 * band in newReg */
1127     register BoxPtr r1BandEnd; /* End of current band in r1 */
1128     register BoxPtr r2BandEnd; /* End of current band in r2 */
1129     wxCoord               top; /* Top of non-overlapping
1130                                 * band */
1131     wxCoord               bot; /* Bottom of non-overlapping
1132                                 * band */
1133
1134     /*
1135      * Initialization:
1136      *        set r1, r2, r1End and r2End appropriately, preserve the important
1137      * parts of the destination region until the end in case it's one of
1138      * the two source regions, then mark the "new" region empty, allocating
1139      * another array of rectangles for it to use.
1140      */
1141     r1 = reg1->rects;
1142     r2 = reg2->rects;
1143     r1End = r1 + reg1->numRects;
1144     r2End = r2 + reg2->numRects;
1145
1146     oldRects = newReg->rects;
1147
1148     EMPTY_REGION(newReg);
1149
1150     /*
1151      * Allocate a reasonable number of rectangles for the new region. The idea
1152      * is to allocate enough so the individual functions don't need to
1153      * reallocate and copy the array, which is time consuming, yet we don't
1154      * have to worry about using too much memory. I hope to be able to
1155      * nuke the realloc() at the end of this function eventually.
1156      */
1157     newReg->size = wxMax(reg1->numRects,reg2->numRects) * 2;
1158
1159     if (! (newReg->rects = (BoxPtr)
1160            malloc ((unsigned) (sizeof(BoxRec) * newReg->size)))) {
1161         newReg->size = 0;
1162         return;
1163     }
1164
1165     /*
1166      * Initialize ybot and ytop.
1167      * In the upcoming loop, ybot and ytop serve different functions depending
1168      * on whether the band being handled is an overlapping or non-overlapping
1169      * band.
1170      *         In the case of a non-overlapping band (only one of the regions
1171      * has points in the band), ybot is the bottom of the most recent
1172      * intersection and thus clips the top of the rectangles in that band.
1173      * ytop is the top of the next intersection between the two regions and
1174      * serves to clip the bottom of the rectangles in the current band.
1175      *        For an overlapping band (where the two regions intersect), ytop clips
1176      * the top of the rectangles of both regions and ybot clips the bottoms.
1177      */
1178     if (reg1->extents.y1 < reg2->extents.y1)
1179         ybot = reg1->extents.y1;
1180     else
1181         ybot = reg2->extents.y1;
1182
1183     /*
1184      * prevBand serves to mark the start of the previous band so rectangles
1185      * can be coalesced into larger rectangles. qv. miCoalesce, above.
1186      * In the beginning, there is no previous band, so prevBand == curBand
1187      * (curBand is set later on, of course, but the first band will always
1188      * start at index 0). prevBand and curBand must be indices because of
1189      * the possible expansion, and resultant moving, of the new region's
1190      * array of rectangles.
1191      */
1192     prevBand = 0;
1193
1194     do
1195     {
1196         curBand = newReg->numRects;
1197
1198         /*
1199          * This algorithm proceeds one source-band (as opposed to a
1200          * destination band, which is determined by where the two regions
1201          * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
1202          * rectangle after the last one in the current band for their
1203          * respective regions.
1204          */
1205         r1BandEnd = r1;
1206         while ((r1BandEnd != r1End) && (r1BandEnd->y1 == r1->y1))
1207         {
1208             r1BandEnd++;
1209         }
1210
1211         r2BandEnd = r2;
1212         while ((r2BandEnd != r2End) && (r2BandEnd->y1 == r2->y1))
1213         {
1214             r2BandEnd++;
1215         }
1216
1217         /*
1218          * First handle the band that doesn't intersect, if any.
1219          *
1220          * Note that attention is restricted to one band in the
1221          * non-intersecting region at once, so if a region has n
1222          * bands between the current position and the next place it overlaps
1223          * the other, this entire loop will be passed through n times.
1224          */
1225         if (r1->y1 < r2->y1)
1226         {
1227             top = wxMax(r1->y1,ybot);
1228             bot = wxMin(r1->y2,r2->y1);
1229
1230             if ((top != bot) && (nonOverlap1Func != NULL))
1231             {
1232                 (* nonOverlap1Func) (newReg, r1, r1BandEnd, top, bot);
1233             }
1234
1235             ytop = r2->y1;
1236         }
1237         else if (r2->y1 < r1->y1)
1238         {
1239             top = wxMax(r2->y1,ybot);
1240             bot = wxMin(r2->y2,r1->y1);
1241
1242             if ((top != bot) && (nonOverlap2Func != NULL))
1243             {
1244                 (* nonOverlap2Func) (newReg, r2, r2BandEnd, top, bot);
1245             }
1246
1247             ytop = r1->y1;
1248         }
1249         else
1250         {
1251             ytop = r1->y1;
1252         }
1253
1254         /*
1255          * If any rectangles got added to the region, try and coalesce them
1256          * with rectangles from the previous band. Note we could just do
1257          * this test in miCoalesce, but some machines incur a not
1258          * inconsiderable cost for function calls, so...
1259          */
1260         if (newReg->numRects != curBand)
1261         {
1262             prevBand = miCoalesce (newReg, prevBand, curBand);
1263         }
1264
1265         /*
1266          * Now see if we've hit an intersecting band. The two bands only
1267          * intersect if ybot > ytop
1268          */
1269         ybot = wxMin(r1->y2, r2->y2);
1270         curBand = newReg->numRects;
1271         if (ybot > ytop)
1272         {
1273             (* overlapFunc) (newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
1274
1275         }
1276
1277         if (newReg->numRects != curBand)
1278         {
1279             prevBand = miCoalesce (newReg, prevBand, curBand);
1280         }
1281
1282         /*
1283          * If we've finished with a band (y2 == ybot) we skip forward
1284          * in the region to the next band.
1285          */
1286         if (r1->y2 == ybot)
1287         {
1288             r1 = r1BandEnd;
1289         }
1290         if (r2->y2 == ybot)
1291         {
1292             r2 = r2BandEnd;
1293         }
1294     } while ((r1 != r1End) && (r2 != r2End));
1295
1296     /*
1297      * Deal with whichever region still has rectangles left.
1298      */
1299     curBand = newReg->numRects;
1300     if (r1 != r1End)
1301     {
1302         if (nonOverlap1Func != NULL)
1303         {
1304             do
1305             {
1306                 r1BandEnd = r1;
1307                 while ((r1BandEnd < r1End) && (r1BandEnd->y1 == r1->y1))
1308                 {
1309                     r1BandEnd++;
1310                 }
1311                 (* nonOverlap1Func) (newReg, r1, r1BandEnd,
1312                                      wxMax(r1->y1,ybot), r1->y2);
1313                 r1 = r1BandEnd;
1314             } while (r1 != r1End);
1315         }
1316     }
1317     else if ((r2 != r2End) && (nonOverlap2Func != NULL))
1318     {
1319         do
1320         {
1321             r2BandEnd = r2;
1322             while ((r2BandEnd < r2End) && (r2BandEnd->y1 == r2->y1))
1323             {
1324                  r2BandEnd++;
1325             }
1326             (* nonOverlap2Func) (newReg, r2, r2BandEnd,
1327                                 wxMax(r2->y1,ybot), r2->y2);
1328             r2 = r2BandEnd;
1329         } while (r2 != r2End);
1330     }
1331
1332     if (newReg->numRects != curBand)
1333     {
1334         (void) miCoalesce (newReg, prevBand, curBand);
1335     }
1336
1337     /*
1338      * A bit of cleanup. To keep regions from growing without bound,
1339      * we shrink the array of rectangles to match the new number of
1340      * rectangles in the region. This never goes to 0, however...
1341      *
1342      * Only do this stuff if the number of rectangles allocated is more than
1343      * twice the number of rectangles in the region (a simple optimization...).
1344      */
1345     if (newReg->numRects < (newReg->size >> 1))
1346     {
1347         if (REGION_NOT_EMPTY(newReg))
1348         {
1349             BoxPtr prev_rects = newReg->rects;
1350             newReg->size = newReg->numRects;
1351             newReg->rects = (BoxPtr) realloc ((char *) newReg->rects,
1352                                    (unsigned) (sizeof(BoxRec) * newReg->size));
1353             if (! newReg->rects)
1354                 newReg->rects = prev_rects;
1355         }
1356         else
1357         {
1358             /*
1359              * No point in doing the extra work involved in an realloc if
1360              * the region is empty
1361              */
1362             newReg->size = 1;
1363             free((char *) newReg->rects);
1364             newReg->rects = (BoxPtr) malloc(sizeof(BoxRec));
1365         }
1366     }
1367     free ((char *) oldRects);
1368     return;
1369 }
1370
1371 /*======================================================================
1372  *            Region Union
1373  *====================================================================*/
1374
1375 /*-
1376  *-----------------------------------------------------------------------
1377  * miUnionNonO --
1378  *        Handle a non-overlapping band for the union operation. Just
1379  *        Adds the rectangles into the region. Doesn't have to check for
1380  *        subsumption or anything.
1381  *
1382  * Results:
1383  *        None.
1384  *
1385  * Side Effects:
1386  *        pReg->numRects is incremented and the final rectangles overwritten
1387  *        with the rectangles we're passed.
1388  *
1389  *-----------------------------------------------------------------------
1390  */
1391 /* static void*/
1392 int REGION::
1393 miUnionNonO (
1394     register Region        pReg,
1395     register BoxPtr        r,
1396     BoxPtr                 rEnd,
1397     register wxCoord       y1,
1398     register wxCoord       y2)
1399 {
1400     register BoxPtr        pNextRect;
1401
1402     pNextRect = &pReg->rects[pReg->numRects];
1403
1404     assert(y1 < y2);
1405
1406     while (r != rEnd)
1407     {
1408         assert(r->x1 < r->x2);
1409         MEMCHECK(pReg, pNextRect, pReg->rects);
1410         pNextRect->x1 = r->x1;
1411         pNextRect->y1 = y1;
1412         pNextRect->x2 = r->x2;
1413         pNextRect->y2 = y2;
1414         pReg->numRects += 1;
1415         pNextRect++;
1416
1417         assert(pReg->numRects<=pReg->size);
1418         r++;
1419     }
1420     return 0;        /* lint */
1421 }
1422
1423
1424 /*-
1425  *-----------------------------------------------------------------------
1426  * miUnionO --
1427  *        Handle an overlapping band for the union operation. Picks the
1428  *        left-most rectangle each time and merges it into the region.
1429  *
1430  * Results:
1431  *        None.
1432  *
1433  * Side Effects:
1434  *        Rectangles are overwritten in pReg->rects and pReg->numRects will
1435  *        be changed.
1436  *
1437  *-----------------------------------------------------------------------
1438  */
1439
1440 /* static void*/
1441 int REGION::
1442 miUnionO (
1443     register Region        pReg,
1444     register BoxPtr        r1,
1445     BoxPtr                 r1End,
1446     register BoxPtr        r2,
1447     BoxPtr                 r2End,
1448     register wxCoord       y1,
1449     register wxCoord       y2)
1450 {
1451     register BoxPtr        pNextRect;
1452
1453     pNextRect = &pReg->rects[pReg->numRects];
1454
1455 #define MERGERECT(r) \
1456     if ((pReg->numRects != 0) &&  \
1457         (pNextRect[-1].y1 == y1) &&  \
1458         (pNextRect[-1].y2 == y2) &&  \
1459         (pNextRect[-1].x2 >= r->x1))  \
1460     {  \
1461         if (pNextRect[-1].x2 < r->x2)  \
1462         {  \
1463             pNextRect[-1].x2 = r->x2;  \
1464             assert(pNextRect[-1].x1<pNextRect[-1].x2); \
1465         }  \
1466     }  \
1467     else  \
1468     {  \
1469         MEMCHECK(pReg, pNextRect, pReg->rects);  \
1470         pNextRect->y1 = y1;  \
1471         pNextRect->y2 = y2;  \
1472         pNextRect->x1 = r->x1;  \
1473         pNextRect->x2 = r->x2;  \
1474         pReg->numRects += 1;  \
1475         pNextRect += 1;  \
1476     }  \
1477     assert(pReg->numRects<=pReg->size);\
1478     r++;
1479
1480     assert (y1<y2);
1481     while ((r1 != r1End) && (r2 != r2End))
1482     {
1483         if (r1->x1 < r2->x1)
1484         {
1485             MERGERECT(r1);
1486         }
1487         else
1488         {
1489             MERGERECT(r2);
1490         }
1491     }
1492
1493     if (r1 != r1End)
1494     {
1495         do
1496         {
1497             MERGERECT(r1);
1498         } while (r1 != r1End);
1499     }
1500     else while (r2 != r2End)
1501     {
1502         MERGERECT(r2);
1503     }
1504     return 0;        /* lint */
1505 }
1506
1507 bool REGION::
1508 XUnionRegion(
1509     Region           reg1,
1510     Region          reg2,             /* source regions     */
1511     Region           newReg)                  /* destination Region */
1512 {
1513     /*  checks all the simple cases */
1514
1515     /*
1516      * Region 1 and 2 are the same or region 1 is empty
1517      */
1518     if ( (reg1 == reg2) || (!(reg1->numRects)) )
1519     {
1520         if (newReg != reg2)
1521             miRegionCopy(newReg, reg2);
1522         return 1;
1523     }
1524
1525     /*
1526      * if nothing to union (region 2 empty)
1527      */
1528     if (!(reg2->numRects))
1529     {
1530         if (newReg != reg1)
1531             miRegionCopy(newReg, reg1);
1532         return 1;
1533     }
1534
1535     /*
1536      * Region 1 completely subsumes region 2
1537      */
1538     if ((reg1->numRects == 1) &&
1539         (reg1->extents.x1 <= reg2->extents.x1) &&
1540         (reg1->extents.y1 <= reg2->extents.y1) &&
1541         (reg1->extents.x2 >= reg2->extents.x2) &&
1542         (reg1->extents.y2 >= reg2->extents.y2))
1543     {
1544         if (newReg != reg1)
1545             miRegionCopy(newReg, reg1);
1546         return 1;
1547     }
1548
1549     /*
1550      * Region 2 completely subsumes region 1
1551      */
1552     if ((reg2->numRects == 1) &&
1553         (reg2->extents.x1 <= reg1->extents.x1) &&
1554         (reg2->extents.y1 <= reg1->extents.y1) &&
1555         (reg2->extents.x2 >= reg1->extents.x2) &&
1556         (reg2->extents.y2 >= reg1->extents.y2))
1557     {
1558         if (newReg != reg2)
1559             miRegionCopy(newReg, reg2);
1560         return 1;
1561     }
1562
1563     miRegionOp (newReg, reg1, reg2, miUnionO,
1564                     miUnionNonO, miUnionNonO);
1565
1566     newReg->extents.x1 = wxMin(reg1->extents.x1, reg2->extents.x1);
1567     newReg->extents.y1 = wxMin(reg1->extents.y1, reg2->extents.y1);
1568     newReg->extents.x2 = wxMax(reg1->extents.x2, reg2->extents.x2);
1569     newReg->extents.y2 = wxMax(reg1->extents.y2, reg2->extents.y2);
1570
1571     return 1;
1572 }
1573
1574 /*======================================================================
1575  *                       Region Subtraction
1576  *====================================================================*/
1577
1578 /*-
1579  *-----------------------------------------------------------------------
1580  * miSubtractNonO --
1581  *        Deal with non-overlapping band for subtraction. Any parts from
1582  *        region 2 we discard. Anything from region 1 we add to the region.
1583  *
1584  * Results:
1585  *        None.
1586  *
1587  * Side Effects:
1588  *        pReg may be affected.
1589  *
1590  *-----------------------------------------------------------------------
1591  */
1592 /* static void*/
1593 int REGION::
1594 miSubtractNonO1 (
1595     register Region        pReg,
1596     register BoxPtr        r,
1597     BoxPtr                    rEnd,
1598     register wxCoord          y1,
1599     register wxCoord           y2)
1600 {
1601     register BoxPtr        pNextRect;
1602
1603     pNextRect = &pReg->rects[pReg->numRects];
1604
1605     assert(y1<y2);
1606
1607     while (r != rEnd)
1608     {
1609         assert(r->x1<r->x2);
1610         MEMCHECK(pReg, pNextRect, pReg->rects);
1611         pNextRect->x1 = r->x1;
1612         pNextRect->y1 = y1;
1613         pNextRect->x2 = r->x2;
1614         pNextRect->y2 = y2;
1615         pReg->numRects += 1;
1616         pNextRect++;
1617
1618         assert(pReg->numRects <= pReg->size);
1619
1620         r++;
1621     }
1622     return 0;        /* lint */
1623 }
1624
1625 /*-
1626  *-----------------------------------------------------------------------
1627  * miSubtractO --
1628  *        Overlapping band subtraction. x1 is the left-most point not yet
1629  *        checked.
1630  *
1631  * Results:
1632  *        None.
1633  *
1634  * Side Effects:
1635  *        pReg may have rectangles added to it.
1636  *
1637  *-----------------------------------------------------------------------
1638  */
1639 /* static void*/
1640 int REGION::
1641 miSubtractO (
1642     register Region        pReg,
1643     register BoxPtr        r1,
1644     BoxPtr                    r1End,
1645     register BoxPtr        r2,
1646     BoxPtr                    r2End,
1647     register wxCoord          y1,
1648     register wxCoord          y2)
1649 {
1650     register BoxPtr        pNextRect;
1651     register int          x1;
1652
1653     x1 = r1->x1;
1654
1655     assert(y1<y2);
1656     pNextRect = &pReg->rects[pReg->numRects];
1657
1658     while ((r1 != r1End) && (r2 != r2End))
1659     {
1660         if (r2->x2 <= x1)
1661         {
1662             /*
1663              * Subtrahend missed the boat: go to next subtrahend.
1664              */
1665             r2++;
1666         }
1667         else if (r2->x1 <= x1)
1668         {
1669             /*
1670              * Subtrahend preceeds minuend: nuke left edge of minuend.
1671              */
1672             x1 = r2->x2;
1673             if (x1 >= r1->x2)
1674             {
1675                 /*
1676                  * Minuend completely covered: advance to next minuend and
1677                  * reset left fence to edge of new minuend.
1678                  */
1679                 r1++;
1680                 if (r1 != r1End)
1681                     x1 = r1->x1;
1682             }
1683             else
1684             {
1685                 /*
1686                  * Subtrahend now used up since it doesn't extend beyond
1687                  * minuend
1688                  */
1689                 r2++;
1690             }
1691         }
1692         else if (r2->x1 < r1->x2)
1693         {
1694             /*
1695              * Left part of subtrahend covers part of minuend: add uncovered
1696              * part of minuend to region and skip to next subtrahend.
1697              */
1698             assert(x1<r2->x1);
1699             MEMCHECK(pReg, pNextRect, pReg->rects);
1700             pNextRect->x1 = x1;
1701             pNextRect->y1 = y1;
1702             pNextRect->x2 = r2->x1;
1703             pNextRect->y2 = y2;
1704             pReg->numRects += 1;
1705             pNextRect++;
1706
1707             assert(pReg->numRects<=pReg->size);
1708
1709             x1 = r2->x2;
1710             if (x1 >= r1->x2)
1711             {
1712                 /*
1713                  * Minuend used up: advance to new...
1714                  */
1715                 r1++;
1716                 if (r1 != r1End)
1717                     x1 = r1->x1;
1718             }
1719             else
1720             {
1721                 /*
1722                  * Subtrahend used up
1723                  */
1724                 r2++;
1725             }
1726         }
1727         else
1728         {
1729             /*
1730              * Minuend used up: add any remaining piece before advancing.
1731              */
1732             if (r1->x2 > x1)
1733             {
1734                 MEMCHECK(pReg, pNextRect, pReg->rects);
1735                 pNextRect->x1 = x1;
1736                 pNextRect->y1 = y1;
1737                 pNextRect->x2 = r1->x2;
1738                 pNextRect->y2 = y2;
1739                 pReg->numRects += 1;
1740                 pNextRect++;
1741                 assert(pReg->numRects<=pReg->size);
1742             }
1743             r1++;
1744             if (r1 != r1End)
1745                 x1 = r1->x1;
1746         }
1747     }
1748
1749     /*
1750      * Add remaining minuend rectangles to region.
1751      */
1752     while (r1 != r1End)
1753     {
1754         assert(x1<r1->x2);
1755         MEMCHECK(pReg, pNextRect, pReg->rects);
1756         pNextRect->x1 = x1;
1757         pNextRect->y1 = y1;
1758         pNextRect->x2 = r1->x2;
1759         pNextRect->y2 = y2;
1760         pReg->numRects += 1;
1761         pNextRect++;
1762
1763         assert(pReg->numRects<=pReg->size);
1764
1765         r1++;
1766         if (r1 != r1End)
1767         {
1768             x1 = r1->x1;
1769         }
1770     }
1771     return 0;        /* lint */
1772 }
1773
1774 /*-
1775  *-----------------------------------------------------------------------
1776  * miSubtract --
1777  *        Subtract regS from regM and leave the result in regD.
1778  *        S stands for subtrahend, M for minuend and D for difference.
1779  *
1780  * Results:
1781  *        true.
1782  *
1783  * Side Effects:
1784  *        regD is overwritten.
1785  *
1786  *-----------------------------------------------------------------------
1787  */
1788
1789 bool REGION::
1790 XSubtractRegion(
1791     Region                   regM,
1792     Region                  regS,
1793     register Region        regD)
1794 {
1795    /* check for trivial reject */
1796     if ( (!(regM->numRects)) || (!(regS->numRects))  ||
1797         (!EXTENTCHECK(&regM->extents, &regS->extents)) )
1798     {
1799         miRegionCopy(regD, regM);
1800         return true;
1801     }
1802
1803     miRegionOp (regD, regM, regS, miSubtractO,
1804                     miSubtractNonO1, NULL);
1805
1806     /*
1807      * Can't alter newReg's extents before we call miRegionOp because
1808      * it might be one of the source regions and miRegionOp depends
1809      * on the extents of those regions being the unaltered. Besides, this
1810      * way there's no checking against rectangles that will be nuked
1811      * due to coalescing, so we have to examine fewer rectangles.
1812      */
1813     miSetExtents (regD);
1814     return true;
1815 }
1816
1817 bool REGION::
1818 XXorRegion(Region sra, Region srb, Region dr)
1819 {
1820     Region tra, trb;
1821
1822     if ((! (tra = XCreateRegion())) || (! (trb = XCreateRegion())))
1823         return 0;
1824     (void) XSubtractRegion(sra,srb,tra);
1825     (void) XSubtractRegion(srb,sra,trb);
1826     (void) XUnionRegion(tra,trb,dr);
1827     XDestroyRegion(tra);
1828     XDestroyRegion(trb);
1829     return 0;
1830 }
1831
1832 /*
1833  * Check to see if the region is empty.  Assumes a region is passed
1834  * as a parameter
1835  */
1836 bool REGION::
1837 XEmptyRegion(
1838     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::
1848 XEqualRegion(Region r1, Region r2)
1849 {
1850     int i;
1851
1852     if( r1->numRects != r2->numRects ) return false;
1853     else if( r1->numRects == 0 ) return true;
1854     else if ( r1->extents.x1 != r2->extents.x1 ) return false;
1855     else if ( r1->extents.x2 != r2->extents.x2 ) return false;
1856     else if ( r1->extents.y1 != r2->extents.y1 ) return false;
1857     else if ( r1->extents.y2 != r2->extents.y2 ) return false;
1858     else for( i=0; i < r1->numRects; i++ ) {
1859             if ( r1->rects[i].x1 != r2->rects[i].x1 ) return false;
1860             else if ( r1->rects[i].x2 != r2->rects[i].x2 ) return false;
1861             else if ( r1->rects[i].y1 != r2->rects[i].y1 ) return false;
1862             else if ( r1->rects[i].y2 != r2->rects[i].y2 ) return false;
1863     }
1864     return true;
1865 }
1866
1867 bool REGION::
1868 XPointInRegion(
1869     Region pRegion,
1870     int x, int y)
1871 {
1872     int i;
1873
1874     if (pRegion->numRects == 0)
1875         return false;
1876     if (!INBOX(pRegion->extents, x, y))
1877         return false;
1878     for (i=0; i<pRegion->numRects; i++)
1879     {
1880         if (INBOX (pRegion->rects[i], x, y))
1881             return true;
1882     }
1883     return false;
1884 }
1885
1886 wxRegionContain REGION::
1887 XRectInRegion(
1888     register Region        region,
1889     int rx, int ry,
1890     unsigned int rwidth, unsigned int rheight)
1891 {
1892     register BoxPtr pbox;
1893     register BoxPtr pboxEnd;
1894     Box rect;
1895     register BoxPtr prect = &rect;
1896     int      partIn, partOut;
1897
1898     prect->x1 = rx;
1899     prect->y1 = ry;
1900     prect->x2 = rwidth + rx;
1901     prect->y2 = rheight + ry;
1902
1903     /* this is (just) a useful optimization */
1904     if ((region->numRects == 0) || !EXTENTCHECK(&region->extents, prect))
1905         return(wxOutRegion);
1906
1907     partOut = false;
1908     partIn = false;
1909
1910     /* can stop when both partOut and partIn are true, or we reach prect->y2 */
1911     for (pbox = region->rects, pboxEnd = pbox + region->numRects;
1912          pbox < pboxEnd;
1913          pbox++)
1914     {
1915
1916         if (pbox->y2 <= ry)
1917            continue;        /* getting up to speed or skipping remainder of band */
1918
1919         if (pbox->y1 > ry)
1920         {
1921            partOut = true;        /* missed part of rectangle above */
1922            if (partIn || (pbox->y1 >= prect->y2))
1923               break;
1924            ry = pbox->y1;        /* x guaranteed to be == prect->x1 */
1925         }
1926
1927         if (pbox->x2 <= rx)
1928            continue;                /* not far enough over yet */
1929
1930         if (pbox->x1 > rx)
1931         {
1932            partOut = true;        /* missed part of rectangle to left */
1933            if (partIn)
1934               break;
1935         }
1936
1937         if (pbox->x1 < prect->x2)
1938         {
1939             partIn = true;        /* definitely overlap */
1940             if (partOut)
1941                break;
1942         }
1943
1944         if (pbox->x2 >= prect->x2)
1945         {
1946            ry = pbox->y2;        /* finished with this band */
1947            if (ry >= prect->y2)
1948               break;
1949            rx = prect->x1;        /* reset x out to left again */
1950         } else
1951         {
1952             /*
1953              * Because boxes in a band are maximal width, if the first box
1954              * to overlap the rectangle doesn't completely cover it in that
1955              * band, the rectangle must be partially out, since some of it
1956              * will be uncovered in that band. partIn will have been set true
1957              * by now...
1958              */
1959             break;
1960         }
1961
1962     }
1963
1964     return(partIn ? ((ry < prect->y2) ? wxPartRegion : wxInRegion) :
1965                 wxOutRegion);
1966 }