5 files changed, 165 insertions, 5 deletions

diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp
index 3249bb1..c3934c7 100644
--- a/src/gui/graphicsview/qgraphicsitem.cpp
+++ b/src/gui/graphicsview/qgraphicsitem.cpp
@@ -1479,6 +1479,7 @@ QList<QGraphicsItem *> QGraphicsItem::children() const
 */
 QList<QGraphicsItem *> QGraphicsItem::childItems() const
 {
+    const_cast<QGraphicsItem *>(this)->d_ptr->ensureSortedChildren();
     return d_ptr->children;
 }
 
@@ -4048,6 +4049,82 @@ void QGraphicsItem::setZValue(qreal z)
 }
 
 /*!
+    \internal
+
+    Ensures that the list of children is sorted by insertion order, and that
+    the siblingIndexes are packed (no gaps), and start at 0.
+
+    ### This function is almost identical to
+    QGraphicsScenePrivate::ensureSequentialTopLevelSiblingIndexes().
+*/
+void QGraphicsItemPrivate::ensureSequentialSiblingIndex()
+{
+    if (!sequentialOrdering) {
+        qSort(children.begin(), children.end(), insertionOrder);
+        sequentialOrdering = 1;
+        needSortChildren = 1;
+    }
+    if (holesInSiblingIndex) {
+        holesInSiblingIndex = 0;
+        for (int i = 0; i < children.size(); ++i)
+            children[i]->d_ptr->siblingIndex = i;
+    }
+}
+
+/*!
+    \since 4.6
+
+    Stacks this item before \a sibling, which must be a sibling item (i.e., the
+    two items must share the same parent item, or must both be toplevel items).
+    The \a sibling must have the same Z value as this item, otherwise calling
+    this function will have no effect.
+
+    By default, all items are stacked by insertion order (i.e., the first item
+    you add is drawn before the next item you add). If two items' Z values are
+    different, then the item with the highest Z value is drawn on top. When the
+    Z values are the same, the insertion order will decide the stacking order.
+
+    \sa setZValue(), ItemStacksBehindParent
+*/
+void QGraphicsItem::stackBefore(const QGraphicsItem *sibling)
+{
+    if (sibling == this)
+        return;
+    if (!sibling || d_ptr->parent != sibling->parentItem()) {
+        qWarning("QGraphicsItem::stackUnder: cannot stack under %p, which must be a sibling", sibling);
+        return;
+    }
+    QList<QGraphicsItem *> *siblings = d_ptr->parent
+                                       ? &d_ptr->parent->d_ptr->children
+                                       : (d_ptr->scene ? &d_ptr->scene->d_func()->topLevelItems : 0);
+    if (!siblings) {
+        qWarning("QGraphicsItem::stackUnder: cannot stack under %p, which must be a sibling", sibling);
+        return;
+    }
+
+    // First, make sure that the sibling indexes have no holes. This also
+    // marks the children list for sorting.
+    if (d_ptr->parent)
+        d_ptr->parent->d_ptr->ensureSequentialSiblingIndex();
+    else
+        d_ptr->scene->d_func()->ensureSequentialTopLevelSiblingIndexes();
+
+    // Only move items with the same Z value, and that need moving.
+    int siblingIndex = sibling->d_ptr->siblingIndex;
+    int myIndex = d_ptr->siblingIndex;
+    if (myIndex >= siblingIndex && d_ptr->z == sibling->d_ptr->z) {
+        siblings->move(myIndex, siblingIndex);
+        // Fixup the insertion ordering.
+        for (int i = 0; i < siblings->size(); ++i) {
+            int &index = siblings->at(i)->d_ptr->siblingIndex;
+            if (i != siblingIndex && index >= siblingIndex && index <= myIndex)
+                ++index;
+        }
+        d_ptr->siblingIndex = siblingIndex;
+    }
+}
+
+/*!
     Returns the bounding rect of this item's descendants (i.e., its
     children, their children, etc.) in local coordinates. The
     rectangle will contain all descendants after they have been mapped
@@ -4753,20 +4830,36 @@ void QGraphicsItemPrivate::resolveDepth()
 
 /*!
     \internal
+
+    ### This function is almost identical to
+    QGraphicsScenePrivate::registerTopLevelItem().
 */
 void QGraphicsItemPrivate::addChild(QGraphicsItem *child)
 {
-    needSortChildren = 1;
+    // Remove all holes from the sibling index list. Now the max index
+    // number is equal to the size of the children list.
+    ensureSequentialSiblingIndex();
+    needSortChildren = 1; // ### maybe 0
     child->d_ptr->siblingIndex = children.size();
     children.append(child);
 }
 
 /*!
     \internal
+
+    ### This function is almost identical to
+    QGraphicsScenePrivate::unregisterTopLevelItem().
 */
 void QGraphicsItemPrivate::removeChild(QGraphicsItem *child)
 {
-    children.removeOne(child);
+    // When removing elements in the middle of the children list,
+    // there will be a "gap" in the list of sibling indexes (0,1,3,4).
+    if (!holesInSiblingIndex)
+        holesInSiblingIndex = child->d_ptr->siblingIndex != children.size() - 1;
+    if (sequentialOrdering && !holesInSiblingIndex)
+        children.removeAt(child->d_ptr->siblingIndex);
+    else
+        children.removeOne(child);
     // NB! Do not use children.removeAt(child->d_ptr->siblingIndex) because
     // the child is not guaranteed to be at the index after the list is sorted.
     // (see ensureSortedChildren()).
diff --git a/src/gui/graphicsview/qgraphicsitem.h b/src/gui/graphicsview/qgraphicsitem.h
index 089d6fe..99d2e12 100644
--- a/src/gui/graphicsview/qgraphicsitem.h
+++ b/src/gui/graphicsview/qgraphicsitem.h
@@ -302,6 +302,7 @@ public:
     // Stacking order
     qreal zValue() const;
     void setZValue(qreal z);
+    void stackBefore(const QGraphicsItem *sibling);
 
     // Hit test
     virtual QRectF boundingRect() const = 0;
diff --git a/src/gui/graphicsview/qgraphicsitem_p.h b/src/gui/graphicsview/qgraphicsitem_p.h
index fd2ff34..3feccdc 100644
--- a/src/gui/graphicsview/qgraphicsitem_p.h
+++ b/src/gui/graphicsview/qgraphicsitem_p.h
@@ -153,7 +153,7 @@ public:
         dirtyClipPath(1),
         emptyClipPath(0),
         inSetPosHelper(0),
-        needSortChildren(1),
+        needSortChildren(1), // ### can be 0 by default?
         allChildrenDirty(0),
         fullUpdatePending(0),
         flags(0),
@@ -174,6 +174,8 @@ public:
         mouseSetsFocus(1),
         explicitActivate(0),
         wantsActive(0),
+        holesInSiblingIndex(0),
+        sequentialOrdering(1),
         globalStackingOrder(-1),
         q_ptr(0)
     {
@@ -421,6 +423,8 @@ public:
 
     inline QTransform transformToParent() const;
     inline void ensureSortedChildren();
+    static inline bool insertionOrder(QGraphicsItem *a, QGraphicsItem *b);
+    void ensureSequentialSiblingIndex();
 
     QPainterPath cachedClipPath;
     QRectF childrenBoundingRect;
@@ -493,6 +497,8 @@ public:
     // New 32 bits
     quint32 explicitActivate : 1;
     quint32 wantsActive : 1;
+    quint32 holesInSiblingIndex : 1;
+    quint32 sequentialOrdering : 1;
 
     // Optional stacking order
     int globalStackingOrder;
@@ -646,14 +652,32 @@ inline QTransform QGraphicsItemPrivate::transformToParent() const
     return matrix;
 }
 
+/*!
+    \internal
+*/
 inline void QGraphicsItemPrivate::ensureSortedChildren()
 {
     if (needSortChildren) {
         qSort(children.begin(), children.end(), qt_notclosestLeaf);
         needSortChildren = 0;
+        sequentialOrdering = 1;
+        for (int i = 0; i < children.size(); ++i) {
+            if (children[i]->d_ptr->siblingIndex != i) {
+                sequentialOrdering = 0;
+                break;
+            }
+        }
     }
 }
 
+/*!
+    \internal
+*/
+inline bool QGraphicsItemPrivate::insertionOrder(QGraphicsItem *a, QGraphicsItem *b)
+{
+    return a->d_ptr->siblingIndex < b->d_ptr->siblingIndex;
+}
+
 QT_END_NAMESPACE
 
 #endif // QT_NO_GRAPHICSVIEW
diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp
index 0655ecc..4b74b67 100644
--- a/src/gui/graphicsview/qgraphicsscene.cpp
+++ b/src/gui/graphicsview/qgraphicsscene.cpp
@@ -283,6 +283,8 @@ QGraphicsScenePrivate::QGraphicsScenePrivate()
       processDirtyItemsEmitted(false),
       selectionChanging(0),
       needSortTopLevelItems(true),
+      holesInTopLevelSiblingIndex(false),
+      topLevelSequentialOrdering(true),
       stickyFocus(false),
       hasFocus(false),
       focusItem(0),
@@ -379,24 +381,36 @@ void QGraphicsScenePrivate::_q_emitUpdated()
 
 /*!
     \internal
+
+    ### This function is almost identical to QGraphicsItemPrivate::addChild().
 */
 void QGraphicsScenePrivate::registerTopLevelItem(QGraphicsItem *item)
 {
-    needSortTopLevelItems = true;
+    item->d_ptr->ensureSequentialSiblingIndex();
+    needSortTopLevelItems = true; // ### maybe false
     item->d_ptr->siblingIndex = topLevelItems.size();
     topLevelItems.append(item);
 }
 
 /*!
     \internal
+
+    ### This function is almost identical to QGraphicsItemPrivate::removeChild().
 */
 void QGraphicsScenePrivate::unregisterTopLevelItem(QGraphicsItem *item)
 {
-    topLevelItems.removeOne(item);
+    if (!holesInTopLevelSiblingIndex)
+        holesInTopLevelSiblingIndex = item->d_ptr->siblingIndex != topLevelItems.size() - 1;
+    if (topLevelSequentialOrdering && !holesInTopLevelSiblingIndex)
+        topLevelItems.removeAt(item->d_ptr->siblingIndex);
+    else
+        topLevelItems.removeOne(item);
     // 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;
+    if (topLevelSequentialOrdering)
+        topLevelSequentialOrdering = !holesInTopLevelSiblingIndex;
 }
 
 /*!
@@ -1239,6 +1253,29 @@ void QGraphicsScenePrivate::mousePressEventHandler(QGraphicsSceneMouseEvent *mou
 /*!
     \internal
 
+    Ensures that the list of toplevels is sorted by insertion order, and that
+    the siblingIndexes are packed (no gaps), and start at 0.
+
+    ### This function is almost identical to
+    QGraphicsItemPrivate::ensureSequentialSiblingIndex().
+*/
+void QGraphicsScenePrivate::ensureSequentialTopLevelSiblingIndexes()
+{
+    if (!topLevelSequentialOrdering) {
+        qSort(topLevelItems.begin(), topLevelItems.end(), QGraphicsItemPrivate::insertionOrder);
+        topLevelSequentialOrdering = true;
+        needSortTopLevelItems = 1;
+    }
+    if (holesInTopLevelSiblingIndex) {
+        holesInTopLevelSiblingIndex = 0;
+        for (int i = 0; i < topLevelItems.size(); ++i)
+            topLevelItems[i]->d_ptr->siblingIndex = i;
+    }
+}
+
+/*!
+    \internal
+
     Set the font and propagate the changes if the font is different from the
     current font.
 */
diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h
index 3b03624..46917ce 100644
--- a/src/gui/graphicsview/qgraphicsscene_p.h
+++ b/src/gui/graphicsview/qgraphicsscene_p.h
@@ -111,6 +111,9 @@ public:
     QList<QGraphicsItem *> unpolishedItems;
     QList<QGraphicsItem *> topLevelItems;
     bool needSortTopLevelItems;
+    bool holesInTopLevelSiblingIndex;
+    bool topLevelSequentialOrdering;
+
     QMap<QGraphicsItem *, QPointF> movingItemsInitialPositions;
     void registerTopLevelItem(QGraphicsItem *item);
     void unregisterTopLevelItem(QGraphicsItem *item);
@@ -255,6 +258,8 @@ public:
         }
     }
 
+    void ensureSequentialTopLevelSiblingIndexes();
+
     QStyle *style;
     QFont font;
     void setFont_helper(const QFont &font);