More re-factoring of QGraphicsSceneIndex.

New method: QGraphicsSceneIndex::estimateTopLevelItems.
QGraphicsSceneIndex::estimateItems returns *all* items within the rect,
but we are only interested in the top-levels (those that are within the
rect themselves or have descendants within the rect) when doing
recursive drawing/item-lookup.

All auto-tests pass. Demos/examples/manualtests run fine.

10 files changed, 98 insertions, 96 deletions

diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 3b1c8ad..85d05e9 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -1085,36 +1085,6 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item)
     return 0;
 }
 
-QList<QGraphicsItem *> QGraphicsScenePrivate::topLevelItemsInStackingOrder(const QTransform *const viewTransform,
-                                                                           const QRectF &sceneRect)
-{
-    if (indexMethod == QGraphicsScene::NoIndex || sceneRect.isNull()) {
-        ensureSortedTopLevelItems();
-        return topLevelItems;
-    }
-
-    const QList<QGraphicsItem *> tmp = index->estimateItems(sceneRect, Qt::SortOrder(-1),
-                                                            viewTransform ? *viewTransform : QTransform());
-    // estimateItems returns a list of *all* items, but we are only interested
-    // in the top-levels (those that are within the rect themselves and those that
-    // have descendants within the rect).
-    // ### Look into how we can add this feature to the BSP.
-    QList<QGraphicsItem *> tli;
-    for (int i = 0; i < tmp.size(); ++i) {
-        QGraphicsItem *topLevelItem = tmp.at(i)->topLevelItem();
-        if (!topLevelItem->d_ptr->itemDiscovered) {
-            tli << topLevelItem;
-            topLevelItem->d_ptr->itemDiscovered = 1;
-        }
-    }
-    // Reset discovered bit.
-    for (int i = 0; i < tli.size(); ++i)
-        tli.at(i)->d_ptr->itemDiscovered = 0;
-
-    qSort(tli.begin(), tli.end(), qt_notclosestLeaf);
-    return tli;
-}
-
 /*!
     \internal
 
@@ -1759,7 +1729,7 @@ QList<QGraphicsItem *> QGraphicsScene::collidingItems(const QGraphicsItem *item,
 
     // Does not support ItemIgnoresTransformations.
     QList<QGraphicsItem *> tmp;
-    foreach (QGraphicsItem *itemInVicinity, d->index->estimateItems(item->sceneBoundingRect(), Qt::AscendingOrder, QTransform())) {
+    foreach (QGraphicsItem *itemInVicinity, d->index->estimateItems(item->sceneBoundingRect(), Qt::AscendingOrder)) {
         if (item != itemInVicinity && item->collidesWithItem(itemInVicinity, mode))
             tmp << itemInVicinity;
     }
@@ -4209,6 +4179,20 @@ void QGraphicsScenePrivate::drawItemHelper(QGraphicsItem *item, QPainter *painte
     }
 }
 
+void QGraphicsScenePrivate::drawItems(QPainter *painter, const QTransform *const viewTransform,
+                                      QRegion *exposedRegion, QWidget *widget)
+{
+    QRectF exposedSceneRect;
+    if (exposedRegion && indexMethod != QGraphicsScene::NoIndex) {
+        exposedSceneRect = exposedRegion->boundingRect().adjusted(-1, -1, 1, 1);
+        if (viewTransform)
+            exposedSceneRect = viewTransform->inverted().mapRect(exposedSceneRect);
+    }
+    const QList<QGraphicsItem *> tli = index->estimateTopLevelItems(exposedSceneRect, Qt::DescendingOrder);
+    for (int i = 0; i < tli.size(); ++i)
+        drawSubtreeRecursive(tli.at(i), painter, viewTransform, exposedRegion, widget);
+}
+
 void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter,
                                                  const QTransform *const viewTransform,
                                                  QRegion *exposedRegion, QWidget *widget,
diff --git a/src/gui/graphicsview/qgraphicsscene_bsp.cpp b/src/gui/graphicsview/qgraphicsscene_bsp.cpp
index 7d30749..fb4b9a4 100644
--- a/src/gui/graphicsview/qgraphicsscene_bsp.cpp
+++ b/src/gui/graphicsview/qgraphicsscene_bsp.cpp
@@ -70,12 +70,15 @@ class QGraphicsSceneFindItemBspTreeVisitor : public QGraphicsSceneBspTreeVisitor
 {
 public:
     QList<QGraphicsItem *> *foundItems;
+    bool onlyTopLevelItems;
 
     void visit(QList<QGraphicsItem *> *items)
     {
         for (int i = 0; i < items->size(); ++i) {
             QGraphicsItem *item = items->at(i);
-            if (!item->d_func()->itemDiscovered && item->isVisible()) {
+            if (onlyTopLevelItems && item->d_ptr->parent)
+                item = item->topLevelItem();
+            if (!item->d_func()->itemDiscovered && item->d_ptr->visible) {
                 item->d_func()->itemDiscovered = 1;
                 foundItems->prepend(item);
             }
@@ -143,10 +146,11 @@ void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items)
     }
 }
 
-QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect) const
+QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect, bool onlyTopLevelItems) const
 {
     QList<QGraphicsItem *> tmp;
     findVisitor->foundItems = &tmp;
+    findVisitor->onlyTopLevelItems = onlyTopLevelItems;
     climbTree(findVisitor, rect);
     // Reset discovery bits.
     for (int i = 0; i < tmp.size(); ++i)
diff --git a/src/gui/graphicsview/qgraphicsscene_bsp_p.h b/src/gui/graphicsview/qgraphicsscene_bsp_p.h
index 24b926c..4cac64a 100644
--- a/src/gui/graphicsview/qgraphicsscene_bsp_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_bsp_p.h
@@ -92,7 +92,7 @@ public:
     void removeItem(QGraphicsItem *item, const QRectF &rect);
     void removeItems(const QSet<QGraphicsItem *> &items);
 
-    QList<QGraphicsItem *> items(const QRectF &rect) const;
+    QList<QGraphicsItem *> items(const QRectF &rect, bool onlyTopLevelItems = false) const;
     int leafCount() const;
 
     inline int firstChildIndex(int index) const
@@ -106,8 +106,6 @@ public:
 private:
     void initialize(const QRectF &rect, int depth, int index);
     void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index = 0) const;
-
-    void findItems(QList<QGraphicsItem *> *foundItems, const QRectF &rect, int index);
     QRectF rectForIndex(int index) const;
 
     QVector<Node> nodes;
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index 23b0dd5..245380f 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -191,26 +191,13 @@ public:
     QGraphicsWidget *windowForItem(const QGraphicsItem *item) const;
 
     bool sortCacheEnabled; // for compatibility
-    QList<QGraphicsItem *> topLevelItemsInStackingOrder(const QTransform *const, const QRectF&);
 
     void drawItemHelper(QGraphicsItem *item, QPainter *painter,
                         const QStyleOptionGraphicsItem *option, QWidget *widget,
                         bool painterStateProtection);
 
-    inline void drawItems(QPainter *painter, const QTransform *const viewTransform,
-                          QRegion *exposedRegion, QWidget *widget)
-    {
-        QRectF exposedSceneRect;
-        if (exposedRegion && indexMethod != QGraphicsScene::NoIndex) {
-            exposedSceneRect = exposedRegion->boundingRect().adjusted(-1, -1, 1, 1);
-            if (viewTransform)
-                exposedSceneRect = viewTransform->inverted().mapRect(exposedSceneRect);
-        }
-        const QList<QGraphicsItem *> tli = topLevelItemsInStackingOrder(viewTransform, exposedSceneRect);
-        for (int i = 0; i < tli.size(); ++i)
-            drawSubtreeRecursive(tli.at(i), painter, viewTransform, exposedRegion, widget);
-        return;
-    }
+    void drawItems(QPainter *painter, const QTransform *const viewTransform,
+                   QRegion *exposedRegion, QWidget *widget);
 
     void drawSubtreeRecursive(QGraphicsItem *item, QPainter *painter, const QTransform *const,
                               QRegion *exposedRegion, QWidget *widget, qreal parentOpacity = qreal(1.0));
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
index 0688cb1..a7b4828 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp
@@ -372,6 +372,32 @@ void QGraphicsSceneBspTreeIndexPrivate::removeItem(QGraphicsItem *item, bool rec
     }
 }
 
+QList<QGraphicsItem *> QGraphicsSceneBspTreeIndexPrivate::estimateItems(const QRectF &rect, Qt::SortOrder order,
+                                                                        bool onlyTopLevelItems)
+{
+    Q_Q(QGraphicsSceneBspTreeIndex);
+    if (onlyTopLevelItems && rect.isNull())
+        return q->QGraphicsSceneIndex::estimateTopLevelItems(rect, order);
+
+    purgeRemovedItems();
+    _q_updateSortCache();
+    Q_ASSERT(unindexedItems.isEmpty());
+
+    QList<QGraphicsItem *> rectItems = bsp.items(rect, onlyTopLevelItems);
+    if (onlyTopLevelItems) {
+        for (int i = 0; i < untransformableItems.size(); ++i) {
+            QGraphicsItem *item = untransformableItems.at(i);
+            if (!item->d_ptr->parent)
+                rectItems << item;
+        }
+    } else {
+        rectItems += untransformableItems;
+    }
+
+    sortItems(&rectItems, order, sortCacheEnabled, onlyTopLevelItems);
+    return rectItems;
+}
+
 /*!
     Returns true if \a item1 is on top of \a item2.
 
@@ -442,8 +468,19 @@ bool QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withoutCache(const QGrap
     \internal
 */
 void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
-                                      bool sortCacheEnabled)
+                                                  bool sortCacheEnabled, bool onlyTopLevelItems)
 {
+    if (order == Qt::SortOrder(-1))
+        return;
+
+    if (onlyTopLevelItems) {
+        if (order == Qt::AscendingOrder)
+            qSort(itemList->begin(), itemList->end(), qt_closestLeaf);
+        else if (order == Qt::DescendingOrder)
+            qSort(itemList->begin(), itemList->end(), qt_notclosestLeaf);
+        return;
+    }
+
     if (sortCacheEnabled) {
         if (order == Qt::AscendingOrder) {
             qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
@@ -548,36 +585,17 @@ void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *
     \a deviceTransform is the transformation apply to the view.
 
 */
-QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order,
-                                                                 const QTransform &deviceTransform) const
+QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order) const
 {
     Q_D(const QGraphicsSceneBspTreeIndex);
-    const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems();
-    const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->_q_updateSortCache();
-
-    // ### Handle items that ignore transformations
-    Q_UNUSED(deviceTransform);
-
-    QList<QGraphicsItem *> rectItems = d->bsp.items(rect);
-
-    // Fill in with any unindexed items
-    for (int i = 0; i < d->unindexedItems.size(); ++i) {
-        if (QGraphicsItem *item = d->unindexedItems.at(i)) {
-            if (item->d_ptr->visible
-                && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) {
-                QRectF boundingRect = item->sceneBoundingRect();
-                if (QRectF_intersects(boundingRect, rect))
-                    rectItems << item;
-            }
-        }
-    }
-
-    rectItems += d->untransformableItems;
-    d->sortItems(&rectItems, order, d->sortCacheEnabled);
-
-    return rectItems;
+    return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order);
 }
 
+QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const
+{
+    Q_D(const QGraphicsSceneBspTreeIndex);
+    return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order, /*onlyTopLevels=*/true);
+}
 
 /*!
     \fn QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order = Qt::AscendingOrder) const;
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
index 437b17d..3ac922b 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
@@ -82,8 +82,8 @@ public:
     QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0);
     ~QGraphicsSceneBspTreeIndex();
 
-    QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const;
-
+    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::AscendingOrder) const;
 
     int bspTreeDepth();
@@ -145,6 +145,7 @@ public:
     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 bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2);
@@ -159,7 +160,8 @@ public:
         return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
     }
 
-    static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order, bool cached);
+    static void sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
+                          bool cached, bool onlyTopLevelItems = false);
 };
 
 
diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp
index d6281e2..5626051 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.cpp
+++ b/src/gui/graphicsview/qgraphicssceneindex.cpp
@@ -482,12 +482,25 @@ QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::
 /*!
     This virtual function return an estimation of items at position \a point.
     This method return a list sorted using \a order.
-    \a deviceTransform is the transformation apply to the view.
 */
-QList<QGraphicsItem *> QGraphicsSceneIndex::estimateItems(const QPointF &point, Qt::SortOrder order,
-                                                          const QTransform &deviceTransform) const
+QList<QGraphicsItem *> QGraphicsSceneIndex::estimateItems(const QPointF &point, Qt::SortOrder order) const
+{
+    return estimateItems(QRectF(point, QSize(1, 1)), order);
+}
+
+QList<QGraphicsItem *> QGraphicsSceneIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const
 {
-    return estimateItems(QRectF(point, QSize(1,1)), order, deviceTransform);
+    Q_D(const QGraphicsSceneIndex);
+    Q_UNUSED(rect);
+    QGraphicsScenePrivate *scened = d->scene->d_func();
+    scened->ensureSortedTopLevelItems();
+    if (order == Qt::AscendingOrder) {
+        QList<QGraphicsItem *> sorted;
+        for (int i = scened->topLevelItems.size() - 1; i >= 0; --i)
+            sorted << scened->topLevelItems.at(i);
+        return sorted;
+    }
+    return scened->topLevelItems;
 }
 
 /*!
diff --git a/src/gui/graphicsview/qgraphicssceneindex_p.h b/src/gui/graphicsview/qgraphicssceneindex_p.h
index aabfa79..6521765 100644
--- a/src/gui/graphicsview/qgraphicssceneindex_p.h
+++ b/src/gui/graphicsview/qgraphicssceneindex_p.h
@@ -97,10 +97,9 @@ public:
                                          Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
     virtual QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode,
                                          Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
-    virtual QList<QGraphicsItem *> estimateItems(const QPointF &point,
-                                                 Qt::SortOrder order, const QTransform &deviceTransform) const;
-    virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect,
-                                                 Qt::SortOrder order, const QTransform &deviceTransform) const = 0;
+    virtual QList<QGraphicsItem *> estimateItems(const QPointF &point, Qt::SortOrder order) const;
+    virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const = 0;
+    virtual QList<QGraphicsItem *> estimateTopLevelItems(const QRectF &, Qt::SortOrder order) const;
 
 protected Q_SLOTS:
     virtual void updateSceneRect(const QRectF &rect);
@@ -154,7 +153,8 @@ inline void QGraphicsSceneIndexPrivate::items_helper(const QRectF &rect, QGraphi
                                                      QList<QGraphicsItem *> *items, const QTransform &viewTransform,
                                                      Qt::ItemSelectionMode mode, Qt::SortOrder order) const
 {
-    const QList<QGraphicsItem *> tli = scene->d_func()->topLevelItemsInStackingOrder(&viewTransform, rect);
+    Q_Q(const QGraphicsSceneIndex);
+    const QList<QGraphicsItem *> tli = q->estimateTopLevelItems(rect, Qt::DescendingOrder);
     const QTransform identity;
     for (int i = 0; i < tli.size(); ++i)
         recursive_items_helper(tli.at(i), rect, intersector, items, identity, viewTransform, mode, order);
diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex.cpp b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp
index bc401f2..5e6ac30 100644
--- a/src/gui/graphicsview/qgraphicsscenelinearindex.cpp
+++ b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp
@@ -30,13 +30,10 @@
 
 
 /*!
-    \fn virtual QList<QGraphicsItem *> QGraphicsSceneLinearIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const;
+    \fn virtual QList<QGraphicsItem *> QGraphicsSceneLinearIndex::estimateItems(const QRectF &rect, Qt::SortOrder order) const;
 
     Returns an estimation visible items that are either inside or
     intersect with the specified \a rect and return a list sorted using \a order.
-
-    \a deviceTransform is the transformation apply to the view.
-
 */
 
 /*!
diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
index 9463487..56dde3a 100644
--- a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
@@ -79,11 +79,10 @@ public:
     QList<QGraphicsItem *> items(Qt::SortOrder order = Qt::AscendingOrder) const
     { Q_UNUSED(order); return m_items; }
 
-    virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const
+    virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order) const
     {
         Q_UNUSED(rect);
         Q_UNUSED(order);
-        Q_UNUSED(deviceTransform);
         return m_items;
     }