--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h	Mon Jan 11 14:00:40 2010 +0000
@@ -0,0 +1,206 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists for the convenience
+// of other Qt classes.  This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#ifndef QGRAPHICSBSPTREEINDEX_H
+#define QGRAPHICSBSPTREEINDEX_H
+
+#include <QtCore/qglobal.h>
+
+#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
+
+#include "qgraphicssceneindex_p.h"
+#include "qgraphicsitem_p.h"
+#include "qgraphicsscene_bsp_p.h"
+
+#include <QtCore/qrect.h>
+#include <QtCore/qlist.h>
+
+QT_BEGIN_NAMESPACE
+
+static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
+
+class QGraphicsScene;
+class QGraphicsSceneBspTreeIndexPrivate;
+
+class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
+{
+    Q_OBJECT
+    Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth)
+public:
+    QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0);
+    ~QGraphicsSceneBspTreeIndex();
+
+    QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const;
+    QList<QGraphicsItem *> estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const;
+    QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::DescendingOrder) const;
+
+    int bspTreeDepth();
+    void setBspTreeDepth(int depth);
+
+protected Q_SLOTS:
+    void updateSceneRect(const QRectF &rect);
+
+protected:
+    bool event(QEvent *event);
+    void clear();
+
+    void addItem(QGraphicsItem *item);
+    void removeItem(QGraphicsItem *item);
+    void prepareBoundingRectChange(const QGraphicsItem *item);
+
+    void itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value);
+
+private :
+    Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex)
+    Q_DISABLE_COPY(QGraphicsSceneBspTreeIndex)
+    Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
+    Q_PRIVATE_SLOT(d_func(), void _q_updateIndex())
+
+    friend class QGraphicsScene;
+    friend class QGraphicsScenePrivate;
+};
+
+class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate
+{
+    Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)
+public:
+    QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);
+
+    QGraphicsSceneBspTree bsp;
+    QRectF sceneRect;
+    int bspTreeDepth;
+    int indexTimerId;
+    bool restartIndexTimer;
+    bool regenerateIndex;
+    int lastItemCount;
+
+    QList<QGraphicsItem *> indexedItems;
+    QList<QGraphicsItem *> unindexedItems;
+    QList<QGraphicsItem *> untransformableItems;
+    QList<int> freeItemIndexes;
+
+    bool purgePending;
+    QSet<QGraphicsItem *> removedItems;
+    void purgeRemovedItems();
+
+    void _q_updateIndex();
+    void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
+    void resetIndex();
+
+    void _q_updateSortCache();
+    bool sortCacheEnabled;
+    bool updatingSortCache;
+    void invalidateSortCache();
+    void addItem(QGraphicsItem *item, bool recursive = false);
+    void removeItem(QGraphicsItem *item, bool recursive = false, bool moveToUnindexedItems = false);
+    QList<QGraphicsItem *> estimateItems(const QRectF &, Qt::SortOrder, bool b = false);
+
+    static void climbTree(QGraphicsItem *item, int *stackingOrder);
+
+    static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
+    {
+        return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
+    }
+    static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
+    {
+        return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
+    }
+
+    static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
+                          bool cached, bool onlyTopLevelItems = false);
+};
+
+static inline bool QRectF_intersects(const QRectF &s, const QRectF &r)
+{
+    qreal xp = s.left();
+    qreal yp = s.top();
+    qreal w = s.width();
+    qreal h = s.height();
+    qreal l1 = xp;
+    qreal r1 = xp;
+    if (w < 0)
+        l1 += w;
+    else
+        r1 += w;
+
+    qreal l2 = r.left();
+    qreal r2 = r.left();
+    if (w < 0)
+        l2 += r.width();
+    else
+        r2 += r.width();
+
+    if (l1 >= r2 || l2 >= r1)
+        return false;
+
+    qreal t1 = yp;
+    qreal b1 = yp;
+    if (h < 0)
+        t1 += h;
+    else
+        b1 += h;
+
+    qreal t2 = r.top();
+    qreal b2 = r.top();
+    if (r.height() < 0)
+        t2 += r.height();
+    else
+        b2 += r.height();
+
+    return !(t1 >= b2 || t2 >= b1);
+}
+
+QT_END_NAMESPACE
+
+#endif // QT_NO_GRAPHICSVIEW
+
+#endif // QGRAPHICSBSPTREEINDEX_H