1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#include "qbsptree_p.h"
5
6QT_BEGIN_NAMESPACE
7
8QBspTree::QBspTree() : depth(6), visited(0) {}
9
10void QBspTree::create(int n, int d)
11{
12 // simple heuristics to find the best tree depth
13 if (d == -1) {
14 int c;
15 for (c = 0; n; ++c)
16 n = n / 10;
17 depth = c << 1;
18 } else {
19 depth = d;
20 }
21 depth = qMax(a: depth, b: uint(1));
22
23 nodes.resize(size: (1ll << depth) - 1); // resize to number of nodes
24 leaves.resize(size: 1ll << depth); // resize to number of leaves
25}
26
27void QBspTree::destroy()
28{
29 leaves.clear();
30 nodes.clear();
31}
32
33void QBspTree::climbTree(const QRect &rect, callback *function, QBspTreeData data)
34{
35 if (nodes.isEmpty())
36 return;
37 ++visited;
38 climbTree(rect, function, data, index: 0);
39}
40
41void QBspTree::climbTree(const QRect &area, callback *function, QBspTreeData data, int index)
42{
43 if (index >= nodes.size()) { // the index points to a leaf
44 Q_ASSERT(!nodes.isEmpty());
45 function(leaf(i: index - nodes.size()), area, visited, data);
46 return;
47 }
48
49 Node::Type t = (Node::Type) nodes.at(i: index).type;
50
51 int pos = nodes.at(i: index).pos;
52 int idx = firstChildIndex(i: index);
53 if (t == Node::VerticalPlane) {
54 if (area.left() < pos)
55 climbTree(area, function, data, index: idx); // back
56 if (area.right() >= pos)
57 climbTree(area, function, data, index: idx + 1); // front
58 } else {
59 if (area.top() < pos)
60 climbTree(area, function, data, index: idx); // back
61 if (area.bottom() >= pos)
62 climbTree(area, function, data, index: idx + 1); // front
63 }
64}
65
66void QBspTree::init(const QRect &area, int depth, NodeType type, int index)
67{
68 Node::Type t = Node::None; // t should never have this value
69 if (type == Node::Both) // if both planes are specified, use 2d bsp
70 t = (depth & 1) ? Node::HorizontalPlane : Node::VerticalPlane;
71 else
72 t = type;
73 QPoint center = area.center();
74 nodes[index].pos = (t == Node::VerticalPlane ? center.x() : center.y());
75 nodes[index].type = t;
76
77 QRect front = area;
78 QRect back = area;
79
80 if (t == Node::VerticalPlane) {
81 front.setLeft(center.x());
82 back.setRight(center.x() - 1); // front includes the center
83 } else { // t == Node::HorizontalPlane
84 front.setTop(center.y());
85 back.setBottom(center.y() - 1);
86 }
87
88 int idx = firstChildIndex(i: index);
89 if (--depth) {
90 init(area: back, depth, type, index: idx);
91 init(area: front, depth, type, index: idx + 1);
92 }
93}
94
95void QBspTree::insert(QList<int> &leaf, const QRect &, uint, QBspTreeData data)
96{
97 leaf.append(t: data.i);
98}
99
100void QBspTree::remove(QList<int> &leaf, const QRect &, uint, QBspTreeData data)
101{
102 int i = leaf.indexOf(t: data.i);
103 if (i != -1)
104 leaf.remove(i);
105}
106
107QT_END_NAMESPACE
108

source code of qtbase/src/widgets/itemviews/qbsptree.cpp