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 QtCore 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 //

    43 //  W A R N I N G

    44 //  -------------

    45 //

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

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

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

    49 //

    50 // We mean it.

    51 //

    52 

    53 #ifndef QGRAPHICSBSPTREEINDEX_H

    54 #define QGRAPHICSBSPTREEINDEX_H

    55 

    56 #include <QtCore/qglobal.h>

    57 

    58 #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW

    59 

    60 #include "qgraphicssceneindex_p.h"

    61 #include "qgraphicsitem_p.h"

    62 #include "qgraphicsscene_bsp_p.h"

    63 

    64 #include <QtCore/qrect.h>

    65 #include <QtCore/qlist.h>

    66 

    67 QT_BEGIN_NAMESPACE

    68 

    69 static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;

    70 

    71 class QGraphicsScene;

    72 class QGraphicsSceneBspTreeIndexPrivate;

    73 

    74 class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex

    75 {

    76     Q_OBJECT

    77     Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth)

    78 public:

    79     QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0);

    80     ~QGraphicsSceneBspTreeIndex();

    81 

    82     QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const;

    83     QList<QGraphicsItem *> estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const;

    84     QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const;

    85 

    86     int bspTreeDepth();

    87     void setBspTreeDepth(int depth);

    88 

    89 protected Q_SLOTS:

    90     void updateSceneRect(const QRectF &rect);

    91 

    92 protected:

    93     bool event(QEvent *event);

    94     void clear();

    95 

    96     void addItem(QGraphicsItem *item);

    97     void removeItem(QGraphicsItem *item);

    98     void prepareBoundingRectChange(const QGraphicsItem *item);

    99 

   100     void itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value);

   101 

   102 private :

   103     Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex)

   104     Q_DISABLE_COPY(QGraphicsSceneBspTreeIndex)

   105     Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())

   106     Q_PRIVATE_SLOT(d_func(), void _q_updateIndex())

   107 

   108     friend class QGraphicsScene;

   109     friend class QGraphicsScenePrivate;

   110 };

   111 

   112 class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate

   113 {

   114     Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)

   115 public:

   116     QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);

   117 

   118     QGraphicsSceneBspTree bsp;

   119     QRectF sceneRect;

   120     int bspTreeDepth;

   121     int indexTimerId;

   122     bool restartIndexTimer;

   123     bool regenerateIndex;

   124     int lastItemCount;

   125 

   126     QList<QGraphicsItem *> indexedItems;

   127     QList<QGraphicsItem *> unindexedItems;

   128     QList<QGraphicsItem *> untransformableItems;

   129     QList<int> freeItemIndexes;

   130 

   131     bool purgePending;

   132     QSet<QGraphicsItem *> removedItems;

   133     void purgeRemovedItems();

   134 

   135     void _q_updateIndex();

   136     void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);

   137     void resetIndex();

   138 

   139     void _q_updateSortCache();

   140     bool sortCacheEnabled;

   141     bool updatingSortCache;

   142     void invalidateSortCache();

   143     void addItem(QGraphicsItem *item, bool recursive = false);

   144     void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false);

   145     QList<QGraphicsItem *> estimateItems(const QRectF &, Qt::SortOrder, bool b = false);

   146 

   147     static void climbTree(QGraphicsItem *item, int *stackingOrder);

   148 

   149     static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)

   150     {

   151         return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;

   152     }

   153     static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)

   154     {

   155         return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;

   156     }

   157 

   158     static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,

   159                           bool cached, bool onlyTopLevelItems = false);

   160 };

   161 

   162 static inline bool QRectF_intersects(const QRectF &s, const QRectF &r)

   163 {

   164     qreal xp = s.left();

   165     qreal yp = s.top();

   166     qreal w = s.width();

   167     qreal h = s.height();

   168     qreal l1 = xp;

   169     qreal r1 = xp;

   170     if (w < 0)

   171         l1 += w;

   172     else

   173         r1 += w;

   174 

   175     qreal l2 = r.left();

   176     qreal r2 = r.left();

   177     if (w < 0)

   178         l2 += r.width();

   179     else

   180         r2 += r.width();

   181 

   182     if (l1 >= r2 || l2 >= r1)

   183         return false;

   184 

   185     qreal t1 = yp;

   186     qreal b1 = yp;

   187     if (h < 0)

   188         t1 += h;

   189     else

   190         b1 += h;

   191 

   192     qreal t2 = r.top();

   193     qreal b2 = r.top();

   194     if (r.height() < 0)

   195         t2 += r.height();

   196     else

   197         b2 += r.height();

   198 

   199     return !(t1 >= b2 || t2 >= b1);

   200 }

   201 

   202 QT_END_NAMESPACE

   203 

   204 #endif // QT_NO_GRAPHICSVIEW

   205 

   206 #endif // QGRAPHICSBSPTREEINDEX_H