src/gui/painting/qregion.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtGui module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  32 **
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include "qregion.h"
  43 #include "qpainterpath.h"
  44 #include "qpolygon.h"
  45 #include "qbuffer.h"
  46 #include "qdatastream.h"
  47 #include "qvariant.h"
  48 #include "qvarlengtharray.h"
  49 #include "qimage.h"
  50 #include "qbitmap.h"
  51
  52 #include <qdebug.h>
  53
  54 QT_BEGIN_NAMESPACE
  55
  56 /*!
  57     \class QRegion
  58     \brief The QRegion class specifies a clip region for a painter.
  59
  60     \ingroup painting
  61     \ingroup shared
  62
  63     QRegion is used with QPainter::setClipRegion() to limit the paint
  64     area to what needs to be painted. There is also a QWidget::repaint()
  65     function that takes a QRegion parameter. QRegion is the best tool for
  66     minimizing the amount of screen area to be updated by a repaint.
  67
  68     This class is not suitable for constructing shapes for rendering, especially
  69     as outlines. Use QPainterPath to create paths and shapes for use with
  70     QPainter.
  71
  72     QRegion is an \l{implicitly shared} class.
  73
  74     \section1 Creating and Using Regions
  75
  76     A region can be created from a rectangle, an ellipse, a polygon or
  77     a bitmap. Complex regions may be created by combining simple
  78     regions using united(), intersected(), subtracted(), or xored() (exclusive
  79     or). You can move a region using translate().
  80
  81     You can test whether a region isEmpty() or if it
  82     contains() a QPoint or QRect. The bounding rectangle can be found
  83     with boundingRect().
  84
  85     The function rects() gives a decomposition of the region into
  86     rectangles.
  87
  88     Example of using complex regions:
  89     \snippet doc/src/snippets/code/src_gui_painting_qregion.cpp 0
  90
  91     \section1 Additional License Information
  92
  93     On Embedded Linux, Windows CE and X11 platforms, parts of this class rely on
  94     code obtained under the following licenses:
  95
  96     \legalese
  97     Copyright (c) 1987  X Consortium
  98
  99     Permission is hereby granted, free of charge, to any person obtaining a copy
 100     of this software and associated documentation files (the "Software"), to deal
 101     in the Software without restriction, including without limitation the rights
 102     to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 103     copies of the Software, and to permit persons to whom the Software is
 104     furnished to do so, subject to the following conditions:
 105
 106     The above copyright notice and this permission notice shall be included in
 107     all copies or substantial portions of the Software.
 108
 109     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 110     IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 111     FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 112     X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
 113     AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 114     CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 115
 116     Except as contained in this notice, the name of the X Consortium shall not be
 117     used in advertising or otherwise to promote the sale, use or other dealings
 118     in this Software without prior written authorization from the X Consortium.
 119     \endlegalese
 120
 121     \br
 122
 123     \legalese
 124     Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
 125
 126                             All Rights Reserved
 127
 128     Permission to use, copy, modify, and distribute this software and its
 129     documentation for any purpose and without fee is hereby granted,
 130     provided that the above copyright notice appear in all copies and that
 131     both that copyright notice and this permission notice appear in
 132     supporting documentation, and that the name of Digital not be
 133     used in advertising or publicity pertaining to distribution of the
 134     software without specific, written prior permission.
 135
 136     DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 137     ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
 138     DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
 139     ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
 140     WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
 141     ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 142     SOFTWARE.
 143     \endlegalese
 144
 145     \sa QPainter::setClipRegion(), QPainter::setClipRect(), QPainterPath
 146 */
 147
 148
 149 /*!
 150     \enum QRegion::RegionType
 151
 152     Specifies the shape of the region to be created.
 153
 154     \value Rectangle  the region covers the entire rectangle.
 155     \value Ellipse  the region is an ellipse inside the rectangle.
 156 */
 157
 158 /*!
 159     \fn void QRegion::translate(const QPoint &point)
 160
 161     \overload
 162
 163     Translates the region \a{point}\e{.x()} along the x axis and
 164     \a{point}\e{.y()} along the y axis, relative to the current
 165     position. Positive values move the region to the right and down.
 166
 167     Translates to the given \a point.
 168 */
 169
 170 /*!
 171     \fn Handle QRegion::handle() const
 172
 173     Returns a platform-specific region handle. The \c Handle type is
 174     \c HRGN on Windows, \c Region on X11, and \c RgnHandle on Mac OS
 175     X. On \l{Qt for Embedded Linux} it is \c {void *}.
 176
 177     \warning This function is not portable.
 178 */
 179
 180 /*****************************************************************************
 181   QRegion member functions
 182  *****************************************************************************/
 183
 184 /*!
 185     \fn QRegion::QRegion()
 186
 187     Constructs an empty region.
 188
 189     \sa isEmpty()
 190 */
 191
 192 /*!
 193     \fn QRegion::QRegion(const QRect &r, RegionType t)
 194     \overload
 195
 196     Create a region based on the rectange \a r with region type \a t.
 197
 198     If the rectangle is invalid a null region will be created.
 199
 200     \sa QRegion::RegionType
 201 */
 202
 203 /*!
 204     \fn QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
 205
 206     Constructs a polygon region from the point array \a a with the fill rule
 207     specified by \a fillRule.
 208
 209     If \a fillRule is \l{Qt::WindingFill}, the polygon region is defined
 210     using the winding algorithm; if it is \l{Qt::OddEvenFill}, the odd-even fill
 211     algorithm is used.
 212
 213     \warning This constructor can be used to create complex regions that will
 214     slow down painting when used.
 215 */
 216
 217 /*!
 218     \fn QRegion::QRegion(const QRegion &r)
 219
 220     Constructs a new region which is equal to region \a r.
 221 */
 222
 223 /*!
 224     \fn QRegion::QRegion(const QBitmap &bm)
 225
 226     Constructs a region from the bitmap \a bm.
 227
 228     The resulting region consists of the pixels in bitmap \a bm that
 229     are Qt::color1, as if each pixel was a 1 by 1 rectangle.
 230
 231     This constructor may create complex regions that will slow down
 232     painting when used. Note that drawing masked pixmaps can be done
 233     much faster using QPixmap::setMask().
 234 */
 235
 236 /*!
 237     Constructs a rectangular or elliptic region.
 238
 239     If \a t is \c Rectangle, the region is the filled rectangle (\a x,
 240     \a y, \a w, \a h). If \a t is \c Ellipse, the region is the filled
 241     ellipse with center at (\a x + \a w / 2, \a y + \a h / 2) and size
 242     (\a w ,\a h).
 243 */
 244 QRegion::QRegion(int x, int y, int w, int h, RegionType t)
 245 {
 246     QRegion tmp(QRect(x, y, w, h), t);
 247     tmp.d->ref.ref();
 248     d = tmp.d;
 249 }
 250
 251 /*!
 252     \fn QRegion::~QRegion()
 253     \internal
 254
 255     Destroys the region.
 256 */
 257
 258 void QRegion::detach()
 259 {
 260     if (d->ref.load() != 1)
 261         *this = copy();
 262 }
 263
 264 // duplicates in qregion_win.cpp and qregion_wce.cpp
 265 #define QRGN_SETRECT          1                // region stream commands
 266 #define QRGN_SETELLIPSE       2                //  (these are internal)
 267 #define QRGN_SETPTARRAY_ALT   3
 268 #define QRGN_SETPTARRAY_WIND  4
 269 #define QRGN_TRANSLATE        5
 270 #define QRGN_OR               6
 271 #define QRGN_AND              7
 272 #define QRGN_SUB              8
 273 #define QRGN_XOR              9
 274 #define QRGN_RECTS            10
 275
 276
 277 #ifndef QT_NO_DATASTREAM
 278
 279 /*
 280     Executes region commands in the internal buffer and rebuilds the
 281     original region.
 282
 283     We do this when we read a region from the data stream.
 284
 285     If \a ver is non-0, uses the format version \a ver on reading the
 286     byte array.
 287 */
 288 void QRegion::exec(const QByteArray &buffer, int ver, QDataStream::ByteOrder byteOrder)
 289 {
 290     QByteArray copy = buffer;
 291     QDataStream s(&copy, QIODevice::ReadOnly);
 292     if (ver)
 293         s.setVersion(ver);
 294     s.setByteOrder(byteOrder);
 295     QRegion rgn;
 296 #ifndef QT_NO_DEBUG
 297     int test_cnt = 0;
 298 #endif
 299     while (!s.atEnd()) {
 300         qint32 id;
 301         if (s.version() == 1) {
 302             int id_int;
 303             s >> id_int;
 304             id = id_int;
 305         } else {
 306             s >> id;
 307         }
 308 #ifndef QT_NO_DEBUG
 309         if (test_cnt > 0 && id != QRGN_TRANSLATE)
 310             qWarning("QRegion::exec: Internal error");
 311         test_cnt++;
 312 #endif
 313         if (id == QRGN_SETRECT || id == QRGN_SETELLIPSE) {
 314             QRect r;
 315             s >> r;
 316             rgn = QRegion(r, id == QRGN_SETRECT ? Rectangle : Ellipse);
 317         } else if (id == QRGN_SETPTARRAY_ALT || id == QRGN_SETPTARRAY_WIND) {
 318             QPolygon a;
 319             s >> a;
 320             rgn = QRegion(a, id == QRGN_SETPTARRAY_WIND ? Qt::WindingFill : Qt::OddEvenFill);
 321         } else if (id == QRGN_TRANSLATE) {
 322             QPoint p;
 323             s >> p;
 324             rgn.translate(p.x(), p.y());
 325         } else if (id >= QRGN_OR && id <= QRGN_XOR) {
 326             QByteArray bop1, bop2;
 327             QRegion r1, r2;
 328             s >> bop1;
 329             r1.exec(bop1);
 330             s >> bop2;
 331             r2.exec(bop2);
 332
 333             switch (id) {
 334                 case QRGN_OR:
 335                     rgn = r1.united(r2);
 336                     break;
 337                 case QRGN_AND:
 338                     rgn = r1.intersected(r2);
 339                     break;
 340                 case QRGN_SUB:
 341                     rgn = r1.subtracted(r2);
 342                     break;
 343                 case QRGN_XOR:
 344                     rgn = r1.xored(r2);
 345                     break;
 346             }
 347         } else if (id == QRGN_RECTS) {
 348             // (This is the only form used in Qt 2.0)
 349             quint32 n;
 350             s >> n;
 351             QRect r;
 352             for (int i=0; i<(int)n; i++) {
 353                 s >> r;
 354                 rgn = rgn.united(QRegion(r));
 355             }
 356         }
 357     }
 358     *this = rgn;
 359 }
 360
 361
 362 /*****************************************************************************
 363   QRegion stream functions
 364  *****************************************************************************/
 365
 366 /*!
 367     \fn QRegion &QRegion::operator=(const QRegion &r)
 368
 369     Assigns \a r to this region and returns a reference to the region.
 370 */
 371
 372 /*!
 373     \fn void QRegion::swap(QRegion &other)
 374     \since 4.8
 375
 376     Swaps region \a other with this region. This operation is very
 377     fast and never fails.
 378 */
 379
 380 /*!
 381     \relates QRegion
 382
 383     Writes the region \a r to the stream \a s and returns a reference
 384     to the stream.
 385
 386     \sa \link datastreamformat.html Format of the QDataStream operators \endlink
 387 */
 388
 389 QDataStream &operator<<(QDataStream &s, const QRegion &r)
 390 {
 391     QVector<QRect> a = r.rects();
 392     if (a.isEmpty()) {
 393         s << (quint32)0;
 394     } else {
 395         if (s.version() == 1) {
 396             int i;
 397             for (i = a.size() - 1; i > 0; --i) {
 398                 s << (quint32)(12 + i * 24);
 399                 s << (int)QRGN_OR;
 400             }
 401             for (i = 0; i < a.size(); ++i) {
 402                 s << (quint32)(4+8) << (int)QRGN_SETRECT << a[i];
 403             }
 404         } else {
 405             s << (quint32)(4 + 4 + 16 * a.size()); // 16: storage size of QRect
 406             s << (qint32)QRGN_RECTS;
 407             s << a;
 408         }
 409     }
 410     return s;
 411 }
 412
 413 /*!
 414     \relates QRegion
 415
 416     Reads a region from the stream \a s into \a r and returns a
 417     reference to the stream.
 418
 419     \sa \link datastreamformat.html Format of the QDataStream operators \endlink
 420 */
 421
 422 QDataStream &operator>>(QDataStream &s, QRegion &r)
 423 {
 424     QByteArray b;
 425     s >> b;
 426     r.exec(b, s.version(), s.byteOrder());
 427     return s;
 428 }
 429 #endif //QT_NO_DATASTREAM
 430
 431 #ifndef QT_NO_DEBUG_STREAM
 432 QDebug operator<<(QDebug s, const QRegion &r)
 433 {
 434     QVector<QRect> rects = r.rects();
 435     s.nospace() << "QRegion(size=" << rects.size() << "), "
 436                 << "bounds = " << r.boundingRect() << '\n';
 437     for (int i=0; i<rects.size(); ++i)
 438         s << "- " << i << rects.at(i) << '\n';
 439     return s;
 440 }
 441 #endif
 442
 443
 444 // These are not inline - they can be implemented better on some platforms
 445 //  (eg. Windows at least provides 3-variable operations).  For now, simple.
 446
 447
 448 /*!
 449     Applies the united() function to this region and \a r. \c r1|r2 is
 450     equivalent to \c r1.united(r2).
 451
 452     \sa united(), operator+()
 453 */
 454 const QRegion QRegion::operator|(const QRegion &r) const
 455     { return united(r); }
 456
 457 /*!
 458     Applies the united() function to this region and \a r. \c r1+r2 is
 459     equivalent to \c r1.united(r2).
 460
 461     \sa united(), operator|()
 462 */
 463 const QRegion QRegion::operator+(const QRegion &r) const
 464     { return united(r); }
 465
 466 /*!
 467    \overload
 468    \since 4.4
 469  */
 470 const QRegion QRegion::operator+(const QRect &r) const
 471     { return united(r); }
 472
 473 /*!
 474     Applies the intersected() function to this region and \a r. \c r1&r2
 475     is equivalent to \c r1.intersected(r2).
 476
 477     \sa intersected()
 478 */
 479 const QRegion QRegion::operator&(const QRegion &r) const
 480     { return intersected(r); }
 481
 482 /*!
 483    \overload
 484    \since 4.4
 485  */
 486 const QRegion QRegion::operator&(const QRect &r) const
 487 {
 488     return intersected(r);
 489 }
 490
 491 /*!
 492     Applies the subtracted() function to this region and \a r. \c r1-r2
 493     is equivalent to \c r1.subtracted(r2).
 494
 495     \sa subtracted()
 496 */
 497 const QRegion QRegion::operator-(const QRegion &r) const
 498     { return subtracted(r); }
 499
 500 /*!
 501     Applies the xored() function to this region and \a r. \c r1^r2 is
 502     equivalent to \c r1.xored(r2).
 503
 504     \sa xored()
 505 */
 506 const QRegion QRegion::operator^(const QRegion &r) const
 507     { return xored(r); }
 508
 509 /*!
 510     Applies the united() function to this region and \a r and assigns
 511     the result to this region. \c r1|=r2 is equivalent to \c
 512     {r1 = r1.united(r2)}.
 513
 514     \sa united()
 515 */
 516 QRegion& QRegion::operator|=(const QRegion &r)
 517     { return *this = *this | r; }
 518
 519 /*!
 520     \fn QRegion& QRegion::operator+=(const QRect &rect)
 521
 522     Returns a region that is the union of this region with the specified \a rect.
 523
 524     \sa united()
 525 */
 526 /*!
 527     \fn QRegion& QRegion::operator+=(const QRegion &r)
 528
 529     Applies the united() function to this region and \a r and assigns
 530     the result to this region. \c r1+=r2 is equivalent to \c
 531     {r1 = r1.united(r2)}.
 532
 533     \sa intersected()
 534 */
 535 #if !defined (Q_OS_UNIX) && !defined (Q_OS_WIN)
 536 QRegion& QRegion::operator+=(const QRect &r)
 537 {
 538     return operator+=(QRegion(r));
 539 }
 540 #endif
 541
 542 /*!
 543   \fn QRegion& QRegion::operator&=(const QRegion &r)
 544
 545   Applies the intersected() function to this region and \a r and
 546   assigns the result to this region. \c r1&=r2 is equivalent to \c
 547   r1 = r1.intersected(r2).
 548
 549   \sa intersected()
 550 */
 551 QRegion& QRegion::operator&=(const QRegion &r)
 552     { return *this = *this & r; }
 553
 554 /*!
 555    \overload
 556    \since 4.4
 557  */
 558 #if defined (Q_OS_UNIX) || defined (Q_OS_WIN)
 559 QRegion& QRegion::operator&=(const QRect &r)
 560 {
 561     return *this = *this & r;
 562 }
 563 #else
 564 QRegion& QRegion::operator&=(const QRect &r)
 565 {
 566     return *this &= (QRegion(r));
 567 }
 568 #endif
 569
 570 /*!
 571   \fn QRegion& QRegion::operator-=(const QRegion &r)
 572
 573   Applies the subtracted() function to this region and \a r and
 574   assigns the result to this region. \c r1-=r2 is equivalent to \c
 575   {r1 = r1.subtracted(r2)}.
 576
 577   \sa subtracted()
 578 */
 579 QRegion& QRegion::operator-=(const QRegion &r)
 580     { return *this = *this - r; }
 581
 582 /*!
 583     Applies the xored() function to this region and \a r and
 584     assigns the result to this region. \c r1^=r2 is equivalent to \c
 585     {r1 = r1.xored(r2)}.
 586
 587     \sa xored()
 588 */
 589 QRegion& QRegion::operator^=(const QRegion &r)
 590     { return *this = *this ^ r; }
 591
 592 /*!
 593     \fn bool QRegion::operator!=(const QRegion &other) const
 594
 595     Returns true if this region is different from the \a other region;
 596     otherwise returns false.
 597 */
 598
 599 /*!
 600    Returns the region as a QVariant
 601 */
 602 QRegion::operator QVariant() const
 603 {
 604     return QVariant(QVariant::Region, this);
 605 }
 606
 607 /*!
 608     \fn bool QRegion::operator==(const QRegion &r) const
 609
 610     Returns true if the region is equal to \a r; otherwise returns
 611     false.
 612 */
 613
 614 /*!
 615     \fn void QRegion::translate(int dx, int dy)
 616
 617     Translates (moves) the region \a dx along the X axis and \a dy
 618     along the Y axis.
 619 */
 620
 621 /*!
 622     \fn QRegion QRegion::translated(const QPoint &p) const
 623     \overload
 624     \since 4.1
 625
 626     Returns a copy of the regtion that is translated \a{p}\e{.x()}
 627     along the x axis and \a{p}\e{.y()} along the y axis, relative to
 628     the current position.  Positive values move the rectangle to the
 629     right and down.
 630
 631     \sa translate()
 632 */
 633
 634 /*!
 635     \since 4.1
 636
 637     Returns a copy of the region that is translated \a dx along the
 638     x axis and \a dy along the y axis, relative to the current
 639     position. Positive values move the region to the right and
 640     down.
 641
 642     \sa translate()
 643 */
 644
 645 QRegion
 646 QRegion::translated(int dx, int dy) const
 647 {
 648     QRegion ret(*this);
 649     ret.translate(dx, dy);
 650     return ret;
 651 }
 652
 653
 654 inline bool rect_intersects(const QRect &r1, const QRect &r2)
 655 {
 656     return (r1.right() >= r2.left() && r1.left() <= r2.right() &&
 657             r1.bottom() >= r2.top() && r1.top() <= r2.bottom());
 658 }
 659
 660 /*!
 661     \since 4.2
 662
 663     Returns true if this region intersects with \a region, otherwise
 664     returns false.
 665 */
 666 bool QRegion::intersects(const QRegion &region) const
 667 {
 668     if (isEmpty() || region.isEmpty())
 669         return false;
 670
 671     if (!rect_intersects(boundingRect(), region.boundingRect()))
 672         return false;
 673     if (rectCount() == 1 && region.rectCount() == 1)
 674         return true;
 675
 676     const QVector<QRect> myRects = rects();
 677     const QVector<QRect> otherRects = region.rects();
 678
 679     for (QVector<QRect>::const_iterator i1 = myRects.constBegin(); i1 < myRects.constEnd(); ++i1)
 680         for (QVector<QRect>::const_iterator i2 = otherRects.constBegin(); i2 < otherRects.constEnd(); ++i2)
 681             if (rect_intersects(*i1, *i2))
 682                 return true;
 683     return false;
 684 }
 685
 686 /*!
 687     \fn bool QRegion::intersects(const QRect &rect) const
 688     \since 4.2
 689
 690     Returns true if this region intersects with \a rect, otherwise
 691     returns false.
 692 */
 693
 694
 695 #if !defined (Q_OS_UNIX) && !defined (Q_OS_WIN)
 696 /*!
 697     \overload
 698     \since 4.4
 699 */
 700 QRegion QRegion::intersect(const QRect &r) const
 701 {
 702     return intersect(QRegion(r));
 703 }
 704 #endif
 705
 706 /*!
 707     \obsolete
 708     \fn int QRegion::numRects() const
 709     \since 4.4
 710
 711     Returns the number of rectangles that will be returned in rects().
 712 */
 713
 714 /*!
 715     \fn int QRegion::rectCount() const
 716     \since 4.6
 717
 718     Returns the number of rectangles that will be returned in rects().
 719 */
 720
 721 /*!
 722     \fn bool QRegion::isEmpty() const
 723
 724     Returns true if the region is empty; otherwise returns false. An
 725     empty region is a region that contains no points.
 726
 727     Example:
 728     \snippet doc/src/snippets/code/src_gui_painting_qregion_unix.cpp 0
 729 */
 730
 731 /*!
 732     \fn bool QRegion::isNull() const
 733     \since 5.0
 734
 735     Returns true if the region is empty; otherwise returns false. An
 736     empty region is a region that contains no points. This function is
 737     the same as isEmpty
 738
 739     \sa isEmpty()
 740 */
 741
 742 /*!
 743     \fn bool QRegion::contains(const QPoint &p) const
 744
 745     Returns true if the region contains the point \a p; otherwise
 746     returns false.
 747 */
 748
 749 /*!
 750     \fn bool QRegion::contains(const QRect &r) const
 751     \overload
 752
 753     Returns true if the region overlaps the rectangle \a r; otherwise
 754     returns false.
 755 */
 756
 757 /*!
 758     \fn QRegion QRegion::unite(const QRegion &r) const
 759     \obsolete
 760
 761     Use united(\a r) instead.
 762 */
 763
 764 /*!
 765     \fn QRegion QRegion::unite(const QRect &rect) const
 766     \since 4.4
 767     \obsolete
 768
 769     Use united(\a rect) instead.
 770 */
 771
 772 /*!
 773     \fn QRegion QRegion::united(const QRect &rect) const
 774     \since 4.4
 775
 776     Returns a region which is the union of this region and the given \a rect.
 777
 778     \sa intersected(), subtracted(), xored()
 779 */
 780
 781 /*!
 782     \fn QRegion QRegion::united(const QRegion &r) const
 783     \since 4.2
 784
 785     Returns a region which is the union of this region and \a r.
 786
 787     \img runion.png Region Union
 788
 789     The figure shows the union of two elliptical regions.
 790
 791     \sa intersected(), subtracted(), xored()
 792 */
 793
 794 /*!
 795     \fn QRegion QRegion::intersect(const QRegion &r) const
 796     \obsolete
 797
 798     Use intersected(\a r) instead.
 799 */
 800
 801 /*!
 802     \fn QRegion QRegion::intersect(const QRect &rect) const
 803     \since 4.4
 804     \obsolete
 805
 806     Use intersected(\a rect) instead.
 807 */
 808
 809 /*!
 810     \fn QRegion QRegion::intersected(const QRect &rect) const
 811     \since 4.4
 812
 813     Returns a region which is the intersection of this region and the given \a rect.
 814
 815     \sa subtracted(), united(), xored()
 816 */
 817
 818 /*!
 819     \fn QRegion QRegion::intersected(const QRegion &r) const
 820     \since 4.2
 821
 822     Returns a region which is the intersection of this region and \a r.
 823
 824     \img rintersect.png Region Intersection
 825
 826     The figure shows the intersection of two elliptical regions.
 827
 828     \sa subtracted(), united(), xored()
 829 */
 830
 831 /*!
 832     \fn QRegion QRegion::subtract(const QRegion &r) const
 833     \obsolete
 834
 835     Use subtracted(\a r) instead.
 836 */
 837
 838 /*!
 839     \fn QRegion QRegion::subtracted(const QRegion &r) const
 840     \since 4.2
 841
 842     Returns a region which is \a r subtracted from this region.
 843
 844     \img rsubtract.png Region Subtraction
 845
 846     The figure shows the result when the ellipse on the right is
 847     subtracted from the ellipse on the left (\c {left - right}).
 848
 849     \sa intersected(), united(), xored()
 850 */
 851
 852 /*!
 853     \fn QRegion QRegion::eor(const QRegion &r) const
 854     \obsolete
 855
 856     Use xored(\a r) instead.
 857 */
 858
 859 /*!
 860     \fn QRegion QRegion::xored(const QRegion &r) const
 861     \since 4.2
 862
 863     Returns a region which is the exclusive or (XOR) of this region
 864     and \a r.
 865
 866     \img rxor.png Region XORed
 867
 868     The figure shows the exclusive or of two elliptical regions.
 869
 870     \sa intersected(), united(), subtracted()
 871 */
 872
 873 /*!
 874     \fn QRect QRegion::boundingRect() const
 875
 876     Returns the bounding rectangle of this region. An empty region
 877     gives a rectangle that is QRect::isNull().
 878 */
 879
 880 /*!
 881     \fn QVector<QRect> QRegion::rects() const
 882
 883     Returns an array of non-overlapping rectangles that make up the
 884     region.
 885
 886     The union of all the rectangles is equal to the original region.
 887 */
 888
 889 /*!
 890     \fn void QRegion::setRects(const QRect *rects, int number)
 891
 892     Sets the region using the array of rectangles specified by \a rects and
 893     \a number.
 894     The rectangles \e must be optimally Y-X sorted and follow these restrictions:
 895
 896     \list
 897     \o The rectangles must not intersect.
 898     \o All rectangles with a given top coordinate must have the same height.
 899     \o No two rectangles may abut horizontally (they should be combined
 900        into a single wider rectangle in that case).
 901     \o The rectangles must be sorted in ascending order, with Y as the major
 902        sort key and X as the minor sort key.
 903     \endlist
 904     \omit
 905     Only some platforms have these restrictions (Qt for Embedded Linux, X11 and Mac OS X).
 906     \endomit
 907 */
 908
 909 namespace {
 910
 911 struct Segment
 912 {
 913     Segment() {}
 914     Segment(const QPoint &p)
 915         : added(false)
 916         , point(p)
 917     {
 918     }
 919
 920     int left() const
 921     {
 922         return qMin(point.x(), next->point.x());
 923     }
 924
 925     int right() const
 926     {
 927         return qMax(point.x(), next->point.x());
 928     }
 929
 930     bool overlaps(const Segment &other) const
 931     {
 932         return left() < other.right() && other.left() < right();
 933     }
 934
 935     void connect(Segment &other)
 936     {
 937         next = &other;
 938         other.prev = this;
 939
 940         horizontal = (point.y() == other.point.y());
 941     }
 942
 943     void merge(Segment &other)
 944     {
 945         if (right() <= other.right()) {
 946             QPoint p = other.point;
 947             Segment *oprev = other.prev;
 948
 949             other.point = point;
 950             other.prev = prev;
 951             prev->next = &other;
 952
 953             point = p;
 954             prev = oprev;
 955             oprev->next = this;
 956         } else {
 957             Segment *onext = other.next;
 958             other.next = next;
 959             next->prev = &other;
 960
 961             next = onext;
 962             next->prev = this;
 963         }
 964     }
 965
 966     int horizontal : 1;
 967     int added : 1;
 968
 969     QPoint point;
 970     Segment *prev;
 971     Segment *next;
 972 };
 973
 974 void mergeSegments(Segment *a, int na, Segment *b, int nb)
 975 {
 976     int i = 0;
 977     int j = 0;
 978
 979     while (i != na && j != nb) {
 980         Segment &sa = a[i];
 981         Segment &sb = b[j];
 982         const int ra = sa.right();
 983         const int rb = sb.right();
 984         if (sa.overlaps(sb))
 985             sa.merge(sb);
 986         i += (rb >= ra);
 987         j += (ra >= rb);
 988     }
 989 }
 990
 991 void addSegmentsToPath(Segment *segment, QPainterPath &path)
 992 {
 993     Segment *current = segment;
 994     path.moveTo(current->point);
 995
 996     current->added = true;
 997
 998     Segment *last = current;
 999     current = current->next;
1000     while (current != segment) {
1001         if (current->horizontal != last->horizontal)
1002             path.lineTo(current->point);
1003         current->added = true;
1004         last = current;
1005         current = current->next;
1006     }
1007 }
1008
1009 }
1010
1011 Q_GUI_EXPORT QPainterPath qt_regionToPath(const QRegion &region)
1012 {
1013     QPainterPath result;
1014     if (region.rectCount() == 1) {
1015         result.addRect(region.boundingRect());
1016         return result;
1017     }
1018
1019     const QVector<QRect> rects = region.rects();
1020
1021     QVarLengthArray<Segment> segments;
1022     segments.resize(4 * rects.size());
1023
1024     const QRect *rect = rects.constData();
1025     const QRect *end = rect + rects.size();
1026
1027     int lastRowSegmentCount = 0;
1028     Segment *lastRowSegments = 0;
1029
1030     int lastSegment = 0;
1031     int lastY = 0;
1032     while (rect != end) {
1033         const int y = rect[0].y();
1034         int count = 0;
1035         while (&rect[count] != end && rect[count].y() == y)
1036             ++count;
1037
1038         for (int i = 0; i < count; ++i) {
1039             int offset = lastSegment + i;
1040             segments[offset] = Segment(rect[i].topLeft());
1041             segments[offset += count] = Segment(rect[i].topRight() + QPoint(1, 0));
1042             segments[offset += count] = Segment(rect[i].bottomRight() + QPoint(1, 1));
1043             segments[offset += count] = Segment(rect[i].bottomLeft() + QPoint(0, 1));
1044
1045             offset = lastSegment + i;
1046             for (int j = 0; j < 4; ++j)
1047                 segments[offset + j * count].connect(segments[offset + ((j + 1) % 4) * count]);
1048         }
1049
1050         if (lastRowSegments && lastY == y)
1051             mergeSegments(lastRowSegments, lastRowSegmentCount, &segments[lastSegment], count);
1052
1053         lastRowSegments = &segments[lastSegment + 2 * count];
1054         lastRowSegmentCount = count;
1055         lastSegment += 4 * count;
1056         lastY = y + rect[0].height();
1057         rect += count;
1058     }
1059
1060     for (int i = 0; i < lastSegment; ++i) {
1061         Segment *segment = &segments[i];
1062         if (!segment->added)
1063             addSegmentsToPath(segment, result);
1064     }
1065
1066     return result;
1067 }
1068
1069 #if defined(Q_OS_UNIX) || defined(Q_OS_WIN)
1070
1071 //#define QT_REGION_DEBUG
1072 /*
1073  *   clip region
1074  */
1075
1076 struct QRegionPrivate {
1077     int numRects;
1078     QVector<QRect> rects;
1079     QRect extents;
1080     QRect innerRect;
1081     int innerArea;
1082
1083     inline QRegionPrivate() : numRects(0), innerArea(-1) {}
1084     inline QRegionPrivate(const QRect &r) {
1085         numRects = 1;
1086         extents = r;
1087         innerRect = r;
1088         innerArea = r.width() * r.height();
1089     }
1090
1091     inline QRegionPrivate(const QRegionPrivate &r) {
1092         rects = r.rects;
1093         numRects = r.numRects;
1094         extents = r.extents;
1095         innerRect = r.innerRect;
1096         innerArea = r.innerArea;
1097     }
1098
1099     inline QRegionPrivate &operator=(const QRegionPrivate &r) {
1100         rects = r.rects;
1101         numRects = r.numRects;
1102         extents = r.extents;
1103         innerRect = r.innerRect;
1104         innerArea = r.innerArea;
1105         return *this;
1106     }
1107
1108     void intersect(const QRect &r);
1109
1110     /*
1111      * Returns true if r is guaranteed to be fully contained in this region.
1112      * A false return value does not guarantee the opposite.
1113      */
1114     inline bool contains(const QRegionPrivate &r) const {
1115         return contains(r.extents);
1116     }
1117
1118     inline bool contains(const QRect &r2) const {
1119         const QRect &r1 = innerRect;
1120         return r2.left() >= r1.left() && r2.right() <= r1.right()
1121             && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
1122     }
1123
1124     /*
1125      * Returns true if this region is guaranteed to be fully contained in r.
1126      */
1127     inline bool within(const QRect &r1) const {
1128         const QRect &r2 = extents;
1129         return r2.left() >= r1.left() && r2.right() <= r1.right()
1130             && r2.top() >= r1.top() && r2.bottom() <= r1.bottom();
1131     }
1132
1133     inline void updateInnerRect(const QRect &rect) {
1134         const int area = rect.width() * rect.height();
1135         if (area > innerArea) {
1136             innerArea = area;
1137             innerRect = rect;
1138         }
1139     }
1140
1141     inline void vectorize() {
1142         if (numRects == 1) {
1143             if (!rects.size())
1144                 rects.resize(1);
1145             rects[0] = extents;
1146         }
1147     }
1148
1149     inline void append(const QRect *r);
1150     void append(const QRegionPrivate *r);
1151     void prepend(const QRect *r);
1152     void prepend(const QRegionPrivate *r);
1153     inline bool canAppend(const QRect *r) const;
1154     inline bool canAppend(const QRegionPrivate *r) const;
1155     inline bool canPrepend(const QRect *r) const;
1156     inline bool canPrepend(const QRegionPrivate *r) const;
1157
1158     inline bool mergeFromRight(QRect *left, const QRect *right);
1159     inline bool mergeFromLeft(QRect *left, const QRect *right);
1160     inline bool mergeFromBelow(QRect *top, const QRect *bottom,
1161                                const QRect *nextToTop,
1162                                const QRect *nextToBottom);
1163     inline bool mergeFromAbove(QRect *bottom, const QRect *top,
1164                                const QRect *nextToBottom,
1165                                const QRect *nextToTop);
1166
1167 #ifdef QT_REGION_DEBUG
1168     void selfTest() const;
1169 #endif
1170 };
1171
1172 static inline bool isEmptyHelper(const QRegionPrivate *preg)
1173 {
1174     return !preg || preg->numRects == 0;
1175 }
1176
1177 static inline bool canMergeFromRight(const QRect *left, const QRect *right)
1178 {
1179     return (right->top() == left->top()
1180             && right->bottom() == left->bottom()
1181             && right->left() <= (left->right() + 1));
1182 }
1183
1184 static inline bool canMergeFromLeft(const QRect *right, const QRect *left)
1185 {
1186     return canMergeFromRight(left, right);
1187 }
1188
1189 bool QRegionPrivate::mergeFromRight(QRect *left, const QRect *right)
1190 {
1191     if (canMergeFromRight(left, right)) {
1192         left->setRight(right->right());
1193         updateInnerRect(*left);
1194         return true;
1195     }
1196     return false;
1197 }
1198
1199 bool QRegionPrivate::mergeFromLeft(QRect *right, const QRect *left)
1200 {
1201     if (canMergeFromLeft(right, left)) {
1202         right->setLeft(left->left());
1203         updateInnerRect(*right);
1204         return true;
1205     }
1206     return false;
1207 }
1208
1209 static inline bool canMergeFromBelow(const QRect *top, const QRect *bottom,
1210                                      const QRect *nextToTop,
1211                                      const QRect *nextToBottom)
1212 {
1213     if (nextToTop && nextToTop->y() == top->y())
1214         return false;
1215     if (nextToBottom && nextToBottom->y() == bottom->y())
1216         return false;
1217
1218     return ((top->bottom() >= (bottom->top() - 1))
1219             && top->left() == bottom->left()
1220             && top->right() == bottom->right());
1221 }
1222
1223 bool QRegionPrivate::mergeFromBelow(QRect *top, const QRect *bottom,
1224                                     const QRect *nextToTop,
1225                                     const QRect *nextToBottom)
1226 {
1227     if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) {
1228         top->setBottom(bottom->bottom());
1229         updateInnerRect(*top);
1230         return true;
1231     }
1232     return false;
1233 }
1234
1235 bool QRegionPrivate::mergeFromAbove(QRect *bottom, const QRect *top,
1236                                     const QRect *nextToBottom,
1237                                     const QRect *nextToTop)
1238 {
1239     if (canMergeFromBelow(top, bottom, nextToTop, nextToBottom)) {
1240         bottom->setTop(top->top());
1241         updateInnerRect(*bottom);
1242         return true;
1243     }
1244     return false;
1245 }
1246
1247 static inline QRect qt_rect_intersect_normalized(const QRect &r1,
1248                                                  const QRect &r2)
1249 {
1250     QRect r;
1251     r.setLeft(qMax(r1.left(), r2.left()));
1252     r.setRight(qMin(r1.right(), r2.right()));
1253     r.setTop(qMax(r1.top(), r2.top()));
1254     r.setBottom(qMin(r1.bottom(), r2.bottom()));
1255     return r;
1256 }
1257
1258 void QRegionPrivate::intersect(const QRect &rect)
1259 {
1260     Q_ASSERT(extents.intersects(rect));
1261     Q_ASSERT(numRects > 1);
1262
1263 #ifdef QT_REGION_DEBUG
1264     selfTest();
1265 #endif
1266
1267     const QRect r = rect.normalized();
1268     extents = QRect();
1269     innerRect = QRect();
1270     innerArea = -1;
1271
1272     QRect *dest = rects.data();
1273     const QRect *src = dest;
1274     int n = numRects;
1275     numRects = 0;
1276     while (n--) {
1277         *dest = qt_rect_intersect_normalized(*src++, r);
1278         if (dest->isEmpty())
1279             continue;
1280
1281         if (numRects == 0) {
1282             extents = *dest;
1283         } else {
1284             extents.setLeft(qMin(extents.left(), dest->left()));
1285             // hw: extents.top() will never change after initialization
1286             //extents.setTop(qMin(extents.top(), dest->top()));
1287             extents.setRight(qMax(extents.right(), dest->right()));
1288             extents.setBottom(qMax(extents.bottom(), dest->bottom()));
1289
1290             const QRect *nextToLast = (numRects > 1 ? dest - 2 : 0);
1291
1292             // mergeFromBelow inlined and optimized
1293             if (canMergeFromBelow(dest - 1, dest, nextToLast, 0)) {
1294                 if (!n || src->y() != dest->y() || src->left() > r.right()) {
1295                     QRect *prev = dest - 1;
1296                     prev->setBottom(dest->bottom());
1297                     updateInnerRect(*prev);
1298                     continue;
1299                 }
1300             }
1301         }
1302         updateInnerRect(*dest);
1303         ++dest;
1304         ++numRects;
1305     }
1306 #ifdef QT_REGION_DEBUG
1307     selfTest();
1308 #endif
1309 }
1310
1311 void QRegionPrivate::append(const QRect *r)
1312 {
1313     Q_ASSERT(!r->isEmpty());
1314
1315     QRect *myLast = (numRects == 1 ? &extents : rects.data() + (numRects - 1));
1316     if (mergeFromRight(myLast, r)) {
1317         if (numRects > 1) {
1318             const QRect *nextToTop = (numRects > 2 ? myLast - 2 : 0);
1319             if (mergeFromBelow(myLast - 1, myLast, nextToTop, 0))
1320                 --numRects;
1321         }
1322     } else if (mergeFromBelow(myLast, r, (numRects > 1 ? myLast - 1 : 0), 0)) {
1323         // nothing
1324     } else {
1325         vectorize();
1326         ++numRects;
1327         updateInnerRect(*r);
1328         if (rects.size() < numRects)
1329             rects.resize(numRects);
1330         rects[numRects - 1] = *r;
1331     }
1332     extents.setCoords(qMin(extents.left(), r->left()),
1333                       qMin(extents.top(), r->top()),
1334                       qMax(extents.right(), r->right()),
1335                       qMax(extents.bottom(), r->bottom()));
1336
1337 #ifdef QT_REGION_DEBUG
1338     selfTest();
1339 #endif
1340 }
1341
1342 void QRegionPrivate::append(const QRegionPrivate *r)
1343 {
1344     Q_ASSERT(!isEmptyHelper(r));
1345
1346     if (r->numRects == 1) {
1347         append(&r->extents);
1348         return;
1349     }
1350
1351     vectorize();
1352
1353     QRect *destRect = rects.data() + numRects;
1354     const QRect *srcRect = r->rects.constData();
1355     int numAppend = r->numRects;
1356
1357     // try merging
1358     {
1359         const QRect *rFirst = srcRect;
1360         QRect *myLast = destRect - 1;
1361         const QRect *nextToLast = (numRects > 1 ? myLast - 1 : 0);
1362         if (mergeFromRight(myLast, rFirst)) {
1363             ++srcRect;
1364             --numAppend;
1365             const QRect *rNextToFirst = (numAppend > 1 ? rFirst + 2 : 0);
1366             if (mergeFromBelow(myLast, rFirst + 1, nextToLast, rNextToFirst)) {
1367                 ++srcRect;
1368                 --numAppend;
1369             }
1370             if (numRects  > 1) {
1371                 nextToLast = (numRects > 2 ? myLast - 2 : 0);
1372                 rNextToFirst = (numAppend > 0 ? srcRect : 0);
1373                 if (mergeFromBelow(myLast - 1, myLast, nextToLast, rNextToFirst)) {
1374                     --destRect;
1375                     --numRects;
1376                 }
1377             }
1378         } else if (mergeFromBelow(myLast, rFirst, nextToLast, rFirst + 1)) {
1379             ++srcRect;
1380             --numAppend;
1381         }
1382     }
1383
1384     // append rectangles
1385     if (numAppend > 0) {
1386         const int newNumRects = numRects + numAppend;
1387         if (newNumRects > rects.size()) {
1388             rects.resize(newNumRects);
1389             destRect = rects.data() + numRects;
1390         }
1391         memcpy(destRect, srcRect, numAppend * sizeof(QRect));
1392
1393         numRects = newNumRects;
1394     }
1395
1396     // update inner rectangle
1397     if (innerArea < r->innerArea) {
1398         innerArea = r->innerArea;
1399         innerRect = r->innerRect;
1400     }
1401
1402     // update extents
1403     destRect = &extents;
1404     srcRect = &r->extents;
1405     extents.setCoords(qMin(destRect->left(), srcRect->left()),
1406                       qMin(destRect->top(), srcRect->top()),
1407                       qMax(destRect->right(), srcRect->right()),
1408                       qMax(destRect->bottom(), srcRect->bottom()));
1409
1410 #ifdef QT_REGION_DEBUG
1411     selfTest();
1412 #endif
1413 }
1414
1415 void QRegionPrivate::prepend(const QRegionPrivate *r)
1416 {
1417     Q_ASSERT(!isEmptyHelper(r));
1418
1419     if (r->numRects == 1) {
1420         prepend(&r->extents);
1421         return;
1422     }
1423
1424     vectorize();
1425
1426     int numPrepend = r->numRects;
1427     int numSkip = 0;
1428
1429     // try merging
1430     {
1431         QRect *myFirst = rects.data();
1432         const QRect *nextToFirst = (numRects > 1 ? myFirst + 1 : 0);
1433         const QRect *rLast = r->rects.constData() + r->numRects - 1;
1434         const QRect *rNextToLast = (r->numRects > 1 ? rLast - 1 : 0);
1435         if (mergeFromLeft(myFirst, rLast)) {
1436             --numPrepend;
1437             --rLast;
1438             rNextToLast = (numPrepend > 1 ? rLast - 1 : 0);
1439             if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) {
1440                 --numPrepend;
1441                 --rLast;
1442             }
1443             if (numRects  > 1) {
1444                 nextToFirst = (numRects > 2? myFirst + 2 : 0);
1445                 rNextToLast = (numPrepend > 0 ? rLast : 0);
1446                 if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, rNextToLast)) {
1447                     --numRects;
1448                     ++numSkip;
1449                 }
1450             }
1451         } else if (mergeFromAbove(myFirst, rLast, nextToFirst, rNextToLast)) {
1452             --numPrepend;
1453         }
1454     }
1455
1456     if (numPrepend > 0) {
1457         const int newNumRects = numRects + numPrepend;
1458         if (newNumRects > rects.size())
1459             rects.resize(newNumRects);
1460
1461         // move existing rectangles
1462         memmove(rects.data() + numPrepend, rects.constData() + numSkip,
1463                 numRects * sizeof(QRect));
1464
1465         // prepend new rectangles
1466         memcpy(rects.data(), r->rects.constData(), numPrepend * sizeof(QRect));
1467
1468         numRects = newNumRects;
1469     }
1470
1471     // update inner rectangle
1472     if (innerArea < r->innerArea) {
1473         innerArea = r->innerArea;
1474         innerRect = r->innerRect;
1475     }
1476
1477     // update extents
1478     extents.setCoords(qMin(extents.left(), r->extents.left()),
1479                       qMin(extents.top(), r->extents.top()),
1480                       qMax(extents.right(), r->extents.right()),
1481                       qMax(extents.bottom(), r->extents.bottom()));
1482
1483 #ifdef QT_REGION_DEBUG
1484     selfTest();
1485 #endif
1486 }
1487
1488 void QRegionPrivate::prepend(const QRect *r)
1489 {
1490     Q_ASSERT(!r->isEmpty());
1491
1492     QRect *myFirst = (numRects == 1 ? &extents : rects.data());
1493     if (mergeFromLeft(myFirst, r)) {
1494         if (numRects > 1) {
1495             const QRect *nextToFirst = (numRects > 2 ? myFirst + 2 : 0);
1496             if (mergeFromAbove(myFirst + 1, myFirst, nextToFirst, 0)) {
1497                 --numRects;
1498                 memmove(rects.data(), rects.constData() + 1,
1499                         numRects * sizeof(QRect));
1500             }
1501         }
1502     } else if (mergeFromAbove(myFirst, r, (numRects > 1 ? myFirst + 1 : 0), 0)) {
1503         // nothing
1504     } else {
1505         vectorize();
1506         ++numRects;
1507         updateInnerRect(*r);
1508         rects.prepend(*r);
1509     }
1510     extents.setCoords(qMin(extents.left(), r->left()),
1511                       qMin(extents.top(), r->top()),
1512                       qMax(extents.right(), r->right()),
1513                       qMax(extents.bottom(), r->bottom()));
1514
1515 #ifdef QT_REGION_DEBUG
1516     selfTest();
1517 #endif
1518 }
1519
1520 bool QRegionPrivate::canAppend(const QRect *r) const
1521 {
1522     Q_ASSERT(!r->isEmpty());
1523
1524     const QRect *myLast = (numRects == 1) ? &extents : (rects.constData() + (numRects - 1));
1525     if (r->top() > myLast->bottom())
1526         return true;
1527     if (r->top() == myLast->top()
1528         && r->height() == myLast->height()
1529         && r->left() > myLast->right())
1530     {
1531         return true;
1532     }
1533
1534     return false;
1535 }
1536
1537 bool QRegionPrivate::canAppend(const QRegionPrivate *r) const
1538 {
1539     return canAppend(r->numRects == 1 ? &r->extents : r->rects.constData());
1540 }
1541
1542 bool QRegionPrivate::canPrepend(const QRect *r) const
1543 {
1544     Q_ASSERT(!r->isEmpty());
1545
1546     const QRect *myFirst = (numRects == 1) ? &extents : rects.constData();
1547     if (r->bottom() < myFirst->top()) // not overlapping
1548         return true;
1549     if (r->top() == myFirst->top()
1550         && r->height() == myFirst->height()
1551         && r->right() < myFirst->left())
1552     {
1553         return true;
1554     }
1555
1556     return false;
1557 }
1558
1559 bool QRegionPrivate::canPrepend(const QRegionPrivate *r) const
1560 {
1561     return canPrepend(r->numRects == 1 ? &r->extents : r->rects.constData() + r->numRects - 1);
1562 }
1563
1564 #ifdef QT_REGION_DEBUG
1565 void QRegionPrivate::selfTest() const
1566 {
1567     if (numRects == 0) {
1568         Q_ASSERT(extents.isEmpty());
1569         Q_ASSERT(innerRect.isEmpty());
1570         return;
1571     }
1572
1573     Q_ASSERT(innerArea == (innerRect.width() * innerRect.height()));
1574
1575     if (numRects == 1) {
1576         Q_ASSERT(innerRect == extents);
1577         Q_ASSERT(!innerRect.isEmpty());
1578         return;
1579     }
1580
1581     for (int i = 0; i < numRects; ++i) {
1582         const QRect r = rects.at(i);
1583         if ((r.width() * r.height()) > innerArea)
1584             qDebug() << "selfTest(): innerRect" << innerRect << '<' << r;
1585     }
1586
1587     QRect r = rects.first();
1588     for (int i = 1; i < numRects; ++i) {
1589         const QRect r2 = rects.at(i);
1590         Q_ASSERT(!r2.isEmpty());
1591         if (r2.y() == r.y()) {
1592             Q_ASSERT(r.bottom() == r2.bottom());
1593             Q_ASSERT(r.right() < (r2.left() + 1));
1594         } else {
1595             Q_ASSERT(r2.y() >= r.bottom());
1596         }
1597         r = r2;
1598     }
1599 }
1600 #endif // QT_REGION_DEBUG
1601
1602 static QRegionPrivate qrp;
1603 QRegion::QRegionData QRegion::shared_empty = {Q_BASIC_ATOMIC_INITIALIZER(1), &qrp};
1604
1605 typedef void (*OverlapFunc)(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1606                             register const QRect *r2, const QRect *r2End, register int y1, register int y2);
1607 typedef void (*NonOverlapFunc)(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
1608                                register int y1, register int y2);
1609
1610 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2);
1611 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest);
1612 static void miRegionOp(register QRegionPrivate &dest, const QRegionPrivate *reg1, const QRegionPrivate *reg2,
1613                        OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
1614                        NonOverlapFunc nonOverlap2Func);
1615
1616 #define RectangleOut 0
1617 #define RectangleIn 1
1618 #define RectanglePart 2
1619 #define EvenOddRule 0
1620 #define WindingRule 1
1621
1622 // START OF region.h extract
1623 /* $XConsortium: region.h,v 11.14 94/04/17 20:22:20 rws Exp $ */
1624 /************************************************************************
1625
1626 Copyright (c) 1987  X Consortium
1627
1628 Permission is hereby granted, free of charge, to any person obtaining a copy
1629 of this software and associated documentation files (the "Software"), to deal
1630 in the Software without restriction, including without limitation the rights
1631 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1632 copies of the Software, and to permit persons to whom the Software is
1633 furnished to do so, subject to the following conditions:
1634
1635 The above copyright notice and this permission notice shall be included in
1636 all copies or substantial portions of the Software.
1637
1638 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1639 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1640 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
1641 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1642 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1643 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1644
1645 Except as contained in this notice, the name of the X Consortium shall not be
1646 used in advertising or otherwise to promote the sale, use or other dealings
1647 in this Software without prior written authorization from the X Consortium.
1648
1649
1650 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
1651
1652                         All Rights Reserved
1653
1654 Permission to use, copy, modify, and distribute this software and its
1655 documentation for any purpose and without fee is hereby granted,
1656 provided that the above copyright notice appear in all copies and that
1657 both that copyright notice and this permission notice appear in
1658 supporting documentation, and that the name of Digital not be
1659 used in advertising or publicity pertaining to distribution of the
1660 software without specific, written prior permission.
1661
1662 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1663 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1664 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1665 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1666 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1667 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1668 SOFTWARE.
1669
1670 ************************************************************************/
1671
1672 #ifndef _XREGION_H
1673 #define _XREGION_H
1674
1675 QT_BEGIN_INCLUDE_NAMESPACE
1676 #include <limits.h>
1677 QT_END_INCLUDE_NAMESPACE
1678
1679 /*  1 if two BOXes overlap.
1680  *  0 if two BOXes do not overlap.
1681  *  Remember, x2 and y2 are not in the region
1682  */
1683 #define EXTENTCHECK(r1, r2) \
1684         ((r1)->right() >= (r2)->left() && \
1685          (r1)->left() <= (r2)->right() && \
1686          (r1)->bottom() >= (r2)->top() && \
1687          (r1)->top() <= (r2)->bottom())
1688
1689 /*
1690  *  update region extents
1691  */
1692 #define EXTENTS(r,idRect){\
1693             if((r)->left() < (idRect)->extents.left())\
1694               (idRect)->extents.setLeft((r)->left());\
1695             if((r)->top() < (idRect)->extents.top())\
1696               (idRect)->extents.setTop((r)->top());\
1697             if((r)->right() > (idRect)->extents.right())\
1698               (idRect)->extents.setRight((r)->right());\
1699             if((r)->bottom() > (idRect)->extents.bottom())\
1700               (idRect)->extents.setBottom((r)->bottom());\
1701         }
1702
1703 /*
1704  *   Check to see if there is enough memory in the present region.
1705  */
1706 #define MEMCHECK(dest, rect, firstrect){\
1707         if ((dest).numRects >= ((dest).rects.size()-1)){\
1708           firstrect.resize(firstrect.size() * 2); \
1709           (rect) = (firstrect).data() + (dest).numRects;\
1710         }\
1711       }
1712
1713
1714 /*
1715  * number of points to buffer before sending them off
1716  * to scanlines(): Must be an even number
1717  */
1718 #define NUMPTSTOBUFFER 200
1719
1720 /*
1721  * used to allocate buffers for points and link
1722  * the buffers together
1723  */
1724 typedef struct _POINTBLOCK {
1725     int data[NUMPTSTOBUFFER * sizeof(QPoint)];
1726     QPoint *pts;
1727     struct _POINTBLOCK *next;
1728 } POINTBLOCK;
1729
1730 #endif
1731 // END OF region.h extract
1732
1733 // START OF Region.c extract
1734 /* $XConsortium: Region.c /main/30 1996/10/22 14:21:24 kaleb $ */
1735 /************************************************************************
1736
1737 Copyright (c) 1987, 1988  X Consortium
1738
1739 Permission is hereby granted, free of charge, to any person obtaining a copy
1740 of this software and associated documentation files (the "Software"), to deal
1741 in the Software without restriction, including without limitation the rights
1742 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
1743 copies of the Software, and to permit persons to whom the Software is
1744 furnished to do so, subject to the following conditions:
1745
1746 The above copyright notice and this permission notice shall be included in
1747 all copies or substantial portions of the Software.
1748
1749 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1750 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1751 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
1752 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
1753 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
1754 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1755
1756 Except as contained in this notice, the name of the X Consortium shall not be
1757 used in advertising or otherwise to promote the sale, use or other dealings
1758 in this Software without prior written authorization from the X Consortium.
1759
1760
1761 Copyright 1987, 1988 by Digital Equipment Corporation, Maynard, Massachusetts.
1762
1763                         All Rights Reserved
1764
1765 Permission to use, copy, modify, and distribute this software and its
1766 documentation for any purpose and without fee is hereby granted,
1767 provided that the above copyright notice appear in all copies and that
1768 both that copyright notice and this permission notice appear in
1769 supporting documentation, and that the name of Digital not be
1770 used in advertising or publicity pertaining to distribution of the
1771 software without specific, written prior permission.
1772
1773 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
1774 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
1775 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
1776 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
1777 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
1778 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
1779 SOFTWARE.
1780
1781 ************************************************************************/
1782 /*
1783  * The functions in this file implement the Region abstraction, similar to one
1784  * used in the X11 sample server. A Region is simply an area, as the name
1785  * implies, and is implemented as a "y-x-banded" array of rectangles. To
1786  * explain: Each Region is made up of a certain number of rectangles sorted
1787  * by y coordinate first, and then by x coordinate.
1788  *
1789  * Furthermore, the rectangles are banded such that every rectangle with a
1790  * given upper-left y coordinate (y1) will have the same lower-right y
1791  * coordinate (y2) and vice versa. If a rectangle has scanlines in a band, it
1792  * will span the entire vertical distance of the band. This means that some
1793  * areas that could be merged into a taller rectangle will be represented as
1794  * several shorter rectangles to account for shorter rectangles to its left
1795  * or right but within its "vertical scope".
1796  *
1797  * An added constraint on the rectangles is that they must cover as much
1798  * horizontal area as possible. E.g. no two rectangles in a band are allowed
1799  * to touch.
1800  *
1801  * Whenever possible, bands will be merged together to cover a greater vertical
1802  * distance (and thus reduce the number of rectangles). Two bands can be merged
1803  * only if the bottom of one touches the top of the other and they have
1804  * rectangles in the same places (of the same width, of course). This maintains
1805  * the y-x-banding that's so nice to have...
1806  */
1807 /* $XFree86: xc/lib/X11/Region.c,v 1.1.1.2.2.2 1998/10/04 15:22:50 hohndel Exp $ */
1808
1809 static void UnionRectWithRegion(register const QRect *rect, const QRegionPrivate *source,
1810                                 QRegionPrivate &dest)
1811 {
1812     if (rect->isEmpty())
1813         return;
1814
1815     Q_ASSERT(EqualRegion(source, &dest));
1816
1817     if (dest.numRects == 0) {
1818         dest = QRegionPrivate(*rect);
1819     } else if (dest.canAppend(rect)) {
1820         dest.append(rect);
1821     } else {
1822         QRegionPrivate p(*rect);
1823         UnionRegion(&p, source, dest);
1824     }
1825 }
1826
1827 /*-
1828  *-----------------------------------------------------------------------
1829  * miSetExtents --
1830  *      Reset the extents and innerRect of a region to what they should be.
1831  *      Called by miSubtract and miIntersect b/c they can't figure it out
1832  *      along the way or do so easily, as miUnion can.
1833  *
1834  * Results:
1835  *      None.
1836  *
1837  * Side Effects:
1838  *      The region's 'extents' and 'innerRect' structure is overwritten.
1839  *
1840  *-----------------------------------------------------------------------
1841  */
1842 static void miSetExtents(QRegionPrivate &dest)
1843 {
1844     register const QRect *pBox,
1845                          *pBoxEnd;
1846     register QRect *pExtents;
1847
1848     dest.innerRect.setCoords(0, 0, -1, -1);
1849     dest.innerArea = -1;
1850     if (dest.numRects == 0) {
1851         dest.extents.setCoords(0, 0, -1, -1);
1852         return;
1853     }
1854
1855     pExtents = &dest.extents;
1856     if (dest.rects.isEmpty())
1857         pBox = &dest.extents;
1858     else
1859         pBox = dest.rects.constData();
1860     pBoxEnd = pBox + dest.numRects - 1;
1861
1862     /*
1863      * Since pBox is the first rectangle in the region, it must have the
1864      * smallest y1 and since pBoxEnd is the last rectangle in the region,
1865      * it must have the largest y2, because of banding. Initialize x1 and
1866      * x2 from  pBox and pBoxEnd, resp., as good things to initialize them
1867      * to...
1868      */
1869     pExtents->setLeft(pBox->left());
1870     pExtents->setTop(pBox->top());
1871     pExtents->setRight(pBoxEnd->right());
1872     pExtents->setBottom(pBoxEnd->bottom());
1873
1874     Q_ASSERT(pExtents->top() <= pExtents->bottom());
1875     while (pBox <= pBoxEnd) {
1876         if (pBox->left() < pExtents->left())
1877             pExtents->setLeft(pBox->left());
1878         if (pBox->right() > pExtents->right())
1879             pExtents->setRight(pBox->right());
1880         dest.updateInnerRect(*pBox);
1881         ++pBox;
1882     }
1883     Q_ASSERT(pExtents->left() <= pExtents->right());
1884 }
1885
1886 /* TranslateRegion(pRegion, x, y)
1887    translates in place
1888    added by raymond
1889 */
1890
1891 static void OffsetRegion(register QRegionPrivate &region, register int x, register int y)
1892 {
1893     if (region.rects.size()) {
1894         register QRect *pbox = region.rects.data();
1895         register int nbox = region.numRects;
1896
1897         while (nbox--) {
1898             pbox->translate(x, y);
1899             ++pbox;
1900         }
1901     }
1902     region.extents.translate(x, y);
1903     region.innerRect.translate(x, y);
1904 }
1905
1906 /*======================================================================
1907  *          Region Intersection
1908  *====================================================================*/
1909 /*-
1910  *-----------------------------------------------------------------------
1911  * miIntersectO --
1912  *      Handle an overlapping band for miIntersect.
1913  *
1914  * Results:
1915  *      None.
1916  *
1917  * Side Effects:
1918  *      Rectangles may be added to the region.
1919  *
1920  *-----------------------------------------------------------------------
1921  */
1922 static void miIntersectO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
1923                          register const QRect *r2, const QRect *r2End, int y1, int y2)
1924 {
1925     register int x1;
1926     register int x2;
1927     register QRect *pNextRect;
1928
1929     pNextRect = dest.rects.data() + dest.numRects;
1930
1931     while (r1 != r1End && r2 != r2End) {
1932         x1 = qMax(r1->left(), r2->left());
1933         x2 = qMin(r1->right(), r2->right());
1934
1935         /*
1936          * If there's any overlap between the two rectangles, add that
1937          * overlap to the new region.
1938          * There's no need to check for subsumption because the only way
1939          * such a need could arise is if some region has two rectangles
1940          * right next to each other. Since that should never happen...
1941          */
1942         if (x1 <= x2) {
1943             Q_ASSERT(y1 <= y2);
1944             MEMCHECK(dest, pNextRect, dest.rects)
1945             pNextRect->setCoords(x1, y1, x2, y2);
1946             ++dest.numRects;
1947             ++pNextRect;
1948         }
1949
1950         /*
1951          * Need to advance the pointers. Shift the one that extends
1952          * to the right the least, since the other still has a chance to
1953          * overlap with that region's next rectangle, if you see what I mean.
1954          */
1955         if (r1->right() < r2->right()) {
1956             ++r1;
1957         } else if (r2->right() < r1->right()) {
1958             ++r2;
1959         } else {
1960             ++r1;
1961             ++r2;
1962         }
1963     }
1964 }
1965
1966 /*======================================================================
1967  *          Generic Region Operator
1968  *====================================================================*/
1969
1970 /*-
1971  *-----------------------------------------------------------------------
1972  * miCoalesce --
1973  *      Attempt to merge the boxes in the current band with those in the
1974  *      previous one. Used only by miRegionOp.
1975  *
1976  * Results:
1977  *      The new index for the previous band.
1978  *
1979  * Side Effects:
1980  *      If coalescing takes place:
1981  *          - rectangles in the previous band will have their y2 fields
1982  *            altered.
1983  *          - dest.numRects will be decreased.
1984  *
1985  *-----------------------------------------------------------------------
1986  */
1987 static int miCoalesce(register QRegionPrivate &dest, int prevStart, int curStart)
1988 {
1989     register QRect *pPrevBox;   /* Current box in previous band */
1990     register QRect *pCurBox;    /* Current box in current band */
1991     register QRect *pRegEnd;    /* End of region */
1992     int curNumRects;    /* Number of rectangles in current band */
1993     int prevNumRects;   /* Number of rectangles in previous band */
1994     int bandY1;         /* Y1 coordinate for current band */
1995     QRect *rData = dest.rects.data();
1996
1997     pRegEnd = rData + dest.numRects;
1998
1999     pPrevBox = rData + prevStart;
2000     prevNumRects = curStart - prevStart;
2001
2002     /*
2003      * Figure out how many rectangles are in the current band. Have to do
2004      * this because multiple bands could have been added in miRegionOp
2005      * at the end when one region has been exhausted.
2006      */
2007     pCurBox = rData + curStart;
2008     bandY1 = pCurBox->top();
2009     for (curNumRects = 0; pCurBox != pRegEnd && pCurBox->top() == bandY1; ++curNumRects) {
2010         ++pCurBox;
2011     }
2012
2013     if (pCurBox != pRegEnd) {
2014         /*
2015          * If more than one band was added, we have to find the start
2016          * of the last band added so the next coalescing job can start
2017          * at the right place... (given when multiple bands are added,
2018          * this may be pointless -- see above).
2019          */
2020         --pRegEnd;
2021         while ((pRegEnd - 1)->top() == pRegEnd->top())
2022             --pRegEnd;
2023         curStart = pRegEnd - rData;
2024         pRegEnd = rData + dest.numRects;
2025     }
2026
2027     if (curNumRects == prevNumRects && curNumRects != 0) {
2028         pCurBox -= curNumRects;
2029         /*
2030          * The bands may only be coalesced if the bottom of the previous
2031          * matches the top scanline of the current.
2032          */
2033         if (pPrevBox->bottom() == pCurBox->top() - 1) {
2034             /*
2035              * Make sure the bands have boxes in the same places. This
2036              * assumes that boxes have been added in such a way that they
2037              * cover the most area possible. I.e. two boxes in a band must
2038              * have some horizontal space between them.
2039              */
2040             do {
2041                 if (pPrevBox->left() != pCurBox->left() || pPrevBox->right() != pCurBox->right()) {
2042                      // The bands don't line up so they can't be coalesced.
2043                     return curStart;
2044                 }
2045                 ++pPrevBox;
2046                 ++pCurBox;
2047                 --prevNumRects;
2048             } while (prevNumRects != 0);
2049
2050             dest.numRects -= curNumRects;
2051             pCurBox -= curNumRects;
2052             pPrevBox -= curNumRects;
2053
2054             /*
2055              * The bands may be merged, so set the bottom y of each box
2056              * in the previous band to that of the corresponding box in
2057              * the current band.
2058              */
2059             do {
2060                 pPrevBox->setBottom(pCurBox->bottom());
2061                 dest.updateInnerRect(*pPrevBox);
2062                 ++pPrevBox;
2063                 ++pCurBox;
2064                 curNumRects -= 1;
2065             } while (curNumRects != 0);
2066
2067             /*
2068              * If only one band was added to the region, we have to backup
2069              * curStart to the start of the previous band.
2070              *
2071              * If more than one band was added to the region, copy the
2072              * other bands down. The assumption here is that the other bands
2073              * came from the same region as the current one and no further
2074              * coalescing can be done on them since it's all been done
2075              * already... curStart is already in the right place.
2076              */
2077             if (pCurBox == pRegEnd) {
2078                 curStart = prevStart;
2079             } else {
2080                 do {
2081                     *pPrevBox++ = *pCurBox++;
2082                     dest.updateInnerRect(*pPrevBox);
2083                 } while (pCurBox != pRegEnd);
2084             }
2085         }
2086     }
2087     return curStart;
2088 }
2089
2090 /*-
2091  *-----------------------------------------------------------------------
2092  * miRegionOp --
2093  *      Apply an operation to two regions. Called by miUnion, miInverse,
2094  *      miSubtract, miIntersect...
2095  *
2096  * Results:
2097  *      None.
2098  *
2099  * Side Effects:
2100  *      The new region is overwritten.
2101  *
2102  * Notes:
2103  *      The idea behind this function is to view the two regions as sets.
2104  *      Together they cover a rectangle of area that this function divides
2105  *      into horizontal bands where points are covered only by one region
2106  *      or by both. For the first case, the nonOverlapFunc is called with
2107  *      each the band and the band's upper and lower extents. For the
2108  *      second, the overlapFunc is called to process the entire band. It
2109  *      is responsible for clipping the rectangles in the band, though
2110  *      this function provides the boundaries.
2111  *      At the end of each band, the new region is coalesced, if possible,
2112  *      to reduce the number of rectangles in the region.
2113  *
2114  *-----------------------------------------------------------------------
2115  */
2116 static void miRegionOp(register QRegionPrivate &dest,
2117                        const QRegionPrivate *reg1, const QRegionPrivate *reg2,
2118                        OverlapFunc overlapFunc, NonOverlapFunc nonOverlap1Func,
2119                        NonOverlapFunc nonOverlap2Func)
2120 {
2121     register const QRect *r1;         // Pointer into first region
2122     register const QRect *r2;         // Pointer into 2d region
2123     const QRect *r1End;               // End of 1st region
2124     const QRect *r2End;               // End of 2d region
2125     register int ybot;          // Bottom of intersection
2126     register int ytop;          // Top of intersection
2127     int prevBand;               // Index of start of previous band in dest
2128     int curBand;                // Index of start of current band in dest
2129     register const QRect *r1BandEnd;  // End of current band in r1
2130     register const QRect *r2BandEnd;  // End of current band in r2
2131     int top;                    // Top of non-overlapping band
2132     int bot;                    // Bottom of non-overlapping band
2133
2134     /*
2135      * Initialization:
2136      *  set r1, r2, r1End and r2End appropriately, preserve the important
2137      * parts of the destination region until the end in case it's one of
2138      * the two source regions, then mark the "new" region empty, allocating
2139      * another array of rectangles for it to use.
2140      */
2141     if (reg1->numRects == 1)
2142         r1 = &reg1->extents;
2143     else
2144         r1 = reg1->rects.constData();
2145     if (reg2->numRects == 1)
2146         r2 = &reg2->extents;
2147     else
2148         r2 = reg2->rects.constData();
2149
2150     r1End = r1 + reg1->numRects;
2151     r2End = r2 + reg2->numRects;
2152
2153     dest.vectorize();
2154
2155     QVector<QRect> oldRects = dest.rects;
2156
2157     dest.numRects = 0;
2158
2159     /*
2160      * Allocate a reasonable number of rectangles for the new region. The idea
2161      * is to allocate enough so the individual functions don't need to
2162      * reallocate and copy the array, which is time consuming, yet we don't
2163      * have to worry about using too much memory. I hope to be able to
2164      * nuke the realloc() at the end of this function eventually.
2165      */
2166     dest.rects.resize(qMax(reg1->numRects,reg2->numRects) * 2);
2167
2168     /*
2169      * Initialize ybot and ytop.
2170      * In the upcoming loop, ybot and ytop serve different functions depending
2171      * on whether the band being handled is an overlapping or non-overlapping
2172      * band.
2173      *  In the case of a non-overlapping band (only one of the regions
2174      * has points in the band), ybot is the bottom of the most recent
2175      * intersection and thus clips the top of the rectangles in that band.
2176      * ytop is the top of the next intersection between the two regions and
2177      * serves to clip the bottom of the rectangles in the current band.
2178      *  For an overlapping band (where the two regions intersect), ytop clips
2179      * the top of the rectangles of both regions and ybot clips the bottoms.
2180      */
2181     if (reg1->extents.top() < reg2->extents.top())
2182         ybot = reg1->extents.top() - 1;
2183     else
2184         ybot = reg2->extents.top() - 1;
2185
2186     /*
2187      * prevBand serves to mark the start of the previous band so rectangles
2188      * can be coalesced into larger rectangles. qv. miCoalesce, above.
2189      * In the beginning, there is no previous band, so prevBand == curBand
2190      * (curBand is set later on, of course, but the first band will always
2191      * start at index 0). prevBand and curBand must be indices because of
2192      * the possible expansion, and resultant moving, of the new region's
2193      * array of rectangles.
2194      */
2195     prevBand = 0;
2196
2197     do {
2198         curBand = dest.numRects;
2199
2200         /*
2201          * This algorithm proceeds one source-band (as opposed to a
2202          * destination band, which is determined by where the two regions
2203          * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the
2204          * rectangle after the last one in the current band for their
2205          * respective regions.
2206          */
2207         r1BandEnd = r1;
2208         while (r1BandEnd != r1End && r1BandEnd->top() == r1->top())
2209             ++r1BandEnd;
2210
2211         r2BandEnd = r2;
2212         while (r2BandEnd != r2End && r2BandEnd->top() == r2->top())
2213             ++r2BandEnd;
2214
2215         /*
2216          * First handle the band that doesn't intersect, if any.
2217          *
2218          * Note that attention is restricted to one band in the
2219          * non-intersecting region at once, so if a region has n
2220          * bands between the current position and the next place it overlaps
2221          * the other, this entire loop will be passed through n times.
2222          */
2223         if (r1->top() < r2->top()) {
2224             top = qMax(r1->top(), ybot + 1);
2225             bot = qMin(r1->bottom(), r2->top() - 1);
2226
2227             if (nonOverlap1Func != 0 && bot >= top)
2228                 (*nonOverlap1Func)(dest, r1, r1BandEnd, top, bot);
2229             ytop = r2->top();
2230         } else if (r2->top() < r1->top()) {
2231             top = qMax(r2->top(), ybot + 1);
2232             bot = qMin(r2->bottom(), r1->top() - 1);
2233
2234             if (nonOverlap2Func != 0 && bot >= top)
2235                 (*nonOverlap2Func)(dest, r2, r2BandEnd, top, bot);
2236             ytop = r1->top();
2237         } else {
2238             ytop = r1->top();
2239         }
2240
2241         /*
2242          * If any rectangles got added to the region, try and coalesce them
2243          * with rectangles from the previous band. Note we could just do
2244          * this test in miCoalesce, but some machines incur a not
2245          * inconsiderable cost for function calls, so...
2246          */
2247         if (dest.numRects != curBand)
2248             prevBand = miCoalesce(dest, prevBand, curBand);
2249
2250         /*
2251          * Now see if we've hit an intersecting band. The two bands only
2252          * intersect if ybot >= ytop
2253          */
2254         ybot = qMin(r1->bottom(), r2->bottom());
2255         curBand = dest.numRects;
2256         if (ybot >= ytop)
2257             (*overlapFunc)(dest, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot);
2258
2259         if (dest.numRects != curBand)
2260             prevBand = miCoalesce(dest, prevBand, curBand);
2261
2262         /*
2263          * If we've finished with a band (y2 == ybot) we skip forward
2264          * in the region to the next band.
2265          */
2266         if (r1->bottom() == ybot)
2267             r1 = r1BandEnd;
2268         if (r2->bottom() == ybot)
2269             r2 = r2BandEnd;
2270     } while (r1 != r1End && r2 != r2End);
2271
2272     /*
2273      * Deal with whichever region still has rectangles left.
2274      */
2275     curBand = dest.numRects;
2276     if (r1 != r1End) {
2277         if (nonOverlap1Func != 0) {
2278             do {
2279                 r1BandEnd = r1;
2280                 while (r1BandEnd < r1End && r1BandEnd->top() == r1->top())
2281                     ++r1BandEnd;
2282                 (*nonOverlap1Func)(dest, r1, r1BandEnd, qMax(r1->top(), ybot + 1), r1->bottom());
2283                 r1 = r1BandEnd;
2284             } while (r1 != r1End);
2285         }
2286     } else if ((r2 != r2End) && (nonOverlap2Func != 0)) {
2287         do {
2288             r2BandEnd = r2;
2289             while (r2BandEnd < r2End && r2BandEnd->top() == r2->top())
2290                  ++r2BandEnd;
2291             (*nonOverlap2Func)(dest, r2, r2BandEnd, qMax(r2->top(), ybot + 1), r2->bottom());
2292             r2 = r2BandEnd;
2293         } while (r2 != r2End);
2294     }
2295
2296     if (dest.numRects != curBand)
2297         (void)miCoalesce(dest, prevBand, curBand);
2298
2299     /*
2300      * A bit of cleanup. To keep regions from growing without bound,
2301      * we shrink the array of rectangles to match the new number of
2302      * rectangles in the region.
2303      *
2304      * Only do this stuff if the number of rectangles allocated is more than
2305      * twice the number of rectangles in the region (a simple optimization).
2306      */
2307     if (qMax(4, dest.numRects) < (dest.rects.size() >> 1))
2308         dest.rects.resize(dest.numRects);
2309 }
2310
2311 /*======================================================================
2312  *          Region Union
2313  *====================================================================*/
2314
2315 /*-
2316  *-----------------------------------------------------------------------
2317  * miUnionNonO --
2318  *      Handle a non-overlapping band for the union operation. Just
2319  *      Adds the rectangles into the region. Doesn't have to check for
2320  *      subsumption or anything.
2321  *
2322  * Results:
2323  *      None.
2324  *
2325  * Side Effects:
2326  *      dest.numRects is incremented and the final rectangles overwritten
2327  *      with the rectangles we're passed.
2328  *
2329  *-----------------------------------------------------------------------
2330  */
2331
2332 static void miUnionNonO(register QRegionPrivate &dest, register const QRect *r, const QRect *rEnd,
2333                         register int y1, register int y2)
2334 {
2335     register QRect *pNextRect;
2336
2337     pNextRect = dest.rects.data() + dest.numRects;
2338
2339     Q_ASSERT(y1 <= y2);
2340
2341     while (r != rEnd) {
2342         Q_ASSERT(r->left() <= r->right());
2343         MEMCHECK(dest, pNextRect, dest.rects)
2344         pNextRect->setCoords(r->left(), y1, r->right(), y2);
2345         dest.numRects++;
2346         ++pNextRect;
2347         ++r;
2348     }
2349 }
2350
2351
2352 /*-
2353  *-----------------------------------------------------------------------
2354  * miUnionO --
2355  *      Handle an overlapping band for the union operation. Picks the
2356  *      left-most rectangle each time and merges it into the region.
2357  *
2358  * Results:
2359  *      None.
2360  *
2361  * Side Effects:
2362  *      Rectangles are overwritten in dest.rects and dest.numRects will
2363  *      be changed.
2364  *
2365  *-----------------------------------------------------------------------
2366  */
2367
2368 static void miUnionO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2369                      register const QRect *r2, const QRect *r2End, register int y1, register int y2)
2370 {
2371     register QRect *pNextRect;
2372
2373     pNextRect = dest.rects.data() + dest.numRects;
2374
2375 #define MERGERECT(r)             \
2376     if ((dest.numRects != 0) &&  \
2377         (pNextRect[-1].top() == y1) &&  \
2378         (pNextRect[-1].bottom() == y2) &&  \
2379         (pNextRect[-1].right() >= r->left()-1)) { \
2380         if (pNextRect[-1].right() < r->right()) { \
2381             pNextRect[-1].setRight(r->right());  \
2382             dest.updateInnerRect(pNextRect[-1]); \
2383             Q_ASSERT(pNextRect[-1].left() <= pNextRect[-1].right()); \
2384         }  \
2385     } else { \
2386         MEMCHECK(dest, pNextRect, dest.rects)  \
2387         pNextRect->setCoords(r->left(), y1, r->right(), y2); \
2388         dest.updateInnerRect(*pNextRect); \
2389         dest.numRects++;  \
2390         pNextRect++;  \
2391     }  \
2392     r++;
2393
2394     Q_ASSERT(y1 <= y2);
2395     while (r1 != r1End && r2 != r2End) {
2396         if (r1->left() < r2->left()) {
2397             MERGERECT(r1)
2398         } else {
2399             MERGERECT(r2)
2400         }
2401     }
2402
2403     if (r1 != r1End) {
2404         do {
2405             MERGERECT(r1)
2406         } while (r1 != r1End);
2407     } else {
2408         while (r2 != r2End) {
2409             MERGERECT(r2)
2410         }
2411     }
2412 }
2413
2414 static void UnionRegion(const QRegionPrivate *reg1, const QRegionPrivate *reg2, QRegionPrivate &dest)
2415 {
2416     Q_ASSERT(!isEmptyHelper(reg1) && !isEmptyHelper(reg2));
2417     Q_ASSERT(!reg1->contains(*reg2));
2418     Q_ASSERT(!reg2->contains(*reg1));
2419     Q_ASSERT(!EqualRegion(reg1, reg2));
2420     Q_ASSERT(!reg1->canAppend(reg2));
2421     Q_ASSERT(!reg2->canAppend(reg1));
2422
2423     if (reg1->innerArea > reg2->innerArea) {
2424         dest.innerArea = reg1->innerArea;
2425         dest.innerRect = reg1->innerRect;
2426     } else {
2427         dest.innerArea = reg2->innerArea;
2428         dest.innerRect = reg2->innerRect;
2429     }
2430     miRegionOp(dest, reg1, reg2, miUnionO, miUnionNonO, miUnionNonO);
2431
2432     dest.extents.setCoords(qMin(reg1->extents.left(), reg2->extents.left()),
2433                            qMin(reg1->extents.top(), reg2->extents.top()),
2434                            qMax(reg1->extents.right(), reg2->extents.right()),
2435                            qMax(reg1->extents.bottom(), reg2->extents.bottom()));
2436 }
2437
2438 /*======================================================================
2439  *        Region Subtraction
2440  *====================================================================*/
2441
2442 /*-
2443  *-----------------------------------------------------------------------
2444  * miSubtractNonO --
2445  *      Deal with non-overlapping band for subtraction. Any parts from
2446  *      region 2 we discard. Anything from region 1 we add to the region.
2447  *
2448  * Results:
2449  *      None.
2450  *
2451  * Side Effects:
2452  *      dest may be affected.
2453  *
2454  *-----------------------------------------------------------------------
2455  */
2456
2457 static void miSubtractNonO1(register QRegionPrivate &dest, register const QRect *r,
2458                             const QRect *rEnd, register int y1, register int y2)
2459 {
2460     register QRect *pNextRect;
2461
2462     pNextRect = dest.rects.data() + dest.numRects;
2463
2464     Q_ASSERT(y1<=y2);
2465
2466     while (r != rEnd) {
2467         Q_ASSERT(r->left() <= r->right());
2468         MEMCHECK(dest, pNextRect, dest.rects)
2469         pNextRect->setCoords(r->left(), y1, r->right(), y2);
2470         ++dest.numRects;
2471         ++pNextRect;
2472         ++r;
2473     }
2474 }
2475
2476 /*-
2477  *-----------------------------------------------------------------------
2478  * miSubtractO --
2479  *      Overlapping band subtraction. x1 is the left-most point not yet
2480  *      checked.
2481  *
2482  * Results:
2483  *      None.
2484  *
2485  * Side Effects:
2486  *      dest may have rectangles added to it.
2487  *
2488  *-----------------------------------------------------------------------
2489  */
2490
2491 static void miSubtractO(register QRegionPrivate &dest, register const QRect *r1, const QRect *r1End,
2492                         register const QRect *r2, const QRect *r2End, register int y1, register int y2)
2493 {
2494     register QRect *pNextRect;
2495     register int x1;
2496
2497     x1 = r1->left();
2498
2499     Q_ASSERT(y1 <= y2);
2500     pNextRect = dest.rects.data() + dest.numRects;
2501
2502     while (r1 != r1End && r2 != r2End) {
2503         if (r2->right() < x1) {
2504             /*
2505              * Subtrahend missed the boat: go to next subtrahend.
2506              */
2507             ++r2;
2508         } else if (r2->left() <= x1) {
2509             /*
2510              * Subtrahend precedes minuend: nuke left edge of minuend.
2511              */
2512             x1 = r2->right() + 1;
2513             if (x1 > r1->right()) {
2514                 /*
2515                  * Minuend completely covered: advance to next minuend and
2516                  * reset left fence to edge of new minuend.
2517                  */
2518                 ++r1;
2519                 if (r1 != r1End)
2520                     x1 = r1->left();
2521             } else {
2522                 // Subtrahend now used up since it doesn't extend beyond minuend
2523                 ++r2;
2524             }
2525         } else if (r2->left() <= r1->right()) {
2526             /*
2527              * Left part of subtrahend covers part of minuend: add uncovered
2528              * part of minuend to region and skip to next subtrahend.
2529              */
2530             Q_ASSERT(x1 < r2->left());
2531             MEMCHECK(dest, pNextRect, dest.rects)
2532             pNextRect->setCoords(x1, y1, r2->left() - 1, y2);
2533             ++dest.numRects;
2534             ++pNextRect;
2535
2536             x1 = r2->right() + 1;
2537             if (x1 > r1->right()) {
2538                 /*
2539                  * Minuend used up: advance to new...
2540                  */
2541                 ++r1;
2542                 if (r1 != r1End)
2543                     x1 = r1->left();
2544             } else {
2545                 // Subtrahend used up
2546                 ++r2;
2547             }
2548         } else {
2549             /*
2550              * Minuend used up: add any remaining piece before advancing.
2551              */
2552             if (r1->right() >= x1) {
2553                 MEMCHECK(dest, pNextRect, dest.rects)
2554                 pNextRect->setCoords(x1, y1, r1->right(), y2);
2555                 ++dest.numRects;
2556                 ++pNextRect;
2557             }
2558             ++r1;
2559             if (r1 != r1End)
2560                 x1 = r1->left();
2561         }
2562     }
2563
2564     /*
2565      * Add remaining minuend rectangles to region.
2566      */
2567     while (r1 != r1End) {
2568         Q_ASSERT(x1 <= r1->right());
2569         MEMCHECK(dest, pNextRect, dest.rects)
2570         pNextRect->setCoords(x1, y1, r1->right(), y2);
2571         ++dest.numRects;
2572         ++pNextRect;
2573
2574         ++r1;
2575         if (r1 != r1End)
2576             x1 = r1->left();
2577     }
2578 }
2579
2580 /*-
2581  *-----------------------------------------------------------------------
2582  * miSubtract --
2583  *      Subtract regS from regM and leave the result in regD.
2584  *      S stands for subtrahend, M for minuend and D for difference.
2585  *
2586  * Side Effects:
2587  *      regD is overwritten.
2588  *
2589  *-----------------------------------------------------------------------
2590  */
2591
2592 static void SubtractRegion(QRegionPrivate *regM, QRegionPrivate *regS,
2593                            register QRegionPrivate &dest)
2594 {
2595     Q_ASSERT(!isEmptyHelper(regM));
2596     Q_ASSERT(!isEmptyHelper(regS));
2597     Q_ASSERT(EXTENTCHECK(&regM->extents, &regS->extents));
2598     Q_ASSERT(!regS->contains(*regM));
2599     Q_ASSERT(!EqualRegion(regM, regS));
2600
2601     miRegionOp(dest, regM, regS, miSubtractO, miSubtractNonO1, 0);
2602
2603     /*
2604      * Can't alter dest's extents before we call miRegionOp because
2605      * it might be one of the source regions and miRegionOp depends
2606      * on the extents of those regions being the unaltered. Besides, this
2607      * way there's no checking against rectangles that will be nuked
2608      * due to coalescing, so we have to examine fewer rectangles.
2609      */
2610     miSetExtents(dest);
2611 }
2612
2613 static void XorRegion(QRegionPrivate *sra, QRegionPrivate *srb, QRegionPrivate &dest)
2614 {
2615     Q_ASSERT(!isEmptyHelper(sra) && !isEmptyHelper(srb));
2616     Q_ASSERT(EXTENTCHECK(&sra->extents, &srb->extents));
2617     Q_ASSERT(!EqualRegion(sra, srb));
2618
2619     QRegionPrivate tra, trb;
2620
2621     if (!srb->contains(*sra))
2622         SubtractRegion(sra, srb, tra);
2623     if (!sra->contains(*srb))
2624         SubtractRegion(srb, sra, trb);
2625
2626     Q_ASSERT(isEmptyHelper(&trb) || !tra.contains(trb));
2627     Q_ASSERT(isEmptyHelper(&tra) || !trb.contains(tra));
2628
2629     if (isEmptyHelper(&tra)) {
2630         dest = trb;
2631     } else if (isEmptyHelper(&trb)) {
2632         dest = tra;
2633     } else if (tra.canAppend(&trb)) {
2634         dest = tra;
2635         dest.append(&trb);
2636     } else if (trb.canAppend(&tra)) {
2637         dest = trb;
2638         dest.append(&tra);
2639     } else {
2640         UnionRegion(&tra, &trb, dest);
2641     }
2642 }
2643
2644 /*
2645  *      Check to see if two regions are equal
2646  */
2647 static bool EqualRegion(const QRegionPrivate *r1, const QRegionPrivate *r2)
2648 {
2649     if (r1->numRects != r2->numRects) {
2650         return false;
2651     } else if (r1->numRects == 0) {
2652         return true;
2653     } else if (r1->extents != r2->extents) {
2654         return false;
2655     } else if (r1->numRects == 1 && r2->numRects == 1) {
2656         return true; // equality tested in previous if-statement
2657     } else {
2658         const QRect *rr1 = (r1->numRects == 1) ? &r1->extents : r1->rects.constData();
2659         const QRect *rr2 = (r2->numRects == 1) ? &r2->extents : r2->rects.constData();
2660         for (int i = 0; i < r1->numRects; ++i, ++rr1, ++rr2) {
2661             if (*rr1 != *rr2)
2662                 return false;
2663         }
2664     }
2665
2666     return true;
2667 }
2668
2669 static bool PointInRegion(QRegionPrivate *pRegion, int x, int y)
2670 {
2671     int i;
2672
2673     if (isEmptyHelper(pRegion))
2674         return false;
2675     if (!pRegion->extents.contains(x, y))
2676         return false;
2677     if (pRegion->numRects == 1)
2678         return pRegion->extents.contains(x, y);
2679     if (pRegion->innerRect.contains(x, y))
2680         return true;
2681     for (i = 0; i < pRegion->numRects; ++i) {
2682         if (pRegion->rects[i].contains(x, y))
2683             return true;
2684     }
2685     return false;
2686 }
2687
2688 static bool RectInRegion(register QRegionPrivate *region, int rx, int ry, uint rwidth, uint rheight)
2689 {
2690     register const QRect *pbox;
2691     register const QRect *pboxEnd;
2692     QRect rect(rx, ry, rwidth, rheight);
2693     register QRect *prect = &rect;
2694     int partIn, partOut;
2695
2696     if (!region || region->numRects == 0 || !EXTENTCHECK(&region->extents, prect))
2697         return RectangleOut;
2698
2699     partOut = false;
2700     partIn = false;
2701
2702     /* can stop when both partOut and partIn are true, or we reach prect->y2 */
2703     pbox = (region->numRects == 1) ? &region->extents : region->rects.constData();
2704     pboxEnd = pbox + region->numRects;
2705     for (; pbox < pboxEnd; ++pbox) {
2706         if (pbox->bottom() < ry)
2707            continue;
2708
2709         if (pbox->top() > ry) {
2710            partOut = true;
2711            if (partIn || pbox->top() > prect->bottom())
2712               break;
2713            ry = pbox->top();
2714         }
2715
2716         if (pbox->right() < rx)
2717            continue;            /* not far enough over yet */
2718
2719         if (pbox->left() > rx) {
2720            partOut = true;      /* missed part of rectangle to left */
2721            if (partIn)
2722               break;
2723         }
2724
2725         if (pbox->left() <= prect->right()) {
2726             partIn = true;      /* definitely overlap */
2727             if (partOut)
2728                break;
2729         }
2730
2731         if (pbox->right() >= prect->right()) {
2732            ry = pbox->bottom() + 1;     /* finished with this band */
2733            if (ry > prect->bottom())
2734               break;
2735            rx = prect->left();  /* reset x out to left again */
2736         } else {
2737             /*
2738              * Because boxes in a band are maximal width, if the first box
2739              * to overlap the rectangle doesn't completely cover it in that
2740              * band, the rectangle must be partially out, since some of it
2741              * will be uncovered in that band. partIn will have been set true
2742              * by now...
2743              */
2744             break;
2745         }
2746     }
2747     return partIn ? ((ry <= prect->bottom()) ? RectanglePart : RectangleIn) : RectangleOut;
2748 }
2749 // END OF Region.c extract
2750 // START OF poly.h extract
2751 /* $XConsortium: poly.h,v 1.4 94/04/17 20:22:19 rws Exp $ */
2752 /************************************************************************
2753
2754 Copyright (c) 1987  X Consortium
2755
2756 Permission is hereby granted, free of charge, to any person obtaining a copy
2757 of this software and associated documentation files (the "Software"), to deal
2758 in the Software without restriction, including without limitation the rights
2759 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
2760 copies of the Software, and to permit persons to whom the Software is
2761 furnished to do so, subject to the following conditions:
2762
2763 The above copyright notice and this permission notice shall be included in
2764 all copies or substantial portions of the Software.
2765
2766 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
2767 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
2768 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
2769 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
2770 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
2771 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
2772
2773 Except as contained in this notice, the name of the X Consortium shall not be
2774 used in advertising or otherwise to promote the sale, use or other dealings
2775 in this Software without prior written authorization from the X Consortium.
2776
2777
2778 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
2779
2780                         All Rights Reserved
2781
2782 Permission to use, copy, modify, and distribute this software and its
2783 documentation for any purpose and without fee is hereby granted,
2784 provided that the above copyright notice appear in all copies and that
2785 both that copyright notice and this permission notice appear in
2786 supporting documentation, and that the name of Digital not be
2787 used in advertising or publicity pertaining to distribution of the
2788 software without specific, written prior permission.
2789
2790 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
2791 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
2792 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
2793 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
2794 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
2795 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
2796 SOFTWARE.
2797
2798 ************************************************************************/
2799
2800 /*
2801  *     This file contains a few macros to help track
2802  *     the edge of a filled object.  The object is assumed
2803  *     to be filled in scanline order, and thus the
2804  *     algorithm used is an extension of Bresenham's line
2805  *     drawing algorithm which assumes that y is always the
2806  *     major axis.
2807  *     Since these pieces of code are the same for any filled shape,
2808  *     it is more convenient to gather the library in one
2809  *     place, but since these pieces of code are also in
2810  *     the inner loops of output primitives, procedure call
2811  *     overhead is out of the question.
2812  *     See the author for a derivation if needed.
2813  */
2814
2815
2816 /*
2817  *  In scan converting polygons, we want to choose those pixels
2818  *  which are inside the polygon.  Thus, we add .5 to the starting
2819  *  x coordinate for both left and right edges.  Now we choose the
2820  *  first pixel which is inside the pgon for the left edge and the
2821  *  first pixel which is outside the pgon for the right edge.
2822  *  Draw the left pixel, but not the right.
2823  *
2824  *  How to add .5 to the starting x coordinate:
2825  *      If the edge is moving to the right, then subtract dy from the
2826  *  error term from the general form of the algorithm.
2827  *      If the edge is moving to the left, then add dy to the error term.
2828  *
2829  *  The reason for the difference between edges moving to the left
2830  *  and edges moving to the right is simple:  If an edge is moving
2831  *  to the right, then we want the algorithm to flip immediately.
2832  *  If it is moving to the left, then we don't want it to flip until
2833  *  we traverse an entire pixel.
2834  */
2835 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
2836     int dx;      /* local storage */ \
2837 \
2838     /* \
2839      *  if the edge is horizontal, then it is ignored \
2840      *  and assumed not to be processed.  Otherwise, do this stuff. \
2841      */ \
2842     if ((dy) != 0) { \
2843         xStart = (x1); \
2844         dx = (x2) - xStart; \
2845         if (dx < 0) { \
2846             m = dx / (dy); \
2847             m1 = m - 1; \
2848             incr1 = -2 * dx + 2 * (dy) * m1; \
2849             incr2 = -2 * dx + 2 * (dy) * m; \
2850             d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
2851         } else { \
2852             m = dx / (dy); \
2853             m1 = m + 1; \
2854             incr1 = 2 * dx - 2 * (dy) * m1; \
2855             incr2 = 2 * dx - 2 * (dy) * m; \
2856             d = -2 * m * (dy) + 2 * dx; \
2857         } \
2858     } \
2859 }
2860
2861 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
2862     if (m1 > 0) { \
2863         if (d > 0) { \
2864             minval += m1; \
2865             d += incr1; \
2866         } \
2867         else { \
2868             minval += m; \
2869             d += incr2; \
2870         } \
2871     } else {\
2872         if (d >= 0) { \
2873             minval += m1; \
2874             d += incr1; \
2875         } \
2876         else { \
2877             minval += m; \
2878             d += incr2; \
2879         } \
2880     } \
2881 }
2882
2883
2884 /*
2885  *     This structure contains all of the information needed
2886  *     to run the bresenham algorithm.
2887  *     The variables may be hardcoded into the declarations
2888  *     instead of using this structure to make use of
2889  *     register declarations.
2890  */
2891 typedef struct {
2892     int minor_axis;     /* minor axis        */
2893     int d;              /* decision variable */
2894     int m, m1;          /* slope and slope+1 */
2895     int incr1, incr2;   /* error increments */
2896 } BRESINFO;
2897
2898
2899 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
2900         BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
2901                      bres.m, bres.m1, bres.incr1, bres.incr2)
2902
2903 #define BRESINCRPGONSTRUCT(bres) \
2904         BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
2905
2906
2907
2908 /*
2909  *     These are the data structures needed to scan
2910  *     convert regions.  Two different scan conversion
2911  *     methods are available -- the even-odd method, and
2912  *     the winding number method.
2913  *     The even-odd rule states that a point is inside
2914  *     the polygon if a ray drawn from that point in any
2915  *     direction will pass through an odd number of
2916  *     path segments.
2917  *     By the winding number rule, a point is decided
2918  *     to be inside the polygon if a ray drawn from that
2919  *     point in any direction passes through a different
2920  *     number of clockwise and counter-clockwise path
2921  *     segments.
2922  *
2923  *     These data structures are adapted somewhat from
2924  *     the algorithm in (Foley/Van Dam) for scan converting
2925  *     polygons.
2926  *     The basic algorithm is to start at the top (smallest y)
2927  *     of the polygon, stepping down to the bottom of
2928  *     the polygon by incrementing the y coordinate.  We
2929  *     keep a list of edges which the current scanline crosses,
2930  *     sorted by x.  This list is called the Active Edge Table (AET)
2931  *     As we change the y-coordinate, we update each entry in
2932  *     in the active edge table to reflect the edges new xcoord.
2933  *     This list must be sorted at each scanline in case
2934  *     two edges intersect.
2935  *     We also keep a data structure known as the Edge Table (ET),
2936  *     which keeps track of all the edges which the current
2937  *     scanline has not yet reached.  The ET is basically a
2938  *     list of ScanLineList structures containing a list of
2939  *     edges which are entered at a given scanline.  There is one
2940  *     ScanLineList per scanline at which an edge is entered.
2941  *     When we enter a new edge, we move it from the ET to the AET.
2942  *
2943  *     From the AET, we can implement the even-odd rule as in
2944  *     (Foley/Van Dam).
2945  *     The winding number rule is a little trickier.  We also
2946  *     keep the EdgeTableEntries in the AET linked by the
2947  *     nextWETE (winding EdgeTableEntry) link.  This allows
2948  *     the edges to be linked just as before for updating
2949  *     purposes, but only uses the edges linked by the nextWETE
2950  *     link as edges representing spans of the polygon to
2951  *     drawn (as with the even-odd rule).
2952  */
2953
2954 /*
2955  * for the winding number rule
2956  */
2957 #define CLOCKWISE          1
2958 #define COUNTERCLOCKWISE  -1
2959
2960 typedef struct _EdgeTableEntry {
2961      int ymax;             /* ycoord at which we exit this edge. */
2962      BRESINFO bres;        /* Bresenham info to run the edge     */
2963      struct _EdgeTableEntry *next;       /* next in the list     */
2964      struct _EdgeTableEntry *back;       /* for insertion sort   */
2965      struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
2966      int ClockWise;        /* flag for winding number rule       */
2967 } EdgeTableEntry;
2968
2969
2970 typedef struct _ScanLineList{
2971      int scanline;              /* the scanline represented */
2972      EdgeTableEntry *edgelist;  /* header node              */
2973      struct _ScanLineList *next;  /* next in the list       */
2974 } ScanLineList;
2975
2976
2977 typedef struct {
2978      int ymax;                 /* ymax for the polygon     */
2979      int ymin;                 /* ymin for the polygon     */
2980      ScanLineList scanlines;   /* header node              */
2981 } EdgeTable;
2982
2983
2984 /*
2985  * Here is a struct to help with storage allocation
2986  * so we can allocate a big chunk at a time, and then take
2987  * pieces from this heap when we need to.
2988  */
2989 #define SLLSPERBLOCK 25
2990
2991 typedef struct _ScanLineListBlock {
2992      ScanLineList SLLs[SLLSPERBLOCK];
2993      struct _ScanLineListBlock *next;
2994 } ScanLineListBlock;
2995
2996
2997
2998 /*
2999  *
3000  *     a few macros for the inner loops of the fill code where
3001  *     performance considerations don't allow a procedure call.
3002  *
3003  *     Evaluate the given edge at the given scanline.
3004  *     If the edge has expired, then we leave it and fix up
3005  *     the active edge table; otherwise, we increment the
3006  *     x value to be ready for the next scanline.
3007  *     The winding number rule is in effect, so we must notify
3008  *     the caller when the edge has been removed so he
3009  *     can reorder the Winding Active Edge Table.
3010  */
3011 #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
3012    if (pAET->ymax == y) {          /* leaving this edge */ \
3013       pPrevAET->next = pAET->next; \
3014       pAET = pPrevAET->next; \
3015       fixWAET = 1; \
3016       if (pAET) \
3017          pAET->back = pPrevAET; \
3018    } \
3019    else { \
3020       BRESINCRPGONSTRUCT(pAET->bres) \
3021       pPrevAET = pAET; \
3022       pAET = pAET->next; \
3023    } \
3024 }
3025
3026
3027 /*
3028  *     Evaluate the given edge at the given scanline.
3029  *     If the edge has expired, then we leave it and fix up
3030  *     the active edge table; otherwise, we increment the
3031  *     x value to be ready for the next scanline.
3032  *     The even-odd rule is in effect.
3033  */
3034 #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
3035    if (pAET->ymax == y) {          /* leaving this edge */ \
3036       pPrevAET->next = pAET->next; \
3037       pAET = pPrevAET->next; \
3038       if (pAET) \
3039          pAET->back = pPrevAET; \
3040    } \
3041    else { \
3042       BRESINCRPGONSTRUCT(pAET->bres) \
3043       pPrevAET = pAET; \
3044       pAET = pAET->next; \
3045    } \
3046 }
3047 // END OF poly.h extract
3048 // START OF PolyReg.c extract
3049 /* $XConsortium: PolyReg.c,v 11.23 94/11/17 21:59:37 converse Exp $ */
3050 /************************************************************************
3051
3052 Copyright (c) 1987  X Consortium
3053
3054 Permission is hereby granted, free of charge, to any person obtaining a copy
3055 of this software and associated documentation files (the "Software"), to deal
3056 in the Software without restriction, including without limitation the rights
3057 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
3058 copies of the Software, and to permit persons to whom the Software is
3059 furnished to do so, subject to the following conditions:
3060
3061 The above copyright notice and this permission notice shall be included in
3062 all copies or substantial portions of the Software.
3063
3064 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
3065 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
3066 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
3067 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
3068 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
3069 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
3070
3071 Except as contained in this notice, the name of the X Consortium shall not be
3072 used in advertising or otherwise to promote the sale, use or other dealings
3073 in this Software without prior written authorization from the X Consortium.
3074
3075
3076 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
3077
3078                         All Rights Reserved
3079
3080 Permission to use, copy, modify, and distribute this software and its
3081 documentation for any purpose and without fee is hereby granted,
3082 provided that the above copyright notice appear in all copies and that
3083 both that copyright notice and this permission notice appear in
3084 supporting documentation, and that the name of Digital not be
3085 used in advertising or publicity pertaining to distribution of the
3086 software without specific, written prior permission.
3087
3088 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
3089 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
3090 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
3091 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
3092 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
3093 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
3094 SOFTWARE.
3095
3096 ************************************************************************/
3097 /* $XFree86: xc/lib/X11/PolyReg.c,v 1.1.1.2.8.2 1998/10/04 15:22:49 hohndel Exp $ */
3098
3099 #define LARGE_COORDINATE INT_MAX
3100 #define SMALL_COORDINATE INT_MIN
3101
3102 /*
3103  *     InsertEdgeInET
3104  *
3105  *     Insert the given edge into the edge table.
3106  *     First we must find the correct bucket in the
3107  *     Edge table, then find the right slot in the
3108  *     bucket.  Finally, we can insert it.
3109  *
3110  */
3111 static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline,
3112                            ScanLineListBlock **SLLBlock, int *iSLLBlock)
3113 {
3114     register EdgeTableEntry *start, *prev;
3115     register ScanLineList *pSLL, *pPrevSLL;
3116     ScanLineListBlock *tmpSLLBlock;
3117
3118     /*
3119      * find the right bucket to put the edge into
3120      */
3121     pPrevSLL = &ET->scanlines;
3122     pSLL = pPrevSLL->next;
3123     while (pSLL && (pSLL->scanline < scanline)) {
3124         pPrevSLL = pSLL;
3125         pSLL = pSLL->next;
3126     }
3127
3128     /*
3129      * reassign pSLL (pointer to ScanLineList) if necessary
3130      */
3131     if ((!pSLL) || (pSLL->scanline > scanline)) {
3132         if (*iSLLBlock > SLLSPERBLOCK-1)
3133         {
3134             tmpSLLBlock =
3135                   (ScanLineListBlock *)malloc(sizeof(ScanLineListBlock));
3136             Q_CHECK_PTR(tmpSLLBlock);
3137             (*SLLBlock)->next = tmpSLLBlock;
3138             tmpSLLBlock->next = (ScanLineListBlock *)NULL;
3139             *SLLBlock = tmpSLLBlock;
3140             *iSLLBlock = 0;
3141         }
3142         pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
3143
3144         pSLL->next = pPrevSLL->next;
3145         pSLL->edgelist = (EdgeTableEntry *)NULL;
3146         pPrevSLL->next = pSLL;
3147     }
3148     pSLL->scanline = scanline;
3149
3150     /*
3151      * now insert the edge in the right bucket
3152      */
3153     prev = 0;
3154     start = pSLL->edgelist;
3155     while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
3156         prev = start;
3157         start = start->next;
3158     }
3159     ETE->next = start;
3160
3161     if (prev)
3162         prev->next = ETE;
3163     else
3164         pSLL->edgelist = ETE;
3165 }
3166
3167 /*
3168  *     CreateEdgeTable
3169  *
3170  *     This routine creates the edge table for
3171  *     scan converting polygons.
3172  *     The Edge Table (ET) looks like:
3173  *
3174  *    EdgeTable
3175  *     --------
3176  *    |  ymax  |        ScanLineLists
3177  *    |scanline|-->------------>-------------->...
3178  *     --------   |scanline|   |scanline|
3179  *                |edgelist|   |edgelist|
3180  *                ---------    ---------
3181  *                    |             |
3182  *                    |             |
3183  *                    V             V
3184  *              list of ETEs   list of ETEs
3185  *
3186  *     where ETE is an EdgeTableEntry data structure,
3187  *     and there is one ScanLineList per scanline at
3188  *     which an edge is initially entered.
3189  *
3190  */
3191
3192 static void CreateETandAET(register int count, register const QPoint *pts,
3193                            EdgeTable *ET, EdgeTableEntry *AET, register EdgeTableEntry *pETEs,
3194                            ScanLineListBlock *pSLLBlock)
3195 {
3196     register const QPoint *top,
3197                           *bottom,
3198                           *PrevPt,
3199                           *CurrPt;
3200     int iSLLBlock = 0;
3201     int dy;
3202
3203     if (count < 2)
3204         return;
3205
3206     /*
3207      *  initialize the Active Edge Table
3208      */
3209     AET->next = 0;
3210     AET->back = 0;
3211     AET->nextWETE = 0;
3212     AET->bres.minor_axis = SMALL_COORDINATE;
3213
3214     /*
3215      *  initialize the Edge Table.
3216      */
3217     ET->scanlines.next = 0;
3218     ET->ymax = SMALL_COORDINATE;
3219     ET->ymin = LARGE_COORDINATE;
3220     pSLLBlock->next = 0;
3221
3222     PrevPt = &pts[count - 1];
3223
3224     /*
3225      *  for each vertex in the array of points.
3226      *  In this loop we are dealing with two vertices at
3227      *  a time -- these make up one edge of the polygon.
3228      */
3229     while (count--) {
3230         CurrPt = pts++;
3231
3232         /*
3233          *  find out which point is above and which is below.
3234          */
3235         if (PrevPt->y() > CurrPt->y()) {
3236             bottom = PrevPt;
3237             top = CurrPt;
3238             pETEs->ClockWise = 0;
3239         } else {
3240             bottom = CurrPt;
3241             top = PrevPt;
3242             pETEs->ClockWise = 1;
3243         }
3244
3245         /*
3246          * don't add horizontal edges to the Edge table.
3247          */
3248         if (bottom->y() != top->y()) {
3249             pETEs->ymax = bottom->y() - 1;  /* -1 so we don't get last scanline */
3250
3251             /*
3252              *  initialize integer edge algorithm
3253              */
3254             dy = bottom->y() - top->y();
3255             BRESINITPGONSTRUCT(dy, top->x(), bottom->x(), pETEs->bres)
3256
3257             InsertEdgeInET(ET, pETEs, top->y(), &pSLLBlock, &iSLLBlock);
3258
3259             if (PrevPt->y() > ET->ymax)
3260                 ET->ymax = PrevPt->y();
3261             if (PrevPt->y() < ET->ymin)
3262                 ET->ymin = PrevPt->y();
3263             ++pETEs;
3264         }
3265
3266         PrevPt = CurrPt;
3267     }
3268 }
3269
3270 /*
3271  *     loadAET
3272  *
3273  *     This routine moves EdgeTableEntries from the
3274  *     EdgeTable into the Active Edge Table,
3275  *     leaving them sorted by smaller x coordinate.
3276  *
3277  */
3278
3279 static void loadAET(register EdgeTableEntry *AET, register EdgeTableEntry *ETEs)
3280 {
3281     register EdgeTableEntry *pPrevAET;
3282     register EdgeTableEntry *tmp;
3283
3284     pPrevAET = AET;
3285     AET = AET->next;
3286     while (ETEs) {
3287         while (AET && AET->bres.minor_axis < ETEs->bres.minor_axis) {
3288             pPrevAET = AET;
3289             AET = AET->next;
3290         }
3291         tmp = ETEs->next;
3292         ETEs->next = AET;
3293         if (AET)
3294             AET->back = ETEs;
3295         ETEs->back = pPrevAET;
3296         pPrevAET->next = ETEs;
3297         pPrevAET = ETEs;
3298
3299         ETEs = tmp;
3300     }
3301 }
3302
3303 /*
3304  *     computeWAET
3305  *
3306  *     This routine links the AET by the
3307  *     nextWETE (winding EdgeTableEntry) link for
3308  *     use by the winding number rule.  The final
3309  *     Active Edge Table (AET) might look something
3310  *     like:
3311  *
3312  *     AET
3313  *     ----------  ---------   ---------
3314  *     |ymax    |  |ymax    |  |ymax    |
3315  *     | ...    |  |...     |  |...     |
3316  *     |next    |->|next    |->|next    |->...
3317  *     |nextWETE|  |nextWETE|  |nextWETE|
3318  *     ---------   ---------   ^--------
3319  *         |                   |       |
3320  *         V------------------->       V---> ...
3321  *
3322  */
3323 static void computeWAET(register EdgeTableEntry *AET)
3324 {
3325     register EdgeTableEntry *pWETE;
3326     register int inside = 1;
3327     register int isInside = 0;
3328
3329     AET->nextWETE = 0;
3330     pWETE = AET;
3331     AET = AET->next;
3332     while (AET) {
3333         if (AET->ClockWise)
3334             ++isInside;
3335         else
3336             --isInside;
3337
3338         if ((!inside && !isInside) || (inside && isInside)) {
3339             pWETE->nextWETE = AET;
3340             pWETE = AET;
3341             inside = !inside;
3342         }
3343         AET = AET->next;
3344     }
3345     pWETE->nextWETE = 0;
3346 }
3347
3348 /*
3349  *     InsertionSort
3350  *
3351  *     Just a simple insertion sort using
3352  *     pointers and back pointers to sort the Active
3353  *     Edge Table.
3354  *
3355  */
3356
3357 static int InsertionSort(register EdgeTableEntry *AET)
3358 {
3359     register EdgeTableEntry *pETEchase;
3360     register EdgeTableEntry *pETEinsert;
3361     register EdgeTableEntry *pETEchaseBackTMP;
3362     register int changed = 0;
3363
3364     AET = AET->next;
3365     while (AET) {
3366         pETEinsert = AET;
3367         pETEchase = AET;
3368         while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis)
3369             pETEchase = pETEchase->back;
3370
3371         AET = AET->next;
3372         if (pETEchase != pETEinsert) {
3373             pETEchaseBackTMP = pETEchase->back;
3374             pETEinsert->back->next = AET;
3375             if (AET)
3376                 AET->back = pETEinsert->back;
3377             pETEinsert->next = pETEchase;
3378             pETEchase->back->next = pETEinsert;
3379             pETEchase->back = pETEinsert;
3380             pETEinsert->back = pETEchaseBackTMP;
3381             changed = 1;
3382         }
3383     }
3384     return changed;
3385 }
3386
3387 /*
3388  *     Clean up our act.
3389  */
3390 static void FreeStorage(register ScanLineListBlock *pSLLBlock)
3391 {
3392     register ScanLineListBlock *tmpSLLBlock;
3393
3394     while (pSLLBlock) {
3395         tmpSLLBlock = pSLLBlock->next;
3396         free(pSLLBlock);
3397         pSLLBlock = tmpSLLBlock;
3398     }
3399 }
3400
3401 struct QRegionSpan {
3402     QRegionSpan() {}
3403     QRegionSpan(int x1_, int x2_) : x1(x1_), x2(x2_) {}
3404
3405     int x1;
3406     int x2;
3407     int width() const { return x2 - x1; }
3408 };
3409
3410 Q_DECLARE_TYPEINFO(QRegionSpan, Q_PRIMITIVE_TYPE);
3411
3412 static inline void flushRow(const QRegionSpan *spans, int y, int numSpans, QRegionPrivate *reg, int *lastRow, int *extendTo, bool *needsExtend)
3413 {
3414     QRect *regRects = reg->rects.data() + *lastRow;
3415     bool canExtend = reg->rects.size() - *lastRow == numSpans
3416         && !(*needsExtend && *extendTo + 1 != y)
3417         && (*needsExtend || regRects[0].y() + regRects[0].height() == y);
3418
3419     for (int i = 0; i < numSpans && canExtend; ++i) {
3420         if (regRects[i].x() != spans[i].x1 || regRects[i].right() != spans[i].x2 - 1)
3421             canExtend = false;
3422     }
3423
3424     if (canExtend) {
3425         *extendTo = y;
3426         *needsExtend = true;
3427     } else {
3428         if (*needsExtend) {
3429             for (int i = 0; i < reg->rects.size() - *lastRow; ++i)
3430                 regRects[i].setBottom(*extendTo);
3431         }
3432
3433         *lastRow = reg->rects.size();
3434         reg->rects.reserve(*lastRow + numSpans);
3435         for (int i = 0; i < numSpans; ++i)
3436             reg->rects << QRect(spans[i].x1, y, spans[i].width(), 1);
3437
3438         if (spans[0].x1 < reg->extents.left())
3439             reg->extents.setLeft(spans[0].x1);
3440
3441         if (spans[numSpans-1].x2 - 1 > reg->extents.right())
3442             reg->extents.setRight(spans[numSpans-1].x2 - 1);
3443
3444         *needsExtend = false;
3445     }
3446 }
3447
3448 /*
3449  *     Create an array of rectangles from a list of points.
3450  *     If indeed these things (POINTS, RECTS) are the same,
3451  *     then this proc is still needed, because it allocates
3452  *     storage for the array, which was allocated on the
3453  *     stack by the calling procedure.
3454  *
3455  */
3456 static void PtsToRegion(register int numFullPtBlocks, register int iCurPtBlock,
3457                        POINTBLOCK *FirstPtBlock, QRegionPrivate *reg)
3458 {
3459     int lastRow = 0;
3460     int extendTo = 0;
3461     bool needsExtend = false;
3462     QVarLengthArray<QRegionSpan> row;
3463     int rowSize = 0;
3464
3465     reg->extents.setLeft(INT_MAX);
3466     reg->extents.setRight(INT_MIN);
3467     reg->innerArea = -1;
3468
3469     POINTBLOCK *CurPtBlock = FirstPtBlock;
3470     for (; numFullPtBlocks >= 0; --numFullPtBlocks) {
3471         /* the loop uses 2 points per iteration */
3472         int i = NUMPTSTOBUFFER >> 1;
3473         if (!numFullPtBlocks)
3474             i = iCurPtBlock >> 1;
3475         if(i) {
3476             row.resize(qMax(row.size(), rowSize + i));
3477             for (QPoint *pts = CurPtBlock->pts; i--; pts += 2) {
3478                 const int width = pts[1].x() - pts[0].x();
3479                 if (width) {
3480                     if (rowSize && row[rowSize-1].x2 == pts[0].x())
3481                         row[rowSize-1].x2 = pts[1].x();
3482                     else
3483                         row[rowSize++] = QRegionSpan(pts[0].x(), pts[1].x());
3484                 }
3485
3486                 if (rowSize) {
3487                     QPoint *next = i ? &pts[2] : (numFullPtBlocks ? CurPtBlock->next->pts : 0);
3488
3489                     if (!next || next->y() != pts[0].y()) {
3490                         flushRow(row.data(), pts[0].y(), rowSize, reg, &lastRow, &extendTo, &needsExtend);
3491                         rowSize = 0;
3492                     }
3493                 }
3494             }
3495         }
3496         CurPtBlock = CurPtBlock->next;
3497     }
3498
3499     if (needsExtend) {
3500         for (int i = lastRow; i < reg->rects.size(); ++i)
3501             reg->rects[i].setBottom(extendTo);
3502     }
3503
3504     reg->numRects = reg->rects.size();
3505
3506     if (reg->numRects) {
3507         reg->extents.setTop(reg->rects[0].top());
3508         reg->extents.setBottom(reg->rects[lastRow].bottom());
3509
3510         for (int i = 0; i < reg->rects.size(); ++i)
3511             reg->updateInnerRect(reg->rects[i]);
3512     } else {
3513         reg->extents.setCoords(0, 0, 0, 0);
3514     }
3515 }
3516
3517 /*
3518  *     polytoregion
3519  *
3520  *     Scan converts a polygon by returning a run-length
3521  *     encoding of the resultant bitmap -- the run-length
3522  *     encoding is in the form of an array of rectangles.
3523  *
3524  *     Can return 0 in case of errors.
3525  */
3526 static QRegionPrivate *PolygonRegion(const QPoint *Pts, int Count, int rule)
3527     //Point     *Pts;                /* the pts                 */
3528     //int       Count;                 /* number of pts           */
3529     //int       rule;                        /* winding rule */
3530 {
3531     QRegionPrivate *region;
3532     register EdgeTableEntry *pAET;   /* Active Edge Table       */
3533     register int y;                  /* current scanline        */
3534     register int iPts = 0;           /* number of pts in buffer */
3535     register EdgeTableEntry *pWETE;  /* Winding Edge Table Entry*/
3536     register ScanLineList *pSLL;     /* current scanLineList    */
3537     register QPoint *pts;             /* output buffer           */
3538     EdgeTableEntry *pPrevAET;        /* ptr to previous AET     */
3539     EdgeTable ET;                    /* header node for ET      */
3540     EdgeTableEntry AET;              /* header node for AET     */
3541     EdgeTableEntry *pETEs;           /* EdgeTableEntries pool   */
3542     ScanLineListBlock SLLBlock;      /* header for scanlinelist */
3543     int fixWAET = false;
3544     POINTBLOCK FirstPtBlock, *curPtBlock; /* PtBlock buffers    */
3545     FirstPtBlock.pts = reinterpret_cast<QPoint *>(FirstPtBlock.data);
3546     POINTBLOCK *tmpPtBlock;
3547     int numFullPtBlocks = 0;
3548
3549     if (!(region = new QRegionPrivate))
3550         return 0;
3551
3552         /* special case a rectangle */
3553     if (((Count == 4) ||
3554          ((Count == 5) && (Pts[4].x() == Pts[0].x()) && (Pts[4].y() == Pts[0].y())))
3555          && (((Pts[0].y() == Pts[1].y()) && (Pts[1].x() == Pts[2].x()) && (Pts[2].y() == Pts[3].y())
3556                && (Pts[3].x() == Pts[0].x())) || ((Pts[0].x() == Pts[1].x())
3557                && (Pts[1].y() == Pts[2].y()) && (Pts[2].x() == Pts[3].x())
3558                && (Pts[3].y() == Pts[0].y())))) {
3559         int x = qMin(Pts[0].x(), Pts[2].x());
3560         region->extents.setLeft(x);
3561         int y = qMin(Pts[0].y(), Pts[2].y());
3562         region->extents.setTop(y);
3563         region->extents.setWidth(qMax(Pts[0].x(), Pts[2].x()) - x);
3564         region->extents.setHeight(qMax(Pts[0].y(), Pts[2].y()) - y);
3565         if ((region->extents.left() <= region->extents.right()) &&
3566             (region->extents.top() <= region->extents.bottom())) {
3567             region->numRects = 1;
3568             region->innerRect = region->extents;
3569             region->innerArea = region->innerRect.width() * region->innerRect.height();
3570         }
3571         return region;
3572     }
3573
3574     if (!(pETEs = static_cast<EdgeTableEntry *>(malloc(sizeof(EdgeTableEntry) * Count))))
3575         return 0;
3576
3577     region->vectorize();
3578
3579     pts = FirstPtBlock.pts;
3580     CreateETandAET(Count, Pts, &ET, &AET, pETEs, &SLLBlock);
3581
3582     pSLL = ET.scanlines.next;
3583     curPtBlock = &FirstPtBlock;
3584
3585     // sanity check that the region won't become too big...
3586     if (ET.ymax - ET.ymin > 100000) {
3587         // clean up region ptr
3588 #ifndef QT_NO_DEBUG
3589         qWarning("QRegion: creating region from big polygon failed...!");
3590 #endif
3591         delete region;
3592         return 0;
3593     }
3594
3595
3596     QT_TRY {
3597         if (rule == EvenOddRule) {
3598             /*
3599              *  for each scanline
3600              */
3601             for (y = ET.ymin; y < ET.ymax; ++y) {
3602
3603                 /*
3604                  *  Add a new edge to the active edge table when we
3605                  *  get to the next edge.
3606                  */
3607                 if (pSLL && y == pSLL->scanline) {
3608                     loadAET(&AET, pSLL->edgelist);
3609                     pSLL = pSLL->next;
3610                 }
3611                 pPrevAET = &AET;
3612                 pAET = AET.next;
3613
3614                 /*
3615                  *  for each active edge
3616                  */
3617                 while (pAET) {
3618                     pts->setX(pAET->bres.minor_axis);
3619                     pts->setY(y);
3620                     ++pts;
3621                     ++iPts;
3622
3623                     /*
3624                      *  send out the buffer
3625                      */
3626                     if (iPts == NUMPTSTOBUFFER) {
3627                         tmpPtBlock = (POINTBLOCK *)malloc(sizeof(POINTBLOCK));
3628                         Q_CHECK_PTR(tmpPtBlock);
3629                         tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data);
3630                         curPtBlock->next = tmpPtBlock;
3631                         curPtBlock = tmpPtBlock;
3632                         pts = curPtBlock->pts;
3633                         ++numFullPtBlocks;
3634                         iPts = 0;
3635                     }
3636                     EVALUATEEDGEEVENODD(pAET, pPrevAET, y)
3637                 }
3638                 InsertionSort(&AET);
3639             }
3640         } else {
3641             /*
3642              *  for each scanline
3643              */
3644             for (y = ET.ymin; y < ET.ymax; ++y) {
3645                 /*
3646                  *  Add a new edge to the active edge table when we
3647                  *  get to the next edge.
3648                  */
3649                 if (pSLL && y == pSLL->scanline) {
3650                     loadAET(&AET, pSLL->edgelist);
3651                     computeWAET(&AET);
3652                     pSLL = pSLL->next;
3653                 }
3654                 pPrevAET = &AET;
3655                 pAET = AET.next;
3656                 pWETE = pAET;
3657
3658                 /*
3659                  *  for each active edge
3660                  */
3661                 while (pAET) {
3662                     /*
3663                      *  add to the buffer only those edges that
3664                      *  are in the Winding active edge table.
3665                      */
3666                     if (pWETE == pAET) {
3667                         pts->setX(pAET->bres.minor_axis);
3668                         pts->setY(y);
3669                         ++pts;
3670                         ++iPts;
3671
3672                         /*
3673                          *  send out the buffer
3674                          */
3675                         if (iPts == NUMPTSTOBUFFER) {
3676                             tmpPtBlock = static_cast<POINTBLOCK *>(malloc(sizeof(POINTBLOCK)));
3677                             tmpPtBlock->pts = reinterpret_cast<QPoint *>(tmpPtBlock->data);
3678                             curPtBlock->next = tmpPtBlock;
3679                             curPtBlock = tmpPtBlock;
3680                             pts = curPtBlock->pts;
3681                             ++numFullPtBlocks;
3682                             iPts = 0;
3683                         }
3684                         pWETE = pWETE->nextWETE;
3685                     }
3686                     EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET)
3687                 }
3688
3689                 /*
3690                  *  recompute the winding active edge table if
3691                  *  we just resorted or have exited an edge.
3692                  */
3693                 if (InsertionSort(&AET) || fixWAET) {
3694                     computeWAET(&AET);
3695                     fixWAET = false;
3696                 }
3697             }
3698         }
3699     } QT_CATCH(...) {
3700         FreeStorage(SLLBlock.next);
3701         PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3702         for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3703             tmpPtBlock = curPtBlock->next;
3704             free(curPtBlock);
3705             curPtBlock = tmpPtBlock;
3706         }
3707         free(pETEs);
3708         return 0; // this function returns 0 in case of an error
3709     }
3710
3711     FreeStorage(SLLBlock.next);
3712     PtsToRegion(numFullPtBlocks, iPts, &FirstPtBlock, region);
3713     for (curPtBlock = FirstPtBlock.next; --numFullPtBlocks >= 0;) {
3714         tmpPtBlock = curPtBlock->next;
3715         free(curPtBlock);
3716         curPtBlock = tmpPtBlock;
3717     }
3718     free(pETEs);
3719     return region;
3720 }
3721 // END OF PolyReg.c extract
3722
3723 QRegionPrivate *qt_bitmapToRegion(const QBitmap& bitmap)
3724 {
3725     QImage image = bitmap.toImage();
3726
3727     QRegionPrivate *region = new QRegionPrivate;
3728
3729     QRect xr;
3730
3731 #define AddSpan \
3732         { \
3733             xr.setCoords(prev1, y, x-1, y); \
3734             UnionRectWithRegion(&xr, region, *region); \
3735         }
3736
3737     const uchar zero = 0;
3738     bool little = image.format() == QImage::Format_MonoLSB;
3739
3740     int x,
3741         y;
3742     for (y = 0; y < image.height(); ++y) {
3743         uchar *line = image.scanLine(y);
3744         int w = image.width();
3745         uchar all = zero;
3746         int prev1 = -1;
3747         for (x = 0; x < w;) {
3748             uchar byte = line[x / 8];
3749             if (x > w - 8 || byte!=all) {
3750                 if (little) {
3751                     for (int b = 8; b > 0 && x < w; --b) {
3752                         if (!(byte & 0x01) == !all) {
3753                             // More of the same
3754                         } else {
3755                             // A change.
3756                             if (all!=zero) {
3757                                 AddSpan
3758                                 all = zero;
3759                             } else {
3760                                 prev1 = x;
3761                                 all = ~zero;
3762                             }
3763                         }
3764                         byte >>= 1;
3765                         ++x;
3766                     }
3767                 } else {
3768                     for (int b = 8; b > 0 && x < w; --b) {
3769                         if (!(byte & 0x80) == !all) {
3770                             // More of the same
3771                         } else {
3772                             // A change.
3773                             if (all != zero) {
3774                                 AddSpan
3775                                 all = zero;
3776                             } else {
3777                                 prev1 = x;
3778                                 all = ~zero;
3779                             }
3780                         }
3781                         byte <<= 1;
3782                         ++x;
3783                     }
3784                 }
3785             } else {
3786                 x += 8;
3787             }
3788         }
3789         if (all != zero) {
3790             AddSpan
3791         }
3792     }
3793 #undef AddSpan
3794
3795     return region;
3796 }
3797
3798 QRegion::QRegion()
3799     : d(&shared_empty)
3800 {
3801     d->ref.ref();
3802 }
3803
3804 QRegion::QRegion(const QRect &r, RegionType t)
3805 {
3806     if (r.isEmpty()) {
3807         d = &shared_empty;
3808         d->ref.ref();
3809     } else {
3810         d = new QRegionData;
3811         d->ref.store(1);
3812         if (t == Rectangle) {
3813             d->qt_rgn = new QRegionPrivate(r);
3814         } else if (t == Ellipse) {
3815             QPainterPath path;
3816             path.addEllipse(r.x(), r.y(), r.width(), r.height());
3817             QPolygon a = path.toSubpathPolygons().at(0).toPolygon();
3818             d->qt_rgn = PolygonRegion(a.constData(), a.size(), EvenOddRule);
3819         }
3820     }
3821 }
3822
3823 QRegion::QRegion(const QPolygon &a, Qt::FillRule fillRule)
3824 {
3825     if (a.count() > 2) {
3826         QRegionPrivate *qt_rgn = PolygonRegion(a.constData(), a.size(),
3827                                                fillRule == Qt::WindingFill ? WindingRule : EvenOddRule);
3828         if (qt_rgn) {
3829             d =  new QRegionData;
3830             d->ref.store(1);
3831             d->qt_rgn = qt_rgn;
3832         } else {
3833             d = &shared_empty;
3834             d->ref.ref();
3835         }
3836     } else {
3837         d = &shared_empty;
3838         d->ref.ref();
3839     }
3840 }
3841
3842 QRegion::QRegion(const QRegion &r)
3843 {
3844     d = r.d;
3845     d->ref.ref();
3846 }
3847
3848
3849 QRegion::QRegion(const QBitmap &bm)
3850 {
3851     if (bm.isNull()) {
3852         d = &shared_empty;
3853         d->ref.ref();
3854     } else {
3855         d = new QRegionData;
3856         d->ref.store(1);
3857         d->qt_rgn = qt_bitmapToRegion(bm);
3858     }
3859 }
3860
3861 void QRegion::cleanUp(QRegion::QRegionData *x)
3862 {
3863     delete x->qt_rgn;
3864     delete x;
3865 }
3866
3867 QRegion::~QRegion()
3868 {
3869     if (!d->ref.deref())
3870         cleanUp(d);
3871 }
3872
3873
3874 QRegion &QRegion::operator=(const QRegion &r)
3875 {
3876     r.d->ref.ref();
3877     if (!d->ref.deref())
3878         cleanUp(d);
3879     d = r.d;
3880     return *this;
3881 }
3882
3883
3884 /*!
3885     \internal
3886 */
3887 QRegion QRegion::copy() const
3888 {
3889     QRegion r;
3890     QScopedPointer<QRegionData> x(new QRegionData);
3891     x->ref.store(1);
3892     if (d->qt_rgn)
3893         x->qt_rgn = new QRegionPrivate(*d->qt_rgn);
3894     else
3895         x->qt_rgn = new QRegionPrivate;
3896     if (!r.d->ref.deref())
3897         cleanUp(r.d);
3898     r.d = x.take();
3899     return r;
3900 }
3901
3902 bool QRegion::isEmpty() const
3903 {
3904     return d == &shared_empty || d->qt_rgn->numRects == 0;
3905 }
3906
3907 bool QRegion::isNull() const
3908 {
3909     return d == &shared_empty || d->qt_rgn->numRects == 0;
3910 }
3911
3912 bool QRegion::contains(const QPoint &p) const
3913 {
3914     return PointInRegion(d->qt_rgn, p.x(), p.y());
3915 }
3916
3917 bool QRegion::contains(const QRect &r) const
3918 {
3919     return RectInRegion(d->qt_rgn, r.left(), r.top(), r.width(), r.height()) != RectangleOut;
3920 }
3921
3922
3923
3924 void QRegion::translate(int dx, int dy)
3925 {
3926     if ((dx == 0 && dy == 0) || isEmptyHelper(d->qt_rgn))
3927         return;
3928
3929     detach();
3930     OffsetRegion(*d->qt_rgn, dx, dy);
3931 }
3932
3933 QRegion QRegion::united(const QRegion &r) const
3934 {
3935     if (isEmptyHelper(d->qt_rgn))
3936         return r;
3937     if (isEmptyHelper(r.d->qt_rgn))
3938         return *this;
3939     if (d == r.d)
3940         return *this;
3941
3942     if (d->qt_rgn->contains(*r.d->qt_rgn)) {
3943         return *this;
3944     } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
3945         return r;
3946     } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
3947         QRegion result(*this);
3948         result.detach();
3949         result.d->qt_rgn->append(r.d->qt_rgn);
3950         return result;
3951     } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
3952         QRegion result(*this);
3953         result.detach();
3954         result.d->qt_rgn->prepend(r.d->qt_rgn);
3955         return result;
3956     } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
3957         return *this;
3958     } else {
3959         QRegion result;
3960         result.detach();
3961         UnionRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
3962         return result;
3963     }
3964 }
3965
3966 QRegion& QRegion::operator+=(const QRegion &r)
3967 {
3968     if (isEmptyHelper(d->qt_rgn))
3969         return *this = r;
3970     if (isEmptyHelper(r.d->qt_rgn))
3971         return *this;
3972     if (d == r.d)
3973         return *this;
3974
3975     if (d->qt_rgn->contains(*r.d->qt_rgn)) {
3976         return *this;
3977     } else if (r.d->qt_rgn->contains(*d->qt_rgn)) {
3978         return *this = r;
3979     } else if (d->qt_rgn->canAppend(r.d->qt_rgn)) {
3980         detach();
3981         d->qt_rgn->append(r.d->qt_rgn);
3982         return *this;
3983     } else if (d->qt_rgn->canPrepend(r.d->qt_rgn)) {
3984         detach();
3985         d->qt_rgn->prepend(r.d->qt_rgn);
3986         return *this;
3987     } else if (EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
3988         return *this;
3989     } else {
3990         detach();
3991         UnionRegion(d->qt_rgn, r.d->qt_rgn, *d->qt_rgn);
3992         return *this;
3993     }
3994 }
3995
3996 QRegion QRegion::united(const QRect &r) const
3997 {
3998     if (isEmptyHelper(d->qt_rgn))
3999         return r;
4000     if (r.isEmpty())
4001         return *this;
4002
4003     if (d->qt_rgn->contains(r)) {
4004         return *this;
4005     } else if (d->qt_rgn->within(r)) {
4006         return r;
4007     } else if (d->qt_rgn->numRects == 1 && d->qt_rgn->extents == r) {
4008         return *this;
4009     } else if (d->qt_rgn->canAppend(&r)) {
4010         QRegion result(*this);
4011         result.detach();
4012         result.d->qt_rgn->append(&r);
4013         return result;
4014     } else if (d->qt_rgn->canPrepend(&r)) {
4015         QRegion result(*this);
4016         result.detach();
4017         result.d->qt_rgn->prepend(&r);
4018         return result;
4019     } else {
4020         QRegion result;
4021         result.detach();
4022         QRegionPrivate rp(r);
4023         UnionRegion(d->qt_rgn, &rp, *result.d->qt_rgn);
4024         return result;
4025     }
4026 }
4027
4028 QRegion& QRegion::operator+=(const QRect &r)
4029 {
4030     if (isEmptyHelper(d->qt_rgn))
4031         return *this = r;
4032     if (r.isEmpty())
4033         return *this;
4034
4035     if (d->qt_rgn->contains(r)) {
4036         return *this;
4037     } else if (d->qt_rgn->within(r)) {
4038         return *this = r;
4039     } else if (d->qt_rgn->canAppend(&r)) {
4040         detach();
4041         d->qt_rgn->append(&r);
4042         return *this;
4043     } else if (d->qt_rgn->canPrepend(&r)) {
4044         detach();
4045         d->qt_rgn->prepend(&r);
4046         return *this;
4047     } else if (d->qt_rgn->numRects == 1 && d->qt_rgn->extents == r) {
4048         return *this;
4049     } else {
4050         detach();
4051         QRegionPrivate p(r);
4052         UnionRegion(d->qt_rgn, &p, *d->qt_rgn);
4053         return *this;
4054     }
4055 }
4056
4057 QRegion QRegion::intersected(const QRegion &r) const
4058 {
4059     if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn)
4060         || !EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
4061         return QRegion();
4062
4063     /* this is fully contained in r */
4064     if (r.d->qt_rgn->contains(*d->qt_rgn))
4065         return *this;
4066
4067     /* r is fully contained in this */
4068     if (d->qt_rgn->contains(*r.d->qt_rgn))
4069         return r;
4070
4071     if (r.d->qt_rgn->numRects == 1 && d->qt_rgn->numRects == 1) {
4072         const QRect rect = qt_rect_intersect_normalized(r.d->qt_rgn->extents,
4073                                                         d->qt_rgn->extents);
4074         return QRegion(rect);
4075     } else if (r.d->qt_rgn->numRects == 1) {
4076         QRegion result(*this);
4077         result.detach();
4078         result.d->qt_rgn->intersect(r.d->qt_rgn->extents);
4079         return result;
4080     } else if (d->qt_rgn->numRects == 1) {
4081         QRegion result(r);
4082         result.detach();
4083         result.d->qt_rgn->intersect(d->qt_rgn->extents);
4084         return result;
4085     }
4086
4087     QRegion result;
4088     result.detach();
4089     miRegionOp(*result.d->qt_rgn, d->qt_rgn, r.d->qt_rgn, miIntersectO, 0, 0);
4090
4091     /*
4092      * Can't alter dest's extents before we call miRegionOp because
4093      * it might be one of the source regions and miRegionOp depends
4094      * on the extents of those regions being the same. Besides, this
4095      * way there's no checking against rectangles that will be nuked
4096      * due to coalescing, so we have to examine fewer rectangles.
4097      */
4098     miSetExtents(*result.d->qt_rgn);
4099     return result;
4100 }
4101
4102 QRegion QRegion::intersected(const QRect &r) const
4103 {
4104     if (isEmptyHelper(d->qt_rgn) || r.isEmpty()
4105         || !EXTENTCHECK(&d->qt_rgn->extents, &r))
4106         return QRegion();
4107
4108     /* this is fully contained in r */
4109     if (d->qt_rgn->within(r))
4110         return *this;
4111
4112     /* r is fully contained in this */
4113     if (d->qt_rgn->contains(r))
4114         return r;
4115
4116     if (d->qt_rgn->numRects == 1) {
4117         const QRect rect = qt_rect_intersect_normalized(d->qt_rgn->extents,
4118                                                         r.normalized());
4119         return QRegion(rect);
4120     }
4121
4122     QRegion result(*this);
4123     result.detach();
4124     result.d->qt_rgn->intersect(r);
4125     return result;
4126 }
4127
4128 QRegion QRegion::subtracted(const QRegion &r) const
4129 {
4130     if (isEmptyHelper(d->qt_rgn) || isEmptyHelper(r.d->qt_rgn))
4131         return *this;
4132     if (r.d->qt_rgn->contains(*d->qt_rgn))
4133         return QRegion();
4134     if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents))
4135         return *this;
4136     if (d == r.d || EqualRegion(d->qt_rgn, r.d->qt_rgn))
4137         return QRegion();
4138
4139 #ifdef QT_REGION_DEBUG
4140     d->qt_rgn->selfTest();
4141     r.d->qt_rgn->selfTest();
4142 #endif
4143
4144     QRegion result;
4145     result.detach();
4146     SubtractRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4147 #ifdef QT_REGION_DEBUG
4148     result.d->qt_rgn->selfTest();
4149 #endif
4150     return result;
4151 }
4152
4153 QRegion QRegion::xored(const QRegion &r) const
4154 {
4155     if (isEmptyHelper(d->qt_rgn)) {
4156         return r;
4157     } else if (isEmptyHelper(r.d->qt_rgn)) {
4158         return *this;
4159     } else if (!EXTENTCHECK(&d->qt_rgn->extents, &r.d->qt_rgn->extents)) {
4160         return (*this + r);
4161     } else if (d == r.d || EqualRegion(d->qt_rgn, r.d->qt_rgn)) {
4162         return QRegion();
4163     } else {
4164         QRegion result;
4165         result.detach();
4166         XorRegion(d->qt_rgn, r.d->qt_rgn, *result.d->qt_rgn);
4167         return result;
4168     }
4169 }
4170
4171 QRect QRegion::boundingRect() const
4172 {
4173     if (isEmpty())
4174         return QRect();
4175     return d->qt_rgn->extents;
4176 }
4177
4178 /*! \internal
4179     Returns true if \a rect is guaranteed to be fully contained in \a region.
4180     A false return value does not guarantee the opposite.
4181 */
4182 Q_GUI_EXPORT
4183 bool qt_region_strictContains(const QRegion &region, const QRect &rect)
4184 {
4185     if (isEmptyHelper(region.d->qt_rgn) || !rect.isValid())
4186         return false;
4187
4188 #if 0 // TEST_INNERRECT
4189     static bool guard = false;
4190     if (guard)
4191         return false;
4192     guard = true;
4193     QRegion inner = region.d->qt_rgn->innerRect;
4194     Q_ASSERT((inner - region).isEmpty());
4195     guard = false;
4196
4197     int maxArea = 0;
4198     for (int i = 0; i < region.d->qt_rgn->numRects; ++i) {
4199         const QRect r = region.d->qt_rgn->rects.at(i);
4200         if (r.width() * r.height() > maxArea)
4201             maxArea = r.width() * r.height();
4202     }
4203
4204     if (maxArea > region.d->qt_rgn->innerArea) {
4205         qDebug() << "not largest rectangle" << region << region.d->qt_rgn->innerRect;
4206     }
4207     Q_ASSERT(maxArea <= region.d->qt_rgn->innerArea);
4208 #endif
4209
4210     const QRect r1 = region.d->qt_rgn->innerRect;
4211     return (rect.left() >= r1.left() && rect.right() <= r1.right()
4212             && rect.top() >= r1.top() && rect.bottom() <= r1.bottom());
4213 }
4214
4215 QVector<QRect> QRegion::rects() const
4216 {
4217     if (d->qt_rgn) {
4218         d->qt_rgn->vectorize();
4219         // hw: modify the vector size directly to avoid reallocation
4220         if (d->qt_rgn->rects.d != &QVectorData::shared_null)
4221             d->qt_rgn->rects.d->size = d->qt_rgn->numRects;
4222         return d->qt_rgn->rects;
4223     } else {
4224         return QVector<QRect>();
4225     }
4226 }
4227
4228 void QRegion::setRects(const QRect *rects, int num)
4229 {
4230     *this = QRegion();
4231     if (!rects || num == 0 || (num == 1 && rects->isEmpty()))
4232         return;
4233
4234     detach();
4235
4236     d->qt_rgn->numRects = num;
4237     if (num == 1) {
4238         d->qt_rgn->extents = *rects;
4239         d->qt_rgn->innerRect = *rects;
4240     } else {
4241         d->qt_rgn->rects.resize(num);
4242
4243         int left = INT_MAX,
4244             right = INT_MIN,
4245             top = INT_MAX,
4246             bottom = INT_MIN;
4247         for (int i = 0; i < num; ++i) {
4248             const QRect &rect = rects[i];
4249             d->qt_rgn->rects[i] = rect;
4250             left = qMin(rect.left(), left);
4251             right = qMax(rect.right(), right);
4252             top = qMin(rect.top(), top);
4253             bottom = qMax(rect.bottom(), bottom);
4254             d->qt_rgn->updateInnerRect(rect);
4255         }
4256         d->qt_rgn->extents = QRect(QPoint(left, top), QPoint(right, bottom));
4257     }
4258 }
4259
4260 int QRegion::rectCount() const
4261 {
4262     return (d->qt_rgn ? d->qt_rgn->numRects : 0);
4263 }
4264
4265
4266 bool QRegion::operator==(const QRegion &r) const
4267 {
4268     if (!d->qt_rgn)
4269         return r.isEmpty();
4270     if (!r.d->qt_rgn)
4271         return isEmpty();
4272
4273     if (d == r.d)
4274         return true;
4275     else
4276         return EqualRegion(d->qt_rgn, r.d->qt_rgn);
4277 }
4278
4279 bool QRegion::intersects(const QRect &rect) const
4280 {
4281     if (isEmptyHelper(d->qt_rgn) || rect.isNull())
4282         return false;
4283
4284     const QRect r = rect.normalized();
4285     if (!rect_intersects(d->qt_rgn->extents, r))
4286         return false;
4287     if (d->qt_rgn->numRects == 1)
4288         return true;
4289
4290     const QVector<QRect> myRects = rects();
4291     for (QVector<QRect>::const_iterator it = myRects.constBegin(); it < myRects.constEnd(); ++it)
4292         if (rect_intersects(r, *it))
4293             return true;
4294     return false;
4295 }
4296
4297
4298 #endif
4299 QT_END_NAMESPACE