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#ifndef QBSPTREE_P_H
5#define QBSPTREE_P_H
6
7//
8// W A R N I N G
9// -------------
10//
11// This file is not part of the Qt API. It exists for the convenience
12// of other Qt classes. This header file may change from version to
13// version without notice, or even be removed.
14//
15// We mean it.
16//
17
18#include <QtWidgets/private/qtwidgetsglobal_p.h>
19#include <qlist.h>
20#include <qrect.h>
21
22QT_BEGIN_NAMESPACE
23
24class QBspTree
25{
26public:
27
28 struct Node
29 {
30 enum Type { None = 0, VerticalPlane = 1, HorizontalPlane = 2, Both = 3 };
31 inline Node() : pos(0), type(None) {}
32 int pos;
33 Type type;
34 };
35 typedef Node::Type NodeType;
36
37 struct Data
38 {
39 Data(void *p) : ptr(p) {}
40 Data(int n) : i(n) {}
41 union {
42 void *ptr;
43 int i;
44 };
45 };
46 typedef QBspTree::Data QBspTreeData;
47 typedef void callback(QList<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
48
49 QBspTree();
50
51 void create(int n, int d = -1);
52 void destroy();
53
54 inline void init(const QRect &area, NodeType type) { init(area, depth, type, index: 0); }
55
56 void climbTree(const QRect &rect, callback *function, QBspTreeData data);
57
58 inline int leafCount() const { return leaves.size(); }
59 inline QList<int> &leaf(int i) { return leaves[i]; }
60 inline void insertLeaf(const QRect &r, int i) { climbTree(rect: r, function: &insert, data: i, index: 0); }
61 inline void removeLeaf(const QRect &r, int i) { climbTree(rect: r, function: &remove, data: i, index: 0); }
62
63protected:
64 void init(const QRect &area, int depth, NodeType type, int index);
65 void climbTree(const QRect &rect, callback *function, QBspTreeData data, int index);
66
67 inline int parentIndex(int i) const { return (i & 1) ? ((i - 1) / 2) : ((i - 2) / 2); }
68 inline int firstChildIndex(int i) const { return ((i * 2) + 1); }
69
70 static void insert(QList<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
71 static void remove(QList<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
72
73private:
74 uint depth;
75 mutable uint visited;
76 QList<Node> nodes;
77 mutable QList<QList<int>> leaves; // the leaves are just indices into the items
78};
79
80QT_END_NAMESPACE
81
82#endif // QBSPTREE_P_H
83

source code of qtbase/src/widgets/itemviews/qbsptree_p.h