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