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 #ifndef QBSPTREE_P_H
41 #define QBSPTREE_P_H
42 
43 //
44 //  W A R N I N G
45 //  -------------
46 //
47 // This file is not part of the Qt API.  It exists for the convenience
48 // of other Qt classes.  This header file may change from version to
49 // version without notice, or even be removed.
50 //
51 // We mean it.
52 //
53 
54 #include <QtWidgets/private/qtwidgetsglobal_p.h>
55 #include <qvector.h>
56 #include <qrect.h>
57 
58 QT_BEGIN_NAMESPACE
59 
60 class QBspTree
61 {
62 public:
63 
64     struct Node
65     {
66         enum Type { None = 0, VerticalPlane = 1, HorizontalPlane = 2, Both = 3 };
NodeNode67         inline Node() : pos(0), type(None) {}
68         int pos;
69         Type type;
70     };
71     typedef Node::Type NodeType;
72 
73     struct Data
74     {
DataData75         Data(void *p) : ptr(p) {}
DataData76         Data(int n) : i(n) {}
77         union {
78             void *ptr;
79             int i;
80         };
81     };
82     typedef QBspTree::Data QBspTreeData;
83     typedef void callback(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
84 
85     QBspTree();
86 
87     void create(int n, int d = -1);
88     void destroy();
89 
init(const QRect & area,NodeType type)90     inline void init(const QRect &area, NodeType type) { init(area, depth, type, 0); }
91 
92     void climbTree(const QRect &rect, callback *function, QBspTreeData data);
93 
leafCount()94     inline int leafCount() const { return leaves.count(); }
leaf(int i)95     inline QVector<int> &leaf(int i) { return leaves[i]; }
insertLeaf(const QRect & r,int i)96     inline void insertLeaf(const QRect &r, int i) { climbTree(r, &insert, i, 0); }
removeLeaf(const QRect & r,int i)97     inline void removeLeaf(const QRect &r, int i) { climbTree(r, &remove, i, 0); }
98 
99 protected:
100     void init(const QRect &area, int depth, NodeType type, int index);
101     void climbTree(const QRect &rect, callback *function, QBspTreeData data, int index);
102 
parentIndex(int i)103     inline int parentIndex(int i) const { return (i & 1) ? ((i - 1) / 2) : ((i - 2) / 2); }
firstChildIndex(int i)104     inline int firstChildIndex(int i) const { return ((i * 2) + 1); }
105 
106     static void insert(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
107     static void remove(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);
108 
109 private:
110     uint depth;
111     mutable uint visited;
112     QVector<Node> nodes;
113     mutable QVector< QVector<int> > leaves; // the leaves are just indices into the items
114 };
115 
116 QT_END_NAMESPACE
117 
118 #endif // QBSPTREE_P_H
119