itemviews/qbsptree.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 "qbsptree_p.h" -
43 -
44QT_BEGIN_NAMESPACE -
45 -
46QBspTree::QBspTree() : depth(6), visited(0) {}
executed: }
Execution Count:16
16
47 -
48void QBspTree::create(int n, int d) -
49{ -
50 // simple heuristics to find the best tree depth -
51 if (d == -1) {
partially evaluated: d == -1
TRUEFALSE
yes
Evaluation Count:15
no
Evaluation Count:0
0-15
52 int c;
executed (the execution status of this line is deduced): int c;
-
53 for (c = 0; n; ++c)
evaluated: n
TRUEFALSE
yes
Evaluation Count:20
yes
Evaluation Count:15
15-20
54 n = n / 10;
executed: n = n / 10;
Execution Count:20
20
55 depth = c << 1;
executed (the execution status of this line is deduced): depth = c << 1;
-
56 } else {
executed: }
Execution Count:15
15
57 depth = d;
never executed (the execution status of this line is deduced): depth = d;
-
58 }
never executed: }
0
59 depth = qMax(depth, uint(1));
executed (the execution status of this line is deduced): depth = qMax(depth, uint(1));
-
60 -
61 nodes.resize((1 << depth) - 1); // resize to number of nodes
executed (the execution status of this line is deduced): nodes.resize((1 << depth) - 1);
-
62 leaves.resize(1 << depth); // resize to number of leaves
executed (the execution status of this line is deduced): leaves.resize(1 << depth);
-
63}
executed: }
Execution Count:15
15
64 -
65void QBspTree::destroy() -
66{ -
67 leaves.clear();
executed (the execution status of this line is deduced): leaves.clear();
-
68 nodes.clear();
executed (the execution status of this line is deduced): nodes.clear();
-
69}
executed: }
Execution Count:247
247
70 -
71void QBspTree::climbTree(const QRect &rect, callback *function, QBspTreeData data) -
72{ -
73 if (nodes.isEmpty())
partially evaluated: nodes.isEmpty()
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:168
0-168
74 return;
never executed: return;
0
75 ++visited;
executed (the execution status of this line is deduced): ++visited;
-
76 climbTree(rect, function, data, 0);
executed (the execution status of this line is deduced): climbTree(rect, function, data, 0);
-
77}
executed: }
Execution Count:168
168
78 -
79void QBspTree::climbTree(const QRect &area, callback *function, QBspTreeData data, int index) -
80{ -
81 if (index >= nodes.count()) { // the index points to a leaf
evaluated: index >= nodes.count()
TRUEFALSE
yes
Evaluation Count:1213
yes
Evaluation Count:2851
1213-2851
82 Q_ASSERT(!nodes.isEmpty());
executed (the execution status of this line is deduced): qt_noop();
-
83 function(leaf(index - nodes.count()), area, visited, data);
executed (the execution status of this line is deduced): function(leaf(index - nodes.count()), area, visited, data);
-
84 return;
executed: return;
Execution Count:1213
1213
85 } -
86 -
87 Node::Type t = (Node::Type) nodes.at(index).type;
executed (the execution status of this line is deduced): Node::Type t = (Node::Type) nodes.at(index).type;
-
88 -
89 int pos = nodes.at(index).pos;
executed (the execution status of this line is deduced): int pos = nodes.at(index).pos;
-
90 int idx = firstChildIndex(index);
executed (the execution status of this line is deduced): int idx = firstChildIndex(index);
-
91 if (t == Node::VerticalPlane) {
evaluated: t == Node::VerticalPlane
TRUEFALSE
yes
Evaluation Count:1184
yes
Evaluation Count:1667
1184-1667
92 if (area.left() < pos)
evaluated: area.left() < pos
TRUEFALSE
yes
Evaluation Count:863
yes
Evaluation Count:321
321-863
93 climbTree(area, function, data, idx); // back
executed: climbTree(area, function, data, idx);
Execution Count:863
863
94 if (area.right() >= pos)
evaluated: area.right() >= pos
TRUEFALSE
yes
Evaluation Count:546
yes
Evaluation Count:638
546-638
95 climbTree(area, function, data, idx + 1); // front
executed: climbTree(area, function, data, idx + 1);
Execution Count:546
546
96 } else {
executed: }
Execution Count:1184
1184
97 if (area.top() < pos)
evaluated: area.top() < pos
TRUEFALSE
yes
Evaluation Count:1226
yes
Evaluation Count:441
441-1226
98 climbTree(area, function, data, idx); // back
executed: climbTree(area, function, data, idx);
Execution Count:1226
1226
99 if (area.bottom() >= pos)
evaluated: area.bottom() >= pos
TRUEFALSE
yes
Evaluation Count:734
yes
Evaluation Count:933
734-933
100 climbTree(area, function, data, idx + 1); // front
executed: climbTree(area, function, data, idx + 1);
Execution Count:734
734
101 }
executed: }
Execution Count:1667
1667
102} -
103 -
104void QBspTree::init(const QRect &area, int depth, NodeType type, int index) -
105{ -
106 Node::Type t = Node::None; // t should never have this value
executed (the execution status of this line is deduced): Node::Type t = Node::None;
-
107 if (type == Node::Both) // if both planes are specified, use 2d bsp
evaluated: type == Node::Both
TRUEFALSE
yes
Evaluation Count:142
yes
Evaluation Count:27
27-142
108 t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;
executed: t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;
Execution Count:142
evaluated: (depth & 1)
TRUEFALSE
yes
Evaluation Count:95
yes
Evaluation Count:47
47-142
109 else -
110 t = type;
executed: t = type;
Execution Count:27
27
111 QPoint center = area.center();
executed (the execution status of this line is deduced): QPoint center = area.center();
-
112 nodes[index].pos = (t == Node::VerticalPlane ? center.x() : center.y());
evaluated: t == Node::VerticalPlane
TRUEFALSE
yes
Evaluation Count:50
yes
Evaluation Count:119
50-119
113 nodes[index].type = t;
executed (the execution status of this line is deduced): nodes[index].type = t;
-
114 -
115 QRect front = area;
executed (the execution status of this line is deduced): QRect front = area;
-
116 QRect back = area;
executed (the execution status of this line is deduced): QRect back = area;
-
117 -
118 if (t == Node::VerticalPlane) {
evaluated: t == Node::VerticalPlane
TRUEFALSE
yes
Evaluation Count:50
yes
Evaluation Count:119
50-119
119 front.setLeft(center.x());
executed (the execution status of this line is deduced): front.setLeft(center.x());
-
120 back.setRight(center.x() - 1); // front includes the center
executed (the execution status of this line is deduced): back.setRight(center.x() - 1);
-
121 } else { // t == Node::HorizontalPlane
executed: }
Execution Count:50
50
122 front.setTop(center.y());
executed (the execution status of this line is deduced): front.setTop(center.y());
-
123 back.setBottom(center.y() - 1);
executed (the execution status of this line is deduced): back.setBottom(center.y() - 1);
-
124 }
executed: }
Execution Count:119
119
125 -
126 int idx = firstChildIndex(index);
executed (the execution status of this line is deduced): int idx = firstChildIndex(index);
-
127 if (--depth) {
evaluated: --depth
TRUEFALSE
yes
Evaluation Count:76
yes
Evaluation Count:93
76-93
128 init(back, depth, type, idx);
executed (the execution status of this line is deduced): init(back, depth, type, idx);
-
129 init(front, depth, type, idx + 1);
executed (the execution status of this line is deduced): init(front, depth, type, idx + 1);
-
130 }
executed: }
Execution Count:76
76
131}
executed: }
Execution Count:169
169
132 -
133void QBspTree::insert(QVector<int> &leaf, const QRect &, uint, QBspTreeData data) -
134{ -
135 leaf.append(data.i);
executed (the execution status of this line is deduced): leaf.append(data.i);
-
136}
executed: }
Execution Count:872
872
137 -
138void QBspTree::remove(QVector<int> &leaf, const QRect &, uint, QBspTreeData data) -
139{ -
140 int i = leaf.indexOf(data.i);
executed (the execution status of this line is deduced): int i = leaf.indexOf(data.i);
-
141 if (i != -1)
partially evaluated: i != -1
TRUEFALSE
yes
Evaluation Count:11
no
Evaluation Count:0
0-11
142 leaf.remove(i);
executed: leaf.remove(i);
Execution Count:11
11
143}
executed: }
Execution Count:11
11
144 -
145QT_END_NAMESPACE -
146 -
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial