graphicsview/qgraphicsscene_bsp.cpp

Switch to Source codePreprocessed file
LineSource CodeCoverage
1 -
2 -
3 -
4 -
5 -
6 -
7class QGraphicsSceneInsertItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor -
8{ -
9public: -
10 QGraphicsItem *item; -
11 -
12 void visit(QList<QGraphicsItem *> *items) -
13 { items->prepend(item); }
executed: }
Execution Count:8855
8855
14}; -
15 -
16class QGraphicsSceneRemoveItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor -
17{ -
18public: -
19 QGraphicsItem *item; -
20 -
21 void visit(QList<QGraphicsItem *> *items) -
22 { items->removeAll(item); }
executed: }
Execution Count:2135
2135
23}; -
24 -
25class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor -
26{ -
27public: -
28 QList<QGraphicsItem *> *foundItems; -
29 bool onlyTopLevelItems; -
30 -
31 void visit(QList<QGraphicsItem *> *items) -
32 { -
33 for (int i = 0; i < items->size(); ++i) {
evaluated: i < items->size()
TRUEFALSE
yes
Evaluation Count:27953
yes
Evaluation Count:28610
27953-28610
34 QGraphicsItem *item = items->at(i); -
35 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
36 item = item->topLevelItem();
executed: item = item->topLevelItem();
Execution Count:2548
2548
37 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
38 item->d_func()->itemDiscovered = 1; -
39 foundItems->prepend(item); -
40 }
executed: }
Execution Count:4390
4390
41 }
executed: }
Execution Count:27953
27953
42 }
executed: }
Execution Count:28610
28610
43}; -
44 -
45QGraphicsSceneBspTree::QGraphicsSceneBspTree() -
46 : leafCnt(0) -
47{ -
48 insertVisitor = new QGraphicsSceneInsertItemBspTreeVisitor; -
49 removeVisitor = new QGraphicsSceneRemoveItemBspTreeVisitor; -
50 findVisitor = new QGraphicsSceneFindItemBspTreeVisitor; -
51}
executed: }
Execution Count:798
798
52 -
53QGraphicsSceneBspTree::~QGraphicsSceneBspTree() -
54{ -
55 delete insertVisitor; -
56 delete removeVisitor; -
57 delete findVisitor; -
58}
executed: }
Execution Count:779
779
59 -
60void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth) -
61{ -
62 this->rect = rect; -
63 leafCnt = 0; -
64 nodes.resize((1 << (depth + 1)) - 1); -
65 nodes.fill(Node()); -
66 leaves.resize(1 << depth); -
67 leaves.fill(QList<QGraphicsItem *>()); -
68 -
69 initialize(rect, depth, 0); -
70}
executed: }
Execution Count:197
197
71 -
72void QGraphicsSceneBspTree::clear() -
73{ -
74 leafCnt = 0; -
75 nodes.clear(); -
76 leaves.clear(); -
77}
executed: }
Execution Count:779
779
78 -
79void QGraphicsSceneBspTree::insertItem(QGraphicsItem *item, const QRectF &rect) -
80{ -
81 insertVisitor->item = item; -
82 climbTree(insertVisitor, rect); -
83}
executed: }
Execution Count:796
796
84 -
85void QGraphicsSceneBspTree::removeItem(QGraphicsItem *item, const QRectF &rect) -
86{ -
87 removeVisitor->item = item; -
88 climbTree(removeVisitor, rect); -
89}
executed: }
Execution Count:260
260
90 -
91void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items) -
92{ -
93 for (int i = 0; i < leaves.size(); ++i) {
evaluated: i < leaves.size()
TRUEFALSE
yes
Evaluation Count:64
yes
Evaluation Count:2
2-64
94 QList<QGraphicsItem *> newItemList; -
95 const QList<QGraphicsItem *> &oldItemList = leaves[i]; -
96 for (int j = 0; j < oldItemList.size(); ++j) {
evaluated: j < oldItemList.size()
TRUEFALSE
yes
Evaluation Count:112
yes
Evaluation Count:64
64-112
97 QGraphicsItem *item = oldItemList.at(j); -
98 if (!items.contains(item))
partially evaluated: !items.contains(item)
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:112
0-112
99 newItemList << item;
never executed: newItemList << item;
0
100 }
executed: }
Execution Count:112
112
101 leaves[i] = newItemList; -
102 }
executed: }
Execution Count:64
64
103}
executed: }
Execution Count:2
2
104 -
105QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const -
106{ -
107 QList<QGraphicsItem *> tmp; -
108 findVisitor->foundItems = &tmp; -
109 findVisitor->onlyTopLevelItems = onlyTopLevelItems; -
110 climbTree(findVisitor, rect); -
111 -
112 for (int i = 0; i < tmp.size(); ++i)
evaluated: i < tmp.size()
TRUEFALSE
yes
Evaluation Count:4390
yes
Evaluation Count:2442
2442-4390
113 tmp.at(i)->d_ptr->itemDiscovered = 0;
executed: tmp.at(i)->d_ptr->itemDiscovered = 0;
Execution Count:4390
4390
114 return tmp;
executed: return tmp;
Execution Count:2442
2442
115} -
116 -
117int QGraphicsSceneBspTree::leafCount() const -
118{ -
119 return leafCnt;
executed: return leafCnt;
Execution Count:178
178
120} -
121 -
122QString QGraphicsSceneBspTree::debug(int index) const -
123{ -
124 const Node *node = &nodes.at(index); -
125 -
126 QString tmp; -
127 if (node->type == Node::Leaf) {
never evaluated: node->type == Node::Leaf
0
128 QRectF rect = rectForIndex(index); -
129 if (!leaves[node->leafIndex].isEmpty()) {
never evaluated: !leaves[node->leafIndex].isEmpty()
0
130 tmp += QString::fromLatin1("[%1, %2, %3, %4] contains %5 items\n") -
131 .arg(rect.left()).arg(rect.top()) -
132 .arg(rect.width()).arg(rect.height()) -
133 .arg(leaves[node->leafIndex].size()); -
134 }
never executed: }
0
135 } else {
never executed: }
0
136 if (node->type == Node::Horizontal) {
never evaluated: node->type == Node::Horizontal
0
137 tmp += debug(firstChildIndex(index)); -
138 tmp += debug(firstChildIndex(index) + 1); -
139 } else {
never executed: }
0
140 tmp += debug(firstChildIndex(index)); -
141 tmp += debug(firstChildIndex(index) + 1); -
142 }
never executed: }
0
143 } -
144 -
145 return tmp;
never executed: return tmp;
0
146} -
147 -
148void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index) -
149{ -
150 Node *node = &nodes[index]; -
151 if (index == 0) {
evaluated: index == 0
TRUEFALSE
yes
Evaluation Count:197
yes
Evaluation Count:12096
197-12096
152 node->type = Node::Horizontal; -
153 node->offset = rect.center().x(); -
154 }
executed: }
Execution Count:197
197
155 -
156 if (depth) {
evaluated: depth
TRUEFALSE
yes
Evaluation Count:6048
yes
Evaluation Count:6245
6048-6245
157 Node::Type type; -
158 QRectF rect1, rect2; -
159 qreal offset1, offset2; -
160 -
161 if (node->type == Node::Horizontal) {
evaluated: node->type == Node::Horizontal
TRUEFALSE
yes
Evaluation Count:4096
yes
Evaluation Count:1952
1952-4096
162 type = Node::Vertical; -
163 rect1.setRect(rect.left(), rect.top(), rect.width(), rect.height() / 2); -
164 rect2.setRect(rect1.left(), rect1.bottom(), rect1.width(), rect.height() - rect1.height()); -
165 offset1 = rect1.center().x(); -
166 offset2 = rect2.center().x(); -
167 } else {
executed: }
Execution Count:4096
4096
168 type = Node::Horizontal; -
169 rect1.setRect(rect.left(), rect.top(), rect.width() / 2, rect.height()); -
170 rect2.setRect(rect1.right(), rect1.top(), rect.width() - rect1.width(), rect1.height()); -
171 offset1 = rect1.center().y(); -
172 offset2 = rect2.center().y(); -
173 }
executed: }
Execution Count:1952
1952
174 -
175 int childIndex = firstChildIndex(index); -
176 -
177 Node *child = &nodes[childIndex]; -
178 child->offset = offset1; -
179 child->type = type; -
180 -
181 child = &nodes[childIndex + 1]; -
182 child->offset = offset2; -
183 child->type = type; -
184 -
185 initialize(rect1, depth - 1, childIndex); -
186 initialize(rect2, depth - 1, childIndex + 1); -
187 } else {
executed: }
Execution Count:6048
6048
188 node->type = Node::Leaf; -
189 node->leafIndex = leafCnt++; -
190 }
executed: }
Execution Count:6245
6245
191} -
192 -
193void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) const -
194{ -
195 if (nodes.isEmpty())
evaluated: nodes.isEmpty()
TRUEFALSE
yes
Evaluation Count:676
yes
Evaluation Count:87266
676-87266
196 return;
executed: return;
Execution Count:676
676
197 -
198 const Node &node = nodes.at(index); -
199 const int childIndex = firstChildIndex(index); -
200 -
201 switch (node.type) { -
202 case Node::Leaf: { -
203 visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex])); -
204 break;
executed: break;
Execution Count:39600
39600
205 } -
206 case Node::Vertical: -
207 if (rect.left() < node.offset) {
evaluated: rect.left() < node.offset
TRUEFALSE
yes
Evaluation Count:14394
yes
Evaluation Count:2000
2000-14394
208 climbTree(visitor, rect, childIndex); -
209 if (rect.right() >= node.offset)
evaluated: rect.right() >= node.offset
TRUEFALSE
yes
Evaluation Count:12066
yes
Evaluation Count:2328
2328-12066
210 climbTree(visitor, rect, childIndex + 1);
executed: climbTree(visitor, rect, childIndex + 1);
Execution Count:12066
12066
211 } else {
executed: }
Execution Count:14394
14394
212 climbTree(visitor, rect, childIndex + 1); -
213 }
executed: }
Execution Count:2000
2000
214 break;
executed: break;
Execution Count:16394
16394
215 case Node::Horizontal: -
216 if (rect.top() < node.offset) {
evaluated: rect.top() < node.offset
TRUEFALSE
yes
Evaluation Count:28238
yes
Evaluation Count:3034
3034-28238
217 climbTree(visitor, rect, childIndex); -
218 if (rect.bottom() >= node.offset)
evaluated: rect.bottom() >= node.offset
TRUEFALSE
yes
Evaluation Count:24712
yes
Evaluation Count:3526
3526-24712
219 climbTree(visitor, rect, childIndex + 1);
executed: climbTree(visitor, rect, childIndex + 1);
Execution Count:24712
24712
220 } else {
executed: }
Execution Count:28238
28238
221 climbTree(visitor, rect, childIndex + 1); -
222 }
executed: }
Execution Count:3034
3034
223 } -
224}
executed: }
Execution Count:87266
87266
225 -
226QRectF QGraphicsSceneBspTree::rectForIndex(int index) const -
227{ -
228 if (index <= 0)
never evaluated: index <= 0
0
229 return rect;
never executed: return rect;
0
230 -
231 int parentIdx = parentIndex(index); -
232 QRectF rect = rectForIndex(parentIdx); -
233 const Node *parent = &nodes.at(parentIdx); -
234 -
235 if (parent->type == Node::Horizontal) {
never evaluated: parent->type == Node::Horizontal
0
236 if (index & 1)
never evaluated: index & 1
0
237 rect.setRight(parent->offset);
never executed: rect.setRight(parent->offset);
0
238 else -
239 rect.setLeft(parent->offset);
never executed: rect.setLeft(parent->offset);
0
240 } else { -
241 if (index & 1)
never evaluated: index & 1
0
242 rect.setBottom(parent->offset);
never executed: rect.setBottom(parent->offset);
0
243 else -
244 rect.setTop(parent->offset);
never executed: rect.setTop(parent->offset);
0
245 } -
246 -
247 return rect;
never executed: return rect;
0
248} -
249 -
250 -
251 -
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial