First bunch of changes after an very first API review

This basically move some logic from the scene to the index base class.
Lot of work need to be done in order to benefits from the device
transform. The sorting needs to be move in the BSP tree.

15 files changed, 857 insertions, 780 deletions

diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri
index 9097497..cc57892 100644
--- a/src/gui/graphicsview/graphicsview.pri
+++ b/src/gui/graphicsview/graphicsview.pri
@@ -10,6 +10,7 @@ HEADERS += \
         graphicsview/qgraphicsscene_bsp_p.h \
         graphicsview/qgraphicsscenelinearindex_p.h \
         graphicsview/qgraphicssceneindex.h \
+        graphicsview/qgraphicssceneindex_p.h \
         graphicsview/qgraphicssceneevent.h \
         graphicsview/qgraphicsview_p.h \
         graphicsview/qgraphicsview.h
diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index c1d44d3..fc5895c 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -567,17 +567,6 @@
 
 QT_BEGIN_NAMESPACE
 
-// QRectF::intersects() returns false always if either the source or target
-// rectangle's width or height are 0. This works around that problem.
-static inline void _q_adjustRect(QRectF *rect)
-{
-    Q_ASSERT(rect);
-    if (!rect->width())
-        rect->adjust(-0.00001, 0, 0.00001, 0);
-    if (!rect->height())
-        rect->adjust(0, -0.00001, 0, 0.00001);
-}
-
 static inline void _q_adjustRect(QRect *rect)
 {
     Q_ASSERT(rect);
@@ -6357,7 +6346,7 @@ void QGraphicsItem::addToIndex()
         return;
     }
     if (d_ptr->scene)
-        d_ptr->scene->d_func()->index->insertItem(this);
+        d_ptr->scene->d_func()->index->addItem(this);
     d_ptr->updateHelper();
 }
 
@@ -6372,7 +6361,7 @@ void QGraphicsItem::removeFromIndex()
 {
     d_ptr->updateHelper();
     if (d_ptr->scene)
-        d_ptr->scene->d_func()->index->removeItem(this,false);
+        d_ptr->scene->d_func()->index->removeItem(this);
 }
 
 /*!
@@ -6393,7 +6382,7 @@ void QGraphicsItem::prepareGeometryChange()
     if (d_ptr->scene) {
         d_ptr->updateHelper(QRectF(), false, /*maybeDirtyClipPath=*/!d_ptr->inSetPosHelper);
         QGraphicsScenePrivate *scenePrivate = d_ptr->scene->d_func();
-        scenePrivate->index->updateItem(this);
+        scenePrivate->index->prepareBoundingRectChange(this);
     }
 
     if (d_ptr->inSetPosHelper)
diff --git a/src/gui/graphicsview/qgraphicsitem.h b/src/gui/graphicsview/qgraphicsitem.h
index cb86020..e244c13 100644
--- a/src/gui/graphicsview/qgraphicsitem.h
+++ b/src/gui/graphicsview/qgraphicsitem.h
@@ -409,6 +409,8 @@ protected:
     virtual void setExtension(Extension extension, const QVariant &variant);
     virtual QVariant extension(const QVariant &variant) const;
 
+    bool operator<(const QGraphicsItem *other) const;
+
 protected:
     QGraphicsItem(QGraphicsItemPrivate &dd,
                   QGraphicsItem *parent, QGraphicsScene *scene);
@@ -430,6 +432,8 @@ private:
     friend class QGraphicsWidget;
     friend class QGraphicsWidgetPrivate;
     friend class QGraphicsProxyWidgetPrivate;
+    friend class QGraphicsSceneIndex;
+    friend class QGraphicsSceneIndexPrivate;
     friend class QGraphicsSceneBspTreeIndex;
     friend class ::tst_QGraphicsItem;
     friend bool qt_closestLeaf(const QGraphicsItem *, const QGraphicsItem *);
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 51c8294..9b6d40b 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -249,65 +249,6 @@
 
 QT_BEGIN_NAMESPACE
 
-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);
-}
-
-// QRectF::intersects() returns false always if either the source or target
-// rectangle's width or height are 0. This works around that problem.
-static inline void _q_adjustRect(QRectF *rect)
-{
-    Q_ASSERT(rect);
-    if (!rect->width())
-        rect->adjust(-0.00001, 0, 0.00001, 0);
-    if (!rect->height())
-        rect->adjust(0, -0.00001, 0, 0.00001);
-}
-
-static inline QRectF adjustedItemBoundingRect(const QGraphicsItem *item)
-{
-    Q_ASSERT(item);
-    QRectF boundingRect(item->boundingRect());
-    _q_adjustRect(&boundingRect);
-    return boundingRect;
-}
-
 static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraphicsSceneMouseEvent *mouseEvent)
 {
     hover->setWidget(mouseEvent->widget());
@@ -374,21 +315,6 @@ void QGraphicsScenePrivate::init()
 /*!
     \internal
 */
-QList<QGraphicsItem *> QGraphicsScenePrivate::estimateItemsInRect(const QRectF &rect) const
-{
-    const_cast<QGraphicsScenePrivate *>(this)->_q_updateSortCache();
-
-    // ### Only do this once in a while.
-    QGraphicsScenePrivate *that = const_cast<QGraphicsScenePrivate *>(this);
-
-    // Get items from index
-    return that->index->items(rect);
-
-}
-
-/*!
-    \internal
-*/
 void QGraphicsScenePrivate::_q_emitUpdated()
 {
     Q_Q(QGraphicsScene);
@@ -528,7 +454,7 @@ void QGraphicsScenePrivate::_q_removeItemLater(QGraphicsItem *item)
     item->clearFocus();
 
     //We ask for a removing in the index
-    this->index->removeItem(item, true);
+    this->index->deleteItem(item);
 
     // Reset the mouse grabber and focus item data.
     if (item == focusItem)
@@ -1145,444 +1071,6 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item)
     return 0;
 }
 
-
-QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QPointF &pos) const
-{
-    QList<QGraphicsItem *> items;
-
-    // The index returns a rough estimate of what items are inside the rect.
-    // Refine it by iterating through all returned items.
-    QRectF adjustedRect = QRectF(pos, QSize(1,1));
-    foreach (QGraphicsItem *item, estimateItemsInRect(adjustedRect)) {
-        // Find the item's scene transform in a clever way.
-        QTransform x = item->sceneTransform();
-        bool keep = false;
-
-        // ### _q_adjustedRect is only needed because QRectF::intersects,
-        // QRectF::contains and QTransform::map() and friends don't work with
-        // flat rectangles.
-        const QRectF br(adjustedItemBoundingRect(item));
-            // Rect intersects/contains item's shape
-        if (QRectF_intersects(adjustedRect, x.mapRect(br))) {
-            bool ok;
-            QTransform xinv = x.inverted(&ok);
-            if (ok) {
-                if (item->contains(xinv.map(pos))) {
-                    items << item;
-                    keep = true;
-                }
-            }
-        }
-
-        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
-            // Recurse into children that clip children.
-            bool ok;
-            QTransform xinv = x.inverted(&ok);
-            if (ok)
-                childItems_helper(&items, item, xinv.map(pos));
-        }
-    }
-
-    sortItems(&items, Qt::AscendingOrder, sortCacheEnabled);
-    return items;
-}
-
-QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QRectF &rect,
-                                                           Qt::ItemSelectionMode mode,
-                                                           Qt::SortOrder order) const
-{
-    QList<QGraphicsItem *> items;
-
-    QPainterPath path;
-
-    // The index returns a rough estimate of what items are inside the rect.
-    // Refine it by iterating through all returned items.
-    QRectF adjustedRect(rect);
-    _q_adjustRect(&adjustedRect);
-    foreach (QGraphicsItem *item, estimateItemsInRect(adjustedRect)) {
-        // Find the item's scene transform in a clever way.
-        QTransform x = item->sceneTransform();
-        bool keep = false;
-
-        // ### _q_adjustedRect is only needed because QRectF::intersects,
-        // QRectF::contains and QTransform::map() and friends don't work with
-        // flat rectangles.
-        const QRectF br(adjustedItemBoundingRect(item));
-        if (mode >= Qt::ContainsItemBoundingRect) {
-            // Rect intersects/contains item's bounding rect
-            QRectF mbr = x.mapRect(br);
-            if ((mode == Qt::IntersectsItemBoundingRect && QRectF_intersects(rect, mbr))
-                || (mode == Qt::ContainsItemBoundingRect && rect != mbr && rect.contains(mbr))) {
-                items << item;
-                keep = true;
-            }
-        } else {
-            // Rect intersects/contains item's shape
-            if (QRectF_intersects(adjustedRect, x.mapRect(br))) {
-                bool ok;
-                QTransform xinv = x.inverted(&ok);
-                if (ok) {
-                    if (path.isEmpty())
-                        path.addRect(rect);
-                    if (itemCollidesWithPath(item, xinv.map(path), mode)) {
-                        items << item;
-                        keep = true;
-                    }
-                }
-            }
-        }
-
-        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
-            // Recurse into children that clip children.
-            bool ok;
-            QTransform xinv = x.inverted(&ok);
-            if (ok) {
-                if (x.type() <= QTransform::TxScale) {
-                    // Rect
-                    childItems_helper(&items, item, xinv.mapRect(rect), mode);
-                } else {
-                    // Polygon
-                    childItems_helper(&items, item, xinv.map(rect), mode);
-                }
-            }
-        }
-    }
-
-    if (order != Qt::SortOrder(-1))
-        sortItems(&items, order, sortCacheEnabled);
-    return items;
-}
-
-QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QPolygonF &polygon,
-                                                           Qt::ItemSelectionMode mode,
-                                                           Qt::SortOrder order) const
-{
-    QList<QGraphicsItem *> items;
-
-    QRectF polyRect(polygon.boundingRect());
-     _q_adjustRect(&polyRect);
-    QPainterPath path;
-
-    // The index returns a rough estimate of what items are inside the rect.
-    // Refine it by iterating through all returned items.
-    foreach (QGraphicsItem *item, estimateItemsInRect(polyRect)) {
-        // Find the item's scene transform in a clever way.
-        QTransform x = item->sceneTransform();
-        bool keep = false;
-
-        // ### _q_adjustedRect is only needed because QRectF::intersects,
-        // QRectF::contains and QTransform::map() and friends don't work with
-        // flat rectangles.
-        const QRectF br(adjustedItemBoundingRect(item));
-        if (mode >= Qt::ContainsItemBoundingRect) {
-            // Polygon contains/intersects item's bounding rect
-            if (path == QPainterPath())
-                path.addPolygon(polygon);
-            if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br)))
-                || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) {
-                items << item;
-                keep = true;
-            }
-        } else {
-            // Polygon contains/intersects item's shape
-            if (QRectF_intersects(polyRect, x.mapRect(br))) {
-                bool ok;
-                QTransform xinv = x.inverted(&ok);
-                if (ok) {
-                    if (path == QPainterPath())
-                        path.addPolygon(polygon);
-                    if (itemCollidesWithPath(item, xinv.map(path), mode)) {
-                        items << item;
-                        keep = true;
-                    }
-                }
-            }
-        }
-
-        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
-            // Recurse into children that clip children.
-            bool ok;
-            QTransform xinv = x.inverted(&ok);
-            if (ok)
-                childItems_helper(&items, item, xinv.map(polygon), mode);
-        }
-    }
-
-    if (order != Qt::SortOrder(-1))
-        sortItems(&items, order, sortCacheEnabled);
-    return items;
-}
-
-QList<QGraphicsItem *> QGraphicsScenePrivate::items_helper(const QPainterPath &path,
-                                                           Qt::ItemSelectionMode mode,
-                                                           Qt::SortOrder order) const
-{
-    QList<QGraphicsItem *> items;
-    QRectF pathRect(path.controlPointRect());
-    _q_adjustRect(&pathRect);
-
-    // The index returns a rough estimate of what items are inside the rect.
-    // Refine it by iterating through all returned items.
-    foreach (QGraphicsItem *item, estimateItemsInRect(pathRect)) {
-        // Find the item's scene transform in a clever way.
-        QTransform x = item->sceneTransform();
-        bool keep = false;
-
-        // ### _q_adjustedRect is only needed because QRectF::intersects,
-        // QRectF::contains and QTransform::map() and friends don't work with
-        // flat rectangles.
-        const QRectF br(adjustedItemBoundingRect(item));
-        if (mode >= Qt::ContainsItemBoundingRect) {
-            // Path contains/intersects item's bounding rect
-            if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br)))
-                || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) {
-                items << item;
-                keep = true;
-            }
-        } else {
-            // Path contains/intersects item's shape
-            if (QRectF_intersects(pathRect, x.mapRect(br))) {
-                bool ok;
-                QTransform xinv = x.inverted(&ok);
-                if (ok) {
-                    if (itemCollidesWithPath(item, xinv.map(path), mode)) {
-                        items << item;
-                        keep = true;
-                    }
-                }
-            }
-        }
-
-        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
-            bool ok;
-            QTransform xinv = x.inverted(&ok);
-            if (ok)
-                childItems_helper(&items, item, xinv.map(path), mode);
-        }
-    }
-
-    if (order != Qt::SortOrder(-1))
-        sortItems(&items, order, sortCacheEnabled);
-    return items;
-}
-
-void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items,
-                                              const QGraphicsItem *parent,
-                                              const QPointF &pos) const
-{
-    bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
-    if (parentClip && parent->d_ptr->isClippedAway())
-        return;
-    // ### is this needed?
-    if (parentClip && !parent->boundingRect().contains(pos))
-        return;
-
-    QList<QGraphicsItem *> &children = parent->d_ptr->children;
-    for (int i = 0; i < children.size(); ++i) {
-        QGraphicsItem *item = children.at(i);
-        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
-            continue;
-
-        // Skip invisible items and all their children.
-        if (item->d_ptr->isInvisible())
-            continue;
-
-        bool keep = false;
-        if (!item->d_ptr->isClippedAway()) {
-            if (item->contains(item->mapFromParent(pos))) {
-                items->append(item);
-                keep = true;
-            }
-        }
-
-        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty())
-            // Recurse into children.
-            childItems_helper(items, item, item->mapFromParent(pos));
-    }
-}
-
-
-void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items,
-                                              const QGraphicsItem *parent,
-                                              const QRectF &rect,
-                                              Qt::ItemSelectionMode mode) const
-{
-    bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
-    if (parentClip && parent->d_ptr->isClippedAway())
-        return;
-    QRectF adjustedRect(rect);
-    _q_adjustRect(&adjustedRect);
-    QRectF r = !parentClip ? adjustedRect : adjustedRect.intersected(adjustedItemBoundingRect(parent));
-    if (r.isEmpty())
-        return;
-
-    QPainterPath path;
-    QList<QGraphicsItem *> &children = parent->d_ptr->children;
-    for (int i = 0; i < children.size(); ++i) {
-        QGraphicsItem *item = children.at(i);
-        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
-            continue;
-
-        // Skip invisible items and all their children.
-        if (item->d_ptr->isInvisible())
-            continue;
-
-        bool keep = false;
-        if (!item->d_ptr->isClippedAway()) {
-            // ### _q_adjustedRect is only needed because QRectF::intersects,
-            // QRectF::contains and QTransform::map() and friends don't work with
-            // flat rectangles.
-            const QRectF br(adjustedItemBoundingRect(item));
-            QRectF mbr = item->mapRectToParent(br);
-            if (mode >= Qt::ContainsItemBoundingRect) {
-                // Rect intersects/contains item's bounding rect
-                if ((mode == Qt::IntersectsItemBoundingRect && QRectF_intersects(rect, mbr))
-                    || (mode == Qt::ContainsItemBoundingRect && rect != mbr && rect.contains(br))) {
-                    items->append(item);
-                    keep = true;
-                }
-            } else {
-                // Rect intersects/contains item's shape
-                if (QRectF_intersects(rect, mbr)) {
-                    if (path == QPainterPath())
-                        path.addRect(rect);
-                    if (itemCollidesWithPath(item, item->mapFromParent(path), mode)) {
-                        items->append(item);
-                        keep = true;
-                    }
-                }
-            }
-        }
-
-        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) {
-            // Recurse into children.
-            if (!item->d_ptr->hasTransform || item->transform().type() <= QTransform::TxScale) {
-                // Rect
-                childItems_helper(items, item, item->mapRectFromParent(rect), mode);
-            } else {
-                // Polygon
-                childItems_helper(items, item, item->mapFromParent(rect), mode);
-            }
-        }
-    }
-}
-
-
-void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items,
-                                              const QGraphicsItem *parent,
-                                              const QPolygonF &polygon,
-                                              Qt::ItemSelectionMode mode) const
-{
-    bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
-    if (parentClip && parent->d_ptr->isClippedAway())
-        return;
-    QRectF polyRect(polygon.boundingRect());
-    _q_adjustRect(&polyRect);
-    QRectF r = !parentClip ? polyRect : polyRect.intersected(adjustedItemBoundingRect(parent));
-    if (r.isEmpty())
-        return;
-
-    QPainterPath path;
-    QList<QGraphicsItem *> &children = parent->d_ptr->children;
-    for (int i = 0; i < children.size(); ++i) {
-        QGraphicsItem *item = children.at(i);
-        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
-            continue;
-
-        // Skip invisible items.
-        if (item->d_ptr->isInvisible())
-            continue;
-
-        bool keep = false;
-        if (!item->d_ptr->isClippedAway()) {
-            // ### _q_adjustedRect is only needed because QRectF::intersects,
-            // QRectF::contains and QTransform::map() and friends don't work with
-            // flat rectangles.
-            const QRectF br(adjustedItemBoundingRect(item));
-            if (mode >= Qt::ContainsItemBoundingRect) {
-                // Polygon contains/intersects item's bounding rect
-                if (path == QPainterPath())
-                    path.addPolygon(polygon);
-                if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br)))
-                    || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) {
-                    items->append(item);
-                    keep = true;
-                }
-            } else {
-                // Polygon contains/intersects item's shape
-                if (QRectF_intersects(polyRect, item->mapRectToParent(br))) {
-                    if (path == QPainterPath())
-                        path.addPolygon(polygon);
-                    if (itemCollidesWithPath(item, item->mapFromParent(path), mode)) {
-                        items->append(item);
-                        keep = true;
-                    }
-                }
-            }
-        }
-
-        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) {
-            // Recurse into children that clip children.
-            childItems_helper(items, item, item->mapFromParent(polygon), mode);
-        }
-    }
-}
-
-void QGraphicsScenePrivate::childItems_helper(QList<QGraphicsItem *> *items,
-                                              const QGraphicsItem *parent,
-                                              const QPainterPath &path,
-                                              Qt::ItemSelectionMode mode) const
-{
-    bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
-    if (parentClip && parent->d_ptr->isClippedAway())
-        return;
-    QRectF pathRect(path.boundingRect());
-    _q_adjustRect(&pathRect);
-    QRectF r = !parentClip ? pathRect : pathRect.intersected(adjustedItemBoundingRect(parent));
-    if (r.isEmpty())
-        return;
-
-    QList<QGraphicsItem *> &children = parent->d_ptr->children;
-    for (int i = 0; i < children.size(); ++i) {
-        QGraphicsItem *item = children.at(i);
-        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
-            continue;
-
-        // Skip invisible items.
-        if (item->d_ptr->isInvisible())
-            continue;
-
-        bool keep = false;
-        if (!item->d_ptr->isClippedAway()) {
-            // ### _q_adjustedRect is only needed because QRectF::intersects,
-            // QRectF::contains and QTransform::map() and friends don't work with
-            // flat rectangles.
-            const QRectF br(adjustedItemBoundingRect(item));
-            if (mode >= Qt::ContainsItemBoundingRect) {
-                // Polygon contains/intersects item's bounding rect
-                if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br)))
-                    || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) {
-                    items->append(item);
-                    keep = true;
-                }
-            } else {
-                // Path contains/intersects item's shape
-                if (QRectF_intersects(pathRect, item->mapRectToParent(br))) {
-                    if (itemCollidesWithPath(item, item->mapFromParent(path), mode)) {
-                        items->append(item);
-                        keep = true;
-                    }
-                }
-            }
-        }
-
-        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) {
-            // Recurse into children that clip children.
-            childItems_helper(items, item, item->mapFromParent(path), mode);
-        }
-    }
-}
-
 void QGraphicsScenePrivate::invalidateSortCache()
 {
     Q_Q(QGraphicsScene);
@@ -1709,7 +1197,8 @@ void QGraphicsScenePrivate::climbTree(QGraphicsItem *item, int *stackingOrder)
 
 void QGraphicsScenePrivate::_q_updateSortCache()
 {
-    index->updateIndex();
+    //### FIXME
+    //index->updateIndex();
 
     if (!sortCacheEnabled || !updatingSortCache)
         return;
@@ -1719,8 +1208,8 @@ void QGraphicsScenePrivate::_q_updateSortCache()
 
     QList<QGraphicsItem *> topLevels;
 
-    for (int i = 0; i < index->indexedItems().count(); ++i) {
-        QGraphicsItem *item = index->indexedItems().at(i);
+    for (int i = 0; i < index->items().count(); ++i) {
+        QGraphicsItem *item = index->items().at(i);
         if (item && item->parentItem() == 0)
             topLevels << item;
     }
@@ -1933,8 +1422,7 @@ QGraphicsScene::~QGraphicsScene()
 QRectF QGraphicsScene::sceneRect() const
 {
     Q_D(const QGraphicsScene);
-    d->index->updateIndex();
-    return d->hasSceneRect ? d->index->rect() : d->growingItemsBoundingRect;
+    return d->hasSceneRect ? d->sceneRect : d->growingItemsBoundingRect;
 }
 void QGraphicsScene::setSceneRect(const QRectF &rect)
 {
@@ -1942,7 +1430,7 @@ void QGraphicsScene::setSceneRect(const QRectF &rect)
     if (rect != d->sceneRect) {
         d->hasSceneRect = !rect.isNull();
         d->sceneRect = rect;
-        d->index->setRect(rect);
+        d->index->sceneRectChanged(rect);
         emit sceneRectChanged(rect);
     }
 }
@@ -2106,9 +1594,11 @@ void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method)
     }
 
     if (d->indexMethod == CustomIndex && method == BspTreeIndex) {
+        //We re-add in the new index all items from the old index
         QGraphicsSceneIndex *oldIndex = d->index;
         d->index = new QGraphicsSceneBspTreeIndex(this);
-        d->index->insertItems(oldIndex->items(oldIndex->rect()));
+        for (int i = 0 ; i < oldIndex->items().size() ; ++ i)
+            d->index->addItem(oldIndex->items().at(i));
     }
 
     if (d->indexMethod == CustomIndex && method == NoIndex) {
@@ -2246,7 +1736,7 @@ QRectF QGraphicsScene::itemsBoundingRect() const
 QList<QGraphicsItem *> QGraphicsScene::items() const
 {
     Q_D(const QGraphicsScene);
-    return d->index->indexedItems();
+    return d->index->items();
 }
 
 /*!
@@ -2259,7 +1749,7 @@ QList<QGraphicsItem *> QGraphicsScene::items() const
 QList<QGraphicsItem *> QGraphicsScene::items(const QPointF &pos) const
 {
     Q_D(const QGraphicsScene);
-    return d->items_helper(pos);
+    return d->index->items(pos, Qt::IntersectsItemShape, Qt::AscendingOrder);
 }
 
 
@@ -2279,7 +1769,7 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QPointF &pos) const
 QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelectionMode mode) const
 {
     Q_D(const QGraphicsScene);
-    return d->items_helper(rect, mode, Qt::AscendingOrder);
+    return d->index->items(rect, mode, Qt::AscendingOrder);
 }
 
 /*!
@@ -2303,7 +1793,7 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelecti
 QList<QGraphicsItem *> QGraphicsScene::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode) const
 {
     Q_D(const QGraphicsScene);
-    return d->items_helper(polygon, mode, Qt::AscendingOrder);
+    return d->index->items(polygon, mode, Qt::AscendingOrder);
 }
 
 /*!
@@ -2320,7 +1810,74 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QPolygonF &polygon, Qt::ItemS
 QList<QGraphicsItem *> QGraphicsScene::items(const QPainterPath &path, Qt::ItemSelectionMode mode) const
 {
     Q_D(const QGraphicsScene);
-    return d->items_helper(path, mode, Qt::AscendingOrder);
+    return d->index->items(path, mode, Qt::AscendingOrder);
+}
+
+/*!
+    Returns all visible items at position \a pos in the scene.
+
+    The default value for \a mode is Qt::IntersectsItemShape; all items whose
+    exact shape intersects with or is contained by \a path are returned.
+
+    \sa itemAt()
+*/
+QList<QGraphicsItem *> QGraphicsScene::items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    Q_D(const QGraphicsScene);
+    return d->index->items(pos, mode, order, deviceTransform);
+}
+
+/*!
+    \fn QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rectangle, Qt::SortOrder order, const QTransform &deviceTransform) const
+
+    \overload
+
+    Returns all visible items that, depending on \a mode, are either inside or
+    intersect with the specified \a rectangle.
+
+    The default value for \a mode is Qt::IntersectsItemShape; all items whose
+    exact shape intersects with or is contained by \a rectangle are returned.
+
+    \sa itemAt()
+*/
+QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    Q_D(const QGraphicsScene);
+    return d->index->items(rect, mode, order, deviceTransform);
+}
+
+/*!
+    \overload
+
+    Returns all visible items that, depending on \a mode, are either inside or
+    intersect with the polygon \a polygon.
+
+    The default value for \a mode is Qt::IntersectsItemShape; all items whose
+    exact shape intersects with or is contained by \a polygon are returned.
+
+    \sa itemAt()
+*/
+QList<QGraphicsItem *> QGraphicsScene::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    Q_D(const QGraphicsScene);
+    return d->index->items(polygon, mode, order, deviceTransform);
+}
+
+/*!
+    \overload
+
+    Returns all visible items that, depending on \a path, are either inside or
+    intersect with the path \a path.
+
+    The default value for \a mode is Qt::IntersectsItemShape; all items whose
+    exact shape intersects with or is contained by \a path are returned.
+
+    \sa itemAt()
+*/
+QList<QGraphicsItem *> QGraphicsScene::items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    Q_D(const QGraphicsScene);
+    return d->index->items(path, mode, order, deviceTransform);
 }
 
 /*!
@@ -2344,10 +1901,11 @@ QList<QGraphicsItem *> QGraphicsScene::collidingItems(const QGraphicsItem *item,
     }
 
     QList<QGraphicsItem *> tmp;
-    foreach (QGraphicsItem *itemInVicinity, d->estimateItemsInRect(item->sceneBoundingRect())) {
+    foreach (QGraphicsItem *itemInVicinity, d->index->estimateItems(item->sceneBoundingRect(), Qt::AscendingOrder, QTransform())) {
         if (item != itemInVicinity && item->collidesWithItem(itemInVicinity, mode))
             tmp << itemInVicinity;
     }
+    //### remove me
     d->sortItems(&tmp, Qt::AscendingOrder, d->sortCacheEnabled);
     return tmp;
 }
@@ -2517,8 +2075,8 @@ void QGraphicsScene::clear()
     Q_D(QGraphicsScene);
     QList<QGraphicsItem *> items;
     // Recursive descent delete
-    for (int i = 0; i < d->index->indexedItems().size(); ++i) {
-        if (QGraphicsItem *item = d->index->indexedItems().at(i)) {
+    for (int i = 0; i < d->index->items().size(); ++i) {
+        if (QGraphicsItem *item = d->index->items().at(i)) {
             if (!item->parentItem())
                 items << item;
         }
@@ -2663,7 +2221,7 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
     item->d_func()->scene = targetScene;
 
     // Add the item in the index
-    d->index->insertItem(item);
+    d->index->addItem(item);
 
     // Add to list of toplevels if this item is a toplevel.
     if (!item->d_ptr->parent)
@@ -3023,7 +2581,7 @@ void QGraphicsScene::removeItem(QGraphicsItem *item)
     // Note: This will access item's sceneBoundingRect(), which (as this is
     // C++) is why we cannot call removeItem() from QGraphicsItem's
     // destructor.
-    d->index->removeItem(item, false);
+    d->index->deleteItem(item);
 
     if (item == d->tabFocusFirst) {
         QGraphicsWidget *widget = static_cast<QGraphicsWidget *>(item);
diff --git a/src/gui/graphicsview/qgraphicsscene.h b/src/gui/graphicsview/qgraphicsscene.h
index 6476b8c..5d70087 100644
--- a/src/gui/graphicsview/qgraphicsscene.h
+++ b/src/gui/graphicsview/qgraphicsscene.h
@@ -156,10 +156,17 @@ public:
     QRectF itemsBoundingRect() const;
 
     QList<QGraphicsItem *> items() const;
+
+    QList<QGraphicsItem *> items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
+    QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
+    QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
+    QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform = QTransform()) const;
+
     QList<QGraphicsItem *> items(const QPointF &pos) const;
     QList<QGraphicsItem *> items(const QRectF &rect, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const;
     QList<QGraphicsItem *> items(const QPolygonF &polygon, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const;
     QList<QGraphicsItem *> items(const QPainterPath &path, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const;
+
     QList<QGraphicsItem *> collidingItems(const QGraphicsItem *item, Qt::ItemSelectionMode mode = Qt::IntersectsItemShape) const;
     QGraphicsItem *itemAt(const QPointF &pos) const;
 
@@ -291,6 +298,8 @@ private:
     friend class QGraphicsViewPrivate;
     friend class QGraphicsWidget;
     friend class QGraphicsWidgetPrivate;
+    friend class QGraphicsSceneIndex;
+    friend class QGraphicsSceneIndexPrivate;
     friend class QGraphicsSceneBspTreeIndex;
 };
 
diff --git a/src/gui/graphicsview/qgraphicsscene_bsp.cpp b/src/gui/graphicsview/qgraphicsscene_bsp.cpp
index f8fa450..5c1820f 100644
--- a/src/gui/graphicsview/qgraphicsscene_bsp.cpp
+++ b/src/gui/graphicsview/qgraphicsscene_bsp.cpp
@@ -143,7 +143,7 @@ void QGraphicsSceneBspTree::removeItems(const QSet<QGraphicsItem *> &items)
     }
 }
 
-QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect)
+QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect) const
 {
     QList<QGraphicsItem *> tmp;
     findVisitor->foundItems = &tmp;
@@ -151,7 +151,7 @@ QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QRectF &rect)
     return tmp;
 }
 
-QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos)
+QList<QGraphicsItem *> QGraphicsSceneBspTree::items(const QPointF &pos) const
 {
     QList<QGraphicsItem *> tmp;
     findVisitor->foundItems = &tmp;
@@ -235,7 +235,7 @@ void QGraphicsSceneBspTree::initialize(const QRectF &rect, int depth, int index)
     }
 }
 
-void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index)
+void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index) const
 {
     if (nodes.isEmpty())
         return;
@@ -245,7 +245,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con
 
     switch (node.type) {
     case Node::Leaf: {
-        visitor->visit(&leaves[node.leafIndex]);
+        visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));
         break;
     }
     case Node::Vertical:
@@ -265,7 +265,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con
     }
 }
 
-void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index)
+void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index) const
 {
     if (nodes.isEmpty())
         return;
@@ -275,7 +275,7 @@ void QGraphicsSceneBspTree::climbTree(QGraphicsSceneBspTreeVisitor *visitor, con
 
     switch (node.type) {
     case Node::Leaf: {
-        visitor->visit(&leaves[node.leafIndex]);
+        visitor->visit(const_cast<QList<QGraphicsItem*>*>(&leaves[node.leafIndex]));
         break;
     }
     case Node::Vertical:
diff --git a/src/gui/graphicsview/qgraphicsscene_bsp_p.h b/src/gui/graphicsview/qgraphicsscene_bsp_p.h
index e6ceb78..a13d862 100644
--- a/src/gui/graphicsview/qgraphicsscene_bsp_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_bsp_p.h
@@ -92,8 +92,8 @@ public:
     void removeItem(QGraphicsItem *item, const QRectF &rect);
     void removeItems(const QSet<QGraphicsItem *> &items);
 
-    QList<QGraphicsItem *> items(const QRectF &rect);
-    QList<QGraphicsItem *> items(const QPointF &pos);
+    QList<QGraphicsItem *> items(const QRectF &rect) const;
+    QList<QGraphicsItem *> items(const QPointF &pos) const;
     int leafCount() const;
 
     inline int firstChildIndex(int index) const
@@ -106,8 +106,8 @@ public:
 
 private:
     void initialize(const QRectF &rect, int depth, int index);
-    void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index = 0);
-    void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index = 0);
+    void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QPointF &pos, int index = 0) const;
+    void climbTree(QGraphicsSceneBspTreeVisitor *visitor, const QRectF &rect, int index = 0) const;
 
     void findItems(QList<QGraphicsItem *> *foundItems, const QRectF &rect, int index);
     void findItems(QList<QGraphicsItem *> *foundItems, const QPointF &pos, int index);
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index 2c0d464..a035159 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -88,8 +88,6 @@ public:
     QGraphicsScene::ItemIndexMethod indexMethod;
     int bspTreeDepth;
 
-    QList<QGraphicsItem *> estimateItemsInRect(const QRectF &rect) const;
-
     int lastItemCount;
 
     QGraphicsSceneIndex *index;
@@ -189,33 +187,6 @@ public:
     void sendMouseEvent(QGraphicsSceneMouseEvent *mouseEvent);
     void mousePressEventHandler(QGraphicsSceneMouseEvent *mouseEvent);
     QGraphicsWidget *windowForItem(const QGraphicsItem *item) const;
-
-    QList<QGraphicsItem *> items_helper(const QPointF &pos) const;
-    QList<QGraphicsItem *> items_helper(const QRectF &rect,
-                                        Qt::ItemSelectionMode mode,
-                                        Qt::SortOrder order) const;
-    QList<QGraphicsItem *> items_helper(const QPolygonF &rect,
-                                        Qt::ItemSelectionMode mode,
-                                        Qt::SortOrder order) const;
-    QList<QGraphicsItem *> items_helper(const QPainterPath &rect,
-                                        Qt::ItemSelectionMode mode,
-                                        Qt::SortOrder order) const;
-    void childItems_helper(QList<QGraphicsItem *> *items,
-                           const QGraphicsItem *parent,
-                           const QPointF &pos) const;
-    void childItems_helper(QList<QGraphicsItem *> *items,
-                           const QGraphicsItem *parent,
-                           const QRectF &rect,
-                           Qt::ItemSelectionMode mode) const;
-    void childItems_helper(QList<QGraphicsItem *> *items,
-                           const QGraphicsItem *parent,
-                           const QPolygonF &polygon,
-                           Qt::ItemSelectionMode mode) const;
-    void childItems_helper(QList<QGraphicsItem *> *items,
-                           const QGraphicsItem *parent,
-                           const QPainterPath &path,
-                           Qt::ItemSelectionMode mode) const;
-
     bool sortCacheEnabled;
     bool updatingSortCache;
     void invalidateSortCache();
@@ -255,6 +226,65 @@ public:
     mutable QVector<int> freeSceneTransformSlots;
 };
 
+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);
+}
+
+// QRectF::intersects() returns false always if either the source or target
+// rectangle's width or height are 0. This works around that problem.
+static inline void _q_adjustRect(QRectF *rect)
+{
+    Q_ASSERT(rect);
+    if (!rect->width())
+        rect->adjust(-0.00001, 0, 0.00001, 0);
+    if (!rect->height())
+        rect->adjust(0, -0.00001, 0, 0.00001);
+}
+
+static inline QRectF adjustedItemBoundingRect(const QGraphicsItem *item)
+{
+    Q_ASSERT(item);
+    QRectF boundingRect(item->boundingRect());
+    _q_adjustRect(&boundingRect);
+    return boundingRect;
+}
+
 QT_END_NAMESPACE
 
 #endif // QT_NO_GRAPHICSVIEW
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
index ebc167a..1f2b81d 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp
@@ -61,18 +61,6 @@ QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)
 
 }
 
-void QGraphicsSceneBspTreeIndex::setRect(const QRectF &rect)
-{
-    m_sceneRect = rect;
-    resetIndex();
-}
-
-QRectF QGraphicsSceneBspTreeIndex::rect() const
-{
-    const_cast<QGraphicsSceneBspTreeIndex *>(this)->updateIndex();
-    return m_sceneRect;
-}
-
 void QGraphicsSceneBspTreeIndex::clear()
 {
     bsp.clear();
@@ -82,7 +70,7 @@ void QGraphicsSceneBspTreeIndex::clear()
     unindexedItems.clear();
 }
 
-void QGraphicsSceneBspTreeIndex::insertItem(QGraphicsItem *item)
+void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item)
 {
     // Prevent reusing a recently deleted pointer: purge all removed items
     // from our lists.
@@ -113,42 +101,43 @@ void QGraphicsSceneBspTreeIndex::addToIndex(QGraphicsItem *item)
     }
 }
 
-void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item, bool itemIsAboutToDie)
+void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item)
 {
-    if (!itemIsAboutToDie) {
-        // Note: This will access item's sceneBoundingRect(), which (as this is
-        // C++) is why we cannot call removeItem() from QGraphicsItem's
-        // destructor.
-        removeFromIndex(item);
-
-        // Remove from our item lists.
-        int index = item->d_func()->index;
-        if (index != -1) {
-            freeItemIndexes << index;
-            m_indexedItems[index] = 0;
-        } else {
-            unindexedItems.removeAll(item);
-        }
+    // Note: This will access item's sceneBoundingRect(), which (as this is
+    // C++) is why we cannot call removeItem() from QGraphicsItem's
+    // destructor.
+    removeFromIndex(item);
 
+    // Remove from our item lists.
+    int index = item->d_func()->index;
+    if (index != -1) {
+        freeItemIndexes << index;
+        m_indexedItems[index] = 0;
     } else {
-        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;
-                scene()->update();
-            }
-            removedItems << item;
-        } else {
-            // Recently added items are purged immediately. unindexedItems() never
-            // contains stale items.
-            unindexedItems.removeAll(item);
+        unindexedItems.removeAll(item);
+    }
+}
+
+void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item)
+{
+    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;
             scene()->update();
         }
+        removedItems << item;
+    } else {
+        // Recently added items are purged immediately. unindexedItems() never
+        // contains stale items.
+        unindexedItems.removeAll(item);
+        scene()->update();
     }
 }
+
 /*!
     \internal
 */
@@ -173,41 +162,17 @@ void QGraphicsSceneBspTreeIndex::removeFromIndex(QGraphicsItem *item)
     startIndexTimer();
 }
 
-void QGraphicsSceneBspTreeIndex::updateItem(QGraphicsItem *item)
+void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item)
 {
     // Note: This will access item's sceneBoundingRect(), which (as this is
     // C++) is why we cannot call removeItem() from QGraphicsItem's
     // destructor.
-    removeFromIndex(item);
-}
-
-QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(const QPointF &point)
-{
-    purgeRemovedItems();
-    QList<QGraphicsItem *> rectItems = bsp.items(QRectF(point, QSizeF(1, 1)));
-    // Fill in with any unindexed items
-    for (int i = 0; i < unindexedItems.size(); ++i) {
-        if (QGraphicsItem *item = unindexedItems.at(i)) {
-            if (!item->d_ptr->itemDiscovered && item->d_ptr->visible && !(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) {
-                QRectF boundingRect = item->sceneBoundingRect();
-                if (boundingRect.intersects(QRectF(point, QSizeF(1, 1)))) {
-                    item->d_ptr->itemDiscovered = 1;
-                    rectItems << item;
-                }
-            }
-        }
-    }
-
-    // Reset the discovered state of all discovered items
-    for (int i = 0; i < rectItems.size(); ++i)
-        rectItems.at(i)->d_func()->itemDiscovered = 0;
-
-    return rectItems;
+    removeFromIndex(const_cast<QGraphicsItem *>(item));
 }
 
-QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(const QRectF &rect)
+QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const
 {
-    purgeRemovedItems();
+    const_cast<QGraphicsSceneBspTreeIndex*>(this)->purgeRemovedItems();
     QList<QGraphicsItem *> rectItems = bsp.items(rect);
     // Fill in with any unindexed items
     for (int i = 0; i < unindexedItems.size(); ++i) {
@@ -229,9 +194,9 @@ QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(const QRectF &rect)
     return rectItems;
 }
 
-QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::indexedItems()
+QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items() const
 {
-    purgeRemovedItems();
+    const_cast<QGraphicsSceneBspTreeIndex*>(this)->purgeRemovedItems();
      // If freeItemIndexes is empty, we know there are no holes in indexedItems and
     // unindexedItems.
     if (freeItemIndexes.isEmpty()) {
@@ -250,11 +215,6 @@ QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::indexedItems()
     return itemList;
 }
 
-void QGraphicsSceneBspTreeIndex::updateIndex()
-{
-    _q_updateIndex();
-}
-
 int QGraphicsSceneBspTreeIndex::bspDepth()
 {
     return bspTreeDepth;
@@ -266,6 +226,12 @@ void QGraphicsSceneBspTreeIndex::setBspDepth(int depth)
     resetIndex();
 }
 
+void QGraphicsSceneBspTreeIndex::sceneRectChanged(const QRectF &rect)
+{
+    m_sceneRect = rect;
+    resetIndex();
+}
+
 bool QGraphicsSceneBspTreeIndex::event(QEvent *event)
 {
     switch (event->type()) {
diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
index 74af910..63cd0e1 100644
--- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h
@@ -62,27 +62,23 @@ class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex
 public:
     QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0);
 
-    void setRect(const QRectF &rect);
-    virtual QRectF rect() const;
-
     void clear();
 
-    void insertItem(QGraphicsItem *item);
-    void removeItem(QGraphicsItem *item, bool itemIsAboutToDie);
-    void updateItem(QGraphicsItem *item);
-
-    QList<QGraphicsItem *> items(const QPointF &point);
-    QList<QGraphicsItem *> items(const QRectF &rect);
+    void addItem(QGraphicsItem *item);
+    void removeItem(QGraphicsItem *item);
+    void deleteItem(QGraphicsItem *item);
+    void prepareBoundingRectChange(const QGraphicsItem *item);
 
-    QList<QGraphicsItem *> indexedItems();
+    QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const;
 
-    void updateIndex();
+    QList<QGraphicsItem *> items() const;
 
     int bspDepth();
     void setBspDepth(int depth);
 
 protected:
     bool event(QEvent *event);
+    void sceneRectChanged(const QRectF &rect);
 
 public slots :
     void _q_updateIndex();
diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp
index 86a2fbb..870a62a 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.cpp
+++ b/src/gui/graphicsview/qgraphicssceneindex.cpp
@@ -40,16 +40,244 @@
 ****************************************************************************/
 
 #include "qgraphicssceneindex.h"
+#include "qgraphicssceneindex_p.h"
 #include "qgraphicsscene.h"
+#include "qgraphicsitem_p.h"
+#include "qgraphicsscene_p.h"
 
 #ifndef QT_NO_GRAPHICSVIEW
 
 QT_BEGIN_NAMESPACE
 
 /*!
+    Constructs a private scene index.
+*/
+QGraphicsSceneIndexPrivate::QGraphicsSceneIndexPrivate(QGraphicsScene *scene) : scene(scene)
+{
+}
+
+void QGraphicsSceneIndexPrivate::childItems_helper(QList<QGraphicsItem *> *items,
+                                              const QGraphicsItem *parent,
+                                              const QPointF &pos) const
+{
+    bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
+    if (parentClip && parent->d_ptr->isClippedAway())
+        return;
+    // ### is this needed?
+    if (parentClip && !parent->boundingRect().contains(pos))
+        return;
+
+    QList<QGraphicsItem *> &children = parent->d_ptr->children;
+    for (int i = 0; i < children.size(); ++i) {
+        QGraphicsItem *item = children.at(i);
+        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
+            continue;
+
+        // Skip invisible items and all their children.
+        if (item->d_ptr->isInvisible())
+            continue;
+
+        bool keep = false;
+        if (!item->d_ptr->isClippedAway()) {
+            if (item->contains(item->mapFromParent(pos))) {
+                items->append(item);
+                keep = true;
+            }
+        }
+
+        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty())
+            // Recurse into children.
+            childItems_helper(items, item, item->mapFromParent(pos));
+    }
+}
+
+
+void QGraphicsSceneIndexPrivate::childItems_helper(QList<QGraphicsItem *> *items,
+                                              const QGraphicsItem *parent,
+                                              const QRectF &rect,
+                                              Qt::ItemSelectionMode mode) const
+{
+    bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
+    if (parentClip && parent->d_ptr->isClippedAway())
+        return;
+    QRectF adjustedRect(rect);
+    _q_adjustRect(&adjustedRect);
+    QRectF r = !parentClip ? adjustedRect : adjustedRect.intersected(adjustedItemBoundingRect(parent));
+    if (r.isEmpty())
+        return;
+
+    QPainterPath path;
+    QList<QGraphicsItem *> &children = parent->d_ptr->children;
+    for (int i = 0; i < children.size(); ++i) {
+        QGraphicsItem *item = children.at(i);
+        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
+            continue;
+
+        // Skip invisible items and all their children.
+        if (item->d_ptr->isInvisible())
+            continue;
+
+        bool keep = false;
+        if (!item->d_ptr->isClippedAway()) {
+            // ### _q_adjustedRect is only needed because QRectF::intersects,
+            // QRectF::contains and QTransform::map() and friends don't work with
+            // flat rectangles.
+            const QRectF br(adjustedItemBoundingRect(item));
+            QRectF mbr = item->mapRectToParent(br);
+            if (mode >= Qt::ContainsItemBoundingRect) {
+                // Rect intersects/contains item's bounding rect
+                if ((mode == Qt::IntersectsItemBoundingRect && QRectF_intersects(rect, mbr))
+                    || (mode == Qt::ContainsItemBoundingRect && rect != mbr && rect.contains(br))) {
+                    items->append(item);
+                    keep = true;
+                }
+            } else {
+                // Rect intersects/contains item's shape
+                if (QRectF_intersects(rect, mbr)) {
+                    if (path == QPainterPath())
+                        path.addRect(rect);
+                    if (scene->d_func()->itemCollidesWithPath(item, item->mapFromParent(path), mode)) {
+                        items->append(item);
+                        keep = true;
+                    }
+                }
+            }
+        }
+
+        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) {
+            // Recurse into children.
+            if (!item->d_ptr->hasTransform || item->transform().type() <= QTransform::TxScale) {
+                // Rect
+                childItems_helper(items, item, item->mapRectFromParent(rect), mode);
+            } else {
+                // Polygon
+                childItems_helper(items, item, item->mapFromParent(rect), mode);
+            }
+        }
+    }
+}
+
+
+void QGraphicsSceneIndexPrivate::childItems_helper(QList<QGraphicsItem *> *items,
+                                              const QGraphicsItem *parent,
+                                              const QPolygonF &polygon,
+                                              Qt::ItemSelectionMode mode) const
+{
+    bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
+    if (parentClip && parent->d_ptr->isClippedAway())
+        return;
+    QRectF polyRect(polygon.boundingRect());
+    _q_adjustRect(&polyRect);
+    QRectF r = !parentClip ? polyRect : polyRect.intersected(adjustedItemBoundingRect(parent));
+    if (r.isEmpty())
+        return;
+
+    QPainterPath path;
+    QList<QGraphicsItem *> &children = parent->d_ptr->children;
+    for (int i = 0; i < children.size(); ++i) {
+        QGraphicsItem *item = children.at(i);
+        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
+            continue;
+
+        // Skip invisible items.
+        if (item->d_ptr->isInvisible())
+            continue;
+
+        bool keep = false;
+        if (!item->d_ptr->isClippedAway()) {
+            // ### _q_adjustedRect is only needed because QRectF::intersects,
+            // QRectF::contains and QTransform::map() and friends don't work with
+            // flat rectangles.
+            const QRectF br(adjustedItemBoundingRect(item));
+            if (mode >= Qt::ContainsItemBoundingRect) {
+                // Polygon contains/intersects item's bounding rect
+                if (path == QPainterPath())
+                    path.addPolygon(polygon);
+                if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br)))
+                    || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) {
+                    items->append(item);
+                    keep = true;
+                }
+            } else {
+                // Polygon contains/intersects item's shape
+                if (QRectF_intersects(polyRect, item->mapRectToParent(br))) {
+                    if (path == QPainterPath())
+                        path.addPolygon(polygon);
+                    if (scene->d_func()->itemCollidesWithPath(item, item->mapFromParent(path), mode)) {
+                        items->append(item);
+                        keep = true;
+                    }
+                }
+            }
+        }
+
+        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) {
+            // Recurse into children that clip children.
+            childItems_helper(items, item, item->mapFromParent(polygon), mode);
+        }
+    }
+}
+
+void QGraphicsSceneIndexPrivate::childItems_helper(QList<QGraphicsItem *> *items,
+                                              const QGraphicsItem *parent,
+                                              const QPainterPath &path,
+                                              Qt::ItemSelectionMode mode) const
+{
+    bool parentClip = (parent->flags() & QGraphicsItem::ItemClipsChildrenToShape);
+    if (parentClip && parent->d_ptr->isClippedAway())
+        return;
+    QRectF pathRect(path.boundingRect());
+    _q_adjustRect(&pathRect);
+    QRectF r = !parentClip ? pathRect : pathRect.intersected(adjustedItemBoundingRect(parent));
+    if (r.isEmpty())
+        return;
+
+    QList<QGraphicsItem *> &children = parent->d_ptr->children;
+    for (int i = 0; i < children.size(); ++i) {
+        QGraphicsItem *item = children.at(i);
+        if (item->d_ptr->hasTransform && !item->transform().isInvertible())
+            continue;
+
+        // Skip invisible items.
+        if (item->d_ptr->isInvisible())
+            continue;
+
+        bool keep = false;
+        if (!item->d_ptr->isClippedAway()) {
+            // ### _q_adjustedRect is only needed because QRectF::intersects,
+            // QRectF::contains and QTransform::map() and friends don't work with
+            // flat rectangles.
+            const QRectF br(adjustedItemBoundingRect(item));
+            if (mode >= Qt::ContainsItemBoundingRect) {
+                // Polygon contains/intersects item's bounding rect
+                if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(item->mapRectToParent(br)))
+                    || (mode == Qt::ContainsItemBoundingRect && path.contains(item->mapRectToParent(br)))) {
+                    items->append(item);
+                    keep = true;
+                }
+            } else {
+                // Path contains/intersects item's shape
+                if (QRectF_intersects(pathRect, item->mapRectToParent(br))) {
+                    if (scene->d_func()->itemCollidesWithPath(item, item->mapFromParent(path), mode)) {
+                        items->append(item);
+                        keep = true;
+                    }
+                }
+            }
+        }
+
+        if ((keep || !(item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) && !item->d_ptr->children.isEmpty()) {
+            // Recurse into children that clip children.
+            childItems_helper(items, item, item->mapFromParent(path), mode);
+        }
+    }
+}
+
+/*!
     Constructs an abstract scene index.
 */
-QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene): QObject(scene), m_scene(scene)
+QGraphicsSceneIndex::QGraphicsSceneIndex(QGraphicsScene *scene)
+: QObject(*new QGraphicsSceneIndexPrivate(scene))
 {
 }
 
@@ -62,109 +290,325 @@ QGraphicsSceneIndex::~QGraphicsSceneIndex()
 }
 
 /*!
-    \fn virtual void setRect(const QRectF &rect) = 0
-
-    This pure virtual function is called when the scene changes its bounding
-    rectangle.
-
-    \sa rect(), QGraphicsScene::setSceneRect
+    Returns the scene of this index.
 */
-
+QGraphicsScene* QGraphicsSceneIndex::scene() const
+{
+    Q_D(const QGraphicsSceneIndex);
+    return d->scene;
+}
 /*!
-    \fn virtual QRectF rect() const = 0
+    \fn QList<QGraphicsItem *> items() const  = 0
 
-    This pure virtual function returns the bounding rectangle of this
-    scene index. It could be as large as or larger than the scene
-    bounding rectangle, depending on the implementation of the
-    scene index.
+    This pure virtual function return the list of items that are actually in the index.
 
-    \sa setRect(), QGraphicsScene::sceneRect
 */
 
-/*!
-    \fn virtual void clear() = 0
+QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPointF &pos, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    Q_D(const QGraphicsSceneIndex);
+    QList<QGraphicsItem *> items;
+
+    // The index returns a rough estimate of what items are inside the rect.
+    // Refine it by iterating through all returned items.
+    QRectF adjustedRect = QRectF(pos, QSize(1,1));
+    foreach (QGraphicsItem *item, estimateItems(adjustedRect, order, deviceTransform)) {
+        // Find the item's scene transform in a clever way.
+        QTransform x = item->sceneTransform();
+        bool keep = false;
+
+        // ### _q_adjustedRect is only needed because QRectF::intersects,
+        // QRectF::contains and QTransform::map() and friends don't work with
+        // flat rectangles.
+        const QRectF br(adjustedItemBoundingRect(item));
+            // Rect intersects/contains item's shape
+        if (QRectF_intersects(adjustedRect, x.mapRect(br))) {
+            bool ok;
+            QTransform xinv = x.inverted(&ok);
+            if (ok) {
+                if (item->contains(xinv.map(pos))) {
+                    items << item;
+                    keep = true;
+                }
+            }
+        }
+
+        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
+            // Recurse into children that clip children.
+            bool ok;
+            QTransform xinv = x.inverted(&ok);
+            if (ok)
+                d->childItems_helper(&items, item, xinv.map(pos));
+        }
+    }
+
+    d->scene->d_func()->sortItems(&items, Qt::AscendingOrder, d->scene->d_func()->sortCacheEnabled);
+    return items;
+}
 
-    This pure virtual function removes all items in the scene index.
-*/
+QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QRectF &rect, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    Q_D(const QGraphicsSceneIndex);
+    QList<QGraphicsItem *> items;
+
+    QPainterPath path;
+
+    // The index returns a rough estimate of what items are inside the rect.
+    // Refine it by iterating through all returned items.
+    QRectF adjustedRect(rect);
+    _q_adjustRect(&adjustedRect);
+    foreach (QGraphicsItem *item, estimateItems(adjustedRect, order, deviceTransform)) {
+        // Find the item's scene transform in a clever way.
+        QTransform x = item->sceneTransform();
+        bool keep = false;
+
+        // ### _q_adjustedRect is only needed because QRectF::intersects,
+        // QRectF::contains and QTransform::map() and friends don't work with
+        // flat rectangles.
+        const QRectF br(adjustedItemBoundingRect(item));
+        if (mode >= Qt::ContainsItemBoundingRect) {
+            // Rect intersects/contains item's bounding rect
+            QRectF mbr = x.mapRect(br);
+            if ((mode == Qt::IntersectsItemBoundingRect && QRectF_intersects(rect, mbr))
+                || (mode == Qt::ContainsItemBoundingRect && rect != mbr && rect.contains(mbr))) {
+                items << item;
+                keep = true;
+            }
+        } else {
+            // Rect intersects/contains item's shape
+            if (QRectF_intersects(adjustedRect, x.mapRect(br))) {
+                bool ok;
+                QTransform xinv = x.inverted(&ok);
+                if (ok) {
+                    if (path.isEmpty())
+                        path.addRect(rect);
+                    if (d->scene->d_func()->itemCollidesWithPath(item, xinv.map(path), mode)) {
+                        items << item;
+                        keep = true;
+                    }
+                }
+            }
+        }
+
+        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
+            // Recurse into children that clip children.
+            bool ok;
+            QTransform xinv = x.inverted(&ok);
+            if (ok) {
+                if (x.type() <= QTransform::TxScale) {
+                    // Rect
+                    d->childItems_helper(&items, item, xinv.mapRect(rect), mode);
+                } else {
+                    // Polygon
+                    d->childItems_helper(&items, item, xinv.map(rect), mode);
+                }
+            }
+        }
+    }
+
+    if (order != Qt::SortOrder(-1))
+        d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+    return items;
+}
 
-/*!
-    \fn virtual void insertItem(QGraphicsItem *item) = 0
+QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPolygonF &polygon, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    Q_D(const QGraphicsSceneIndex);
+    QList<QGraphicsItem *> items;
+
+    QRectF polyRect(polygon.boundingRect());
+     _q_adjustRect(&polyRect);
+    QPainterPath path;
+
+    // The index returns a rough estimate of what items are inside the rect.
+    // Refine it by iterating through all returned items.
+    foreach (QGraphicsItem *item, estimateItems(polyRect, order, deviceTransform)) {
+        // Find the item's scene transform in a clever way.
+        QTransform x = item->sceneTransform();
+        bool keep = false;
+
+        // ### _q_adjustedRect is only needed because QRectF::intersects,
+        // QRectF::contains and QTransform::map() and friends don't work with
+        // flat rectangles.
+        const QRectF br(adjustedItemBoundingRect(item));
+        if (mode >= Qt::ContainsItemBoundingRect) {
+            // Polygon contains/intersects item's bounding rect
+            if (path == QPainterPath())
+                path.addPolygon(polygon);
+            if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br)))
+                || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) {
+                items << item;
+                keep = true;
+            }
+        } else {
+            // Polygon contains/intersects item's shape
+            if (QRectF_intersects(polyRect, x.mapRect(br))) {
+                bool ok;
+                QTransform xinv = x.inverted(&ok);
+                if (ok) {
+                    if (path == QPainterPath())
+                        path.addPolygon(polygon);
+                    if (d->scene->d_func()->itemCollidesWithPath(item, xinv.map(path), mode)) {
+                        items << item;
+                        keep = true;
+                    }
+                }
+            }
+        }
+
+        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
+            // Recurse into children that clip children.
+            bool ok;
+            QTransform xinv = x.inverted(&ok);
+            if (ok)
+                d->childItems_helper(&items, item, xinv.map(polygon), mode);
+        }
+    }
+
+    if (order != Qt::SortOrder(-1))
+        d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+    return items;
+}
+QList<QGraphicsItem *> QGraphicsSceneIndex::items(const QPainterPath &path, Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    Q_D(const QGraphicsSceneIndex);
+    QList<QGraphicsItem *> items;
+    QRectF pathRect(path.controlPointRect());
+    _q_adjustRect(&pathRect);
+
+    // The index returns a rough estimate of what items are inside the rect.
+    // Refine it by iterating through all returned items.
+    foreach (QGraphicsItem *item, estimateItems(pathRect, order, deviceTransform)) {
+        // Find the item's scene transform in a clever way.
+        QTransform x = item->sceneTransform();
+        bool keep = false;
+
+        // ### _q_adjustedRect is only needed because QRectF::intersects,
+        // QRectF::contains and QTransform::map() and friends don't work with
+        // flat rectangles.
+        const QRectF br(adjustedItemBoundingRect(item));
+        if (mode >= Qt::ContainsItemBoundingRect) {
+            // Path contains/intersects item's bounding rect
+            if ((mode == Qt::IntersectsItemBoundingRect && path.intersects(x.mapRect(br)))
+                || (mode == Qt::ContainsItemBoundingRect && path.contains(x.mapRect(br)))) {
+                items << item;
+                keep = true;
+            }
+        } else {
+            // Path contains/intersects item's shape
+            if (QRectF_intersects(pathRect, x.mapRect(br))) {
+                bool ok;
+                QTransform xinv = x.inverted(&ok);
+                if (ok) {
+                    if (d->scene->d_func()->itemCollidesWithPath(item, xinv.map(path), mode)) {
+                        items << item;
+                        keep = true;
+                    }
+                }
+            }
+        }
+
+        if (keep && (item->flags() & QGraphicsItem::ItemClipsChildrenToShape)) {
+            bool ok;
+            QTransform xinv = x.inverted(&ok);
+            if (ok)
+                d->childItems_helper(&items, item, xinv.map(path), mode);
+        }
+    }
+
+    if (order != Qt::SortOrder(-1))
+        d->scene->d_func()->sortItems(&items, order, d->scene->d_func()->sortCacheEnabled);
+    return items;
+}
 
-    This pure virtual function inserts an item to the scene index.
+/*!
+    This pure virtual function return an estimation of items at position \a pos.
 
-    \sa removeItem(), updateItem(), insertItems()
 */
+QList<QGraphicsItem *> QGraphicsSceneIndex::estimateItems(const QPointF &point, Qt::SortOrder order, const QTransform &deviceTransform) const
+{
+    return estimateItems(QRectF(point, QSize(1,1)), order, deviceTransform);
+}
 
 /*!
-    \fn virtual void removeItem(QGraphicsItem *item) = 0
+    \fn virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const = 0
 
-    This pure virtual function removes an item to the scene index.
+    This pure virtual function return an estimation of items in the \a rect.
 
-    \sa insertItem(), updateItem(), removeItems()
 */
 
+
 /*!
-    Returns the scene of this index.
+    This virtual function removes all items in the scene index.
 */
-QGraphicsScene* QGraphicsSceneIndex::scene() const
+void QGraphicsSceneIndex::clear()
 {
-     return m_scene;
+    for (int i = 0 ; i < items().size(); ++i)
+        removeItem(items().at(i));
 }
 
 /*!
-    Updates an item when its geometry has changed.
+    \fn virtual void addItem(QGraphicsItem *item) = 0
 
-    The default implemention will remove the item from the index
-    and then insert it again.
+    This pure virtual function inserts an item to the scene index.
 
-    \sa insertItem(), removeItem(), updateItems()
+    \sa removeItem(), deleteItem()
 */
-void QGraphicsSceneIndex::updateItem(QGraphicsItem *item)
-{
-    removeItem(item,false);
-    insertItem(item);
-}
 
 /*!
-    Inserts a list of items to the index.
+    \fn virtual void removeItem(QGraphicsItem *item) = 0
 
-    The default implemention will insert the items one by one.
+    This pure virtual function removes an item to the scene index.
 
-    \sa insertItem(), removeItems(), updateItems()
+    \sa addItem(), deleteItem()
 */
-void QGraphicsSceneIndex::insertItems(const QList<QGraphicsItem *> &items)
+
+/*!
+    This method is called when an item has been deleted.
+    The default implementation call removeItem. Be carefull,
+    if your implementation of removeItem use pure virtual method
+    of QGraphicsItem like boundingRect(), then you should reimplement
+    this method.
+
+    \sa addItem(), removeItem()
+*/
+void QGraphicsSceneIndex::deleteItem(QGraphicsItem *item)
 {
-    foreach (QGraphicsItem *item, items)
-        insertItem(item);
+    removeItem(item);
 }
 
 /*!
-    Removes a list of items from the index.
+    This virtual function is called by QGraphicsItem to notify the index
+    that some part of the item's state changes. By reimplementing this
+    function, your can react to a change, and in some cases, (depending on \a
+    change,) adjustments in the index can be made.
 
-    The default implemention will remove the items one by one.
+    \a change is the parameter of the item that is changing. \a value is the
+    value that changed; the type of the value depends on \a change.
 
-    \sa removeItem(), removeItems(), updateItems()
+    The default implementation does nothing.
+
+    \sa GraphicsItemChange
 */
-void QGraphicsSceneIndex::removeItems(const QList<QGraphicsItem *> &items, bool itemsAreAboutToDie)
+void QGraphicsSceneIndex::itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange, const QVariant &value)
 {
-    foreach (QGraphicsItem *item, items)
-        removeItem(item,itemsAreAboutToDie);
 }
 
 /*!
-    Update a list of items which have changed the geometry.
-
-    The default implemention will update the items one by one.
+    Notify the index for a geometry change of an item.
 
-    \sa updateItem(), insertItems(), removeItems()
+    \sa QGraphicsItem::prepareGeometryChange
 */
-void QGraphicsSceneIndex::updateItems(const QList<QGraphicsItem *> &items)
+void QGraphicsSceneIndex::prepareBoundingRectChange(const QGraphicsItem *item)
 {
-    foreach (QGraphicsItem *item, items)
-        updateItem(item);
 }
 
-void QGraphicsSceneIndex::updateIndex()
+/*!
+    This virtual function is called when the scene changes its bounding
+    rectangle.
+    \sa QGraphicsScene::sceneRect
+*/
+void QGraphicsSceneIndex::sceneRectChanged(const QRectF &rect)
 {
 }
 
diff --git a/src/gui/graphicsview/qgraphicssceneindex.h b/src/gui/graphicsview/qgraphicssceneindex.h
index a782323..da3096e 100644
--- a/src/gui/graphicsview/qgraphicssceneindex.h
+++ b/src/gui/graphicsview/qgraphicssceneindex.h
@@ -44,6 +44,8 @@
 
 #include <QtCore/qnamespace.h>
 #include <QtCore/qobject.h>
+#include <QtGui/qtransform.h>
+#include <QtGui/qgraphicsitem.h>
 
 QT_BEGIN_HEADER
 
@@ -53,7 +55,7 @@ QT_MODULE(Gui)
 
 #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
 
-class QGraphicsItem;
+class QGraphicsSceneIndexPrivate;
 class QGraphicsScene;
 class QRectF;
 class QPointF;
@@ -67,29 +69,31 @@ public:
     QGraphicsSceneIndex(QGraphicsScene *scene = 0);
     virtual ~QGraphicsSceneIndex();
 
-    QGraphicsScene* scene() const;
-
-    virtual void setRect(const QRectF &rect) = 0;
-    virtual QRectF rect() const = 0;
-    virtual void clear() = 0;
-
-    virtual void insertItem(QGraphicsItem *item) = 0;
-    virtual void removeItem(QGraphicsItem *items, bool itemIsAboutToDie) = 0;
-    virtual void updateItem(QGraphicsItem *item);
-
-    virtual void insertItems(const QList<QGraphicsItem *> &items);
-    virtual void removeItems(const QList<QGraphicsItem *> &items, bool itemsAreAboutToDie);
-    virtual void updateItems(const QList<QGraphicsItem *> &items);
-
-    virtual QList<QGraphicsItem *> items(const QPointF &point) = 0;
-    virtual QList<QGraphicsItem *> items(const QRectF &rect) = 0;
-
-    virtual QList<QGraphicsItem *> indexedItems()  = 0;
-
-    virtual void updateIndex();
-
+    QGraphicsScene *scene() const;
+
+    virtual QList<QGraphicsItem *> items() 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;
+    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;
+
+protected:
+    virtual void clear();
+    virtual void addItem(QGraphicsItem *item) = 0;
+    virtual void removeItem(QGraphicsItem *item) = 0;
+    virtual void deleteItem(QGraphicsItem *item);
+
+    virtual void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange, const QVariant &value);
+    virtual void prepareBoundingRectChange(const QGraphicsItem *item);
+    virtual void sceneRectChanged(const QRectF &rect);
+
+    friend class QGraphicsScene;
+    friend class QGraphicsScenePrivate;
+    friend class QGraphicsItem;
 private:
-    QGraphicsScene *m_scene;
+    Q_DECLARE_PRIVATE(QGraphicsSceneIndex)
 };
 
 #endif // QT_NO_GRAPHICSVIEW
diff --git a/src/gui/graphicsview/qgraphicssceneindex_p.h b/src/gui/graphicsview/qgraphicssceneindex_p.h
new file mode 100644
index 0000000..f2cdca3
--- /dev/null
+++ b/src/gui/graphicsview/qgraphicssceneindex_p.h
@@ -0,0 +1,96 @@
+/****************************************************************************
+**
+** 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 QGRAPHICSSCENEINDEX_P_H
+#define QGRAPHICSSCENEINDEX_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 "qgraphicssceneindex.h"
+
+#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW
+
+#include <private/qobject_p.h>
+
+QT_BEGIN_NAMESPACE
+
+class QGraphicsScene;
+
+class QGraphicsSceneIndexPrivate : public QObjectPrivate
+{
+    Q_DECLARE_PUBLIC(QGraphicsSceneIndex)
+public:
+    QGraphicsSceneIndexPrivate(QGraphicsScene *scene);
+
+
+    void childItems_helper(QList<QGraphicsItem *> *items,
+                           const QGraphicsItem *parent,
+                           const QPointF &pos) const;
+    void childItems_helper(QList<QGraphicsItem *> *items,
+                           const QGraphicsItem *parent,
+                           const QRectF &rect,
+                           Qt::ItemSelectionMode mode) const;
+    void childItems_helper(QList<QGraphicsItem *> *items,
+                           const QGraphicsItem *parent,
+                           const QPolygonF &polygon,
+                           Qt::ItemSelectionMode mode) const;
+    void childItems_helper(QList<QGraphicsItem *> *items,
+                           const QGraphicsItem *parent,
+                           const QPainterPath &path,
+                           Qt::ItemSelectionMode mode) const;
+
+    QGraphicsScene *scene;
+};
+
+QT_END_NAMESPACE
+
+#endif // QGRAPHICSSCENEINDEX_P_H
+
+#endif
diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
index 30948d9..dc45a17 100644
--- a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
+++ b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h
@@ -89,24 +89,15 @@ public:
         m_items.clear();
     }
 
-    virtual void insertItem(QGraphicsItem *item) {
+    virtual void addItem(QGraphicsItem *item) {
         m_items << item;
     }
 
-    virtual void removeItem(QGraphicsItem *item, bool itemIsAboutToDie) {
-        Q_UNUSED(itemIsAboutToDie);
+    virtual void removeItem(QGraphicsItem *item) {
         m_items.removeAll(item);
     }
 
-    virtual QList<QGraphicsItem *> items(const QPointF &point) {
-        QList<QGraphicsItem*> result;
-        foreach (QGraphicsItem *item, m_items)
-            if (item->sceneBoundingRect().contains(point))
-                result << item;
-        return result;
-    }
-
-    virtual QList<QGraphicsItem *> items(const QRectF &rect) {
+    virtual QList<QGraphicsItem *> estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const {
         QList<QGraphicsItem*> result;
         foreach (QGraphicsItem *item, m_items)
             if (item->sceneBoundingRect().intersects(rect))
@@ -114,7 +105,7 @@ public:
         return result;
     }
 
-    QList<QGraphicsItem *> indexedItems() {
+    QList<QGraphicsItem *> items() const {
         return m_items;
     }
 };
diff --git a/src/gui/graphicsview/qgraphicsview.cpp b/src/gui/graphicsview/qgraphicsview.cpp
index 10b837a..91f97a1 100644
--- a/src/gui/graphicsview/qgraphicsview.cpp
+++ b/src/gui/graphicsview/qgraphicsview.cpp
@@ -791,19 +791,6 @@ QRegion QGraphicsViewPrivate::mapToViewRegion(const QGraphicsItem *item, const Q
     return item->boundingRegion(itv) & itv.mapRect(rect).toAlignedRect();
 }
 
-// QRectF::intersects() returns false always if either the source or target
-// rectangle's width or height are 0. This works around that problem.
-static inline QRectF adjustedItemBoundingRect(const QGraphicsItem *item)
-{
-    Q_ASSERT(item);
-    QRectF boundingRect(item->boundingRect());
-    if (!boundingRect.width())
-        boundingRect.adjust(-0.00001, 0, 0.00001, 0);
-    if (!boundingRect.height())
-        boundingRect.adjust(0, -0.00001, 0, 0.00001);
-    return boundingRect;
-}
-
 /*!
     \internal
 */
@@ -1094,7 +1081,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg
     bool simpleRectLookup =  (scene->d_func()->largestUntransformableItem.isNull()
                               && exposedRegion.numRects() == 1 && matrix.type() <= QTransform::TxScale);
     if (simpleRectLookup) {
-        return scene->d_func()->items_helper(exposedRegionSceneBounds,
+        return scene->d_func()->index->items(exposedRegionSceneBounds,
                                              Qt::IntersectsItemBoundingRect,
                                              Qt::DescendingOrder);
     }
@@ -1109,7 +1096,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::findItems(const QRegion &exposedReg
     const QPainterPath exposedPath(qt_regionToPath(adjustedRegion));
     if (scene->d_func()->largestUntransformableItem.isNull()) {
         const QPainterPath exposedScenePath(q->mapToScene(exposedPath));
-        return scene->d_func()->items_helper(exposedScenePath,
+        return scene->d_func()->index->items(exposedScenePath,
                                              Qt::IntersectsItemBoundingRect,
                                              Qt::DescendingOrder);
     }
@@ -2143,7 +2130,7 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat
 
     // First build a (potentially large) list of all items in the vicinity
     // that might be untransformable.
-    QList<QGraphicsItem *> allCandidates = scene->d_func()->estimateItemsInRect(adjustedRect);
+    QList<QGraphicsItem *> allCandidates = scene->d_func()->index->estimateItems(adjustedRect, order, q->transform());
 
     // Then find the minimal list of items that are inside \a path, and
     // convert it to a set.
@@ -2154,6 +2141,8 @@ QList<QGraphicsItem *> QGraphicsViewPrivate::itemsInArea(const QPainterPath &pat
 
     QList<QGraphicsItem *> result;
 
+    //### this will disapear
+
     // Run through all candidates and keep all items that are in candSet, or
     // are untransformable and collide with \a path. ### We can improve this
     // algorithm.