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 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 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//
41// W A R N I N G
42// -------------
43//
44// This file is not part of the Qt API. It exists for the convenience
45// of other Qt classes. This header file may change from version to
46// version without notice, or even be removed.
47//
48// We mean it.
49//
50
51#ifndef QGRAPHICSBSPTREEINDEX_H
52#define QGRAPHICSBSPTREEINDEX_H
53
54#include <QtWidgets/private/qtwidgetsglobal_p.h>
55
56#include "qgraphicssceneindex_p.h"
57#include "qgraphicsitem_p.h"
58#include "qgraphicsscene_bsp_p.h"
59
60#include <QtCore/qrect.h>
61#include <QtCore/qlist.h>
62
63QT_REQUIRE_CONFIG(graphicsview);
64
65QT_BEGIN_NAMESPACE
66
67static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
68
69class QGraphicsScene;
70class QGraphicsSceneBspTreeIndexPrivate;
71
72class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
73{
74 Q_OBJECT
75 Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth)
76public:
77 QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = nullptr);
78 ~QGraphicsSceneBspTreeIndex();
79
80 QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const override;
81 QList<QGraphicsItem *> estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const override;
82 QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const override;
83
84 int bspTreeDepth() const;
85 void setBspTreeDepth(int depth);
86
87protected Q_SLOTS:
88 void updateSceneRect(const QRectF &rect) override;
89
90protected:
91 bool event(QEvent *event) override;
92 void clear() override;
93
94 void addItem(QGraphicsItem *item) override;
95 void removeItem(QGraphicsItem *item) override;
96 void prepareBoundingRectChange(const QGraphicsItem *item) override;
97
98 void itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value) override;
99
100private :
101 Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex)
102 Q_DISABLE_COPY_MOVE(QGraphicsSceneBspTreeIndex)
103 Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
104 Q_PRIVATE_SLOT(d_func(), void _q_updateIndex())
105
106 friend class QGraphicsScene;
107 friend class QGraphicsScenePrivate;
108};
109
110class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate
111{
112 Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)
113public:
114 QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);
115
116 QGraphicsSceneBspTree bsp;
117 QRectF sceneRect;
118 int bspTreeDepth;
119 int indexTimerId;
120 bool restartIndexTimer;
121 bool regenerateIndex;
122 int lastItemCount;
123
124 QList<QGraphicsItem *> indexedItems;
125 QList<QGraphicsItem *> unindexedItems;
126 QList<QGraphicsItem *> untransformableItems;
127 QList<int> freeItemIndexes;
128
129 bool purgePending;
130 QSet<QGraphicsItem *> removedItems;
131 void purgeRemovedItems();
132
133 void _q_updateIndex();
134 void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
135 void resetIndex();
136
137 void _q_updateSortCache();
138 bool sortCacheEnabled;
139 bool updatingSortCache;
140 void invalidateSortCache();
141 void addItem(QGraphicsItem *item, bool recursive = false);
142 void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false);
143 QList<QGraphicsItem *> estimateItems(const QRectF &, Qt::SortOrder, bool b = false);
144
145 static void climbTree(QGraphicsItem *item, int *stackingOrder);
146
147 static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
148 {
149 return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
150 }
151 static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
152 {
153 return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
154 }
155
156 static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
157 bool cached, bool onlyTopLevelItems = false);
158};
159
160static inline bool QRectF_intersects(const QRectF &s, const QRectF &r)
161{
162 qreal xp = s.left();
163 qreal yp = s.top();
164 qreal w = s.width();
165 qreal h = s.height();
166 qreal l1 = xp;
167 qreal r1 = xp;
168 if (w < 0)
169 l1 += w;
170 else
171 r1 += w;
172
173 qreal l2 = r.left();
174 qreal r2 = r.left();
175 if (w < 0)
176 l2 += r.width();
177 else
178 r2 += r.width();
179
180 if (l1 >= r2 || l2 >= r1)
181 return false;
182
183 qreal t1 = yp;
184 qreal b1 = yp;
185 if (h < 0)
186 t1 += h;
187 else
188 b1 += h;
189
190 qreal t2 = r.top();
191 qreal b2 = r.top();
192 if (r.height() < 0)
193 t2 += r.height();
194 else
195 b2 += r.height();
196
197 return !(t1 >= b2 || t2 >= b1);
198}
199
200QT_END_NAMESPACE
201
202#endif // QGRAPHICSBSPTREEINDEX_H
203

source code of qtbase/src/widgets/graphicsview/qgraphicsscenebsptreeindex_p.h