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 QGRAPHICSSCENEBSPTREE_P_H 41 #define QGRAPHICSSCENEBSPTREE_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 <QtCore/qlist.h> 56 57 #include <QtCore/qrect.h> 58 #include <QtCore/qset.h> 59 #include <QtCore/qvector.h> 60 61 QT_REQUIRE_CONFIG(graphicsview); 62 63 QT_BEGIN_NAMESPACE 64 65 class QGraphicsItem; 66 class QGraphicsSceneBspTreeVisitor; 67 class QGraphicsSceneInsertItemBspTreeVisitor; 68 class QGraphicsSceneRemoveItemBspTreeVisitor; 69 class QGraphicsSceneFindItemBspTreeVisitor; 70 71 class QGraphicsSceneBspTree 72 { 73 public: 74 struct Node 75 { 76 enum Type { Horizontal, Vertical, Leaf }; 77 union { 78 qreal offset; 79 int leafIndex; 80 }; 81 Type type; 82 }; 83 84 QGraphicsSceneBspTree(); 85 ~QGraphicsSceneBspTree(); 86 87 void initialize(const QRectF &rect, int depth); 88 void clear(); 89 90 void insertItem(QGraphicsItem *item, const QRectF &rect); 91 void removeItem(QGraphicsItem *item, const QRectF &rect); 92 void removeItems(const QSet<QGraphicsItem *> &items); 93 94 QList<QGraphicsItem *> items(const QRectF &rect, bool onlyTopLevelItems = false) const; 95 int leafCount() const; 96 firstChildIndex(int index)97 inline int firstChildIndex(int index) const 98 { return index * 2 + 1; } 99 parentIndex(int index)100 inline int parentIndex(int index) const 101 { return index > 0 ? ((index & 1) ? ((index - 1) / 2) : ((index - 2) / 2)) : -1; } 102 103 QString debug(int index) const; 104 105 private: 106 void initialize(const QRectF &rect, int depth, int index); 107 void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index = 0) const; 108 QRectF rectForIndex(int index) const; 109 110 QVector<Node> nodes; 111 QVector<QList<QGraphicsItem *> > leaves; 112 int leafCnt; 113 QRectF rect; 114 115 QGraphicsSceneInsertItemBspTreeVisitor *insertVisitor; 116 QGraphicsSceneRemoveItemBspTreeVisitor *removeVisitor; 117 QGraphicsSceneFindItemBspTreeVisitor *findVisitor; 118 }; 119 120 class QGraphicsSceneBspTreeVisitor 121 { 122 public: ~QGraphicsSceneBspTreeVisitor()123 virtual ~QGraphicsSceneBspTreeVisitor() { } 124 virtual void visit(QList<QGraphicsItem *> *items) = 0; 125 }; 126 127 QT_END_NAMESPACE 128 129 #endif // QGRAPHICSSCENEBSPTREE_P_H 130