graphicsview/qgraphicsscene_bsp.cpp

Source codeSwitch to Preprocessed file
LineSource CodeCoverage
1/**************************************************************************** -
2** -
3** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). -
4** Contact: http://www.qt-project.org/legal -
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 Digia. For licensing terms and -
14** conditions see http://qt.digia.com/licensing. For further information -
15** use the contact form at http://qt.digia.com/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 as published by the Free Software -
20** Foundation and appearing in the file LICENSE.LGPL included in the -
21** packaging of this file. Please review the following information to -
22** ensure the GNU Lesser General Public License version 2.1 requirements -
23** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -
24** -
25** In addition, as a special exception, Digia gives you certain additional -
26** rights. These rights are described in the Digia Qt LGPL Exception -
27** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. -
28** -
29** GNU General Public License Usage -
30** Alternatively, this file may be used under the terms of the GNU -
31** General Public License version 3.0 as published by the Free Software -
32** Foundation and appearing in the file LICENSE.GPL included in the -
33** packaging of this file. Please review the following information to -
34** ensure the GNU General Public License version 3.0 requirements will be -
35** met: http://www.gnu.org/copyleft/gpl.html. -
36** -
37** -
38** $QT_END_LICENSE$ -
39** -
40****************************************************************************/ -
41 -
42#include "qgraphicsscene_bsp_p.h" -
43 -
44#ifndef QT_NO_GRAPHICSVIEW -
45 -
46#include <QtCore/qstring.h> -
47#include <private/qgraphicsitem_p.h> -
48 -
49QT_BEGIN_NAMESPACE -
50 -
51class QGraphicsSceneInsertItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor -
52{ -
53public: -
54 QGraphicsItem *item; -
55 -
56 void visit(QList<QGraphicsItem *> *items) -
57 { items->prepend(item); }
executed: }
Execution Count:8855
8855
58}; -
59 -
60class QGraphicsSceneRemoveItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor -
61{ -
62public: -
63 QGraphicsItem *item; -
64 -
65 void visit(QList<QGraphicsItem *> *items) -
66 { items->removeAll(item); }
executed: }
Execution Count:2135
2135
67}; -
68 -
69class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor -
70{ -
71public: -
72 QList<QGraphicsItem *> *foundItems; -
73 bool onlyTopLevelItems; -
74 -
75 void visit(QList<QGraphicsItem *> *items) -
76 { -
77 for (int i = 0; i < items->size(); ++i) {
evaluated: i < items->size()
TRUEFALSE
yes
Evaluation Count:27953
yes
Evaluation Count:28610
27953-28610
78 QGraphicsItem *item = items->at(i);
executed (the execution status of this line is deduced): QGraphicsItem *item = items->at(i);
-
79 if (onlyTopLevelItems && item->d_ptr->parent)
partially evaluated: onlyTopLevelItems
TRUEFALSE
yes
Evaluation Count:27953
no
Evaluation Count:0
evaluated: item->d_ptr->parent
TRUEFALSE
yes
Evaluation Count:2548
yes
Evaluation Count:25405
0-27953
80 item = item->topLevelItem();
executed: item = item->topLevelItem();
Execution Count:2548
2548
81 if (!item->d_func()->itemDiscovered && item->d_ptr->visible) {
evaluated: !item->d_func()->itemDiscovered
TRUEFALSE
yes
Evaluation Count:4390
yes
Evaluation Count:23563
partially evaluated: item->d_ptr->visible
TRUEFALSE
yes
Evaluation Count:4390
no
Evaluation Count:0
0-23563
82 item->d_func()->itemDiscovered = 1;
executed (the execution status of this line is deduced): item->d_func()->itemDiscovered = 1;
-
83 foundItems->prepend(item);
executed (the execution status of this line is deduced): foundItems->prepend(item);
-
84 }
executed: }
Execution Count:4390
4390
85 }
executed: }
Execution Count:27953
27953
86 }
executed: }
Execution Count:28610
28610
87}; -
88 -
89QGraphicsSceneBspTree::QGraphicsSceneBspTree() -
90 : leafCnt(0) -
91{ -
92 insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor;
executed (the execution status of this line is deduced): insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor;
-
93 removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor;
executed (the execution status of this line is deduced): removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor;
-
94 findVisitor = new QGraphicsSceneFindItemBspTreeVisitor;
executed (the execution status of this line is deduced): findVisitor = new QGraphicsSceneFindItemBspTreeVisitor;
-
95}
executed: }
Execution Count:798
798
96 -
97QGraphicsSceneBspTree::~QGraphicsSceneBspTree() -
98{ -
99 delete insertVisitor;
executed (the execution status of this line is deduced): delete insertVisitor;
-
100 delete removeVisitor;
executed (the execution status of this line is deduced): delete removeVisitor;
-
101 delete findVisitor;
executed (the execution status of this line is deduced): delete findVisitor;
-
102}
executed: }
Execution Count:779
779
103 -
104void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth) -
105{ -
106 this->rect = rect;
executed (the execution status of this line is deduced): this->rect = rect;
-
107 leafCnt = 0;
executed (the execution status of this line is deduced): leafCnt = 0;
-
108 nodes.resize((1 << (depth + 1)) - 1);
executed (the execution status of this line is deduced): nodes.resize((1 << (depth + 1)) - 1);
-
109 nodes.fill(Node());
executed (the execution status of this line is deduced): nodes.fill(Node());
-
110 leaves.resize(1 << depth);
executed (the execution status of this line is deduced): leaves.resize(1 << depth);
-
111 leaves.fill(QList<QGraphicsItem *>());
executed (the execution status of this line is deduced): leaves.fill(QList<QGraphicsItem *>());
-
112 -
113 initialize(rect, depth, 0);
executed (the execution status of this line is deduced): initialize(rect, depth, 0);
-
114}
executed: }
Execution Count:197
197
115 -
116void QGraphicsSceneBspTree::clear() -
117{ -
118 leafCnt = 0;
executed (the execution status of this line is deduced): leafCnt = 0;
-
119 nodes.clear();
executed (the execution status of this line is deduced): nodes.clear();
-
120 leaves.clear();
executed (the execution status of this line is deduced): leaves.clear();
-
121}
executed: }
Execution Count:779
779
122 -
123void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect) -
124{ -
125 insertVisitor->item = item;
executed (the execution status of this line is deduced): insertVisitor->item = item;
-
126 climbTree(insertVisitor, rect);
executed (the execution status of this line is deduced): climbTree(insertVisitor, rect);
-
127}
executed: }
Execution Count:796
796
128 -
129void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect) -
130{ -
131 removeVisitor->item = item;
executed (the execution status of this line is deduced): removeVisitor->item = item;
-
132 climbTree(removeVisitor, rect);
executed (the execution status of this line is deduced): climbTree(removeVisitor, rect);
-
133}
executed: }
Execution Count:260
260
134 -
135void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items) -
136{ -
137 for (int i = 0; i < leaves.size(); ++i) {
evaluated: i < leaves.size()
TRUEFALSE
yes
Evaluation Count:64
yes
Evaluation Count:2
2-64
138 QList<QGraphicsItem *> newItemList;
executed (the execution status of this line is deduced): QList<QGraphicsItem *> newItemList;
-
139 const QList<QGraphicsItem *> &oldItemList = leaves[i];
executed (the execution status of this line is deduced): const QList<QGraphicsItem *> &oldItemList = leaves[i];
-
140 for (int j = 0; j < oldItemList.size(); ++j) {
evaluated: j < oldItemList.size()
TRUEFALSE
yes
Evaluation Count:112
yes
Evaluation Count:64
64-112
141 QGraphicsItem *item = oldItemList.at(j);
executed (the execution status of this line is deduced): QGraphicsItem *item = oldItemList.at(j);
-
142 if (!items.contains(item))
partially evaluated: !items.contains(item)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:112
0-112
143 newItemList << item;
never executed: newItemList << item;
0
144 }
executed: }
Execution Count:112
112
145 leaves[i] = newItemList;
executed (the execution status of this line is deduced): leaves[i] = newItemList;
-
146 }
executed: }
Execution Count:64
64
147}
executed: }
Execution Count:2
2
148 -
149QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const -
150{ -
151 QList<QGraphicsItem *> tmp;
executed (the execution status of this line is deduced): QList<QGraphicsItem *> tmp;
-
152 findVisitor->foundItems = &tmp;
executed (the execution status of this line is deduced): findVisitor->foundItems = &tmp;
-
153 findVisitor->onlyTopLevelItems = onlyTopLevelItems;
executed (the execution status of this line is deduced): findVisitor->onlyTopLevelItems = onlyTopLevelItems;
-
154 climbTree(findVisitor, rect);
executed (the execution status of this line is deduced): climbTree(findVisitor, rect);
-
155 // Reset discovery bits. -
156 for (int i = 0; i < tmp.size(); ++i)
evaluated: i < tmp.size()
TRUEFALSE
yes
Evaluation Count:4390
yes
Evaluation Count:2442
2442-4390
157 tmp.at(i)->d_ptr->itemDiscovered = 0;
executed: tmp.at(i)->d_ptr->itemDiscovered = 0;
Execution Count:4390
4390
158 return tmp;
executed: return tmp;
Execution Count:2442
2442
159} -
160 -
161int QGraphicsSceneBspTree::leafCount() const -
162{ -
163 return leafCnt;
executed: return leafCnt;
Execution Count:178
178
164} -
165 -
166QString QGraphicsSceneBspTree::debug(int index) const -
167{ -
168 const Node *node = &nodes.at(index);
never executed (the execution status of this line is deduced): const Node *node = &nodes.at(index);
-
169 -
170 QString tmp;
never executed (the execution status of this line is deduced): QString tmp;
-
171 if (node->type == Node::Leaf) {
never evaluated: node->type == Node::Leaf
0
172 QRectF rect = rectForIndex(index);
never executed (the execution status of this line is deduced): QRectF rect = rectForIndex(index);
-
173 if (!leaves[node->leafIndex].isEmpty()) {
never evaluated: !leaves[node->leafIndex].isEmpty()
0
174 tmp += QString::fromLatin1("[%1, %2, %3, %4] contains %5 items\n")
never executed (the execution status of this line is deduced): tmp += QString::fromLatin1("[%1, %2, %3, %4] contains %5 items\n")
-
175 .arg(rect.left()).arg(rect.top())
never executed (the execution status of this line is deduced): .arg(rect.left()).arg(rect.top())
-
176 .arg(rect.width()).arg(rect.height())
never executed (the execution status of this line is deduced): .arg(rect.width()).arg(rect.height())
-
177 .arg(leaves[node->leafIndex].size());
never executed (the execution status of this line is deduced): .arg(leaves[node->leafIndex].size());
-
178 }
never executed: }
0
179 } else {
never executed: }
0
180 if (node->type == Node::Horizontal) {
never evaluated: node->type == Node::Horizontal
0
181 tmp += debug(firstChildIndex(index));
never executed (the execution status of this line is deduced): tmp += debug(firstChildIndex(index));
-
182 tmp += debug(firstChildIndex(index) + 1);
never executed (the execution status of this line is deduced): tmp += debug(firstChildIndex(index) + 1);
-
183 } else {
never executed: }
0
184 tmp += debug(firstChildIndex(index));
never executed (the execution status of this line is deduced): tmp += debug(firstChildIndex(index));
-
185 tmp += debug(firstChildIndex(index) + 1);
never executed (the execution status of this line is deduced): tmp += debug(firstChildIndex(index) + 1);
-
186 }
never executed: }
0
187 } -
188 -
189 return tmp;
never executed: return tmp;
0
190} -
191 -
192void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index) -
193{ -
194 Node *node = &nodes[index];
executed (the execution status of this line is deduced): Node *node = &nodes[index];
-
195 if (index == 0) {
evaluated: index == 0
TRUEFALSE
yes
Evaluation Count:197
yes
Evaluation Count:12096
197-12096
196 node->type = Node::Horizontal;
executed (the execution status of this line is deduced): node->type = Node::Horizontal;
-
197 node->offset = rect.center().x();
executed (the execution status of this line is deduced): node->offset = rect.center().x();
-
198 }
executed: }
Execution Count:197
197
199 -
200 if (depth) {
evaluated: depth
TRUEFALSE
yes
Evaluation Count:6048
yes
Evaluation Count:6245
6048-6245
201 Node::Type type;
executed (the execution status of this line is deduced): Node::Type type;
-
202 QRectF rect1, rect2;
executed (the execution status of this line is deduced): QRectF rect1, rect2;
-
203 qreal offset1, offset2;
executed (the execution status of this line is deduced): qreal offset1, offset2;
-
204 -
205 if (node->type == Node::Horizontal) {
evaluated: node->type == Node::Horizontal
TRUEFALSE
yes
Evaluation Count:4096
yes
Evaluation Count:1952
1952-4096
206 type = Node::Vertical;
executed (the execution status of this line is deduced): type = Node::Vertical;
-
207 rect1.setRect(rect.left(), rect.top(), rect.width(), rect.height() / 2);
executed (the execution status of this line is deduced): rect1.setRect(rect.left(), rect.top(), rect.width(), rect.height() / 2);
-
208 rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rect.height() - rect1.height());
executed (the execution status of this line is deduced): rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rect.height() - rect1.height());
-
209 offset1 = rect1.center().x();
executed (the execution status of this line is deduced): offset1 = rect1.center().x();
-
210 offset2 = rect2.center().x();
executed (the execution status of this line is deduced): offset2 = rect2.center().x();
-
211 } else {
executed: }
Execution Count:4096
4096
212 type = Node::Horizontal;
executed (the execution status of this line is deduced): type = Node::Horizontal;
-
213 rect1.setRect(rect.left(), rect.top(), rect.width() / 2, rect.height());
executed (the execution status of this line is deduced): rect1.setRect(rect.left(), rect.top(), rect.width() / 2, rect.height());
-
214 rect2.setRect(rect1.right(), rect1.top(), rect.width() - rect1.width(), rect1.height());
executed (the execution status of this line is deduced): rect2.setRect(rect1.right(), rect1.top(), rect.width() - rect1.width(), rect1.height());
-
215 offset1 = rect1.center().y();
executed (the execution status of this line is deduced): offset1 = rect1.center().y();
-
216 offset2 = rect2.center().y();
executed (the execution status of this line is deduced): offset2 = rect2.center().y();
-
217 }
executed: }
Execution Count:1952
1952
218 -
219 int childIndex = firstChildIndex(index);
executed (the execution status of this line is deduced): int childIndex = firstChildIndex(index);
-
220 -
221 Node *child = &nodes[childIndex];
executed (the execution status of this line is deduced): Node *child = &nodes[childIndex];
-
222 child->offset = offset1;
executed (the execution status of this line is deduced): child->offset = offset1;
-
223 child->type = type;
executed (the execution status of this line is deduced): child->type = type;
-
224 -
225 child = &nodes[childIndex + 1];
executed (the execution status of this line is deduced): child = &nodes[childIndex + 1];
-
226 child->offset = offset2;
executed (the execution status of this line is deduced): child->offset = offset2;
-
227 child->type = type;
executed (the execution status of this line is deduced): child->type = type;
-
228 -
229 initialize(rect1, depth - 1, childIndex);
executed (the execution status of this line is deduced): initialize(rect1, depth - 1, childIndex);
-
230 initialize(rect2, depth - 1, childIndex + 1);
executed (the execution status of this line is deduced): initialize(rect2, depth - 1, childIndex + 1);
-
231 } else {
executed: }
Execution Count:6048
6048
232 node->type = Node::Leaf;
executed (the execution status of this line is deduced): node->type = Node::Leaf;
-
233 node->leafIndex = leafCnt++;
executed (the execution status of this line is deduced): node->leafIndex = leafCnt++;
-
234 }
executed: }
Execution Count:6245
6245
235} -
236 -
237void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) const -
238{ -
239 if (nodes.isEmpty())
evaluated: nodes.isEmpty()
TRUEFALSE
yes
Evaluation Count:676
yes
Evaluation Count:87266
676-87266
240 return;
executed: return;
Execution Count:676
676
241 -
242 const Node &node = nodes.at(index);
executed (the execution status of this line is deduced): const Node &node = nodes.at(index);
-
243 const int childIndex = firstChildIndex(index);
executed (the execution status of this line is deduced): const int childIndex = firstChildIndex(index);
-
244 -
245 switch (node.type) { -
246 case Node::Leaf: { -
247 visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));
executed (the execution status of this line is deduced): visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));
-
248 break;
executed: break;
Execution Count:39600
39600
249 } -
250 case Node::Vertical: -
251 if (rect.left() < node.offset) {
evaluated: rect.left() < node.offset
TRUEFALSE
yes
Evaluation Count:14394
yes
Evaluation Count:2000
2000-14394
252 climbTree(visitor, rect, childIndex);
executed (the execution status of this line is deduced): climbTree(visitor, rect, childIndex);
-
253 if (rect.right() >= node.offset)
evaluated: rect.right() >= node.offset
TRUEFALSE
yes
Evaluation Count:12066
yes
Evaluation Count:2328
2328-12066
254 climbTree(visitor, rect, childIndex + 1);
executed: climbTree(visitor, rect, childIndex + 1);
Execution Count:12066
12066
255 } else {
executed: }
Execution Count:14394
14394
256 climbTree(visitor, rect, childIndex + 1);
executed (the execution status of this line is deduced): climbTree(visitor, rect, childIndex + 1);
-
257 }
executed: }
Execution Count:2000
2000
258 break;
executed: break;
Execution Count:16394
16394
259 case Node::Horizontal: -
260 if (rect.top() < node.offset) {
evaluated: rect.top() < node.offset
TRUEFALSE
yes
Evaluation Count:28238
yes
Evaluation Count:3034
3034-28238
261 climbTree(visitor, rect, childIndex);
executed (the execution status of this line is deduced): climbTree(visitor, rect, childIndex);
-
262 if (rect.bottom() >= node.offset)
evaluated: rect.bottom() >= node.offset
TRUEFALSE
yes
Evaluation Count:24712
yes
Evaluation Count:3526
3526-24712
263 climbTree(visitor, rect, childIndex + 1);
executed: climbTree(visitor, rect, childIndex + 1);
Execution Count:24712
24712
264 } else {
executed: }
Execution Count:28238
28238
265 climbTree(visitor, rect, childIndex + 1);
executed (the execution status of this line is deduced): climbTree(visitor, rect, childIndex + 1);
-
266 }
executed: }
Execution Count:3034
3034
267 } -
268}
executed: }
Execution Count:87266
87266
269 -
270QRectF QGraphicsSceneBspTree::rectForIndex(int index) const -
271{ -
272 if (index <= 0)
never evaluated: index <= 0
0
273 return rect;
never executed: return rect;
0
274 -
275 int parentIdx = parentIndex(index);
never executed (the execution status of this line is deduced): int parentIdx = parentIndex(index);
-
276 QRectF rect = rectForIndex(parentIdx);
never executed (the execution status of this line is deduced): QRectF rect = rectForIndex(parentIdx);
-
277 const Node *parent = &nodes.at(parentIdx);
never executed (the execution status of this line is deduced): const Node *parent = &nodes.at(parentIdx);
-
278 -
279 if (parent->type == Node::Horizontal) {
never evaluated: parent->type == Node::Horizontal
0
280 if (index & 1)
never evaluated: index & 1
0
281 rect.setRight(parent->offset);
never executed: rect.setRight(parent->offset);
0
282 else -
283 rect.setLeft(parent->offset);
never executed: rect.setLeft(parent->offset);
0
284 } else { -
285 if (index & 1)
never evaluated: index & 1
0
286 rect.setBottom(parent->offset);
never executed: rect.setBottom(parent->offset);
0
287 else -
288 rect.setTop(parent->offset);
never executed: rect.setTop(parent->offset);
0
289 } -
290 -
291 return rect;
never executed: return rect;
0
292} -
293 -
294QT_END_NAMESPACE -
295 -
296#endif // QT_NO_GRAPHICSVIEW -
297 -
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial