1 /****************************************************************************

     2 **

     3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

     4 ** All rights reserved.

     5 ** Contact: Nokia Corporation (qt-info@nokia.com)

     6 **

     7 ** This file is part of the QtGui module of the Qt Toolkit.

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

    11 ** This file contains pre-release code and may not be distributed.

    12 ** You may use this file in accordance with the terms and conditions

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

    17 ** Alternatively, this file may be used under the terms of the GNU Lesser

    18 ** General Public License version 2.1 as published by the Free Software

    19 ** Foundation and appearing in the file LICENSE.LGPL included in the

    20 ** packaging of this file.  Please review the following information to

    21 ** ensure the GNU Lesser General Public License version 2.1 requirements

    22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

    23 **

    24 ** In addition, as a special exception, Nokia gives you certain additional

    25 ** rights.  These rights are described in the Nokia Qt LGPL Exception

    26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

    27 **

    28 ** If you have questions regarding the use of this file, please contact

    29 ** Nokia at qt-info@nokia.com.

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 #ifndef QBSPTREE_P_H

    43 #define QBSPTREE_P_H

    44 

    45 //

    46 //  W A R N I N G

    47 //  -------------

    48 //

    49 // This file is not part of the Qt API.  It exists for the convenience

    50 // of other Qt classes.  This header file may change from version to

    51 // version without notice, or even be removed.

    52 //

    53 // We mean it.

    54 //

    55 

    56 #include <qvector.h>

    57 #include <qrect.h>

    58 

    59 QT_BEGIN_NAMESPACE

    60 

    61 class QBspTree

    62 {

    63 public:

    64 

    65     struct Node

    66     {

    67         enum Type { None = 0, VerticalPlane = 1, HorizontalPlane = 2, Both = 3 };

    68         inline Node() : pos(0), type(None) {}

    69         int pos;

    70         Type type;

    71     };

    72     typedef Node::Type NodeType;

    73 

    74     struct Data

    75     {

    76         Data(void *p) : ptr(p) {}

    77         Data(int n) : i(n) {}

    78         union {

    79             void *ptr;

    80             int i;

    81         };

    82     };

    83     typedef QBspTree::Data QBspTreeData;

    84     typedef void callback(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);

    85 

    86     QBspTree();

    87 

    88     void create(int n, int d = -1);

    89     void destroy();

    90 

    91     inline void init(const QRect &area, NodeType type) { init(area, depth, type, 0); }

    92 

    93     void climbTree(const QRect &rect, callback *function, QBspTreeData data);

    94 

    95     inline int leafCount() const { return leaves.count(); }

    96     inline QVector<int> &leaf(int i) { return leaves[i]; }

    97     inline void insertLeaf(const QRect &r, int i) { climbTree(r, &insert, i, 0); }

    98     inline void removeLeaf(const QRect &r, int i) { climbTree(r, &remove, i, 0); }

    99 

   100 protected:

   101     void init(const QRect &area, int depth, NodeType type, int index);

   102     void climbTree(const QRect &rect, callback *function, QBspTreeData data, int index);

   103 

   104     inline int parentIndex(int i) const { return (i & 1) ? ((i - 1) / 2) : ((i - 2) / 2); }

   105     inline int firstChildIndex(int i) const { return ((i * 2) + 1); }

   106 

   107     static void insert(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);

   108     static void remove(QVector<int> &leaf, const QRect &area, uint visited, QBspTreeData data);

   109 

   110 private:

   111     uint depth;

   112     mutable uint visited;

   113     QVector<Node> nodes;

   114     mutable QVector< QVector<int> > leaves; // the leaves are just indices into the items

   115 };

   116 

   117 QT_END_NAMESPACE

   118 

   119 #endif // QBSPTREE_P_H