Remove the sorting cache from the QGraphicsScene and move it to the BSP.

Now the QGraphicsScene has no idea how works the index. So we can
improve it separatly, add new ones and benchmarks existing ones.

17 files changed, 642 insertions, 479 deletions

diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri
index cc57892..a4a79e8 100644
--- a/src/gui/graphicsview/graphicsview.pri
+++ b/src/gui/graphicsview/graphicsview.pri
@@ -7,6 +7,7 @@ HEADERS += \
         graphicsview/qgraphicsscene.h \
         graphicsview/qgraphicsscene_p.h \
         graphicsview/qgraphicsscenebsptreeindex_p.h \
+        graphicsview/qgraphicsscenebsptreeindex_p_p.h \
         graphicsview/qgraphicsscene_bsp_p.h \
         graphicsview/qgraphicsscenelinearindex_p.h \
         graphicsview/qgraphicssceneindex.h \
diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index fc5895c..ee32724 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -537,6 +537,7 @@
 #include "qgraphicsview.h"
 #include "qgraphicswidget.h"
 #include "qgraphicsproxywidget.h"
+#include "qgraphicsscenebsptreeindex_p_p.h"
 #include <QtCore/qbitarray.h>
 #include <QtCore/qdebug.h>
 #include <QtCore/qpoint.h>
@@ -888,12 +889,6 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent, bool de
         }
     }
 
-    if (scene) {
-        // Invalidate any sort caching; arrival of a new item means we need to
-        // resort.
-        scene->d_func()->invalidateSortCache();
-    }
-
     // Resolve opacity.
     updateEffectiveOpacity();
 
@@ -905,6 +900,11 @@ void QGraphicsItemPrivate::setParentItemHelper(QGraphicsItem *newParent, bool de
 
     // Deliver post-change notification
     q->itemChange(QGraphicsItem::ItemParentHasChanged, newParentVariant);
+
+    if (scene) {
+        // Deliver the change to the index
+        scene->d_func()->index->itemChanged(q, QGraphicsItem::ItemParentHasChanged, newParentVariant);
+    }
 }
 
 /*!
@@ -3528,11 +3528,9 @@ void QGraphicsItem::setZValue(qreal z)
     d_ptr->z = newZ;
     d_ptr->fullUpdateHelper();
 
-    if (d_ptr->scene) {
-        // Invalidate any sort caching; arrival of a new item means we need to
-        // resort.
-        d_ptr->scene->d_func()->invalidateSortCache();
-    }
+    //Z Value has changed, we have to notify the index.
+    if (d_ptr->scene)
+        d_ptr->scene->d_func()->index->itemChanged(this, ItemZValueChange, z);
 
     itemChange(ItemZValueHasChanged, newZVariant);
 }
@@ -3991,7 +3989,7 @@ bool QGraphicsItem::isObscuredBy(const QGraphicsItem *item) const
 {
     if (!item)
         return false;
-    return QGraphicsScenePrivate::closestItemFirst_withoutCache(item, this)
+    return QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(item, this)
         && qt_QGraphicsItem_isObscured(this, item, boundingRect());
 }
 
diff --git a/src/gui/graphicsview/qgraphicsitem.h b/src/gui/graphicsview/qgraphicsitem.h
index e244c13..7874033 100644
--- a/src/gui/graphicsview/qgraphicsitem.h
+++ b/src/gui/graphicsview/qgraphicsitem.h
@@ -435,6 +435,7 @@ private:
     friend class QGraphicsSceneIndex;
     friend class QGraphicsSceneIndexPrivate;
     friend class QGraphicsSceneBspTreeIndex;
+    friend class QGraphicsSceneBspTreeIndexPrivate;
     friend class ::tst_QGraphicsItem;
     friend bool qt_closestLeaf(const QGraphicsItem *, const QGraphicsItem *);
     friend bool qt_closestItemFirst(const QGraphicsItem *, const QGraphicsItem *);
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 0172a23..4734e74 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -218,6 +218,7 @@
 #include "qgraphicswidget.h"
 #include "qgraphicswidget_p.h"
 #include "qgraphicssceneindex.h"
+#include "qgraphicsscenebsptreeindex_p_p.h"
 
 #include <QtCore/qdebug.h>
 #include <QtCore/qlist.h>
@@ -291,8 +292,6 @@ QGraphicsScenePrivate::QGraphicsScenePrivate()
       allItemsIgnoreHoverEvents(true),
       allItemsUseDefaultCursor(true),
       painterStateProtection(true),
-      sortCacheEnabled(false),
-      updatingSortCache(false),
       style(0)
 {
 }
@@ -1073,175 +1072,6 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item)
     return 0;
 }
 
-void QGraphicsScenePrivate::invalidateSortCache()
-{
-    Q_Q(QGraphicsScene);
-    if (!sortCacheEnabled || updatingSortCache)
-        return;
-
-    updatingSortCache = true;
-    QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);
-}
-
-/*!
-    \internal
-
-    Should not be exported, but we can't change that now.
-    ### Qt 5: Remove symbol / make static
-*/
-inline bool qt_closestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    // Return true if sibling item1 is on top of item2.
-    const QGraphicsItemPrivate *d1 = item1->d_ptr;
-    const QGraphicsItemPrivate *d2 = item2->d_ptr;
-    bool f1 = d1->flags & QGraphicsItem::ItemStacksBehindParent;
-    bool f2 = d2->flags & QGraphicsItem::ItemStacksBehindParent;
-    if (f1 != f2) return f2;
-    qreal z1 = d1->z;
-    qreal z2 = d2->z;
-    return z1 != z2 ? z1 > z2 : d1->siblingIndex > d2->siblingIndex;
-}
-
-/*!
-    \internal
-
-    Should not be exported, but we can't change that now.
-*/
-inline bool qt_closestItemFirst(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    return QGraphicsScenePrivate::closestItemFirst_withoutCache(item1, item2);
-}
-
-/*!
-    Returns true if \a item1 is on top of \a item2.
-
-    \internal
-*/
-bool QGraphicsScenePrivate::closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    // Siblings? Just check their z-values.
-    const QGraphicsItemPrivate *d1 = item1->d_ptr;
-    const QGraphicsItemPrivate *d2 = item2->d_ptr;
-    if (d1->parent == d2->parent)
-        return qt_closestLeaf(item1, item2);
-
-    // Find common ancestor, and each item's ancestor closest to the common
-    // ancestor.
-    int item1Depth = d1->depth;
-    int item2Depth = d2->depth;
-    const QGraphicsItem *p = item1;
-    const QGraphicsItem *t1 = item1;
-    while (item1Depth > item2Depth && (p = p->d_ptr->parent)) {
-        if (p == item2) {
-            // item2 is one of item1's ancestors; item1 is on top
-            return !(t1->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
-        }
-        t1 = p;
-        --item1Depth;
-    }
-    p = item2;
-    const QGraphicsItem *t2 = item2;
-    while (item2Depth > item1Depth && (p = p->d_ptr->parent)) {
-        if (p == item1) {
-            // item1 is one of item2's ancestors; item1 is not on top
-            return (t2->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
-        }
-        t2 = p;
-        --item2Depth;
-    }
-
-    // item1Ancestor is now at the same level as item2Ancestor, but not the same.
-    const QGraphicsItem *a1 = t1;
-    const QGraphicsItem *a2 = t2;
-    while (a1) {
-        const QGraphicsItem *p1 = a1;
-        const QGraphicsItem *p2 = a2;
-        a1 = a1->parentItem();
-        a2 = a2->parentItem();
-        if (a1 && a1 == a2)
-            return qt_closestLeaf(p1, p2);
-    }
-
-    // No common ancestor? Then just compare the items' toplevels directly.
-    return qt_closestLeaf(t1->topLevelItem(), t2->topLevelItem());
-}
-
-/*!
-    Returns true if \a item2 is on top of \a item1.
-
-    \internal
-*/
-bool QGraphicsScenePrivate::closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    return closestItemFirst_withoutCache(item2, item1);
-}
-
-void QGraphicsScenePrivate::climbTree(QGraphicsItem *item, int *stackingOrder)
-{
-    if (!item->d_ptr->children.isEmpty()) {
-        QList<QGraphicsItem *> childList = item->d_ptr->children;
-        qSort(childList.begin(), childList.end(), qt_closestLeaf);
-        for (int i = 0; i < childList.size(); ++i) {
-            QGraphicsItem *item = childList.at(i);
-            if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))
-                climbTree(childList.at(i), stackingOrder);
-        }
-        item->d_ptr->globalStackingOrder = (*stackingOrder)++;
-        for (int i = 0; i < childList.size(); ++i) {
-            QGraphicsItem *item = childList.at(i);
-            if (item->flags() & QGraphicsItem::ItemStacksBehindParent)
-                climbTree(childList.at(i), stackingOrder);
-        }
-    } else {
-        item->d_ptr->globalStackingOrder = (*stackingOrder)++;
-    }
-}
-
-void QGraphicsScenePrivate::_q_updateSortCache()
-{
-    //### FIXME
-    QGraphicsSceneBspTreeIndex *tree = qobject_cast<QGraphicsSceneBspTreeIndex*>(index);
-    if (tree) {
-        tree->_q_updateIndex();
-    }
-
-    if (!sortCacheEnabled || !updatingSortCache)
-        return;
-
-    updatingSortCache = false;
-    int stackingOrder = 0;
-
-    QList<QGraphicsItem *> topLevels;
-
-    for (int i = 0; i < index->items().count(); ++i) {
-        QGraphicsItem *item = index->items().at(i);
-        if (item && item->parentItem() == 0)
-            topLevels << item;
-    }
-
-    qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
-    for (int i = 0; i < topLevels.size(); ++i)
-        climbTree(topLevels.at(i), &stackingOrder);
-}
-
-void QGraphicsScenePrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
-                                      bool sortCacheEnabled)
-{
-    if (sortCacheEnabled) {
-        if (order == Qt::AscendingOrder) {
-            qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
-        } else if (order == Qt::DescendingOrder) {
-            qSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
-        }
-    } else {
-        if (order == Qt::AscendingOrder) {
-            qSort(itemList->begin(), itemList->end(), closestItemFirst_withoutCache);
-        } else if (order == Qt::DescendingOrder) {
-            qSort(itemList->begin(), itemList->end(), closestItemLast_withoutCache);
-        }
-    }
-}
-
 /*!
     \internal
 
@@ -1707,15 +1537,25 @@ void QGraphicsScene::setBspTreeDepth(int depth)
 bool QGraphicsScene::isSortCacheEnabled() const
 {
     Q_D(const QGraphicsScene);
-    return d->sortCacheEnabled;
+    QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index);
+    if (!bspTree) {
+        qWarning("QGraphicsScene::isSortCacheEnabled: can not apply if indexing method is not BSP");
+        return false;
+    }
+    return bspTree->d_func()->sortCacheEnabled;
 }
 void QGraphicsScene::setSortCacheEnabled(bool enabled)
 {
     Q_D(QGraphicsScene);
-    if (enabled == d->sortCacheEnabled)
+    QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex*>(d->index);
+    if (!bspTree) {
+        qWarning("QGraphicsScene::isSortCacheEnabled: can not apply if indexing method is not BSP");
         return;
-    if ((d->sortCacheEnabled = enabled))
-        d->invalidateSortCache();
+    }
+    if (enabled == bspTree->d_func()->sortCacheEnabled)
+        return;
+    if ((bspTree->d_func()->sortCacheEnabled = enabled))
+        bspTree->d_func()->invalidateSortCache();
 }
 
 /*!
@@ -1910,8 +1750,6 @@ QList<QGraphicsItem *> QGraphicsScene::collidingItems(const QGraphicsItem *item,
         if (item != itemInVicinity && item->collidesWithItem(itemInVicinity, mode))
             tmp << itemInVicinity;
     }
-    //### remove me
-    d->sortItems(&tmp, Qt::AscendingOrder, d->sortCacheEnabled);
     return tmp;
 }
 
@@ -2211,10 +2049,6 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
         return;
     }
 
-    // Invalidate any sort caching; arrival of a new item means we need to
-    // resort.
-    d->invalidateSortCache();
-
     // Detach this item from its parent if the parent's scene is different
     // from this scene.
     if (QGraphicsItem *itemParent = item->parentItem()) {
@@ -2232,10 +2066,6 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
     if (!item->d_ptr->parent)
         d->registerTopLevelItem(item);
 
-    // Update the scene's sort cache settings.
-    item->d_ptr->globalStackingOrder = -1;
-    d->invalidateSortCache();
-
     // Add to list of items that require an update. We cannot assume that the
     // item is fully constructed, so calling item->update() can lead to a pure
     // virtual function call to boundingRect().
diff --git a/src/gui/graphicsview/qgraphicsscene.h b/src/gui/graphicsview/qgraphicsscene.h
index 5d70087..702813c 100644
--- a/src/gui/graphicsview/qgraphicsscene.h
+++ b/src/gui/graphicsview/qgraphicsscene.h
@@ -290,7 +290,6 @@ private:
     Q_PRIVATE_SLOT(d_func(), void _q_removeItemLater(QGraphicsItem *item))
     Q_PRIVATE_SLOT(d_func(), void _q_updateLater())
     Q_PRIVATE_SLOT(d_func(), void _q_polishItems())
-    Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache())
     Q_PRIVATE_SLOT(d_func(), void _q_resetDirtyItems())
     friend class QGraphicsItem;
     friend class QGraphicsItemPrivate;
@@ -301,6 +300,7 @@ private:
     friend class QGraphicsSceneIndex;
     friend class QGraphicsSceneIndexPrivate;
     friend class QGraphicsSceneBspTreeIndex;
+    friend class QGraphicsSceneBspTreeIndexPrivate;
 };
 
 Q_DECLARE_OPERATORS_FOR_FLAGS(QGraphicsScene::SceneLayers)
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index a035159..d2a5cdb 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -187,25 +187,6 @@ public:
     void sendMouseEvent(QGraphicsSceneMouseEvent *mouseEvent);
     void mousePressEventHandler(QGraphicsSceneMouseEvent *mouseEvent);
     QGraphicsWidget *windowForItem(const QGraphicsItem *item) const;
-    bool sortCacheEnabled;
-    bool updatingSortCache;
-    void invalidateSortCache();
-    static void climbTree(QGraphicsItem *item, int *stackingOrder);
-    void _q_updateSortCache();
-
-    static bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
-    static bool closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
-
-    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);
 
     void drawItemHelper(QGraphicsItem *item, QPainter *painter,
                         const QStyleOptionGraphicsItem *option, QWidget *widget,
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
index f8f1f56..19aa9d5 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
@@ -39,9 +39,15 @@
 **
 ****************************************************************************/
 
+
 static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
 
 #include "qgraphicsscenebsptreeindex_p.h"
+
+#ifndef QT_NO_GRAPHICSVIEW
+
+#include "qgraphicsscenebsptreeindex_p_p.h"
+#include "qgraphicssceneindex_p.h"
 #include "qgraphicsitem_p.h"
 #include "qgraphicsscene_p.h"
 
@@ -49,51 +55,365 @@ static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000;
 
 #include <QtCore/qdebug.h>
 
-QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)
-    : QGraphicsSceneIndex(scene),
+QT_BEGIN_NAMESPACE
+
+static inline int intmaxlog(int n)
+{
+    return  (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);
+}
+
+/*!
+    Constructs a private scene index.
+*/
+QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene)
+    : scene(scene),
     bspTreeDepth(0),
     indexTimerId(0),
     restartIndexTimer(false),
     regenerateIndex(true),
     lastItemCount(0),
-    purgePending(false)
+    purgePending(false),
+    sortCacheEnabled(false),
+    updatingSortCache(false)
+{
+}
+
+
+/*!
+    \internal
+*/
+void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex()
 {
+    Q_Q(QGraphicsSceneBspTreeIndex);
+    if (!indexTimerId)
+        return;
 
+    QGraphicsScenePrivate * scenePrivate = q->scene()->d_func();
+    q->killTimer(indexTimerId);
+    indexTimerId = 0;
+
+    purgeRemovedItems();
+
+     // Add unindexedItems to indexedItems
+    QRectF unindexedItemsBoundingRect;
+    for (int i = 0; i < unindexedItems.size(); ++i) {
+        if (QGraphicsItem *item = unindexedItems.at(i)) {
+            unindexedItemsBoundingRect |= item->sceneBoundingRect();
+            if (!freeItemIndexes.isEmpty()) {
+                int freeIndex = freeItemIndexes.takeFirst();
+                item->d_func()->index = freeIndex;
+                indexedItems[freeIndex] = item;
+            } else {
+                item->d_func()->index = indexedItems.size();
+                indexedItems << item;
+            }
+        }
+    }
+
+    // Update growing scene rect.
+    QRectF oldGrowingItemsBoundingRect = scenePrivate->growingItemsBoundingRect;
+    scenePrivate->growingItemsBoundingRect |= unindexedItemsBoundingRect;
+
+    // Determine whether we should regenerate the BSP tree.
+    if (bspTreeDepth == 0) {
+        int oldDepth = intmaxlog(lastItemCount);
+        bspTreeDepth = intmaxlog(indexedItems.size());
+        static const int slack = 100;
+        if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - indexedItems.size()) > slack)) {
+            // ### Crude algorithm.
+            regenerateIndex = true;
+        }
+    }
+
+    // Regenerate the tree.
+    if (regenerateIndex) {
+        regenerateIndex = false;
+        bsp.initialize(q->scene()->sceneRect(), bspTreeDepth);
+        unindexedItems = indexedItems;
+        lastItemCount = indexedItems.size();
+        q->scene()->update();
+
+        // Take this opportunity to reset our largest-item counter for
+        // untransformable items. When the items are inserted into the BSP
+        // tree, we'll get an accurate calculation.
+        scenePrivate->largestUntransformableItem = QRectF();
+    }
+
+    // Insert all unindexed items into the tree.
+    for (int i = 0; i < unindexedItems.size(); ++i) {
+        if (QGraphicsItem *item = unindexedItems.at(i)) {
+            QRectF rect = item->sceneBoundingRect();
+            if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)
+                continue;
+
+            bsp.insertItem(item, rect);
+
+            // If the item ignores view transformations, update our
+            // largest-item-counter to ensure that the view can accurately
+            // discover untransformable items when drawing.
+            if (item->d_ptr->itemIsUntransformable()) {
+                QGraphicsItem *topmostUntransformable = item;
+                while (topmostUntransformable && (topmostUntransformable->d_ptr->ancestorFlags
+                                                  & QGraphicsItemPrivate::AncestorIgnoresTransformations)) {
+                    topmostUntransformable = topmostUntransformable->parentItem();
+                }
+                // ### Verify that this is the correct largest untransformable rectangle.
+                scenePrivate->largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect();
+            }
+        }
+    }
+    unindexedItems.clear();
+
+    // Notify scene rect changes.
+    if (!scenePrivate->hasSceneRect && scenePrivate->growingItemsBoundingRect != oldGrowingItemsBoundingRect)
+        emit q->scene()->sceneRectChanged(scenePrivate->growingItemsBoundingRect);
 }
 
-QRectF QGraphicsSceneBspTreeIndex::indexedRect()
+
+/*!
+    \internal
+
+    Removes stale pointers from all data structures.
+*/
+void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems()
+{
+    Q_Q(QGraphicsSceneBspTreeIndex);
+    if (!purgePending && removedItems.isEmpty())
+        return;
+
+    // Remove stale items from the BSP tree.
+    bsp.removeItems(removedItems.toSet());
+    // Purge this list.
+    removedItems.clear();
+    freeItemIndexes.clear();
+    for (int i = 0; i < indexedItems.size(); ++i) {
+        if (!indexedItems.at(i))
+            freeItemIndexes << i;
+    }
+    purgePending = false;
+
+    // No locality info for the items; update the whole scene.
+    q->scene()->update();
+}
+
+/*!
+    \internal
+
+    Starts or restarts the timer used for reindexing unindexed items.
+*/
+void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer()
+{
+    Q_Q(QGraphicsSceneBspTreeIndex);
+    if (indexTimerId) {
+        restartIndexTimer = true;
+    } else {
+        indexTimerId = q->startTimer(QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
+    }
+}
+
+/*!
+    \internal
+*/
+void QGraphicsSceneBspTreeIndexPrivate::resetIndex()
+{
+    purgeRemovedItems();
+    for (int i = 0; i < indexedItems.size(); ++i) {
+        if (QGraphicsItem *item = indexedItems.at(i)) {
+            item->d_ptr->index = -1;
+            unindexedItems << item;
+        }
+    }
+    indexedItems.clear();
+    freeItemIndexes.clear();
+    regenerateIndex = true;
+    startIndexTimer();
+}
+
+void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder)
 {
+    if (!item->d_ptr->children.isEmpty()) {
+        QList<QGraphicsItem *> childList = item->d_ptr->children;
+        qSort(childList.begin(), childList.end(), qt_closestLeaf);
+        for (int i = 0; i < childList.size(); ++i) {
+            QGraphicsItem *item = childList.at(i);
+            if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))
+                climbTree(childList.at(i), stackingOrder);
+        }
+        item->d_ptr->globalStackingOrder = (*stackingOrder)++;
+        for (int i = 0; i < childList.size(); ++i) {
+            QGraphicsItem *item = childList.at(i);
+            if (item->flags() & QGraphicsItem::ItemStacksBehindParent)
+                climbTree(childList.at(i), stackingOrder);
+        }
+    } else {
+        item->d_ptr->globalStackingOrder = (*stackingOrder)++;
+    }
+}
+
+void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache()
+{
+    Q_Q(QGraphicsSceneBspTreeIndex);
     _q_updateIndex();
+
+    if (!sortCacheEnabled || !updatingSortCache)
+        return;
+
+    updatingSortCache = false;
+    int stackingOrder = 0;
+
+    QList<QGraphicsItem *> topLevels;
+
+    for (int i = 0; i < q->items().count(); ++i) {
+        QGraphicsItem *item = q->items().at(i);
+        if (item && item->parentItem() == 0)
+            topLevels << item;
+    }
+
+    qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
+    for (int i = 0; i < topLevels.size(); ++i)
+        climbTree(topLevels.at(i), &stackingOrder);
+}
+
+void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache()
+{
+    Q_Q(QGraphicsSceneBspTreeIndex);
+    if (!sortCacheEnabled || updatingSortCache)
+        return;
+
+    updatingSortCache = true;
+    QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);
+}
+
+/*!
+    Returns true if \a item1 is on top of \a item2.
+
+    \internal
+*/
+bool QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
+{
+    // Siblings? Just check their z-values.
+    const QGraphicsItemPrivate *d1 = item1->d_ptr;
+    const QGraphicsItemPrivate *d2 = item2->d_ptr;
+    if (d1->parent == d2->parent)
+        return qt_closestLeaf(item1, item2);
+
+    // Find common ancestor, and each item's ancestor closest to the common
+    // ancestor.
+    int item1Depth = d1->depth;
+    int item2Depth = d2->depth;
+    const QGraphicsItem *p = item1;
+    const QGraphicsItem *t1 = item1;
+    while (item1Depth > item2Depth && (p = p->d_ptr->parent)) {
+        if (p == item2) {
+            // item2 is one of item1's ancestors; item1 is on top
+            return !(t1->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
+        }
+        t1 = p;
+        --item1Depth;
+    }
+    p = item2;
+    const QGraphicsItem *t2 = item2;
+    while (item2Depth > item1Depth && (p = p->d_ptr->parent)) {
+        if (p == item1) {
+            // item1 is one of item2's ancestors; item1 is not on top
+            return (t2->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
+        }
+        t2 = p;
+        --item2Depth;
+    }
+
+    // item1Ancestor is now at the same level as item2Ancestor, but not the same.
+    const QGraphicsItem *a1 = t1;
+    const QGraphicsItem *a2 = t2;
+    while (a1) {
+        const QGraphicsItem *p1 = a1;
+        const QGraphicsItem *p2 = a2;
+        a1 = a1->parentItem();
+        a2 = a2->parentItem();
+        if (a1 && a1 == a2)
+            return qt_closestLeaf(p1, p2);
+    }
+
+    // No common ancestor? Then just compare the items' toplevels directly.
+    return qt_closestLeaf(t1->topLevelItem(), t2->topLevelItem());
+}
+
+/*!
+    Returns true if \a item2 is on top of \a item1.
+
+    \internal
+*/
+bool QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
+{
+    return closestItemFirst_withoutCache(item2, item1);
+}
+
+void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
+                                      bool sortCacheEnabled)
+{
+    if (sortCacheEnabled) {
+        if (order == Qt::AscendingOrder) {
+            qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
+        } else if (order == Qt::DescendingOrder) {
+            qSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
+        }
+    } else {
+        if (order == Qt::AscendingOrder) {
+            qSort(itemList->begin(), itemList->end(), closestItemFirst_withoutCache);
+        } else if (order == Qt::DescendingOrder) {
+            qSort(itemList->begin(), itemList->end(), closestItemLast_withoutCache);
+        }
+    }
+}
+
+QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)
+    : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene)
+{
+
+}
+
+QRectF QGraphicsSceneBspTreeIndex::indexedRect() const
+{
+    Q_D(const QGraphicsSceneBspTreeIndex);
+    const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->_q_updateIndex();
     return scene()->d_func()->hasSceneRect ? scene()->d_func()->sceneRect : scene()->d_func()->growingItemsBoundingRect;
 }
 
 void QGraphicsSceneBspTreeIndex::clear()
 {
-    bsp.clear();
-    lastItemCount = 0;
-    freeItemIndexes.clear();
-    m_indexedItems.clear();
-    unindexedItems.clear();
+    Q_D(QGraphicsSceneBspTreeIndex);
+    d->bsp.clear();
+    d->lastItemCount = 0;
+    d->freeItemIndexes.clear();
+    d->indexedItems.clear();
+    d->unindexedItems.clear();
 }
 
 void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item)
 {
+    Q_D(QGraphicsSceneBspTreeIndex);
     // Prevent reusing a recently deleted pointer: purge all removed items
     // from our lists.
-    purgeRemovedItems();
+    d->purgeRemovedItems();
+
+    // Invalidate any sort caching; arrival of a new item means we need to
+    // resort.
+    // Update the scene's sort cache settings.
+    item->d_ptr->globalStackingOrder = -1;
+    d->invalidateSortCache();
 
     // Indexing requires sceneBoundingRect(), but because \a item might
     // not be completely constructed at this point, we need to store it in
     // a temporary list and schedule an indexing for later.
-    unindexedItems << item;
+    d->unindexedItems << item;
     item->d_func()->index = -1;
-    startIndexTimer();
+    d->startIndexTimer();
 }
 
 /*!
     \internal
 */
-void QGraphicsSceneBspTreeIndex::addToIndex(QGraphicsItem *item)
+void QGraphicsSceneBspTreeIndexPrivate::addToIndex(QGraphicsItem *item)
 {
     if (item->d_func()->index != -1) {
         bsp.insertItem(item, item->sceneBoundingRect());
@@ -109,37 +429,47 @@ void QGraphicsSceneBspTreeIndex::addToIndex(QGraphicsItem *item)
 
 void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item)
 {
+    Q_D(QGraphicsSceneBspTreeIndex);
     // Note: This will access item's sceneBoundingRect(), which (as this is
     // C++) is why we cannot call removeItem() from QGraphicsItem's
     // destructor.
-    removeFromIndex(item);
+    d->removeFromIndex(item);
+
+    // Invalidate any sort caching; arrival of a new item means we need to
+    // resort.
+    d->invalidateSortCache();
 
     // Remove from our item lists.
     int index = item->d_func()->index;
     if (index != -1) {
-        freeItemIndexes << index;
-        m_indexedItems[index] = 0;
+        d->freeItemIndexes << index;
+        d->indexedItems[index] = 0;
     } else {
-        unindexedItems.removeAll(item);
+        d->unindexedItems.removeAll(item);
     }
 }
 
 void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item)
 {
+    Q_D(QGraphicsSceneBspTreeIndex);
+    // Invalidate any sort caching; arrival of a new item means we need to
+    // resort.
+    d->invalidateSortCache();
+
     int index = item->d_func()->index;
     if (index != -1) {
         // Important: The index is useless until purgeRemovedItems() is
         // called.
-        m_indexedItems[index] = (QGraphicsItem *)0;
-        if (!purgePending) {
-            purgePending = true;
+        d->indexedItems[index] = (QGraphicsItem *)0;
+        if (!d->purgePending) {
+            d->purgePending = true;
             scene()->update();
         }
-        removedItems << item;
+        d->removedItems << item;
     } else {
         // Recently added items are purged immediately. unindexedItems() never
         // contains stale items.
-        unindexedItems.removeAll(item);
+        d->unindexedItems.removeAll(item);
         scene()->update();
     }
 }
@@ -147,7 +477,7 @@ void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item)
 /*!
     \internal
 */
-void QGraphicsSceneBspTreeIndex::removeFromIndex(QGraphicsItem *item)
+void QGraphicsSceneBspTreeIndexPrivate::removeFromIndex(QGraphicsItem *item)
 {
     if (item->d_func()->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) {
         // ### remove from child index only if applicable
@@ -157,7 +487,7 @@ void QGraphicsSceneBspTreeIndex::removeFromIndex(QGraphicsItem *item)
     if (index != -1) {
         bsp.removeItem(item, item->sceneBoundingRect());
         freeItemIndexes << index;
-        m_indexedItems[index] = 0;
+        indexedItems[index] = 0;
         item->d_func()->index = -1;
         unindexedItems << item;
 
@@ -170,21 +500,23 @@ void QGraphicsSceneBspTreeIndex::removeFromIndex(QGraphicsItem *item)
 
 void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item)
 {
+    Q_D(QGraphicsSceneBspTreeIndex);
     // Note: This will access item's sceneBoundingRect(), which (as this is
     // C++) is why we cannot call removeItem() from QGraphicsItem's
     // destructor.
-    removeFromIndex(const_cast<QGraphicsItem *>(item));
+    d->removeFromIndex(const_cast<QGraphicsItem *>(item));
 }
 
 QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const
 {
-    const_cast<QGraphicsSceneBspTreeIndex*>(this)->purgeRemovedItems();
-    scene()->d_func()->_q_updateSortCache();
+    Q_D(const QGraphicsSceneBspTreeIndex);
+    const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems();
+    const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->_q_updateSortCache();
 
-    QList<QGraphicsItem *> rectItems = bsp.items(rect);
+    QList<QGraphicsItem *> rectItems = d->bsp.items(rect);
     // Fill in with any unindexed items
-    for (int i = 0; i < unindexedItems.size(); ++i) {
-        if (QGraphicsItem *item = unindexedItems.at(i)) {
+    for (int i = 0; i < d->unindexedItems.size(); ++i) {
+        if (QGraphicsItem *item = d->unindexedItems.at(i)) {
             if (!item->d_ptr->itemDiscovered && item->d_ptr->visible && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) {
                 QRectF boundingRect = item->sceneBoundingRect();
                 if (QRectF_intersects(boundingRect, rect)) {
@@ -199,57 +531,83 @@ QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &r
     for (int i = 0; i < rectItems.size(); ++i)
         rectItems.at(i)->d_func()->itemDiscovered = 0;
 
+    d->sortItems(&rectItems, order, d->sortCacheEnabled);
+
     return rectItems;
 }
 
-QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items() const
+QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) const
 {
-    const_cast<QGraphicsSceneBspTreeIndex*>(this)->purgeRemovedItems();
+    Q_D(const QGraphicsSceneBspTreeIndex);
+    const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems();
+    QList<QGraphicsItem *> itemList;
      // If freeItemIndexes is empty, we know there are no holes in indexedItems and
     // unindexedItems.
-    if (freeItemIndexes.isEmpty()) {
-        if (unindexedItems.isEmpty())
-            return m_indexedItems;
-        return m_indexedItems + unindexedItems;
-    }
-
-    // Rebuild the list of items to avoid holes. ### We could also just
-    // compress the item lists at this point.
-    QList<QGraphicsItem *> itemList;
-    foreach (QGraphicsItem *item, m_indexedItems + unindexedItems) {
-        if (item)
-            itemList << item;
+    if (d->freeItemIndexes.isEmpty()) {
+        if (d->unindexedItems.isEmpty()) {
+            itemList = d->indexedItems;
+        } else {
+            itemList = d->indexedItems + d->unindexedItems;
+        }
+    } else {
+        // Rebuild the list of items to avoid holes. ### We could also just
+        // compress the item lists at this point.
+        foreach (QGraphicsItem *item, d->indexedItems + d->unindexedItems) {
+            if (item)
+                itemList << item;
+        }
     }
+    //We sort descending order
+    d->sortItems(&itemList, order, d->sortCacheEnabled);
     return itemList;
 }
 
 int QGraphicsSceneBspTreeIndex::bspDepth()
 {
-    return bspTreeDepth;
+    Q_D(const QGraphicsSceneBspTreeIndex);
+    return d->bspTreeDepth;
 }
 
 void QGraphicsSceneBspTreeIndex::setBspDepth(int depth)
 {
-    bspTreeDepth = depth;
-    resetIndex();
+    Q_D(QGraphicsSceneBspTreeIndex);
+    d->bspTreeDepth = depth;
+    d->resetIndex();
 }
 
 void QGraphicsSceneBspTreeIndex::sceneRectChanged(const QRectF &rect)
 {
-    m_sceneRect = rect;
-    resetIndex();
+    Q_D(QGraphicsSceneBspTreeIndex);
+    d->sceneRect = rect;
+    d->resetIndex();
+}
+
+void QGraphicsSceneBspTreeIndex::itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value)
+{
+    Q_D(QGraphicsSceneBspTreeIndex);
+    switch (change) {
+        case QGraphicsItem::ItemZValueChange:
+        case QGraphicsItem::ItemParentChange: {
+            d->invalidateSortCache();
+            break;
+        }
+        default:
+            break;
+    }
+    return QGraphicsSceneIndex::itemChanged(item, change, value);
 }
 
 bool QGraphicsSceneBspTreeIndex::event(QEvent *event)
 {
+    Q_D(QGraphicsSceneBspTreeIndex);
     switch (event->type()) {
     case QEvent::Timer:
-            if (indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == indexTimerId) {
-                if (restartIndexTimer) {
-                    restartIndexTimer = false;
+            if (d->indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == d->indexTimerId) {
+                if (d->restartIndexTimer) {
+                    d->restartIndexTimer = false;
                 } else {
                     // this call will kill the timer
-                    _q_updateIndex();
+                    d->_q_updateIndex();
                 }
             }
      // Fallthrough intended - support timers in subclasses.
@@ -259,153 +617,9 @@ bool QGraphicsSceneBspTreeIndex::event(QEvent *event)
     return true;
 }
 
-static inline int intmaxlog(int n)
-{
-    return  (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);
-}
+QT_END_NAMESPACE
 
-/*!
-    \internal
-*/
-void QGraphicsSceneBspTreeIndex::_q_updateIndex()
-{
-    if (!indexTimerId)
-        return;
+#include "moc_qgraphicsscenebsptreeindex_p.cpp"
 
-    killTimer(indexTimerId);
-    indexTimerId = 0;
+#endif  // QT_NO_GRAPHICSVIEW
 
-    purgeRemovedItems();
-
-     // Add unindexedItems to indexedItems
-    QRectF unindexedItemsBoundingRect;
-    for (int i = 0; i < unindexedItems.size(); ++i) {
-        if (QGraphicsItem *item = unindexedItems.at(i)) {
-            unindexedItemsBoundingRect |= item->sceneBoundingRect();
-            if (!freeItemIndexes.isEmpty()) {
-                int freeIndex = freeItemIndexes.takeFirst();
-                item->d_func()->index = freeIndex;
-                m_indexedItems[freeIndex] = item;
-            } else {
-                item->d_func()->index = m_indexedItems.size();
-                m_indexedItems << item;
-            }
-        }
-    }
-
-    // Update growing scene rect.
-    QRectF oldGrowingItemsBoundingRect = scene()->d_func()->growingItemsBoundingRect;
-    scene()->d_func()->growingItemsBoundingRect |= unindexedItemsBoundingRect;
-
-    // Determine whether we should regenerate the BSP tree.
-    if (bspTreeDepth == 0) {
-        int oldDepth = intmaxlog(lastItemCount);
-        bspTreeDepth = intmaxlog(m_indexedItems.size());
-        static const int slack = 100;
-        if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - m_indexedItems.size()) > slack)) {
-            // ### Crude algorithm.
-            regenerateIndex = true;
-        }
-    }
-
-    // Regenerate the tree.
-    if (regenerateIndex) {
-        regenerateIndex = false;
-        bsp.initialize(scene()->sceneRect(), bspTreeDepth);
-        unindexedItems = m_indexedItems;
-        lastItemCount = m_indexedItems.size();
-        scene()->update();
-
-        // Take this opportunity to reset our largest-item counter for
-        // untransformable items. When the items are inserted into the BSP
-        // tree, we'll get an accurate calculation.
-        scene()->d_func()->largestUntransformableItem = QRectF();
-    }
-
-    // Insert all unindexed items into the tree.
-    for (int i = 0; i < unindexedItems.size(); ++i) {
-        if (QGraphicsItem *item = unindexedItems.at(i)) {
-            QRectF rect = item->sceneBoundingRect();
-            if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)
-                continue;
-
-            bsp.insertItem(item, rect);
-
-            // If the item ignores view transformations, update our
-            // largest-item-counter to ensure that the view can accurately
-            // discover untransformable items when drawing.
-            if (item->d_ptr->itemIsUntransformable()) {
-                QGraphicsItem *topmostUntransformable = item;
-                while (topmostUntransformable && (topmostUntransformable->d_ptr->ancestorFlags
-                                                  & QGraphicsItemPrivate::AncestorIgnoresTransformations)) {
-                    topmostUntransformable = topmostUntransformable->parentItem();
-                }
-                // ### Verify that this is the correct largest untransformable rectangle.
-                scene()->d_func()->largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect();
-            }
-        }
-    }
-    unindexedItems.clear();
-
-    // Notify scene rect changes.
-    if (!scene()->d_func()->hasSceneRect && scene()->d_func()->growingItemsBoundingRect != oldGrowingItemsBoundingRect)
-        emit scene()->sceneRectChanged(scene()->d_func()->growingItemsBoundingRect);
-}
-
-
-/*!
-    \internal
-
-    Removes stale pointers from all data structures.
-*/
-void QGraphicsSceneBspTreeIndex::purgeRemovedItems()
-{
-    if (!purgePending && removedItems.isEmpty())
-        return;
-
-    // Remove stale items from the BSP tree.
-    bsp.removeItems(removedItems.toSet());
-    // Purge this list.
-    removedItems.clear();
-    freeItemIndexes.clear();
-    for (int i = 0; i < m_indexedItems.size(); ++i) {
-        if (!m_indexedItems.at(i))
-            freeItemIndexes << i;
-    }
-    purgePending = false;
-
-    // No locality info for the items; update the whole scene.
-    scene()->update();
-}
-
-/*!
-    \internal
-
-    Starts or restarts the timer used for reindexing unindexed items.
-*/
-void QGraphicsSceneBspTreeIndex::startIndexTimer()
-{
-    if (indexTimerId) {
-        restartIndexTimer = true;
-    } else {
-        indexTimerId = startTimer(QGRAPHICSSCENE_INDEXTIMER_TIMEOUT);
-    }
-}
-
-/*!
-    \internal
-*/
-void QGraphicsSceneBspTreeIndex::resetIndex()
-{
-    purgeRemovedItems();
-    for (int i = 0; i < m_indexedItems.size(); ++i) {
-        if (QGraphicsItem *item = m_indexedItems.at(i)) {
-            item->d_ptr->index = -1;
-            unindexedItems << item;
-        }
-    }
-    m_indexedItems.clear();
-    freeItemIndexes.clear();
-    regenerateIndex = true;
-    startIndexTimer();
-}
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
index 7a6ea0b..b1ea977 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
@@ -56,56 +56,41 @@ QT_BEGIN_NAMESPACE
 
 #include "qgraphicsscene_bsp_p.h"
 
+class QGraphicsSceneBspTreeIndexPrivate;
 class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
 {
     Q_OBJECT
 public:
     QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0);
-    QRectF indexedRect();
-
-    void clear();
-
-    void addItem(QGraphicsItem *item);
-    void removeItem(QGraphicsItem *item);
-    void deleteItem(QGraphicsItem *item);
-    void prepareBoundingRectChange(const QGraphicsItem *item);
+    QRectF indexedRect() const;
 
     QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const;
 
-    QList<QGraphicsItem *> items() const;
+    QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const;
 
     int bspDepth();
     void setBspDepth(int depth);
 
 protected:
     bool event(QEvent *event);
-    void sceneRectChanged(const QRectF &rect);
+    void clear();
+
+    void addItem(QGraphicsItem *item);
+    void removeItem(QGraphicsItem *item);
+    void deleteItem(QGraphicsItem *item);
+    void prepareBoundingRectChange(const QGraphicsItem *item);
 
-public slots :
-    void _q_updateIndex();
+    void sceneRectChanged(const QRectF &rect);
+    void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value);
 
 private :
-    QGraphicsSceneBspTree bsp;
-    QRectF m_sceneRect;
-    int bspTreeDepth;
-    int indexTimerId;
-    bool restartIndexTimer;
-    bool regenerateIndex;
-    int lastItemCount;
-
-    QList<QGraphicsItem *> m_indexedItems;
-    QList<QGraphicsItem *> unindexedItems;
-    QList<int> freeItemIndexes;
-
-    bool purgePending;
-    QList<QGraphicsItem *> removedItems;
-    void purgeRemovedItems();
-
-    void startIndexTimer();
-    void resetIndex();
-
-    void addToIndex(QGraphicsItem *item);
-    void removeFromIndex(QGraphicsItem *item);
+    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;
 };
 
 QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h
new file mode 100644
index 0000000..2df5fbc
--- /dev/null
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h
@@ -0,0 +1,140 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the QtGui 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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QGRAPHICSSCENEBSPTREEINDEX_P_P_H
+#define QGRAPHICSSCENEBSPTREEINDEX_P_P_H
+
+//
+//  W A R N I N G
+//  -------------
+//
+// This file is not part of the Qt API.  It exists for the convenience
+// of qapplication_*.cpp, qwidget*.cpp and qfiledialog.cpp.  This header
+// file may change from version to version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include "qgraphicsscenebsptreeindex_p.h"
+
+#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
+
+#include <private/qobject_p.h>
+#include <private/qgraphicsitem_p.h>
+
+QT_BEGIN_NAMESPACE
+
+class QGraphicsScene;
+
+class QGraphicsSceneBspTreeIndexPrivate : public QObjectPrivate
+{
+    Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex)
+public:
+    QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene);
+
+    QGraphicsScene *scene;
+    QGraphicsSceneBspTree bsp;
+    QRectF sceneRect;
+    int bspTreeDepth;
+    int indexTimerId;
+    bool restartIndexTimer;
+    bool regenerateIndex;
+    int lastItemCount;
+
+    QList<QGraphicsItem *> indexedItems;
+    QList<QGraphicsItem *> unindexedItems;
+    QList<int> freeItemIndexes;
+
+    bool purgePending;
+    QList<QGraphicsItem *> removedItems;
+    void purgeRemovedItems();
+
+    void _q_updateIndex();
+    void startIndexTimer();
+    void resetIndex();
+
+    void addToIndex(QGraphicsItem *item);
+    void removeFromIndex(QGraphicsItem *item);
+
+    void _q_updateSortCache();
+    bool sortCacheEnabled;
+    bool updatingSortCache;
+    void invalidateSortCache();
+
+    static void climbTree(QGraphicsItem *item, int *stackingOrder);
+    static bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
+    static bool closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
+
+    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);
+};
+
+
+/*!
+    \internal
+*/
+inline bool qt_closestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
+{
+    // Return true if sibling item1 is on top of item2.
+    const QGraphicsItemPrivate *d1 = item1->d_ptr;
+    const QGraphicsItemPrivate *d2 = item2->d_ptr;
+    bool f1 = d1->flags & QGraphicsItem::ItemStacksBehindParent;
+    bool f2 = d2->flags & QGraphicsItem::ItemStacksBehindParent;
+    if (f1 != f2) return f2;
+    qreal z1 = d1->z;
+    qreal z2 = d2->z;
+    return z1 != z2 ? z1 > z2 : d1->siblingIndex > d2->siblingIndex;
+}
+
+QT_END_NAMESPACE
+
+#endif // QGRAPHICSSCENEBSPTREEINDEX_P_P_H
+
+#endif
+
diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp
index d0d6081..eeee74e 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.cpp
+++ b/src/gui/graphicsview/qgraphicssceneindex.cpp
@@ -41,6 +41,7 @@
 
 #include "qgraphicssceneindex.h"
 #include "qgraphicssceneindex_p.h"
+#include "qgraphicsscenebsptreeindex_p_p.h"
 #include "qgraphicsscene.h"
 #include "qgraphicsitem_p.h"
 #include "qgraphicsscene_p.h"
@@ -282,6 +283,14 @@ QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene)
 }
 
 /*!
+    \internal
+*/
+QGraphicsSceneIndex::QGraphicsSceneIndex(QObjectPrivate &dd, QGraphicsScene *scene)
+    : QObject(dd, scene)
+{
+}
+
+/*!
     Destroys the scene index.
 */
 QGraphicsSceneIndex::~QGraphicsSceneIndex()
@@ -301,7 +310,7 @@ QGraphicsScene* QGraphicsSceneIndex::scene() const
 /*!
     Returns the indexed area for the index
 */
-QRectF QGraphicsSceneIndex::indexedRect()
+QRectF QGraphicsSceneIndex::indexedRect() const
 {
     Q_D(const QGraphicsSceneIndex);
     return d->scene->d_func()->sceneRect;
@@ -351,8 +360,9 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, Qt::ItemSe
                 d->childItems_helper(&items, item, xinv.map(pos));
         }
     }
-
-    d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+    //### Needed but it should be handle differently
+    if (order != Qt::SortOrder(-1))
+        QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false);
     return items;
 }
 
@@ -415,9 +425,9 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, Qt::ItemSe
             }
         }
     }
-
+    //### Needed but it should be handle differently
     if (order != Qt::SortOrder(-1))
-        d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+        QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false);
     return items;
 }
 
@@ -474,9 +484,9 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF &polygon, Qt::
                 d->childItems_helper(&items, item, xinv.map(polygon), mode);
         }
     }
-
+    //### Needed but it should be handle differently
     if (order != Qt::SortOrder(-1))
-        d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+        QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false);
     return items;
 }
 QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
@@ -525,9 +535,9 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::
                 d->childItems_helper(&items, item, xinv.map(path), mode);
         }
     }
-
+    //### Needed but it should be handle differently
     if (order != Qt::SortOrder(-1))
-        d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+        QGraphicsSceneBspTreeIndexPrivate::sortItems(&items, order, false);
     return items;
 }
 
diff --git a/src/gui/graphicsview/qgraphicssceneindex.h b/src/gui/graphicsview/qgraphicssceneindex.h
index 11d9aae..084a623 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.h
+++ b/src/gui/graphicsview/qgraphicssceneindex.h
@@ -71,9 +71,9 @@ public:
 
     QGraphicsScene *scene() const;
 
-    virtual QRectF indexedRect();
+    virtual QRectF indexedRect() const;
 
-    virtual QList<QGraphicsItem *> items() const  = 0;
+    virtual QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const  = 0;
     virtual QList<QGraphicsItem *> items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
     virtual QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
     virtual QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
@@ -91,10 +91,15 @@ protected:
     virtual void prepareBoundingRectChange(const QGraphicsItem *item);
     virtual void sceneRectChanged(const QRectF &rect);
 
+    QGraphicsSceneIndex(QObjectPrivate &dd, QGraphicsScene *scene);
+
     friend class QGraphicsScene;
     friend class QGraphicsScenePrivate;
     friend class QGraphicsItem;
+    friend class QGraphicsItemPrivate;
+    friend class QGraphicsSceneBspTreeIndex;
 private:
+    Q_DISABLE_COPY(QGraphicsSceneIndex)
     Q_DECLARE_PRIVATE(QGraphicsSceneIndex)
 };
 
diff --git a/src/gui/graphicsview/qgraphicssceneindex_p.h b/src/gui/graphicsview/qgraphicssceneindex_p.h
index f2cdca3..2014693 100644
--- a/src/gui/graphicsview/qgraphicssceneindex_p.h
+++ b/src/gui/graphicsview/qgraphicssceneindex_p.h
@@ -58,6 +58,7 @@
 #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
 
 #include <private/qobject_p.h>
+#include <private/qgraphicsitem_p.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -86,7 +87,7 @@ public:
                            const QPainterPath &path,
                            Qt::ItemSelectionMode mode) const;
 
-    QGraphicsScene *scene;
+   QGraphicsScene *scene;
 };
 
 QT_END_NAMESPACE
diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
index dc45a17..3057b4a 100644
--- a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
@@ -105,7 +105,7 @@ public:
         return result;
     }
 
-    QList<QGraphicsItem *> items() const {
+    QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const {
         return m_items;
     }
 };
diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp
index 91f97a1..e8330a9 100644
--- a/src/gui/graphicsview/qgraphicsview.cpp
+++ b/src/gui/graphicsview/qgraphicsview.cpp
@@ -1056,7 +1056,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg
         *allItems = true;
 
         // All items are guaranteed within the exposed region, don't bother using the index.
-        QList<QGraphicsItem *> itemList(scene->items());
+        QList<QGraphicsItem *> itemList(scene->d_func()->index->items(Qt::DescendingOrder));
         int i = 0;
         while (i < itemList.size()) {
             const QGraphicsItem *item = itemList.at(i);
@@ -1069,9 +1069,6 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg
             else
                 ++i;
         }
-
-        // Sort the items.
-        QGraphicsScenePrivate::sortItems(&itemList, Qt::DescendingOrder, scene->d_func()->sortCacheEnabled);
         return itemList;
     }
 
@@ -2134,7 +2131,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat
 
     // Then find the minimal list of items that are inside \a path, and
     // convert it to a set.
-    QList<QGraphicsItem *> regularCandidates = scene->items(q->mapToScene(path), mode);
+    QList<QGraphicsItem *> regularCandidates = scene->items(q->mapToScene(path), mode, order, q->transform());
     QSet<QGraphicsItem *> candSet = QSet<QGraphicsItem *>::fromList(regularCandidates);
 
     QTransform viewMatrix = q->viewportTransform();
@@ -2161,10 +2158,6 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat
         }
         ++it;
     }
-
-    // ### Insertion sort would be faster.
-    if (order != Qt::SortOrder(-1))
-        QGraphicsScenePrivate::sortItems(&result, order, scene->d_func()->sortCacheEnabled);
     return result;
 }
 
diff --git a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
index 8afdeb4..c83134f 100644
--- a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
+++ b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
@@ -4685,6 +4685,11 @@ void tst_QGraphicsItem::itemClipsChildrenToShape()
     scene.render(&painter);
     painter.end();
 
+    QGraphicsView view(&scene);
+    view.show();
+
+    QTest::qWait(5000);
+
     QCOMPARE(image.pixel(16, 16), QColor(255, 0, 0).rgba());
     QCOMPARE(image.pixel(32, 32), QColor(0, 0, 255).rgba());
     QCOMPARE(image.pixel(50, 50), QColor(0, 255, 0).rgba());
diff --git a/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp b/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp
index eb117ab..dd997c7 100644
--- a/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp
+++ b/tests/auto/qgraphicsscene/tst_qgraphicsscene.cpp
@@ -379,8 +379,7 @@ void tst_QGraphicsScene::items()
             for (int x = minX; x < maxX; x += 100)
                 items << scene.addRect(QRectF(0, 0, 10, 10));
         }
-
-        QCOMPARE(scene.items(), items);
+        QCOMPARE(scene.items().size(), items.size());
         scene.itemAt(0, 0); // trigger indexing
 
         scene.removeItem(items.at(5));
@@ -397,7 +396,7 @@ void tst_QGraphicsScene::items()
         QVERIFY(!l2->sceneBoundingRect().intersects(l1->sceneBoundingRect()));
         QList<QGraphicsItem *> items;
         items<<l1<<l2;
-        QCOMPARE(scene.items(), items);
+        QCOMPARE(scene.items().size(), items.size());
         QVERIFY(scene.items(-1, -1, 2, 2).contains(l1));
         QVERIFY(scene.items(-1, -1, 2, 2).contains(l2));
     }
diff --git a/tests/auto/qgraphicsview/tst_qgraphicsview.cpp b/tests/auto/qgraphicsview/tst_qgraphicsview.cpp
index 8e490ad..447de34 100644
--- a/tests/auto/qgraphicsview/tst_qgraphicsview.cpp
+++ b/tests/auto/qgraphicsview/tst_qgraphicsview.cpp
@@ -2102,12 +2102,12 @@ void tst_QGraphicsView::resizeAnchor()
             view.setResizeAnchor(QGraphicsView::AnchorViewCenter);
         }
         view.centerOn(0, 0);
-        QTest::qWait(100);
+        QTest::qWait(250);
 
         QPointF f = view.mapToScene(50, 50);
         QPointF center = view.mapToScene(view.viewport()->rect().center());
 
-        QTest::qWait(100);
+        QTest::qWait(250);
 
         for (int size = 200; size <= 400; size += 25) {
             view.resize(size, size);
@@ -2122,7 +2122,7 @@ void tst_QGraphicsView::resizeAnchor()
                 QVERIFY(qAbs(newCenter.x() - center.x()) < slack);
                 QVERIFY(qAbs(newCenter.y() - center.y()) < slack);
             }
-            QTest::qWait(100);
+            QTest::qWait(250);
         }
     }
 }
@@ -2925,7 +2925,7 @@ void tst_QGraphicsView::task245469_itemsAtPointWithClip()
     QTest::qWait(100);
 
     QList<QGraphicsItem *> itemsAtCenter = view.items(view.viewport()->rect().center());
-    QCOMPARE(itemsAtCenter, (QList<QGraphicsItem *>() << child << parent));
+    QCOMPARE(itemsAtCenter, (QList<QGraphicsItem *>() << parent << child));
 
     QPolygonF p = view.mapToScene(QRect(view.viewport()->rect().center(), QSize(1, 1)));
     QList<QGraphicsItem *> itemsAtCenter2 = scene.items(p);