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