Merge commit 'qt/master-stable'

Conflicts:
	configure.exe
	qmake/Makefile.unix
	qmake/generators/makefile.cpp
	src/corelib/global/qglobal.h
	src/corelib/kernel/kernel.pri
	src/corelib/kernel/qcoreevent.cpp
	src/corelib/kernel/qsharedmemory_unix.cpp
	src/gui/graphicsview/qgraphicsscene.cpp
	src/gui/kernel/qaction.cpp
	src/gui/kernel/qaction.h
	src/gui/kernel/qaction_p.h
	src/gui/kernel/qapplication.cpp
	src/gui/kernel/qapplication.h
	src/gui/kernel/qwidget.cpp
	src/gui/kernel/qwidget.h
	src/gui/kernel/qwidget_mac.mm
	src/gui/painting/qgraphicssystemfactory.cpp
	src/gui/styles/qwindowsstyle.cpp
	src/gui/text/qfontengine_qpf.cpp
	src/gui/widgets/qabstractscrollarea_p.h
	src/network/access/qnetworkaccessdebugpipebackend.cpp
	src/network/socket/qlocalsocket_unix.cpp
	src/network/socket/qnativesocketengine_p.h
	src/network/socket/qnativesocketengine_unix.cpp
	src/openvg/qpaintengine_vg.cpp
	tests/auto/q3sqlcursor/tst_q3sqlcursor.cpp
	tests/auto/qcssparser/qcssparser.pro
	tests/auto/qdir/tst_qdir.cpp
	tests/auto/qfile/tst_qfile.cpp
	tests/auto/qobject/tst_qobject.cpp
	tests/auto/qpathclipper/qpathclipper.pro
	tests/auto/qprocess/tst_qprocess.cpp
	tests/auto/qsettings/tst_qsettings.cpp
	tests/auto/qsharedpointer/qsharedpointer.pro
	tests/auto/qsqlquerymodel/qsqlquerymodel.pro
	tests/auto/qsqlrelationaltablemodel/qsqlrelationaltablemodel.pro
	tests/auto/qsqltablemodel/qsqltablemodel.pro
	tests/auto/qsqlthread/qsqlthread.pro
	tests/auto/qwidget/tst_qwidget.cpp

1 files changed, 628 insertions, 1532 deletions

diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 13d3bd6..d721d0d 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -39,7 +39,6 @@
 **
 ****************************************************************************/
 
-
 /*!
     \class QGraphicsScene
     \brief The QGraphicsScene class provides a surface for managing a large
@@ -218,6 +217,9 @@
 #include "qgraphicsview_p.h"
 #include "qgraphicswidget.h"
 #include "qgraphicswidget_p.h"
+#include "qgraphicssceneindex_p.h"
+#include "qgraphicsscenebsptreeindex_p.h"
+#include "qgraphicsscenelinearindex_p.h"
 
 #include <QtCore/qdebug.h>
 #include <QtCore/qlist.h>
@@ -242,77 +244,15 @@
 #include <QtGui/qtooltip.h>
 #include <QtGui/qtransform.h>
 #include <QtGui/qgesture.h>
+#include <QtGui/qinputcontext.h>
 #include <private/qapplication_p.h>
 #include <private/qobject_p.h>
 #ifdef Q_WS_X11
 #include <private/qt_x11_p.h>
 #endif
-#include <private/qgesturemanager_p.h>
-#include <private/qgesture_p.h>
 
 QT_BEGIN_NAMESPACE
 
-static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2);
-
-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());
@@ -332,18 +272,15 @@ static void _q_hoverFromMouseEvent(QGraphicsSceneHoverEvent *hover, const QGraph
 QGraphicsScenePrivate::QGraphicsScenePrivate()
     : changedSignalMask(0),
       indexMethod(QGraphicsScene::BspTreeIndex),
-      bspTreeDepth(0),
+      index(0),
       lastItemCount(0),
       hasSceneRect(false),
+      dirtyGrowingItemsBoundingRect(true),
       updateAll(false),
       calledEmitUpdated(false),
       processDirtyItemsEmitted(false),
       selectionChanging(0),
       needSortTopLevelItems(true),
-      regenerateIndex(true),
-      purgePending(false),
-      indexTimerId(0),
-      restartIndexTimer(false),
       stickyFocus(false),
       hasFocus(false),
       focusItem(0),
@@ -360,7 +297,6 @@ QGraphicsScenePrivate::QGraphicsScenePrivate()
       allItemsUseDefaultCursor(true),
       painterStateProtection(true),
       sortCacheEnabled(false),
-      updatingSortCache(false),
       style(0),
       allItemsIgnoreTouchEvents(true)
 {
@@ -373,6 +309,8 @@ void QGraphicsScenePrivate::init()
 {
     Q_Q(QGraphicsScene);
 
+    index = new QGraphicsSceneBspTreeIndex(q);
+
     // Keep this index so we can check for connected slots later on.
     changedSignalMask = (1 << q->metaObject()->indexOfSignal("changed(QList<QRectF>)"));
     qApp->d_func()->scene_list.append(q);
@@ -382,224 +320,26 @@ void QGraphicsScenePrivate::init()
 /*!
     \internal
 */
-QList<QGraphicsItem *> QGraphicsScenePrivate::estimateItemsInRect(const QRectF &rect) const
-{
-    const_cast<QGraphicsScenePrivate *>(this)->purgeRemovedItems();
-    const_cast<QGraphicsScenePrivate *>(this)->_q_updateSortCache();
-
-    if (indexMethod == QGraphicsScene::BspTreeIndex) {
-        // ### Only do this once in a while.
-        QGraphicsScenePrivate *that = const_cast<QGraphicsScenePrivate *>(this);
-
-        // Get items from BSP tree
-        QList<QGraphicsItem *> items = that->bspTree.items(rect);
-
-        // 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 (QRectF_intersects(boundingRect, rect)) {
-                        item->d_ptr->itemDiscovered = 1;
-                        items << item;
-                    }
-                }
-            }
-        }
-
-        // Reset the discovered state of all discovered items
-        for (int i = 0; i < items.size(); ++i)
-            items.at(i)->d_func()->itemDiscovered = 0;
-        return items;
-    }
-
-    QList<QGraphicsItem *> itemsInRect;
-    for (int i = 0; i < unindexedItems.size(); ++i) {
-        if (QGraphicsItem *item = unindexedItems.at(i)) {
-            if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)
-                continue;
-            if (item->d_ptr->visible && !item->d_ptr->isFullyTransparent())
-                itemsInRect << item;
-        }
-    }
-    for (int i = 0; i < indexedItems.size(); ++i) {
-        if (QGraphicsItem *item = indexedItems.at(i)) {
-            if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)
-                continue;
-            if (item->d_ptr->visible && !item->d_ptr->isFullyTransparent())
-                itemsInRect << item;
-        }
-    }
-
-    return itemsInRect;
-}
-
-/*!
-    \internal
-*/
-void QGraphicsScenePrivate::addToIndex(QGraphicsItem *item)
+QGraphicsScenePrivate *QGraphicsScenePrivate::get(QGraphicsScene *q)
 {
-    if (indexMethod == QGraphicsScene::BspTreeIndex) {
-        if (item->d_func()->index != -1) {
-            bspTree.insertItem(item, item->sceneBoundingRect());
-            foreach (QGraphicsItem *child, item->children())
-                child->addToIndex();
-        } else {
-            // The BSP tree is regenerated if the number of items grows to a
-            // certain threshold, or if the bounding rect of the graph doubles in
-            // size.
-            startIndexTimer();
-        }
-    }
+    return q->d_func();
 }
 
-/*!
-    \internal
-*/
-void QGraphicsScenePrivate::removeFromIndex(QGraphicsItem *item)
-{
-    if (indexMethod == QGraphicsScene::BspTreeIndex) {
-        int index = item->d_func()->index;
-        if (index != -1) {
-            bspTree.removeItem(item, item->sceneBoundingRect());
-            freeItemIndexes << index;
-            indexedItems[index] = 0;
-            item->d_func()->index = -1;
-            unindexedItems << item;
-
-            foreach (QGraphicsItem *child, item->children())
-                child->removeFromIndex();
-        }
-
-        startIndexTimer();
-    }
-}
-
-/*!
-    \internal
-*/
-void QGraphicsScenePrivate::resetIndex()
-{
-    purgeRemovedItems();
-    if (indexMethod == QGraphicsScene::BspTreeIndex) {
-        for (int i = 0; i < indexedItems.size(); ++i) {
-            if (QGraphicsItem *item = indexedItems.at(i)) {
-                item->d_ptr->index = -1;
-                unindexedItems << item;
-            }
-        }
-        indexedItems.clear();
-        freeItemIndexes.clear();
-        regenerateIndex = true;
-        startIndexTimer();
-    }
-}
-
-static inline int intmaxlog(int n)
-{
-    return  (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);
-}
-
-/*!
-    \internal
-*/
-void QGraphicsScenePrivate::_q_updateIndex()
+void QGraphicsScenePrivate::_q_emitUpdated()
 {
-    if (!indexTimerId)
-        return;
-
     Q_Q(QGraphicsScene);
-    q->killTimer(indexTimerId);
-    indexTimerId = 0;
-
-    purgeRemovedItems();
-
-    // Add unindexedItems to indexedItems
-    QRectF unindexedItemsBoundingRect;
-    for (int i = 0; i < unindexedItems.size(); ++i) {
-        if (QGraphicsItem *item = unindexedItems.at(i)) {
-            unindexedItemsBoundingRect |= item->sceneBoundingRect();
-            if (!freeItemIndexes.isEmpty()) {
-                int freeIndex = freeItemIndexes.takeFirst();
-                item->d_func()->index = freeIndex;
-                indexedItems[freeIndex] = item;
-            } else {
-                item->d_func()->index = indexedItems.size();
-                indexedItems << item;
-            }
-        }
-    }
-
-    // Update growing scene rect.
-    QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect;
-    growingItemsBoundingRect |= unindexedItemsBoundingRect;
-
-    // Determine whether we should regenerate the BSP tree.
-    if (indexMethod == QGraphicsScene::BspTreeIndex) {
-        int depth = bspTreeDepth;
-        if (depth == 0) {
-            int oldDepth = intmaxlog(lastItemCount);
-            depth = intmaxlog(indexedItems.size());
-            static const int slack = 100;
-            if (bspTree.leafCount() == 0 || (oldDepth != depth && qAbs(lastItemCount - indexedItems.size()) > slack)) {
-                // ### Crude algorithm.
-                regenerateIndex = true;
-            }
-        }
+    calledEmitUpdated = false;
 
-        // Regenerate the tree.
-        if (regenerateIndex) {
-            regenerateIndex = false;
-            bspTree.initialize(q->sceneRect(), depth);
-            unindexedItems = indexedItems;
-            lastItemCount = indexedItems.size();
-            q->update();
-
-            // Take this opportunity to reset our largest-item counter for
-            // untransformable items. When the items are inserted into the BSP
-            // tree, we'll get an accurate calculation.
-            largestUntransformableItem = QRectF();
+    if (dirtyGrowingItemsBoundingRect) {
+        if (!hasSceneRect) {
+            const QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect;
+            growingItemsBoundingRect |= q->itemsBoundingRect();
+            if (oldGrowingItemsBoundingRect != growingItemsBoundingRect)
+                emit q->sceneRectChanged(growingItemsBoundingRect);
         }
+        dirtyGrowingItemsBoundingRect = false;
     }
 
-    // Insert all unindexed items into the tree.
-    for (int i = 0; i < unindexedItems.size(); ++i) {
-        if (QGraphicsItem *item = unindexedItems.at(i)) {
-            QRectF rect = item->sceneBoundingRect();
-            if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)
-                continue;
-            if (indexMethod == QGraphicsScene::BspTreeIndex)
-                bspTree.insertItem(item, rect);
-
-            // If the item ignores view transformations, update our
-            // largest-item-counter to ensure that the view can accurately
-            // discover untransformable items when drawing.
-            if (item->d_ptr->itemIsUntransformable()) {
-                QGraphicsItem *topmostUntransformable = item;
-                while (topmostUntransformable && (topmostUntransformable->d_ptr->ancestorFlags
-                                                  & QGraphicsItemPrivate::AncestorIgnoresTransformations)) {
-                    topmostUntransformable = topmostUntransformable->parentItem();
-                }
-                // ### Verify that this is the correct largest untransformable rectangle.
-                largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect();
-            }
-        }
-    }
-    unindexedItems.clear();
-
-    // Notify scene rect changes.
-    if (!hasSceneRect && growingItemsBoundingRect != oldGrowingItemsBoundingRect)
-        emit q->sceneRectChanged(growingItemsBoundingRect);
-}
-
-/*!
-    \internal
-*/
-void QGraphicsScenePrivate::_q_emitUpdated()
-{
-    Q_Q(QGraphicsScene);
-    calledEmitUpdated = false;
-
     // Ensure all views are connected if anything is connected. This disables
     // the optimization that items send updates directly to the views, but it
     // needs to happen in order to keep compatibility with the behavior from
@@ -617,6 +357,9 @@ void QGraphicsScenePrivate::_q_emitUpdated()
         updateAll = false;
         for (int i = 0; i < views.size(); ++i)
             views.at(i)->d_func()->processPendingUpdates();
+        // It's important that we update all views before we dispatch, hence two for-loops.
+        for (int i = 0; i < views.size(); ++i)
+            views.at(i)->d_func()->dispatchPendingUpdateRequests();
         return;
     }
 
@@ -634,6 +377,7 @@ void QGraphicsScenePrivate::_q_emitUpdated()
 void QGraphicsScenePrivate::registerTopLevelItem(QGraphicsItem *item)
 {
     needSortTopLevelItems = true;
+    item->d_ptr->siblingIndex = topLevelItems.size();
     topLevelItems.append(item);
 }
 
@@ -643,19 +387,10 @@ void QGraphicsScenePrivate::registerTopLevelItem(QGraphicsItem *item)
 void QGraphicsScenePrivate::unregisterTopLevelItem(QGraphicsItem *item)
 {
     topLevelItems.removeOne(item);
-}
-
-/*!
-    \internal
-
-    Updates all items in the pending update list. At this point, the list is
-    unlikely to contain partially constructed items.
-*/
-void QGraphicsScenePrivate::_q_updateLater()
-{
-    foreach (QGraphicsItem *item, pendingUpdateItems)
-        item->update();
-    pendingUpdateItems.clear();
+    // NB! Do not use topLevelItems.removeAt(item->d_ptr->siblingIndex) because
+    // the item is not guaranteed to be at the index after the list is sorted
+    // (see ensureSortedTopLevelItems()).
+    item->d_ptr->siblingIndex = -1;
 }
 
 /*!
@@ -681,9 +416,23 @@ void QGraphicsScenePrivate::_q_processDirtyItems()
 {
     processDirtyItemsEmitted = false;
 
+    if (updateAll) {
+        Q_ASSERT(calledEmitUpdated);
+        // No need for further processing (except resetting the dirty states).
+        // The growingItemsBoundingRect is updated in _q_emitUpdated.
+        for (int i = 0; i < topLevelItems.size(); ++i)
+            resetDirtyItem(topLevelItems.at(i), /*recursive=*/true);
+        return;
+    }
+
     const bool wasPendingSceneUpdate = calledEmitUpdated;
     const QRectF oldGrowingItemsBoundingRect = growingItemsBoundingRect;
-    processDirtyItemsRecursive(0);
+
+    // Process items recursively.
+    for (int i = 0; i < topLevelItems.size(); ++i)
+        processDirtyItemsRecursive(topLevelItems.at(i));
+
+    dirtyGrowingItemsBoundingRect = false;
     if (!hasSceneRect && oldGrowingItemsBoundingRect != growingItemsBoundingRect)
         emit q_func()->sceneRectChanged(growingItemsBoundingRect);
 
@@ -701,13 +450,8 @@ void QGraphicsScenePrivate::_q_processDirtyItems()
     }
 
     // Immediately dispatch all pending update requests on the views.
-    for (int i = 0; i < views.size(); ++i) {
-        QWidget *viewport = views.at(i)->d_func()->viewport;
-        if (qt_widget_private(viewport)->paintOnScreen())
-            QCoreApplication::sendPostedEvents(viewport, QEvent::UpdateRequest);
-        else
-            QCoreApplication::sendPostedEvents(viewport->window(), QEvent::UpdateRequest);
-    }
+    for (int i = 0; i < views.size(); ++i)
+        views.at(i)->d_func()->dispatchPendingUpdateRequests();
 }
 
 /*!
@@ -728,22 +472,16 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item)
 
     // Clear focus on the item to remove any reference in the focusWidget chain.
     item->clearFocus();
+
     markDirty(item, QRectF(), false, false, false, false, /*removingItemFromScene=*/true);
 
-    if (!item->d_ptr->inDestructor) {
+    if (item->d_ptr->inDestructor) {
+        // The item is actually in its destructor, we call the special method in the index.
+        index->deleteItem(item);
+    } else {
         // Can potentially call item->boundingRect() (virtual function), that's why
         // we only can call this function if the item is not in its destructor.
-        removeFromIndex(item);
-    } else if (item->d_ptr->index != -1) {
-        // Important: The index is useless until purgeRemovedItems() is called.
-        indexedItems[item->d_ptr->index] = (QGraphicsItem *)0;
-        if (!purgePending)
-            purgePending = true;
-        removedItems << item;
-    } else {
-        // Recently added items are purged immediately. unindexedItems() never
-        // contains stale items.
-        unindexedItems.removeAll(item);
+        index->removeItem(item);
     }
 
     if (!item->d_ptr->inDestructor && item == tabFocusFirst) {
@@ -753,6 +491,13 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item)
 
     item->d_func()->scene = 0;
 
+    // Unregister focus proxy.
+    QMultiHash<QGraphicsItem *, QGraphicsItem *>::iterator it = focusProxyReverseMap.find(item);
+    while (it != focusProxyReverseMap.end() && it.key() == item) {
+        it.value()->d_ptr->focusProxy = 0;
+        it = focusProxyReverseMap.erase(it);
+    }
+
     // Remove from parent, or unregister from toplevels.
     if (QGraphicsItem *parentItem = item->parentItem()) {
         if (parentItem->scene()) {
@@ -764,17 +509,6 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item)
         unregisterTopLevelItem(item);
     }
 
-    if (!item->d_ptr->inDestructor) {
-        // Remove from our item lists.
-        int index = item->d_func()->index;
-        if (index != -1) {
-            freeItemIndexes << index;
-            indexedItems[index] = 0;
-        } else {
-            unindexedItems.removeAll(item);
-        }
-    }
-
     // Reset the mouse grabber and focus item data.
     if (item == focusItem)
         focusItem = 0;
@@ -794,7 +528,6 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item)
     hoverItems.removeAll(item);
     cachedItemsUnderMouse.removeAll(item);
     unpolishedItems.removeAll(item);
-    pendingUpdateItems.removeAll(item);
     resetDirtyItem(item);
 
     //We remove all references of item from the sceneEventFilter arrays
@@ -832,41 +565,54 @@ void QGraphicsScenePrivate::removeItemHelper(QGraphicsItem *item)
 
 /*!
     \internal
-
-    Removes stale pointers from all data structures.
 */
-void QGraphicsScenePrivate::purgeRemovedItems()
+void QGraphicsScenePrivate::setFocusItemHelper(QGraphicsItem *item,
+                                               Qt::FocusReason focusReason)
 {
-    if (!purgePending && removedItems.isEmpty())
+    Q_Q(QGraphicsScene);
+    if (item == focusItem)
         return;
+    if (item && (!(item->flags() & QGraphicsItem::ItemIsFocusable)
+                 || !item->isVisible() || !item->isEnabled())) {
+        item = 0;
+    }
 
-    // Remove stale items from the BSP tree.
-    if (indexMethod != QGraphicsScene::NoIndex)
-        bspTree.removeItems(removedItems);
+    if (item) {
+        q->setFocus(focusReason);
+        if (item == focusItem)
+            return;
+    }
 
-    // Purge this list.
-    removedItems.clear();
-    freeItemIndexes.clear();
-    for (int i = 0; i < indexedItems.size(); ++i) {
-        if (!indexedItems.at(i))
-            freeItemIndexes << i;
+    if (focusItem) {
+        QFocusEvent event(QEvent::FocusOut, focusReason);
+        lastFocusItem = focusItem;
+        focusItem = 0;
+        sendEvent(lastFocusItem, &event);
+
+        if (lastFocusItem
+            && (lastFocusItem->flags() & QGraphicsItem::ItemAcceptsInputMethod)) {
+            // Reset any visible preedit text
+            QInputMethodEvent imEvent;
+            sendEvent(lastFocusItem, &imEvent);
+
+            // Close any external input method panel
+            for (int i = 0; i < views.size(); ++i)
+                views.at(i)->inputContext()->reset();
+        }
     }
-    purgePending = false;
-}
 
-/*!
-    \internal
+    if (item) {
+        if (item->isWidget()) {
+            // Update focus child chain.
+            static_cast<QGraphicsWidget *>(item)->d_func()->setFocusWidget();
+        }
 
-    Starts or restarts the timer used for reindexing unindexed items.
-*/
-void QGraphicsScenePrivate::startIndexTimer(int interval)
-{
-    Q_Q(QGraphicsScene);
-    if (indexTimerId) {
-        restartIndexTimer = true;
-    } else {
-        indexTimerId = q->startTimer(interval);
+        focusItem = item;
+        QFocusEvent event(QEvent::FocusIn, focusReason);
+        sendEvent(item, &event);
     }
+
+    updateInputMethodSensitivityInViews();
 }
 
 /*!
@@ -1105,41 +851,20 @@ QList<QGraphicsItem *> QGraphicsScenePrivate::itemsAtPosition(const QPoint &scre
 {
     Q_Q(const QGraphicsScene);
     QGraphicsView *view = widget ? qobject_cast<QGraphicsView *>(widget->parentWidget()) : 0;
-    QList<QGraphicsItem *> items;
-    if (view)
-        items = view->items(view->viewport()->mapFromGlobal(screenPos));
-    else
-        items = q->items(scenePos);
-    return items;
-}
+    if (!view)
+        return q->items(scenePos, Qt::IntersectsItemShape, Qt::AscendingOrder, QTransform());
 
-/*!
-    \internal
+    const QRectF pointRect(QPointF(widget->mapFromGlobal(screenPos)), QSizeF(1, 1));
+    if (!view->isTransformed())
+        return q->items(pointRect, Qt::IntersectsItemShape, Qt::AscendingOrder);
 
-    Checks if item collides with the path and mode, but also checks that if it
-    doesn't collide, maybe its frame rect will.
-*/
-bool QGraphicsScenePrivate::itemCollidesWithPath(QGraphicsItem *item,
-                                                 const QPainterPath &path,
-                                                 Qt::ItemSelectionMode mode)
-{
-    if (item->collidesWithPath(path, mode))
-        return true;
-    if (item->isWidget()) {
-        // Check if this is a window, and if its frame rect collides.
-        QGraphicsWidget *widget = static_cast<QGraphicsWidget *>(item);
-        if (widget->isWindow()) {
-            QRectF frameRect = widget->windowFrameRect();
-            QPainterPath framePath;
-            framePath.addRect(frameRect);
-            bool intersects = path.intersects(frameRect);
-            if (mode == Qt::IntersectsItemShape || mode == Qt::IntersectsItemBoundingRect)
-                return intersects || path.contains(frameRect.topLeft())
-                    || framePath.contains(path.elementAt(0));
-            return !intersects && path.contains(frameRect.topLeft());
-        }
+    const QTransform viewTransform = view->viewportTransform();
+    if (viewTransform.type() <= QTransform::TxScale) {
+        return q->items(viewTransform.inverted().mapRect(pointRect), Qt::IntersectsItemShape,
+                        Qt::AscendingOrder, viewTransform);
     }
-    return false;
+    return q->items(viewTransform.inverted().map(pointRect), Qt::IntersectsItemShape,
+                    Qt::AscendingOrder, viewTransform);
 }
 
 /*!
@@ -1151,7 +876,7 @@ void QGraphicsScenePrivate::storeMouseButtonsForMouseGrabber(QGraphicsSceneMouse
         if (event->buttons() & i) {
             mouseGrabberButtonDownPos.insert(Qt::MouseButton(i),
                                              mouseGrabberItems.last()->d_ptr->genericMapFromScene(event->scenePos(),
-                                                                                          event->widget()));
+                                                                                                  event->widget()));
             mouseGrabberButtonDownScenePos.insert(Qt::MouseButton(i), event->scenePos());
             mouseGrabberButtonDownScreenPos.insert(Qt::MouseButton(i), event->screenPos());
         }
@@ -1185,6 +910,24 @@ void QGraphicsScenePrivate::removeSceneEventFilter(QGraphicsItem *watched, QGrap
 }
 
 /*!
+  \internal
+*/
+bool QGraphicsScenePrivate::filterDescendantEvent(QGraphicsItem *item, QEvent *event)
+{
+    if (item && (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorFiltersChildEvents)) {
+        QGraphicsItem *parent = item->parentItem();
+        while (parent) {
+            if (parent->d_ptr->filtersDescendantEvents && parent->sceneEventFilter(item, event))
+                return true;
+            if (!(parent->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorFiltersChildEvents))
+                return false;
+            parent = parent->parentItem();
+        }
+    }
+    return false;
+}
+
+/*!
     \internal
 */
 bool QGraphicsScenePrivate::filterEvent(QGraphicsItem *item, QEvent *event)
@@ -1216,7 +959,9 @@ bool QGraphicsScenePrivate::sendEvent(QGraphicsItem *item, QEvent *event)
 {
     if (filterEvent(item, event))
         return false;
-    return (item && item->isEnabled()) ? item->sceneEvent(event) : false;
+    if (filterDescendantEvent(item, event))
+        return false;
+    return (item && item->isEnabled() ? item->sceneEvent(event) : false);
 }
 
 /*!
@@ -1429,779 +1174,6 @@ QGraphicsWidget *QGraphicsScenePrivate::windowForItem(const QGraphicsItem *item)
     return 0;
 }
 
-QList<QGraphicsItem *> QGraphicsScenePrivate::topLevelItemsInStackingOrder(const QTransform *const viewTransform,
-                                                                           QRegion *exposedRegion)
-{
-    if (indexMethod == QGraphicsScene::NoIndex || !exposedRegion) {
-        if (needSortTopLevelItems) {
-            needSortTopLevelItems = false;
-            qStableSort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf);
-        }
-        return topLevelItems;
-    }
-
-    const QRectF exposedRect = exposedRegion->boundingRect().adjusted(-1, -1, 1, 1);
-    QRectF sceneRect;
-    QTransform invertedViewTransform(Qt::Uninitialized);
-    if (!viewTransform) {
-        sceneRect = exposedRect;
-    } else {
-        invertedViewTransform = viewTransform->inverted();
-        sceneRect = invertedViewTransform.mapRect(exposedRect);
-    }
-    if (!largestUntransformableItem.isEmpty()) {
-        // ### Nuke this when we move the indexing code into a separate
-        // class.  All the largestUntransformableItem code should then go
-        // away, and the estimate function should return untransformable
-        // items as well.
-        QRectF untr = largestUntransformableItem;
-        QRectF ltri = !viewTransform ? untr : invertedViewTransform.mapRect(untr);
-        ltri.adjust(-untr.width(), -untr.height(), untr.width(), untr.height());
-        sceneRect.adjust(-ltri.width(), -ltri.height(), ltri.width(), ltri.height());
-    }
-
-    QList<QGraphicsItem *> tmp = estimateItemsInRect(sceneRect);
-    for (int i = 0; i < tmp.size(); ++i)
-        tmp.at(i)->topLevelItem()->d_ptr->itemDiscovered = 1;
-
-    // Sort if the toplevel list is unsorted.
-    if (needSortTopLevelItems) {
-        needSortTopLevelItems = false;
-        qStableSort(topLevelItems.begin(), topLevelItems.end(), qt_notclosestLeaf);
-    }
-
-    QList<QGraphicsItem *> tli;
-    for (int i = 0; i < topLevelItems.size(); ++i) {
-        // ### Investigate smarter ways. Looping through all top level
-        // items is not optimal. If the BSP tree is to have maximum
-        // effect, it should be possible to sort the subset of items
-        // quickly. We must use this approach for now, as it's the only
-        // current way to keep the stable sorting order (insertion order).
-        QGraphicsItem *item = topLevelItems.at(i);
-        if (item->d_ptr->itemDiscovered) {
-            item->d_ptr->itemDiscovered = 0;
-            tli << item;
-        }
-    }
-    return tli;
-}
-
-void QGraphicsScenePrivate::recursive_items_helper(QGraphicsItem *item, QRectF rect,
-                                                   QList<QGraphicsItem *> *items,
-                                                   const QTransform &parentTransform,
-                                                   const QTransform &viewTransform,
-                                                   Qt::ItemSelectionMode mode, Qt::SortOrder order,
-                                                   qreal parentOpacity) const
-{
-    // Calculate opacity.
-    qreal opacity;
-    if (item) {
-        if (!item->d_ptr->visible)
-            return;
-        QGraphicsItem *p = item->d_ptr->parent;
-        bool itemIgnoresParentOpacity = item->d_ptr->flags & QGraphicsItem::ItemIgnoresParentOpacity;
-        bool parentDoesntPropagateOpacity = (p && (p->d_ptr->flags & QGraphicsItem::ItemDoesntPropagateOpacityToChildren));
-        if (!itemIgnoresParentOpacity && !parentDoesntPropagateOpacity) {
-            opacity = parentOpacity * item->opacity();
-        } else {
-            opacity = item->d_ptr->opacity;
-        }
-        if (opacity == 0.0 && !(item->d_ptr->flags & QGraphicsItem::ItemDoesntPropagateOpacityToChildren))
-            return;
-    } else {
-        opacity = parentOpacity;
-    }
-
-    // Calculate the full transform for this item.
-    QTransform transform = parentTransform;
-    bool keep = false;
-    if (item) {
-        item->d_ptr->combineTransformFromParent(&transform, &viewTransform);
-
-        // ### This does not take the clip into account.
-        QRectF brect = item->boundingRect();
-        _q_adjustRect(&brect);
-
-        keep = true;
-        if (mode == Qt::ContainsItemShape || mode == Qt::ContainsItemBoundingRect)
-            keep = rect.contains(transform.mapRect(brect)) && rect != brect;
-        else
-            keep = rect.intersects(transform.mapRect(brect));
-
-        if (keep && (mode == Qt::ContainsItemShape || mode == Qt::IntersectsItemShape)) {
-            QPainterPath rectPath;
-            rectPath.addRect(rect);
-            keep = itemCollidesWithPath(item, transform.inverted().map(rectPath), mode);
-        }
-    }
-
-    bool childClip = (item && (item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape));
-    bool dontProcessItem = !item || !keep;
-    bool dontProcessChildren = item && dontProcessItem && childClip;
-
-    // Find and sort children.
-    QList<QGraphicsItem *> &children = item ? item->d_ptr->children : const_cast<QGraphicsScenePrivate *>(this)->topLevelItems;
-    if (!dontProcessChildren) {
-        if (item && item->d_ptr->needSortChildren) {
-            item->d_ptr->needSortChildren = 0;
-            qStableSort(children.begin(), children.end(), qt_notclosestLeaf);
-        } else if (!item && needSortTopLevelItems) {
-            const_cast<QGraphicsScenePrivate *>(this)->needSortTopLevelItems = false;
-            qStableSort(children.begin(), children.end(), qt_notclosestLeaf);
-        }
-    }
-
-    childClip &= !dontProcessChildren & !children.isEmpty();
-
-    // Clip.
-    if (childClip)
-        rect &= transform.map(item->shape()).controlPointRect();
-
-    // Process children behind
-    int i = 0;
-    if (!dontProcessChildren) {
-        for (i = 0; i < children.size(); ++i) {
-            QGraphicsItem *child = children.at(i);
-            if (!(child->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent))
-                break;
-            recursive_items_helper(child, rect, items, transform, viewTransform,
-                                   mode, order, opacity);
-        }
-    }
-
-    // Process item
-    if (!dontProcessItem)
-        items->append(item);
-
-    // Process children in front
-    if (!dontProcessChildren) {
-        for (; i < children.size(); ++i)
-            recursive_items_helper(children.at(i), rect, items, transform, viewTransform,
-                                   mode, order, opacity);
-    }
-
-    if (!item && order == Qt::AscendingOrder) {
-        int n = items->size();
-        for (int i = 0; i < n / 2; ++i) {
-            QGraphicsItem *tmp = (*items)[n - i - 1];
-            (*items)[n - i - 1] = (*items)[i];
-            (*items)[i] = tmp;
-        }
-    }
-}
-
-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->transformData && !item->d_ptr->transformData->computedFullTransform().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->transformData && !item->d_ptr->transformData->computedFullTransform().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->transformData || item->d_ptr->transformData->computedFullTransform().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->transformData && !item->d_ptr->transformData->computedFullTransform().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->transformData && !item->d_ptr->transformData->computedFullTransform().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);
-    if (!sortCacheEnabled || updatingSortCache)
-        return;
-
-    updatingSortCache = true;
-    QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);
-}
-
-/*!
-    \internal
-
-    Should not be exported, but we can't change that now.
-    ### Qt 5: Remove symbol / make static
-*/
-inline bool qt_closestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    // Return true if sibling item1 is on top of item2.
-    const QGraphicsItemPrivate *d1 = item1->d_ptr.data();
-    const QGraphicsItemPrivate *d2 = item2->d_ptr.data();
-    bool f1 = d1->flags & QGraphicsItem::ItemStacksBehindParent;
-    bool f2 = d2->flags & QGraphicsItem::ItemStacksBehindParent;
-    if (f1 != f2) return f2;
-    qreal z1 = d1->z;
-    qreal z2 = d2->z;
-    return z1 > z2;
-}
-
-static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    return qt_closestLeaf(item2, item1);
-}
-
-/*!
-    \internal
-
-    Should not be exported, but we can't change that now.
-*/
-inline bool qt_closestItemFirst(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    return QGraphicsScenePrivate::closestItemFirst_withoutCache(item1, item2);
-}
-
-/*!
-    Returns true if \a item1 is on top of \a item2.
-
-    \internal
-*/
-bool QGraphicsScenePrivate::closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    // Siblings? Just check their z-values.
-    const QGraphicsItemPrivate *d1 = item1->d_ptr.data();
-    const QGraphicsItemPrivate *d2 = item2->d_ptr.data();
-    if (d1->parent == d2->parent)
-        return qt_closestLeaf(item1, item2);
-
-    // Find common ancestor, and each item's ancestor closest to the common
-    // ancestor.
-    int item1Depth = d1->depth;
-    int item2Depth = d2->depth;
-    const QGraphicsItem *p = item1;
-    const QGraphicsItem *t1 = item1;
-    while (item1Depth > item2Depth && (p = p->d_ptr->parent)) {
-        if (p == item2) {
-            // item2 is one of item1's ancestors; item1 is on top
-            return !(t1->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
-        }
-        t1 = p;
-        --item1Depth;
-    }
-    p = item2;
-    const QGraphicsItem *t2 = item2;
-    while (item2Depth > item1Depth && (p = p->d_ptr->parent)) {
-        if (p == item1) {
-            // item1 is one of item2's ancestors; item1 is not on top
-            return (t2->d_ptr->flags & QGraphicsItem::ItemStacksBehindParent);
-        }
-        t2 = p;
-        --item2Depth;
-    }
-
-    // item1Ancestor is now at the same level as item2Ancestor, but not the same.
-    const QGraphicsItem *a1 = t1;
-    const QGraphicsItem *a2 = t2;
-    while (a1) {
-        const QGraphicsItem *p1 = a1;
-        const QGraphicsItem *p2 = a2;
-        a1 = a1->parentItem();
-        a2 = a2->parentItem();
-        if (a1 && a1 == a2)
-            return qt_closestLeaf(p1, p2);
-    }
-
-    // No common ancestor? Then just compare the items' toplevels directly.
-    return qt_closestLeaf(t1->topLevelItem(), t2->topLevelItem());
-}
-
-/*!
-    Returns true if \a item2 is on top of \a item1.
-
-    \internal
-*/
-bool QGraphicsScenePrivate::closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2)
-{
-    return closestItemFirst_withoutCache(item2, item1);
-}
-
-void QGraphicsScenePrivate::climbTree(QGraphicsItem *item, int *stackingOrder)
-{
-    if (!item->d_ptr->children.isEmpty()) {
-        QList<QGraphicsItem *> childList = item->d_ptr->children;
-        qSort(childList.begin(), childList.end(), qt_closestLeaf);
-        for (int i = 0; i < childList.size(); ++i) {
-            QGraphicsItem *item = childList.at(i);
-            if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))
-                climbTree(childList.at(i), stackingOrder);
-        }
-        item->d_ptr->globalStackingOrder = (*stackingOrder)++;
-        for (int i = 0; i < childList.size(); ++i) {
-            QGraphicsItem *item = childList.at(i);
-            if (item->flags() & QGraphicsItem::ItemStacksBehindParent)
-                climbTree(childList.at(i), stackingOrder);
-        }
-    } else {
-        item->d_ptr->globalStackingOrder = (*stackingOrder)++;
-    }
-}
-
-void QGraphicsScenePrivate::_q_updateSortCache()
-{
-    _q_updateIndex();
-
-    if (!sortCacheEnabled || !updatingSortCache)
-        return;
-
-    updatingSortCache = false;
-    int stackingOrder = 0;
-
-    QList<QGraphicsItem *> topLevels;
-
-    for (int i = 0; i < indexedItems.size(); ++i) {
-        QGraphicsItem *item = indexedItems.at(i);
-        if (item && item->parentItem() == 0)
-            topLevels << item;
-    }
-    for (int i = 0; i < unindexedItems.size(); ++i) {
-        QGraphicsItem *item = unindexedItems.at(i);
-        if (item->parentItem() == 0)
-            topLevels << item;
-    }
-
-    qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
-    for (int i = 0; i < topLevels.size(); ++i)
-        climbTree(topLevels.at(i), &stackingOrder);
-}
-
-void QGraphicsScenePrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,
-                                      bool sortCacheEnabled)
-{
-    if (sortCacheEnabled) {
-        if (order == Qt::AscendingOrder) {
-            qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
-        } else if (order == Qt::DescendingOrder) {
-            qSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
-        }
-    } else {
-        if (order == Qt::AscendingOrder) {
-            qSort(itemList->begin(), itemList->end(), closestItemFirst_withoutCache);
-        } else if (order == Qt::DescendingOrder) {
-            qSort(itemList->begin(), itemList->end(), closestItemLast_withoutCache);
-        }
-    }
-}
-
 /*!
     \internal
 
@@ -2334,8 +1306,8 @@ QGraphicsScene::QGraphicsScene(QObject *parent)
 QGraphicsScene::QGraphicsScene(const QRectF &sceneRect, QObject *parent)
     : QObject(*new QGraphicsScenePrivate, parent)
 {
-    setSceneRect(sceneRect);
     d_func()->init();
+    setSceneRect(sceneRect);
 }
 
 /*!
@@ -2349,8 +1321,8 @@ QGraphicsScene::QGraphicsScene(const QRectF &sceneRect, QObject *parent)
 QGraphicsScene::QGraphicsScene(qreal x, qreal y, qreal width, qreal height, QObject *parent)
     : QObject(*new QGraphicsScenePrivate, parent)
 {
-    setSceneRect(x, y, width, height);
     d_func()->init();
+    setSceneRect(x, y, width, height);
 }
 
 /*!
@@ -2387,8 +1359,19 @@ QGraphicsScene::~QGraphicsScene()
 QRectF QGraphicsScene::sceneRect() const
 {
     Q_D(const QGraphicsScene);
-    const_cast<QGraphicsScenePrivate *>(d)->_q_updateIndex();
-    return d->hasSceneRect ? d->sceneRect : d->growingItemsBoundingRect;
+    if (d->hasSceneRect)
+        return d->sceneRect;
+
+    if (d->dirtyGrowingItemsBoundingRect) {
+        // Lazily update the growing items bounding rect
+        QGraphicsScenePrivate *thatd = const_cast<QGraphicsScenePrivate *>(d);
+        QRectF oldGrowingBoundingRect = thatd->growingItemsBoundingRect;
+        thatd->growingItemsBoundingRect |= itemsBoundingRect();
+        thatd->dirtyGrowingItemsBoundingRect = false;
+        if (oldGrowingBoundingRect != thatd->growingItemsBoundingRect)
+            emit const_cast<QGraphicsScene *>(this)->sceneRectChanged(thatd->growingItemsBoundingRect);
+    }
+    return d->growingItemsBoundingRect;
 }
 void QGraphicsScene::setSceneRect(const QRectF &rect)
 {
@@ -2396,8 +1379,7 @@ void QGraphicsScene::setSceneRect(const QRectF &rect)
     if (rect != d->sceneRect) {
         d->hasSceneRect = !rect.isNull();
         d->sceneRect = rect;
-        d->resetIndex();
-        emit sceneRectChanged(rect);
+        emit sceneRectChanged(d->hasSceneRect ? rect : d->growingItemsBoundingRect);
     }
 }
 
@@ -2438,6 +1420,8 @@ void QGraphicsScene::setSceneRect(const QRectF &rect)
 void QGraphicsScene::render(QPainter *painter, const QRectF &target, const QRectF &source,
                             Qt::AspectRatioMode aspectRatioMode)
 {
+    // ### Switch to using the recursive rendering algorithm instead.
+
     // Default source rect = scene rect
     QRectF sourceRect = source;
     if (sourceRect.isNull())
@@ -2532,8 +1516,19 @@ QGraphicsScene::ItemIndexMethod QGraphicsScene::itemIndexMethod() const
 void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method)
 {
     Q_D(QGraphicsScene);
-    d->resetIndex();
+    if (d->indexMethod == method)
+        return;
+
     d->indexMethod = method;
+
+    QList<QGraphicsItem *> oldItems = d->index->items(Qt::AscendingOrder);
+    delete d->index;
+    if (method == BspTreeIndex)
+        d->index = new QGraphicsSceneBspTreeIndex(this);
+    else
+        d->index = new QGraphicsSceneLinearIndex(this);
+    for (int i = oldItems.size() - 1; i >= 0; --i)
+        d->index->addItem(oldItems.at(i));
 }
 
 /*!
@@ -2571,35 +1566,32 @@ void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method)
 int QGraphicsScene::bspTreeDepth() const
 {
     Q_D(const QGraphicsScene);
-    return d->bspTreeDepth;
+    QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex *>(d->index);
+    return bspTree ? bspTree->bspTreeDepth() : 0;
 }
 void QGraphicsScene::setBspTreeDepth(int depth)
 {
     Q_D(QGraphicsScene);
-    if (d->bspTreeDepth == depth)
-        return;
-
     if (depth < 0) {
         qWarning("QGraphicsScene::setBspTreeDepth: invalid depth %d ignored; must be >= 0", depth);
         return;
     }
 
-    d->bspTreeDepth = depth;
-    d->resetIndex();
+    QGraphicsSceneBspTreeIndex *bspTree = qobject_cast<QGraphicsSceneBspTreeIndex *>(d->index);
+    if (!bspTree) {
+        qWarning("QGraphicsScene::setBspTreeDepth: can not apply if indexing method is not BSP");
+        return;
+    }
+    bspTree->setBspTreeDepth(depth);
 }
 
 /*!
     \property QGraphicsScene::sortCacheEnabled
     \brief whether sort caching is enabled
     \since 4.5
+    \obsolete
 
-    When enabled, this property adds a cache that speeds up sorting and
-    transformations for scenes with deep hierarchies (i.e., items with many
-    levels of descendents), at the cost of using more memory (approx. 100 more
-    bytes of memory per item).
-
-    Items that are not part of a deep hierarchy suffer no penalty from this
-    cache.
+    Since Qt 4.6, this property has no effect.
 */
 bool QGraphicsScene::isSortCacheEnabled() const
 {
@@ -2609,10 +1601,9 @@ bool QGraphicsScene::isSortCacheEnabled() const
 void QGraphicsScene::setSortCacheEnabled(bool enabled)
 {
     Q_D(QGraphicsScene);
-    if (enabled == d->sortCacheEnabled)
+    if (d->sortCacheEnabled == enabled)
         return;
-    if ((d->sortCacheEnabled = enabled))
-        d->invalidateSortCache();
+    d->sortCacheEnabled = enabled;
 }
 
 /*!
@@ -2624,6 +1615,7 @@ void QGraphicsScene::setSortCacheEnabled(bool enabled)
 */
 QRectF QGraphicsScene::itemsBoundingRect() const
 {
+    // Does not take untransformable items into account.
     QRectF boundingRect;
     foreach (QGraphicsItem *item, items())
         boundingRect |= item->sceneBoundingRect();
@@ -2638,43 +1630,43 @@ QRectF QGraphicsScene::itemsBoundingRect() const
 QList<QGraphicsItem *> QGraphicsScene::items() const
 {
     Q_D(const QGraphicsScene);
-    const_cast<QGraphicsScenePrivate *>(d)->purgeRemovedItems();
+    return d->index->items(Qt::AscendingOrder);
+}
 
-    // If freeItemIndexes is empty, we know there are no holes in indexedItems and
-    // unindexedItems.
-    if (d->freeItemIndexes.isEmpty()) {
-        if (d->unindexedItems.isEmpty())
-            return d->indexedItems;
-        return d->indexedItems + d->unindexedItems;
-    }
+/*!
+    Returns an ordered list of all items on the scene. \a order decides the
+    sorting.
 
-    // Rebuild the list of items to avoid holes. ### We could also just
-    // compress the item lists at this point.
-    QList<QGraphicsItem *> itemList;
-    foreach (QGraphicsItem *item, d->indexedItems + d->unindexedItems) {
-        if (item)
-            itemList << item;
-    }
-    return itemList;
+    \sa addItem(), removeItem()
+*/
+QList<QGraphicsItem *> QGraphicsScene::items(Qt::SortOrder order) const
+{
+    Q_D(const QGraphicsScene);
+    return d->index->items(order);
 }
 
 /*!
+    \obsolete
+
     Returns all visible items at position \a pos in the scene. The items are
-    listed in descending Z order (i.e., the first item in the list is the
+    listed in descending stacking order (i.e., the first item in the list is the
     top-most item, and the last item is the bottom-most item).
 
+    This function is deprecated and returns incorrect results if the scene
+    contains items that ignore transformations. Use the overload that takes
+    a QTransform instead.
+
     \sa itemAt()
 */
 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);
 }
 
 /*!
-    \fn QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rectangle, Qt::ItemSelectionMode mode) const
-
     \overload
+    \obsolete
 
     Returns all visible items that, depending on \a mode, are either inside or
     intersect with the specified \a rectangle.
@@ -2682,25 +1674,47 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QPointF &pos) const
     The default value for \a mode is Qt::IntersectsItemShape; all items whose
     exact shape intersects with or is contained by \a rectangle are returned.
 
+    This function is deprecated and returns incorrect results if the scene
+    contains items that ignore transformations. Use the overload that takes
+    a QTransform instead.
+
     \sa itemAt()
 */
-QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelectionMode mode) const
+QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rectangle, Qt::ItemSelectionMode mode) const
 {
     Q_D(const QGraphicsScene);
-    QList<QGraphicsItem *> itemList;
-    d->recursive_items_helper(0, rect, &itemList, QTransform(), QTransform(), mode, Qt::AscendingOrder);
-    return itemList;
+    return d->index->items(rectangle, mode, Qt::AscendingOrder);
 }
 
 /*!
     \fn QList<QGraphicsItem *> QGraphicsScene::items(qreal x, qreal y, qreal w, qreal h, Qt::ItemSelectionMode mode) const
+    \obsolete
     \since 4.3
 
     This convenience function is equivalent to calling items(QRectF(\a x, \a y, \a w, \a h), \a mode).
+    
+    This function is deprecated and returns incorrect results if the scene
+    contains items that ignore transformations. Use the overload that takes
+    a QTransform instead.
 */
 
 /*!
+    \fn QList<QGraphicsItem *> QGraphicsScene::items(qreal x, qreal y, qreal w, qreal h,
+        Qt::ItemSelectionMode mode, Qt::SortOrder order, const QTransform &deviceTransform) const
     \overload
+    \since 4.6
+
+    Returns all visible items that, depending on \a mode, are either inside or
+    intersect with the rectangle defined by \a x, \a y, \a w and \a h, in a list
+    sorted using \a order.
+
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+*/
+
+/*!
+    \overload
+    \obsolete
 
     Returns all visible items that, depending on \a mode, are either inside or
     intersect with the polygon \a polygon.
@@ -2708,16 +1722,21 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QRectF &rect, Qt::ItemSelecti
     The default value for \a mode is Qt::IntersectsItemShape; all items whose
     exact shape intersects with or is contained by \a polygon are returned.
 
+    This function is deprecated and returns incorrect results if the scene
+    contains items that ignore transformations. Use the overload that takes
+    a QTransform instead.
+
     \sa itemAt()
 */
 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);
 }
 
 /*!
     \overload
+    \obsolete
 
     Returns all visible items that, depending on \a path, are either inside or
     intersect with the path \a path.
@@ -2725,12 +1744,103 @@ QList<QGraphicsItem *> QGraphicsScene::items(const QPolygonF &polygon, Qt::ItemS
     The default value for \a mode is Qt::IntersectsItemShape; all items whose
     exact shape intersects with or is contained by \a path are returned.
 
+    This function is deprecated and returns incorrect results if the scene
+    contains items that ignore transformations. Use the overload that takes
+    a QTransform instead.
+
     \sa itemAt()
 */
 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);
+}
+
+/*!
+    \since 4.6
+
+    Returns all visible items that, depending on \a mode, are at the specified \a pos
+    in a list sorted using \a order.
+
+    The default value for \a mode is Qt::IntersectsItemShape; all items whose
+    exact shape intersects with \a pos are returned.
+
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+
+    \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);
+}
+
+/*!
+    \overload
+    \since 4.6
+
+    Returns all visible items that, depending on \a mode, are either inside or
+    intersect with the specified \a rect and return a list sorted using \a order.
+
+    The default value for \a mode is Qt::IntersectsItemShape; all items whose
+    exact shape intersects with or is contained by \a rect are returned.
+
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+
+    \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
+    \since 4.6
+
+    Returns all visible items that, depending on \a mode, are either inside or
+    intersect with the specified \a polygon and return a list sorted using \a order.
+
+    The default value for \a mode is Qt::IntersectsItemShape; all items whose
+    exact shape intersects with or is contained by \a polygon are returned.
+
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+
+    \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
+    \since 4.6
+
+    Returns all visible items that, depending on \a mode, are either inside or
+    intersect with the specified \a path and return a list sorted using \a order.
+
+    The default value for \a mode is Qt::IntersectsItemShape; all items whose
+    exact shape intersects with or is contained by \a path are returned.
+
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+
+    \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);
 }
 
 /*!
@@ -2753,34 +1863,77 @@ QList<QGraphicsItem *> QGraphicsScene::collidingItems(const QGraphicsItem *item,
         return QList<QGraphicsItem *>();
     }
 
+    // Does not support ItemIgnoresTransformations.
     QList<QGraphicsItem *> tmp;
-    foreach (QGraphicsItem *itemInVicinity, d->estimateItemsInRect(item->sceneBoundingRect())) {
+    foreach (QGraphicsItem *itemInVicinity, d->index->estimateItems(item->sceneBoundingRect(), Qt::AscendingOrder)) {
         if (item != itemInVicinity && item->collidesWithItem(itemInVicinity, mode))
             tmp << itemInVicinity;
     }
-    d->sortItems(&tmp, Qt::AscendingOrder, d->sortCacheEnabled);
     return tmp;
 }
 
 /*!
-    \fn QGraphicsItem *QGraphicsScene::itemAt(const QPointF &position) const
+    \overload
+    \obsolete
 
     Returns the topmost visible item at the specified \a position, or 0 if
     there are no items at this position.
 
     \note The topmost item is the one with the highest Z-value.
 
+    This function is deprecated and returns incorrect results if the scene
+    contains items that ignore transformations. Use the overload that takes
+    a QTransform instead.
+
     \sa items(), collidingItems(), QGraphicsItem::setZValue()
 */
-QGraphicsItem *QGraphicsScene::itemAt(const QPointF &pos) const
+QGraphicsItem *QGraphicsScene::itemAt(const QPointF &position) const
 {
-    QList<QGraphicsItem *> itemsAtPoint = items(pos);
+    QList<QGraphicsItem *> itemsAtPoint = items(position);
     return itemsAtPoint.isEmpty() ? 0 : itemsAtPoint.first();
 }
 
 /*!
+    \since 4.6
+
+    Returns the topmost visible item at the specified \a position, or 0
+    if there are no items at this position.
+
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+
+    \note The topmost item is the one with the highest Z-value.
+
+    \sa items(), collidingItems(), QGraphicsItem::setZValue()
+    */
+QGraphicsItem *QGraphicsScene::itemAt(const QPointF &position, const QTransform &deviceTransform) const
+{
+    QList<QGraphicsItem *> itemsAtPoint = items(position, Qt::IntersectsItemShape,
+                                                Qt::AscendingOrder, deviceTransform);
+    return itemsAtPoint.isEmpty() ? 0 : itemsAtPoint.first();
+}
+
+/*!
+    \fn QGraphicsScene::itemAt(qreal x, qreal y, const QTransform &deviceTransform) const
+    \overload
+    \since 4.6
+
+    Returns the topmost item at the position specified by (\a x, \a
+    y), or 0 if there are no items at this position.
+
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+
+    This convenience function is equivalent to calling \c
+    {itemAt(QPointF(x, y), deviceTransform)}.
+
+    \note The topmost item is the one with the highest Z-value.
+*/
+
+/*!
     \fn QGraphicsScene::itemAt(qreal x, qreal y) const
     \overload
+    \obsolete
 
     Returns the topmost item at the position specified by (\a x, \a
     y), or 0 if there are no items at this position.
@@ -2788,6 +1941,10 @@ QGraphicsItem *QGraphicsScene::itemAt(const QPointF &pos) const
     This convenience function is equivalent to calling \c
     {itemAt(QPointF(x, y))}.
 
+    This function is deprecated and returns incorrect results if the scene
+    contains items that ignore transformations. Use the overload that takes
+    a QTransform instead.
+
     \note The topmost item is the one with the highest Z-value.
 */
 
@@ -2828,21 +1985,42 @@ QPainterPath QGraphicsScene::selectionArea() const
 }
 
 /*!
+    \since 4.6
+
     Sets the selection area to \a path. All items within this area are
     immediately selected, and all items outside are unselected. You can get
     the list of all selected items by calling selectedItems().
 
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+
     For an item to be selected, it must be marked as \e selectable
     (QGraphicsItem::ItemIsSelectable).
 
     \sa clearSelection(), selectionArea()
 */
+void QGraphicsScene::setSelectionArea(const QPainterPath &path, const QTransform &deviceTransform)
+{
+    setSelectionArea(path, Qt::IntersectsItemShape, deviceTransform);
+}
+
+/*!
+    \obsolete
+    \overload
+
+    Sets the selection area to \a path.
+
+    This function is deprecated and leads to incorrect results if the scene
+    contains items that ignore transformations. Use the overload that takes
+    a QTransform instead.
+*/
 void QGraphicsScene::setSelectionArea(const QPainterPath &path)
 {
-    setSelectionArea(path, Qt::IntersectsItemShape);
+    setSelectionArea(path, Qt::IntersectsItemShape, QTransform());
 }
 
 /*!
+    \obsolete
     \overload
     \since 4.3
 
@@ -2853,6 +2031,24 @@ void QGraphicsScene::setSelectionArea(const QPainterPath &path)
 */
 void QGraphicsScene::setSelectionArea(const QPainterPath &path, Qt::ItemSelectionMode mode)
 {
+    setSelectionArea(path, mode, QTransform());
+}
+
+/*!
+    \overload
+    \since 4.6
+
+    Sets the selection area to \a path using \a mode to determine if items are
+    included in the selection area.
+
+    \a deviceTransform is the transformation that applies to the view, and needs to
+    be provided if the scene contains items that ignore transformations.
+
+    \sa clearSelection(), selectionArea()
+*/
+void QGraphicsScene::setSelectionArea(const QPainterPath &path, Qt::ItemSelectionMode mode,
+                                      const QTransform &deviceTransform)
+{
     Q_D(QGraphicsScene);
 
     // Note: with boolean path operations, we can improve performance here
@@ -2868,7 +2064,7 @@ void QGraphicsScene::setSelectionArea(const QPainterPath &path, Qt::ItemSelectio
     bool changed = false;
 
     // Set all items in path to selected.
-    foreach (QGraphicsItem *item, items(path, mode)) {
+    foreach (QGraphicsItem *item, items(path, mode, Qt::AscendingOrder, deviceTransform)) {
         if (item->flags() & QGraphicsItem::ItemIsSelectable) {
             if (!item->isSelected())
                 changed = true;
@@ -2925,26 +2121,13 @@ void QGraphicsScene::clearSelection()
 void QGraphicsScene::clear()
 {
     Q_D(QGraphicsScene);
-    // Recursive descent delete
-    for (int i = 0; i < d->indexedItems.size(); ++i) {
-        if (QGraphicsItem *item = d->indexedItems.at(i)) {
-            if (!item->parentItem())
-                delete item;
-        }
-    }
-    QList<QGraphicsItem *> unindexedParents;
-    for (int i = 0; i < d->unindexedItems.size(); ++i) {
-        QGraphicsItem *item = d->unindexedItems.at(i);
-        if (!item->parentItem())
-            unindexedParents << item;
-    }
-    d->unindexedItems.clear();
-    qDeleteAll(unindexedParents);
-    d->indexedItems.clear();
-    d->freeItemIndexes.clear();
+    // NB! We have to clear the index before deleting items; otherwise the
+    // index might try to access dangling item pointers.
+    d->index->clear();
+    const QList<QGraphicsItem *> items = d->topLevelItems;
+    qDeleteAll(items);
+    Q_ASSERT(d->topLevelItems.isEmpty());
     d->lastItemCount = 0;
-    d->bspTree.clear();
-    d->largestUntransformableItem = QRectF();
     d->allItemsIgnoreHoverEvents = true;
     d->allItemsUseDefaultCursor = true;
     d->allItemsIgnoreTouchEvents = true;
@@ -3066,14 +2249,6 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
         return;
     }
 
-    // Prevent reusing a recently deleted pointer: purge all removed items
-    // from our lists.
-    d->purgeRemovedItems();
-
-    // Invalidate any sort caching; arrival of a new item means we need to
-    // resort.
-    d->invalidateSortCache();
-
     // Detach this item from its parent if the parent's scene is different
     // from this scene.
     if (QGraphicsItem *itemParent = item->parentItem()) {
@@ -3084,29 +2259,18 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
     // Add the item to this scene
     item->d_func()->scene = targetScene;
 
-    // Indexing requires sceneBoundingRect(), but because \a item might
-    // not be completely constructed at this point, we need to store it in
-    // a temporary list and schedule an indexing for later.
-    d->unindexedItems << item;
-    item->d_func()->index = -1;
-    d->startIndexTimer(0);
+    // Add the item in the index
+    d->index->addItem(item);
 
     // Add to list of toplevels if this item is a toplevel.
     if (!item->d_ptr->parent)
         d->registerTopLevelItem(item);
 
-    // Update the scene's sort cache settings.
-    item->d_ptr->globalStackingOrder = -1;
-    d->invalidateSortCache();
-
     // Add to list of items that require an update. We cannot assume that the
     // item is fully constructed, so calling item->update() can lead to a pure
     // virtual function call to boundingRect().
-    if (!d->updateAll) {
-        if (d->pendingUpdateItems.isEmpty())
-            QMetaObject::invokeMethod(this, "_q_updateLater", Qt::QueuedConnection);
-        d->pendingUpdateItems << item;
-    }
+    d->markDirty(item);
+    d->dirtyGrowingItemsBoundingRect = true;
 
     // Disable selectionChanged() for individual items
     ++d->selectionChanging;
@@ -3177,6 +2341,8 @@ void QGraphicsScene::addItem(QGraphicsItem *item)
 
     // Deliver post-change notification
     item->itemChange(QGraphicsItem::ItemSceneHasChanged, newSceneVariant);
+
+    d->updateInputMethodSensitivityInViews();
 }
 
 /*!
@@ -3452,6 +2618,8 @@ void QGraphicsScene::removeItem(QGraphicsItem *item)
 
     // Deliver post-change notification
     item->itemChange(QGraphicsItem::ItemSceneHasChanged, newSceneVariant);
+
+    d->updateInputMethodSensitivityInViews();
 }
 
 /*!
@@ -3488,36 +2656,10 @@ QGraphicsItem *QGraphicsScene::focusItem() const
 void QGraphicsScene::setFocusItem(QGraphicsItem *item, Qt::FocusReason focusReason)
 {
     Q_D(QGraphicsScene);
-    if (item == d->focusItem)
-        return;
-    if (item && (!(item->flags() & QGraphicsItem::ItemIsFocusable)
-                 || !item->isVisible() || !item->isEnabled())) {
-        item = 0;
-    }
-
-    if (item) {
-        setFocus(focusReason);
-        if (item == d->focusItem)
-            return;
-    }
-
-    if (d->focusItem) {
-        QFocusEvent event(QEvent::FocusOut, focusReason);
-        d->lastFocusItem = d->focusItem;
-        d->focusItem = 0;
-        d->sendEvent(d->lastFocusItem, &event);
-    }
-
-    if (item) {
-        if (item->isWidget()) {
-            // Update focus child chain.
-            static_cast<QGraphicsWidget *>(item)->d_func()->setFocusWidget();
-        }
-
-        d->focusItem = item;
-        QFocusEvent event(QEvent::FocusIn, focusReason);
-        d->sendEvent(item, &event);
-    }
+    if (item)
+        item->setFocus(focusReason);
+    else
+        d->setFocusItemHelper(item, focusReason);
 }
 
 /*!
@@ -3572,13 +2714,17 @@ void QGraphicsScene::clearFocus()
 
 /*!
     \property QGraphicsScene::stickyFocus
-    \brief whether or not clicking the scene will clear focus
+    \brief whether clicking into the scene background will clear focus
 
-    If this property is false (the default), then clicking on the scene
-    background or on an item that does not accept focus, will clear
-    focus. Otherwise, focus will remain unchanged.
+    \since 4.6
 
-    The focus change happens in response to a mouse press. You can reimplement
+    In a QGraphicsScene with stickyFocus set to true, focus will remain
+    unchanged when the user clicks into the scene background or on an item
+    that does not accept focus. Otherwise, focus will be cleared.
+
+    By default, this property is false.
+
+    Focus changes in response to a mouse press. You can reimplement
     mousePressEvent() in a subclass of QGraphicsScene to toggle this property
     based on where the user has clicked.
 
@@ -3701,7 +2847,7 @@ void QGraphicsScene::setForegroundBrush(const QBrush &brush)
 QVariant QGraphicsScene::inputMethodQuery(Qt::InputMethodQuery query) const
 {
     Q_D(const QGraphicsScene);
-    if (!d->focusItem)
+    if (!d->focusItem || !(d->focusItem->flags() & QGraphicsItem::ItemAcceptsInputMethod))
         return QVariant();
     const QTransform matrix = d->focusItem->sceneTransform();
     QVariant value = d->focusItem->inputMethodQuery(query);
@@ -3737,7 +2883,7 @@ void QGraphicsScene::update(const QRectF &rect)
         if (directUpdates) {
             // Update all views.
             for (int i = 0; i < d->views.size(); ++i)
-                d->views.at(i)->d_func()->updateAll();
+                d->views.at(i)->d_func()->fullUpdatePending = true;
         }
     } else {
         if (directUpdates) {
@@ -4018,132 +3164,17 @@ bool QGraphicsScene::event(QEvent *event)
         // geometries that do not have an explicit style set.
         update();
         break;
-    case QEvent::GraphicsSceneGesture: {
-        QGraphicsSceneGestureEvent *ev = static_cast<QGraphicsSceneGestureEvent*>(event);
-        QGraphicsView *view = qobject_cast<QGraphicsView*>(ev->widget());
-        if (!view) {
-            qWarning("QGraphicsScene::event: gesture event was received without a view");
-            break;
-        }
-
-        // get a list of gestures that just started.
-        QSet<QGesture*> startedGestures;
-        QList<QGesture*> gestures = ev->gestures();
-        for(QList<QGesture*>::const_iterator it = gestures.begin(), e = gestures.end();
-            it != e; ++it) {
-            QGesture *g = *it;
-            QGesturePrivate *gd = g->d_func();
-            if (g->state() == Qt::GestureStarted || gd->singleshot) {
-                startedGestures.insert(g);
-            }
-        }
-        if (!startedGestures.isEmpty()) {
-            // find a target for each started gesture.
-            for(QSet<QGesture*>::const_iterator it = startedGestures.begin(), e = startedGestures.end();
-                it != e; ++it) {
-                QGesture *g = *it;
-                QGesturePrivate *gd = g->d_func();
-                gd->graphicsItem = 0;
-                QList<QGraphicsItem*> itemsInGestureArea = items(g->hotSpot());
-                const QString gestureName = g->type();
-                foreach(QGraphicsItem *item, itemsInGestureArea) {
-                    if (item->d_func()->hasGesture(gestureName)) {
-                        Q_ASSERT(gd->graphicsItem == 0);
-                        gd->graphicsItem = item;
-                        d->itemsWithGestures[item].insert(g);
-                        break;
-                    }
-                }
-            }
-        }
-        d->sendGestureEvent(ev->gestures().toSet(), ev->cancelledGestures());
-    }
-        break;
     case QEvent::TouchBegin:
     case QEvent::TouchUpdate:
     case QEvent::TouchEnd:
         d->touchEventHandler(static_cast<QTouchEvent *>(event));
         break;
-    case QEvent::Timer:
-        if (d->indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == d->indexTimerId) {
-            if (d->restartIndexTimer) {
-                d->restartIndexTimer = false;
-            } else {
-                // this call will kill the timer
-                d->_q_updateIndex();
-            }
-        }
-        // Fallthrough intended - support timers in subclasses.
     default:
         return QObject::event(event);
     }
     return true;
 }
 
-void QGraphicsScenePrivate::sendGestureEvent(const QSet<QGesture*> &gestures, const QSet<QString> &cancelled)
-{
-    Q_Q(QGraphicsScene);
-    typedef QMap<QGraphicsItem*, QSet<QGesture*> > ItemGesturesMap;
-    ItemGesturesMap itemGestures;
-    QSet<QGesture*> startedGestures;
-    for(QSet<QGesture*>::const_iterator it = gestures.begin(), e = gestures.end();
-        it != e; ++it) {
-        QGesture *g = *it;
-        Q_ASSERT(g != 0);
-        QGesturePrivate *gd = g->d_func();
-        if (gd->graphicsItem != 0) {
-            itemGestures[gd->graphicsItem].insert(g);
-            if (g->state() == Qt::GestureStarted || gd->singleshot)
-                startedGestures.insert(g);
-        }
-    }
-
-    QSet<QGesture*> ignoredGestures;
-    for(ItemGesturesMap::const_iterator it = itemGestures.begin(), e = itemGestures.end();
-        it != e; ++it) {
-        QGraphicsItem *receiver = it.key();
-        Q_ASSERT(receiver != 0);
-        QGraphicsSceneGestureEvent event;
-        event.setGestures(it.value());
-        event.setCancelledGestures(cancelled);
-        bool processed = sendEvent(receiver, &event);
-        QSet<QGesture*> started = startedGestures.intersect(it.value());
-        if (event.isAccepted())
-            foreach(QGesture *g, started)
-                g->accept();
-        if (!started.isEmpty() && !(processed && event.isAccepted())) {
-            // there are started gestures event that weren't
-            // accepted, so propagating each gesture independently.
-            QSet<QGesture*>::const_iterator it = started.begin(),
-                                             e = started.end();
-            for(; it != e; ++it) {
-                QGesture *g = *it;
-                if (processed && g->isAccepted()) {
-                    continue;
-                }
-                QGesturePrivate *gd = g->d_func();
-                QGraphicsItem *item = gd->graphicsItem;
-                gd->graphicsItem = 0;
-
-                //### THIS IS BS, DONT FORGET TO REWRITE THIS CODE
-                // need to make sure we try to deliver event just once to each widget
-                const QString gestureType = g->type();
-                QList<QGraphicsItem*> itemsUnderGesture = q->items(g->hotSpot());
-                for (int i = 0; i < itemsUnderGesture.size(); ++i) {
-                    QGraphicsItem *item = itemsUnderGesture.at(i);
-                    if (item != receiver && item->d_func()->hasGesture(gestureType)) {
-                        ignoredGestures.insert(g);
-                        gd->graphicsItem = item;
-                        break;
-                    }
-                }
-            }
-        }
-    }
-    if (!ignoredGestures.isEmpty())
-        sendGestureEvent(ignoredGestures, cancelled);
-}
-
 /*!
     \reimp
 
@@ -4769,16 +3800,16 @@ void QGraphicsScene::wheelEvent(QGraphicsSceneWheelEvent *wheelEvent)
     subclass to receive input method events for the scene.
 
     The default implementation forwards the event to the focusItem().
-    If no item currently has focus, this function does nothing.
+    If no item currently has focus or the current focus item does not
+    accept input methods, this function does nothing.
 
     \sa QGraphicsItem::inputMethodEvent()
 */
 void QGraphicsScene::inputMethodEvent(QInputMethodEvent *event)
 {
     Q_D(QGraphicsScene);
-    if (!d->focusItem)
-        return;
-    d->sendEvent(d->focusItem, event);
+    if (d->focusItem && (d->focusItem->flags() & QGraphicsItem::ItemAcceptsInputMethod))
+        d->sendEvent(d->focusItem, event);
 }
 
 /*!
@@ -5226,6 +4257,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,
@@ -5248,6 +4293,7 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
 
     QTransform transform(Qt::Uninitialized);
     QTransform *transformPtr = 0;
+    bool translateOnlyTransform = false;
 #define ENSURE_TRANSFORM_PTR \
     if (!transformPtr) { \
         Q_ASSERT(!itemIsUntransformable); \
@@ -5257,6 +4303,7 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
             transformPtr = &transform; \
         } else { \
             transformPtr = &item->d_ptr->sceneTransform; \
+            translateOnlyTransform = item->d_ptr->sceneTransformTranslateOnly; \
         } \
     }
 
@@ -5268,10 +4315,8 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
         transform = item->deviceTransform(viewTransform ? *viewTransform : QTransform());
         transformPtr = &transform;
     } else if (item->d_ptr->dirtySceneTransform) {
-        item->d_ptr->sceneTransform = item->d_ptr->parent ? item->d_ptr->parent->d_ptr->sceneTransform
-                                                          : QTransform();
-        item->d_ptr->combineTransformFromParent(&item->d_ptr->sceneTransform);
-        item->d_ptr->dirtySceneTransform = 0;
+        item->d_ptr->updateSceneTransformFromParent();
+        Q_ASSERT(!item->d_ptr->dirtySceneTransform);
         wasDirtyParentSceneTransform = true;
     }
 
@@ -5280,7 +4325,8 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     if (drawItem) {
         const QRectF brect = adjustedItemBoundingRect(item);
         ENSURE_TRANSFORM_PTR
-        QRect viewBoundingRect = transformPtr->mapRect(brect).toRect();
+        QRect viewBoundingRect = translateOnlyTransform ? brect.translated(transformPtr->dx(), transformPtr->dy()).toRect()
+                                                        : transformPtr->mapRect(brect).toRect();
         item->d_ptr->paintedViewBoundingRects.insert(widget, viewBoundingRect);
         viewBoundingRect.adjust(-1, -1, 1, 1);
         drawItem = exposedRegion ? exposedRegion->intersects(viewBoundingRect) : !viewBoundingRect.isEmpty();
@@ -5297,10 +4343,7 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
 
     int i = 0;
     if (itemHasChildren) {
-        if (item->d_ptr->needSortChildren) {
-            item->d_ptr->needSortChildren = 0;
-            qStableSort(item->d_ptr->children.begin(), item->d_ptr->children.end(), qt_notclosestLeaf);
-        }
+        item->d_ptr->ensureSortedChildren();
 
         if (itemClipsChildrenToShape) {
             painter->save();
@@ -5326,7 +4369,8 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
     if (drawItem) {
         Q_ASSERT(!itemIsFullyTransparent);
         Q_ASSERT(itemHasContents);
-        item->d_ptr->initStyleOption(&styleOptionTmp, transform, exposedRegion
+        ENSURE_TRANSFORM_PTR
+        item->d_ptr->initStyleOption(&styleOptionTmp, *transformPtr, exposedRegion
                                      ? *exposedRegion : QRegion(), exposedRegion == 0);
 
         const bool itemClipsToShape = item->d_ptr->flags & QGraphicsItem::ItemClipsToShape;
@@ -5334,10 +4378,9 @@ void QGraphicsScenePrivate::drawSubtreeRecursive(QGraphicsItem *item, QPainter *
         if (savePainter)
             painter->save();
 
-        if (!itemHasChildren || !itemClipsChildrenToShape) {
-            ENSURE_TRANSFORM_PTR
+        if (!itemHasChildren || !itemClipsChildrenToShape)
             painter->setWorldTransform(*transformPtr);
-        }
+
         if (itemClipsToShape)
             painter->setClipPath(item->shape(), Qt::IntersectClip);
         painter->setOpacity(opacity);
@@ -5380,6 +4423,16 @@ void QGraphicsScenePrivate::markDirty(QGraphicsItem *item, const QRectF &rect, b
                                           /*ignoreVisibleBit=*/force,
                                           /*ignoreDirtyBit=*/removingItemFromScene || invalidateChildren,
                                           /*ignoreOpacity=*/ignoreOpacity)) {
+        if (item->d_ptr->dirty) {
+            // The item is already marked as dirty and will be processed later. However,
+            // we have to make sure ignoreVisible and ignoreOpacity are set properly;
+            // otherwise things like: item->update(); item->hide() (force is now true)
+            // won't work as expected.
+            if (force)
+                item->d_ptr->ignoreVisible = 1;
+            if (ignoreOpacity)
+                item->d_ptr->ignoreOpacity = 1;
+        }
         return;
     }
 
@@ -5439,65 +4492,121 @@ void QGraphicsScenePrivate::markDirty(QGraphicsItem *item, const QRectF &rect, b
 }
 
 static inline bool updateHelper(QGraphicsViewPrivate *view, QGraphicsItemPrivate *item,
-                                const QRectF &rect, const QTransform &xform)
+                                const QRectF &rect, bool itemIsUntransformable)
 {
     Q_ASSERT(view);
     Q_ASSERT(item);
-    if (item->hasBoundingRegionGranularity)
+
+    QGraphicsItem *itemq = static_cast<QGraphicsItem *>(item->q_ptr);
+    QGraphicsView *viewq = static_cast<QGraphicsView *>(view->q_ptr);
+
+    if (itemIsUntransformable) {
+        const QTransform xform = itemq->deviceTransform(viewq->viewportTransform());
+        if (!item->hasBoundingRegionGranularity)
+            return view->updateRect(xform.mapRect(rect).toRect());
         return view->updateRegion(xform.map(QRegion(rect.toRect())));
-    return view->updateRect(xform.mapRect(rect).toRect());
+    }
+
+    if (item->sceneTransformTranslateOnly && view->identityMatrix) {
+        const qreal dx = item->sceneTransform.dx();
+        const qreal dy = item->sceneTransform.dy();
+        if (!item->hasBoundingRegionGranularity) {
+            QRectF r(rect);
+            r.translate(dx - view->horizontalScroll(), dy - view->verticalScroll());
+            return view->updateRect(r.toRect());
+        }
+        QRegion r(rect.toRect());
+        r.translate(qRound(dx) - view->horizontalScroll(), qRound(dy) - view->verticalScroll());
+        return view->updateRegion(r);
+    }
+
+    if (!viewq->isTransformed()) {
+        if (!item->hasBoundingRegionGranularity)
+            return view->updateRect(item->sceneTransform.mapRect(rect).toRect());
+        return view->updateRegion(item->sceneTransform.map(QRegion(rect.toRect())));
+    }
+
+    QTransform xform = item->sceneTransform;
+    xform *= viewq->viewportTransform();
+    if (!item->hasBoundingRegionGranularity)
+        return view->updateRect(xform.mapRect(rect).toRect());
+    return view->updateRegion(xform.map(QRegion(rect.toRect())));
 }
 
 void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, bool dirtyAncestorContainsChildren,
                                                        qreal parentOpacity)
 {
     Q_Q(QGraphicsScene);
+    Q_ASSERT(item);
+    Q_ASSERT(!updateAll);
 
-    bool wasDirtyParentViewBoundingRects = false;
-    bool wasDirtyParentSceneTransform = false;
-    qreal opacity = parentOpacity;
+    if (!item->d_ptr->dirty && !item->d_ptr->dirtyChildren) {
+        resetDirtyItem(item);
+        return;
+    }
 
-    if (item) {
-        wasDirtyParentViewBoundingRects = item->d_ptr->paintedViewBoundingRectsNeedRepaint;
-        opacity = item->d_ptr->combineOpacityFromParent(parentOpacity);
-        const bool itemIsHidden = !item->d_ptr->ignoreVisible && !item->d_ptr->visible;
-        const bool itemIsFullyTransparent = !item->d_ptr->ignoreOpacity && opacity == 0.0;
-
-        if (item->d_ptr->dirtySceneTransform && !itemIsHidden && !item->d_ptr->itemIsUntransformable()
-            && !(itemIsFullyTransparent && item->d_ptr->childrenCombineOpacity())) {
-            // Calculate the full scene transform for this item.
-            item->d_ptr->sceneTransform = item->d_ptr->parent ? item->d_ptr->parent->d_ptr->sceneTransform
-                                                              : QTransform();
-            item->d_ptr->combineTransformFromParent(&item->d_ptr->sceneTransform);
-            item->d_ptr->dirtySceneTransform = 0;
-            wasDirtyParentSceneTransform = true;
-        }
+    const bool itemIsHidden = !item->d_ptr->ignoreVisible && !item->d_ptr->visible;
+    if (itemIsHidden) {
+        resetDirtyItem(item, /*recursive=*/true);
+        return;
+    }
+
+    const bool itemHasContents = !(item->d_ptr->flags & QGraphicsItem::ItemHasNoContents);
+    const bool itemHasChildren = !item->d_ptr->children.isEmpty();
+    if (!itemHasContents && !itemHasChildren) {
+        resetDirtyItem(item);
+        return; // Item has neither contents nor children!(?)
+    }
+
+    const qreal opacity = item->d_ptr->combineOpacityFromParent(parentOpacity);
+    const bool itemIsFullyTransparent = !item->d_ptr->ignoreOpacity && opacity < 0.0001;
+    if (itemIsFullyTransparent && (!itemHasChildren || item->d_ptr->childrenCombineOpacity())) {
+        resetDirtyItem(item, /*recursive=*/itemHasChildren);
+        return;
+    }
 
-        if (itemIsHidden || itemIsFullyTransparent || (item->d_ptr->flags & QGraphicsItem::ItemHasNoContents)) {
-            // Make sure we don't process invisible items or items with no content.
-            item->d_ptr->dirty = 0;
+    bool wasDirtyParentSceneTransform = item->d_ptr->dirtySceneTransform;
+    const bool itemIsUntransformable = item->d_ptr->itemIsUntransformable();
+    if (wasDirtyParentSceneTransform && !itemIsUntransformable) {
+        item->d_ptr->updateSceneTransformFromParent();
+        Q_ASSERT(!item->d_ptr->dirtySceneTransform);
+    }
+
+    const bool wasDirtyParentViewBoundingRects = item->d_ptr->paintedViewBoundingRectsNeedRepaint;
+    if (itemIsFullyTransparent || !itemHasContents || dirtyAncestorContainsChildren) {
+        // Make sure we don't process invisible items or items with no content.
+        item->d_ptr->dirty = 0;
+        item->d_ptr->fullUpdatePending = 0;
+        // Might have a dirty view bounding rect otherwise.
+        if (itemIsFullyTransparent || !itemHasContents)
             item->d_ptr->paintedViewBoundingRectsNeedRepaint = 0;
+    }
+
+    if (!hasSceneRect && item->d_ptr->geometryChanged && item->d_ptr->visible) {
+        // Update growingItemsBoundingRect.
+        if (item->d_ptr->sceneTransformTranslateOnly) {
+            growingItemsBoundingRect |= item->boundingRect().translated(item->d_ptr->sceneTransform.dx(),
+                                                                        item->d_ptr->sceneTransform.dy());
+        } else {
+            growingItemsBoundingRect |= item->d_ptr->sceneTransform.mapRect(item->boundingRect());
         }
     }
 
     // Process item.
-    if (item && (item->d_ptr->dirty || item->d_ptr->paintedViewBoundingRectsNeedRepaint)) {
+    if (item->d_ptr->dirty || item->d_ptr->paintedViewBoundingRectsNeedRepaint) {
         const bool useCompatUpdate = views.isEmpty() || (connectedSignals & changedSignalMask);
-        const bool untransformableItem = item->d_ptr->itemIsUntransformable();
         const QRectF itemBoundingRect = adjustedItemBoundingRect(item);
 
-        if (item->d_ptr->geometryChanged) {
-            // Update growingItemsBoundingRect.
-            if (!hasSceneRect)
-                growingItemsBoundingRect |= item->d_ptr->sceneTransform.mapRect(itemBoundingRect);
-            item->d_ptr->geometryChanged = 0;
-        }
-
-        if (useCompatUpdate && !untransformableItem && qFuzzyIsNull(item->boundingRegionGranularity())) {
+        if (useCompatUpdate && !itemIsUntransformable && qFuzzyIsNull(item->boundingRegionGranularity())) {
             // This block of code is kept for compatibility. Since 4.5, by default
             // QGraphicsView does not connect the signal and we use the below
             // method of delivering updates.
-            q->update(item->d_ptr->sceneTransform.mapRect(itemBoundingRect));
+            if (item->d_ptr->sceneTransformTranslateOnly) {
+                q->update(itemBoundingRect.translated(item->d_ptr->sceneTransform.dx(),
+                                                      item->d_ptr->sceneTransform.dy()));
+            } else {
+                q->update(item->d_ptr->sceneTransform.mapRect(itemBoundingRect));
+            }
         } else {
             QRectF dirtyRect;
             bool uninitializedDirtyRect = true;
@@ -5505,30 +4614,31 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, bool
             for (int j = 0; j < views.size(); ++j) {
                 QGraphicsView *view = views.at(j);
                 QGraphicsViewPrivate *viewPrivate = view->d_func();
-                if (viewPrivate->fullUpdatePending)
-                    continue;
-                switch (viewPrivate->viewportUpdateMode) {
-                case QGraphicsView::NoViewportUpdate:
-                    continue;
-                case QGraphicsView::FullViewportUpdate:
-                    view->viewport()->update();
-                    viewPrivate->fullUpdatePending = 1;
+                QRect &paintedViewBoundingRect = item->d_ptr->paintedViewBoundingRects[viewPrivate->viewport];
+                if (viewPrivate->fullUpdatePending
+                    || viewPrivate->viewportUpdateMode == QGraphicsView::NoViewportUpdate) {
+                    // Okay, if we have a full update pending or no viewport update, this item's
+                    // paintedViewBoundingRect  will be updated correctly in the next paintEvent if
+                    // it is inside the viewport, but for now we can pretend that it is outside.
+                    paintedViewBoundingRect = QRect(-1, -1, -1, -1);
                     continue;
-                default:
-                    break;
                 }
 
-                QRect &paintedViewBoundingRect = item->d_ptr->paintedViewBoundingRects[viewPrivate->viewport];
-                if (item->d_ptr->paintedViewBoundingRectsNeedRepaint) {
-                    wasDirtyParentViewBoundingRects = true;
+                if (item->d_ptr->paintedViewBoundingRectsNeedRepaint && !paintedViewBoundingRect.isEmpty()) {
                     paintedViewBoundingRect.translate(viewPrivate->dirtyScrollOffset);
                     if (!viewPrivate->updateRect(paintedViewBoundingRect))
-                        paintedViewBoundingRect = QRect();
+                        paintedViewBoundingRect = QRect(-1, -1, -1, -1); // Outside viewport.
                 }
 
                 if (!item->d_ptr->dirty)
                     continue;
 
+                if (!item->d_ptr->paintedViewBoundingRectsNeedRepaint
+                    && paintedViewBoundingRect.x() == -1 && paintedViewBoundingRect.y() == -1
+                    && paintedViewBoundingRect.width() == -1 && paintedViewBoundingRect.height() == -1) {
+                    continue; // Outside viewport.
+                }
+
                 if (uninitializedDirtyRect) {
                     dirtyRect = itemBoundingRect;
                     if (!item->d_ptr->fullUpdatePending) {
@@ -5541,35 +4651,25 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, bool
                 if (dirtyRect.isEmpty())
                     continue; // Discard updates outside the bounding rect.
 
-                bool valid = false;
-                if (untransformableItem) {
-                    valid = updateHelper(viewPrivate, item->d_ptr.data(), dirtyRect,
-                                         item->deviceTransform(view->viewportTransform()));
-                } else if (!view->isTransformed()) {
-                    valid = updateHelper(viewPrivate, item->d_ptr.data(), dirtyRect, item->d_ptr->sceneTransform);
-                } else {
-                    QTransform deviceTransform = item->d_ptr->sceneTransform;
-                    deviceTransform *= view->viewportTransform();
-                    valid = updateHelper(viewPrivate, item->d_ptr.data(), dirtyRect, deviceTransform);
+                if (!updateHelper(viewPrivate, item->d_ptr, dirtyRect, itemIsUntransformable)
+                    && item->d_ptr->paintedViewBoundingRectsNeedRepaint) {
+                    paintedViewBoundingRect = QRect(-1, -1, -1, -1); // Outside viewport.
                 }
-                if (!valid)
-                    paintedViewBoundingRect = QRect();
             }
         }
     }
 
-    // Process root items / children.
-    if (!item || item->d_ptr->dirtyChildren) {
-        QList<QGraphicsItem *> *children = item ? &item->d_ptr->children : &topLevelItems;
-        const bool allChildrenDirty = item && item->d_ptr->allChildrenDirty;
+    // Process children.
+    if (itemHasChildren && item->d_ptr->dirtyChildren) {
         if (!dirtyAncestorContainsChildren) {
-            dirtyAncestorContainsChildren = item && item->d_ptr->fullUpdatePending
+            dirtyAncestorContainsChildren = item->d_ptr->fullUpdatePending
                                             && (item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape);
         }
-        const bool parentIgnoresVisible = item && item->d_ptr->ignoreVisible;
-        const bool parentIgnoresOpacity = item && item->d_ptr->ignoreOpacity;
-        for (int i = 0; i < children->size(); ++i) {
-            QGraphicsItem *child = children->at(i);
+        const bool allChildrenDirty = item->d_ptr->allChildrenDirty;
+        const bool parentIgnoresVisible = item->d_ptr->ignoreVisible;
+        const bool parentIgnoresOpacity = item->d_ptr->ignoreOpacity;
+        for (int i = 0; i < item->d_ptr->children.size(); ++i) {
+            QGraphicsItem *child = item->d_ptr->children.at(i);
             if (wasDirtyParentSceneTransform)
                 child->d_ptr->dirtySceneTransform = 1;
             if (wasDirtyParentViewBoundingRects)
@@ -5578,36 +4678,19 @@ void QGraphicsScenePrivate::processDirtyItemsRecursive(QGraphicsItem *item, bool
                 child->d_ptr->ignoreVisible = 1;
             if (parentIgnoresOpacity)
                 child->d_ptr->ignoreOpacity = 1;
-
             if (allChildrenDirty) {
                 child->d_ptr->dirty = 1;
                 child->d_ptr->fullUpdatePending = 1;
                 child->d_ptr->dirtyChildren = 1;
                 child->d_ptr->allChildrenDirty = 1;
-            } else if (!child->d_ptr->dirty && !child->d_ptr->dirtyChildren) {
-                resetDirtyItem(child);
-                continue;
-            }
-
-            if (dirtyAncestorContainsChildren || updateAll) {
-                // No need to process this child's dirty rect, hence reset the dirty state.
-                // However, we have to continue the recursion because it might have a dirty
-                // view bounding rect that needs repaint. We also have to reset the dirty
-                // state of its descendants.
-                child->d_ptr->dirty = 0;
-                child->d_ptr->fullUpdatePending = 0;
-                if (updateAll)
-                    child->d_ptr->paintedViewBoundingRectsNeedRepaint = 0;
             }
-
             processDirtyItemsRecursive(child, dirtyAncestorContainsChildren, opacity);
         }
     } else if (wasDirtyParentSceneTransform) {
         item->d_ptr->invalidateChildrenSceneTransform();
     }
 
-    if (item)
-        resetDirtyItem(item);
+    resetDirtyItem(item);
 }
 
 /*!
@@ -5988,34 +5071,42 @@ void QGraphicsScene::setActiveWindow(QGraphicsWidget *widget)
     }
 }
 
-void QGraphicsScenePrivate::addView(QGraphicsView *view)
-{
-    views << view;
-    foreach(int gestureId, grabbedGestures)
-        view->d_func()->grabGesture(gestureId);
-}
+/*!
+    \since 4.6
 
-void QGraphicsScenePrivate::removeView(QGraphicsView *view)
+    Sends event \a event to item \a item through possible event filters.
+
+    The event is sent only if the item is enabled.
+
+    Returns \c false if the event was filtered or if the item is disabled.
+    Otherwise returns the value that was returned from the event handler.
+
+    \sa QGraphicsItem::sceneEvent(), QGraphicsItem::sceneEventFilter()
+*/
+bool QGraphicsScene::sendEvent(QGraphicsItem *item, QEvent *event)
 {
-    views.removeAll(view);
-    foreach(int gestureId, grabbedGestures)
-        view->releaseGesture(gestureId);
+    Q_D(QGraphicsScene);
+    if (!item) {
+        qWarning("QGraphicsScene::sendEvent: cannot send event to a null item");
+        return false;
+    }
+    if (item->scene() != this) {
+        qWarning("QGraphicsScene::sendEvent: item %p's scene (%p)"
+                 " is different from this scene (%p)",
+                 item, item->scene(), this);
+        return false;
+    }
+    return d->sendEvent(item, event);
 }
 
-void QGraphicsScenePrivate::grabGesture(QGraphicsItem *item, int gestureId)
+void QGraphicsScenePrivate::addView(QGraphicsView *view)
 {
-    if (!grabbedGestures.contains(gestureId)) {
-        foreach(QGraphicsView *view, views)
-            view->d_func()->grabGesture(gestureId);
-    }
-    (void)itemsWithGestures[item];
-    grabbedGestures << gestureId;
+    views << view;
 }
 
-void QGraphicsScenePrivate::releaseGesture(QGraphicsItem *item, int gestureId)
+void QGraphicsScenePrivate::removeView(QGraphicsView *view)
 {
-    itemsWithGestures.remove(item);
-    //###
+    views.removeAll(view);
 }
 
 void QGraphicsScenePrivate::updateTouchPointsForItem(QGraphicsItem *item, QTouchEvent *touchEvent)
@@ -6227,6 +5318,11 @@ void QGraphicsScenePrivate::enableTouchEventsOnViews()
         view->viewport()->setAttribute(Qt::WA_AcceptTouchEvents, true);
 }
 
+void QGraphicsScenePrivate::updateInputMethodSensitivityInViews()
+{
+    for (int i = 0; i < views.size(); ++i)
+        views.at(i)->d_func()->updateInputMethodSensitivity();
+}
 
 QT_END_NAMESPACE