qbsptree.cpp

Absolute File Name:/home/qt/qt5_coco/qt5/qtbase/src/widgets/itemviews/qbsptree.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 "qbsptree_p.h"-
41-
42QT_BEGIN_NAMESPACE-
43-
44QBspTree::QBspTree() : depth(6), visited(0) {}
never executed: end of block
0
45-
46void QBspTree::create(int n, int d)-
47{-
48 // simple heuristics to find the best tree depth-
49 if (d == -1) {
d == -1Description
TRUEnever evaluated
FALSEnever evaluated
0
50 int c;-
51 for (c = 0; n; ++c)
nDescription
TRUEnever evaluated
FALSEnever evaluated
0
52 n = n / 10;
never executed: n = n / 10;
0
53 depth = c << 1;-
54 } else {
never executed: end of block
0
55 depth = d;-
56 }
never executed: end of block
0
57 depth = qMax(depth, uint(1));-
58-
59 nodes.resize((1 << depth) - 1); // resize to number of nodes-
60 leaves.resize(1 << depth); // resize to number of leaves-
61}
never executed: end of block
0
62-
63void QBspTree::destroy()-
64{-
65 leaves.clear();-
66 nodes.clear();-
67}
never executed: end of block
0
68-
69void QBspTree::climbTree(const QRect &rect, callback *function, QBspTreeData data)-
70{-
71 if (nodes.isEmpty())
nodes.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
0
72 return;
never executed: return;
0
73 ++visited;-
74 climbTree(rect, function, data, 0);-
75}
never executed: end of block
0
76-
77void QBspTree::climbTree(const QRect &area, callback *function, QBspTreeData data, int index)-
78{-
79 if (index >= nodes.count()) { // the index points to a leaf
index >= nodes.count()Description
TRUEnever evaluated
FALSEnever evaluated
0
80 Q_ASSERT(!nodes.isEmpty());-
81 function(leaf(index - nodes.count()), area, visited, data);-
82 return;
never executed: return;
0
83 }-
84-
85 Node::Type t = (Node::Type) nodes.at(index).type;-
86-
87 int pos = nodes.at(index).pos;-
88 int idx = firstChildIndex(index);-
89 if (t == Node::VerticalPlane) {
t == Node::VerticalPlaneDescription
TRUEnever evaluated
FALSEnever evaluated
0
90 if (area.left() < pos)
area.left() < posDescription
TRUEnever evaluated
FALSEnever evaluated
0
91 climbTree(area, function, data, idx); // back
never executed: climbTree(area, function, data, idx);
0
92 if (area.right() >= pos)
area.right() >= posDescription
TRUEnever evaluated
FALSEnever evaluated
0
93 climbTree(area, function, data, idx + 1); // front
never executed: climbTree(area, function, data, idx + 1);
0
94 } else {
never executed: end of block
0
95 if (area.top() < pos)
area.top() < posDescription
TRUEnever evaluated
FALSEnever evaluated
0
96 climbTree(area, function, data, idx); // back
never executed: climbTree(area, function, data, idx);
0
97 if (area.bottom() >= pos)
area.bottom() >= posDescription
TRUEnever evaluated
FALSEnever evaluated
0
98 climbTree(area, function, data, idx + 1); // front
never executed: climbTree(area, function, data, idx + 1);
0
99 }
never executed: end of block
0
100}-
101-
102void QBspTree::init(const QRect &area, int depth, NodeType type, int index)-
103{-
104 Node::Type t = Node::None; // t should never have this value-
105 if (type == Node::Both) // if both planes are specified, use 2d bsp
type == Node::BothDescription
TRUEnever evaluated
FALSEnever evaluated
0
106 t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;
never executed: t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;
(depth & 1)Description
TRUEnever evaluated
FALSEnever evaluated
0
107 else-
108 t = type;
never executed: t = type;
0
109 QPoint center = area.center();-
110 nodes[index].pos = (t == Node::VerticalPlane ? center.x() : center.y());
t == Node::VerticalPlaneDescription
TRUEnever evaluated
FALSEnever evaluated
0
111 nodes[index].type = t;-
112-
113 QRect front = area;-
114 QRect back = area;-
115-
116 if (t == Node::VerticalPlane) {
t == Node::VerticalPlaneDescription
TRUEnever evaluated
FALSEnever evaluated
0
117 front.setLeft(center.x());-
118 back.setRight(center.x() - 1); // front includes the center-
119 } else { // t == Node::HorizontalPlane
never executed: end of block
0
120 front.setTop(center.y());-
121 back.setBottom(center.y() - 1);-
122 }
never executed: end of block
0
123-
124 int idx = firstChildIndex(index);-
125 if (--depth) {
--depthDescription
TRUEnever evaluated
FALSEnever evaluated
0
126 init(back, depth, type, idx);-
127 init(front, depth, type, idx + 1);-
128 }
never executed: end of block
0
129}
never executed: end of block
0
130-
131void QBspTree::insert(QVector<int> &leaf, const QRect &, uint, QBspTreeData data)-
132{-
133 leaf.append(data.i);-
134}
never executed: end of block
0
135-
136void QBspTree::remove(QVector<int> &leaf, const QRect &, uint, QBspTreeData data)-
137{-
138 int i = leaf.indexOf(data.i);-
139 if (i != -1)
i != -1Description
TRUEnever evaluated
FALSEnever evaluated
0
140 leaf.remove(i);
never executed: leaf.remove(i);
0
141}
never executed: end of block
0
142-
143QT_END_NAMESPACE-
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9