qgraphicsscene_bsp.cpp

Absolute File Name:/home/qt/qt5_coco/qt5/qtbase/src/widgets/graphicsview/qgraphicsscene_bsp.cpp
Source codeSwitch to Preprocessed file
LineSourceCount
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 QtWidgets 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 "qgraphicsscene_bsp_p.h"-
41-
42#ifndef QT_NO_GRAPHICSVIEW-
43-
44#include <QtCore/qstring.h>-
45#include <private/qgraphicsitem_p.h>-
46-
47QT_BEGIN_NAMESPACE-
48-
49class QGraphicsSceneInsertItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor-
50{-
51public:-
52 QGraphicsItem *item;-
53-
54 void visit(QList<QGraphicsItem *> *items) Q_DECL_OVERRIDE-
55 { items->prepend(item); }
never executed: end of block
0
56};-
57-
58class QGraphicsSceneRemoveItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor-
59{-
60public:-
61 QGraphicsItem *item;-
62-
63 void visit(QList<QGraphicsItem *> *items) Q_DECL_OVERRIDE-
64 { items->removeAll(item); }
never executed: end of block
0
65};-
66-
67class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor-
68{-
69public:-
70 QList<QGraphicsItem *> *foundItems;-
71 bool onlyTopLevelItems;-
72-
73 void visit(QList<QGraphicsItem *> *items) Q_DECL_OVERRIDE-
74 {-
75 for (int i = 0; i < items->size(); ++i) {
i < items->size()Description
TRUEnever evaluated
FALSEnever evaluated
0
76 QGraphicsItem *item = items->at(i);-
77 if (onlyTopLevelItems && item->d_ptr->parent)
onlyTopLevelItemsDescription
TRUEnever evaluated
FALSEnever evaluated
item->d_ptr->parentDescription
TRUEnever evaluated
FALSEnever evaluated
0
78 item = item->topLevelItem();
never executed: item = item->topLevelItem();
0
79 if (!item->d_func()->itemDiscovered && item->d_ptr->visible) {
!item->d_func(...itemDiscoveredDescription
TRUEnever evaluated
FALSEnever evaluated
item->d_ptr->visibleDescription
TRUEnever evaluated
FALSEnever evaluated
0
80 item->d_func()->itemDiscovered = 1;-
81 foundItems->prepend(item);-
82 }
never executed: end of block
0
83 }
never executed: end of block
0
84 }
never executed: end of block
0
85};-
86-
87QGraphicsSceneBspTree::QGraphicsSceneBspTree()-
88 : leafCnt(0)-
89{-
90 insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor;-
91 removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor;-
92 findVisitor = new QGraphicsSceneFindItemBspTreeVisitor;-
93}
never executed: end of block
0
94-
95QGraphicsSceneBspTree::~QGraphicsSceneBspTree()-
96{-
97 delete insertVisitor;-
98 delete removeVisitor;-
99 delete findVisitor;-
100}
never executed: end of block
0
101-
102void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth)-
103{-
104 this->rect = rect;-
105 leafCnt = 0;-
106 nodes.resize((1 << (depth + 1)) - 1);-
107 nodes.fill(Node());-
108 leaves.resize(1 << depth);-
109 leaves.fill(QList<QGraphicsItem *>());-
110-
111 initialize(rect, depth, 0);-
112}
never executed: end of block
0
113-
114void QGraphicsSceneBspTree::clear()-
115{-
116 leafCnt = 0;-
117 nodes.clear();-
118 leaves.clear();-
119}
never executed: end of block
0
120-
121void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect)-
122{-
123 insertVisitor->item = item;-
124 climbTree(insertVisitor, rect);-
125}
never executed: end of block
0
126-
127void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect)-
128{-
129 removeVisitor->item = item;-
130 climbTree(removeVisitor, rect);-
131}
never executed: end of block
0
132-
133void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items)-
134{-
135 for (int i = 0; i < leaves.size(); ++i) {
i < leaves.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
136 QList<QGraphicsItem *> newItemList;-
137 const QList<QGraphicsItem *> &oldItemList = leaves[i];-
138 for (int j = 0; j < oldItemList.size(); ++j) {
j < oldItemList.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
139 QGraphicsItem *item = oldItemList.at(j);-
140 if (!items.contains(item))
!items.contains(item)Description
TRUEnever evaluated
FALSEnever evaluated
0
141 newItemList << item;
never executed: newItemList << item;
0
142 }
never executed: end of block
0
143 leaves[i] = newItemList;-
144 }
never executed: end of block
0
145}
never executed: end of block
0
146-
147QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const-
148{-
149 QList<QGraphicsItem *> tmp;-
150 findVisitor->foundItems = &tmp;-
151 findVisitor->onlyTopLevelItems = onlyTopLevelItems;-
152 climbTree(findVisitor, rect);-
153 // Reset discovery bits.-
154 for (int i = 0; i < tmp.size(); ++i)
i < tmp.size()Description
TRUEnever evaluated
FALSEnever evaluated
0
155 tmp.at(i)->d_ptr->itemDiscovered = 0;
never executed: tmp.at(i)->d_ptr->itemDiscovered = 0;
0
156 return tmp;
never executed: return tmp;
0
157}-
158-
159int QGraphicsSceneBspTree::leafCount() const-
160{-
161 return leafCnt;
never executed: return leafCnt;
0
162}-
163-
164QString QGraphicsSceneBspTree::debug(int index) const-
165{-
166 const Node *node = &nodes.at(index);-
167-
168 QString tmp;-
169 if (node->type == Node::Leaf) {
node->type == Node::LeafDescription
TRUEnever evaluated
FALSEnever evaluated
0
170 QRectF rect = rectForIndex(index);-
171 if (!leaves[node->leafIndex].isEmpty()) {
!leaves[node->...dex].isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
172 tmp += QString::fromLatin1("[%1, %2, %3, %4] contains %5 items\n")-
173 .arg(rect.left()).arg(rect.top())-
174 .arg(rect.width()).arg(rect.height())-
175 .arg(leaves[node->leafIndex].size());-
176 }
never executed: end of block
0
177 } else {
never executed: end of block
0
178 if (node->type == Node::Horizontal) {
node->type == Node::HorizontalDescription
TRUEnever evaluated
FALSEnever evaluated
0
179 tmp += debug(firstChildIndex(index));-
180 tmp += debug(firstChildIndex(index) + 1);-
181 } else {
never executed: end of block
0
182 tmp += debug(firstChildIndex(index));-
183 tmp += debug(firstChildIndex(index) + 1);-
184 }
never executed: end of block
0
185 }-
186-
187 return tmp;
never executed: return tmp;
0
188}-
189-
190void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index)-
191{-
192 Node *node = &nodes[index];-
193 if (index == 0) {
index == 0Description
TRUEnever evaluated
FALSEnever evaluated
0
194 node->type = Node::Horizontal;-
195 node->offset = rect.center().x();-
196 }
never executed: end of block
0
197-
198 if (depth) {
depthDescription
TRUEnever evaluated
FALSEnever evaluated
0
199 Node::Type type;-
200 QRectF rect1, rect2;-
201 qreal offset1, offset2;-
202-
203 if (node->type == Node::Horizontal) {
node->type == Node::HorizontalDescription
TRUEnever evaluated
FALSEnever evaluated
0
204 type = Node::Vertical;-
205 rect1.setRect(rect.left(), rect.top(), rect.width(), rect.height() / 2);-
206 rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rect.height() - rect1.height());-
207 offset1 = rect1.center().x();-
208 offset2 = rect2.center().x();-
209 } else {
never executed: end of block
0
210 type = Node::Horizontal;-
211 rect1.setRect(rect.left(), rect.top(), rect.width() / 2, rect.height());-
212 rect2.setRect(rect1.right(), rect1.top(), rect.width() - rect1.width(), rect1.height());-
213 offset1 = rect1.center().y();-
214 offset2 = rect2.center().y();-
215 }
never executed: end of block
0
216-
217 int childIndex = firstChildIndex(index);-
218-
219 Node *child = &nodes[childIndex];-
220 child->offset = offset1;-
221 child->type = type;-
222-
223 child = &nodes[childIndex + 1];-
224 child->offset = offset2;-
225 child->type = type;-
226-
227 initialize(rect1, depth - 1, childIndex);-
228 initialize(rect2, depth - 1, childIndex + 1);-
229 } else {
never executed: end of block
0
230 node->type = Node::Leaf;-
231 node->leafIndex = leafCnt++;-
232 }
never executed: end of block
0
233}-
234-
235void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) const-
236{-
237 if (nodes.isEmpty())
nodes.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
238 return;
never executed: return;
0
239-
240 const Node &node = nodes.at(index);-
241 const int childIndex = firstChildIndex(index);-
242-
243 switch (node.type) {-
244 case Node::Leaf: {
never executed: case Node::Leaf:
0
245 visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));-
246 break;
never executed: break;
0
247 }-
248 case Node::Vertical:
never executed: case Node::Vertical:
0
249 if (rect.left() < node.offset) {
rect.left() < node.offsetDescription
TRUEnever evaluated
FALSEnever evaluated
0
250 climbTree(visitor, rect, childIndex);-
251 if (rect.right() >= node.offset)
rect.right() >= node.offsetDescription
TRUEnever evaluated
FALSEnever evaluated
0
252 climbTree(visitor, rect, childIndex + 1);
never executed: climbTree(visitor, rect, childIndex + 1);
0
253 } else {
never executed: end of block
0
254 climbTree(visitor, rect, childIndex + 1);-
255 }
never executed: end of block
0
256 break;
never executed: break;
0
257 case Node::Horizontal:
never executed: case Node::Horizontal:
0
258 if (rect.top() < node.offset) {
rect.top() < node.offsetDescription
TRUEnever evaluated
FALSEnever evaluated
0
259 climbTree(visitor, rect, childIndex);-
260 if (rect.bottom() >= node.offset)
rect.bottom() >= node.offsetDescription
TRUEnever evaluated
FALSEnever evaluated
0
261 climbTree(visitor, rect, childIndex + 1);
never executed: climbTree(visitor, rect, childIndex + 1);
0
262 } else {
never executed: end of block
0
263 climbTree(visitor, rect, childIndex + 1);-
264 }
never executed: end of block
0
265 }-
266}
never executed: end of block
0
267-
268QRectF QGraphicsSceneBspTree::rectForIndex(int index) const-
269{-
270 if (index <= 0)
index <= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
271 return rect;
never executed: return rect;
0
272-
273 int parentIdx = parentIndex(index);-
274 QRectF rect = rectForIndex(parentIdx);-
275 const Node *parent = &nodes.at(parentIdx);-
276-
277 if (parent->type == Node::Horizontal) {
parent->type =...de::HorizontalDescription
TRUEnever evaluated
FALSEnever evaluated
0
278 if (index & 1)
index & 1Description
TRUEnever evaluated
FALSEnever evaluated
0
279 rect.setRight(parent->offset);
never executed: rect.setRight(parent->offset);
0
280 else-
281 rect.setLeft(parent->offset);
never executed: rect.setLeft(parent->offset);
0
282 } else {-
283 if (index & 1)
index & 1Description
TRUEnever evaluated
FALSEnever evaluated
0
284 rect.setBottom(parent->offset);
never executed: rect.setBottom(parent->offset);
0
285 else-
286 rect.setTop(parent->offset);
never executed: rect.setTop(parent->offset);
0
287 }-
288-
289 return rect;
never executed: return rect;
0
290}-
291-
292QT_END_NAMESPACE-
293-
294#endif // QT_NO_GRAPHICSVIEW-
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9