1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://www.qt.io/licensing/
5 **
6 ** This file is part of the QtCore 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 http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://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 2.1 or version 3 as published by the Free
20 ** Software Foundation and appearing in the file LICENSE.LGPLv21 and
21 ** LICENSE.LGPLv3 included in the packaging of this file. Please review the
22 ** following information to ensure the GNU Lesser General Public License
23 ** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
24 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
25 **
26 ** As a special exception, The Qt Company gives you certain additional
27 ** rights. These rights are described in The Qt Company LGPL Exception
28 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
29 **
30 ** GNU General Public License Usage
31 ** Alternatively, this file may be used under the terms of the GNU
32 ** General Public License version 3.0 as published by the Free Software
33 ** Foundation and appearing in the file LICENSE.GPL included in the
34 ** packaging of this file. Please review the following information to
35 ** ensure the GNU General Public License version 3.0 requirements will be
36 ** met: http://www.gnu.org/copyleft/gpl.html.
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41
42 //
43 // W A R N I N G
44 // -------------
45 //
46 // This file is not part of the Qt API. It exists for the convenience
47 // of other Qt classes. This header file may change from version to
48 // version without notice, or even be removed.
49 //
50 // We mean it.
51 //
52
53 #ifndef QGRAPHICSBSPTREEINDEX_H
54 #define QGRAPHICSBSPTREEINDEX_H
55
56 #include <QtCore/qglobal.h>
57
58 #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
59
60 #include "qgraphicssceneindex_p.h"
61 #include "qgraphicsitem_p.h"
62 #include "qgraphicsscene_bsp_p.h"
63
64 #include <QtCore/qrect.h>
65 #include <QtCore/qlist.h>
66
67 QT_BEGIN_NAMESPACE
68
69 static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
70
71 class QGraphicsScene;
72 class QGraphicsSceneBspTreeIndexPrivate;
73
74 class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
75 {
76 Q_OBJECT
77 Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth)
78 public:
79 QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0);
80 ~QGraphicsSceneBspTreeIndex();
81
82 QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const;
83 QList<QGraphicsItem *> estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const;
84 QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const;
85
86 int bspTreeDepth();
87 void setBspTreeDepth(int depth);
88
89 protected Q_SLOTS:
90 void updateSceneRect(const QRectF &rect);
91
92 protected:
93 bool event(QEvent *event);
94 void clear();
95
96 void addItem(QGraphicsItem *item);
97 void removeItem(QGraphicsItem *item);
98 void prepareBoundingRectChange(const QGraphicsItem *item);
99
100 void itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value);
101
102 private :
103 Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex)
104 Q_DISABLE_COPY(QGraphicsSceneBspTreeIndex)
105 Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
106 Q_PRIVATE_SLOT(d_func(), void _q_updateIndex())
107
108 friend class QGraphicsScene;
109 friend class QGraphicsScenePrivate;
110 };
111
112 class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate
113 {
114 Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)
115 public:
116 QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);
117
118 QGraphicsSceneBspTree bsp;
119 QRectF sceneRect;
120 int bspTreeDepth;
121 int indexTimerId;
122 bool restartIndexTimer;
123 bool regenerateIndex;
124 int lastItemCount;
125
126 QList<QGraphicsItem *> indexedItems;
127 QList<QGraphicsItem *> unindexedItems;
128 QList<QGraphicsItem *> untransformableItems;
129 QList<int> freeItemIndexes;
130
131 bool purgePending;
132 QSet<QGraphicsItem *> removedItems;
133 void purgeRemovedItems();
134
135 void _q_updateIndex();
136 void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
137 void resetIndex();
138
139 void _q_updateSortCache();
140 bool sortCacheEnabled;
141 bool updatingSortCache;
142 void invalidateSortCache();
143 void addItem(QGraphicsItem *item, bool recursive = false);
144 void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false);
145 QList<QGraphicsItem *> estimateItems(const QRectF &, Qt::SortOrder, bool b = false);
146
147 static void climbTree(QGraphicsItem *item, int *stackingOrder);
148
closestItemFirst_withCache(const QGraphicsItem * item1,const QGraphicsItem * item2)149 static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
150 {
151 return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
152 }
closestItemLast_withCache(const QGraphicsItem * item1,const QGraphicsItem * item2)153 static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
154 {
155 return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
156 }
157
158 static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
159 bool cached, bool onlyTopLevelItems = false);
160 };
161
QRectF_intersects(const QRectF & s,const QRectF & r)162 static inline bool QRectF_intersects(const QRectF &s, const QRectF &r)
163 {
164 qreal xp = s.left();
165 qreal yp = s.top();
166 qreal w = s.width();
167 qreal h = s.height();
168 qreal l1 = xp;
169 qreal r1 = xp;
170 if (w < 0)
171 l1 += w;
172 else
173 r1 += w;
174
175 qreal l2 = r.left();
176 qreal r2 = r.left();
177 if (w < 0)
178 l2 += r.width();
179 else
180 r2 += r.width();
181
182 if (l1 >= r2 || l2 >= r1)
183 return false;
184
185 qreal t1 = yp;
186 qreal b1 = yp;
187 if (h < 0)
188 t1 += h;
189 else
190 b1 += h;
191
192 qreal t2 = r.top();
193 qreal b2 = r.top();
194 if (r.height() < 0)
195 t2 += r.height();
196 else
197 b2 += r.height();
198
199 return !(t1 >= b2 || t2 >= b1);
200 }
201
202 QT_END_NAMESPACE
203
204 #endif // QT_NO_GRAPHICSVIEW
205
206 #endif // QGRAPHICSBSPTREEINDEX_H
207