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