Add QGraphicsItem::stackBefore(), and fix Z ordering bugs.

When we changed the sibling stacking order to be defined (4.5) instead of
undefined (4.2, 4.3, 4.4), the need to control this stacking order
arose. Before we could just say the order was random, but stable,
and the only way people could rely on order was to set Z. Now, when the
default order is defined as "insertion order", people start relying on
this order, and incidentally they want more control.

In QML, the need to have insertion order semantics is very evident as
the order you define the elements in QML more strongly implies a
graphical stacking order than the imperative order they get when added
in C++.

This change adds QGraphicsItem::stackBefore(const QGraphicsItem *), which
works similarily to QWidget::stackUnder(). It moves the item in front of
the sibling item passed as an argument.

While implementing this function, and writing tests for how this
function behaves in combination with Z values, I found that the code
we had for updating siblingIndex was broken in the case where you remove
an item from the middle of the children list. In this case newly added
items would be assigned the same sibling index order as one that's already
in the list.

So in order to get the tests to pass I had to fix this bug as well.. The
approach is to sort the children list by insertion order, so that we can
fix up the sibling indexes.

Performancewise this has little implications. If there are gaps in
the sibling index list, which only occurs if you remove an item from the
middle of the children list, will the sibling index list be adjusted /
corrected before used (for example, by stackBehind()). Multiple calls to
stackBehind will be fast, and the list is flagged for resorting (including
Z order).

Reviewed-by: jasplin

6 files changed, 244 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);
diff --git a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
index b0e4b9d..956faa1 100644
--- a/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
+++ b/tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp
@@ -296,6 +296,7 @@ private slots:
     void moveWhileDeleting();
     void ensureDirtySceneTransform();
     void focusScope();
+    void stackBefore();
 
     // task specific tests below me
     void task141694_textItemEnsureVisible();
@@ -8384,5 +8385,83 @@ void tst_QGraphicsItem::focusScope()
     QCOMPARE(scopeB->focusItem(), (QGraphicsItem *)scopeB);
 }
 
+void tst_QGraphicsItem::stackBefore()
+{
+    QGraphicsRectItem parent;
+    QGraphicsRectItem *child1 = new QGraphicsRectItem(QRectF(0, 0, 5, 5), &parent);
+    QGraphicsRectItem *child2 = new QGraphicsRectItem(QRectF(0, 0, 5, 5), &parent);
+    QGraphicsRectItem *child3 = new QGraphicsRectItem(QRectF(0, 0, 5, 5), &parent);
+    QGraphicsRectItem *child4 = new QGraphicsRectItem(QRectF(0, 0, 5, 5), &parent);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child1 << child2 << child3 << child4));
+    child1->setData(0, "child1");
+    child2->setData(0, "child2");
+    child3->setData(0, "child3");
+    child4->setData(0, "child4");
+
+    // Remove and append
+    child2->setParentItem(0);
+    child2->setParentItem(&parent);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child1 << child3 << child4 << child2));
+
+    // Move child2 before child1
+    child2->stackBefore(child1);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child1 << child3 << child4));
+    child2->stackBefore(child2);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child1 << child3 << child4));
+    child1->setZValue(1);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child3 << child4 << child1));
+    child1->stackBefore(child2); // no effect
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child3 << child4 << child1));
+    child1->setZValue(0);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child1 << child3 << child4));
+    child4->stackBefore(child1);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child4 << child1 << child3));
+    child4->setZValue(1);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child1 << child3 << child4));
+    child3->stackBefore(child1);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child3 << child1 << child4));
+    child4->setZValue(0);
+    QCOMPARE(parent.childItems(), (QList<QGraphicsItem *>() << child2 << child4 << child3 << child1));
+
+    // Make them all toplevels
+    child1->setParentItem(0);
+    child2->setParentItem(0);
+    child3->setParentItem(0);
+    child4->setParentItem(0);
+
+    QGraphicsScene scene;
+    scene.addItem(child1);
+    scene.addItem(child2);
+    scene.addItem(child3);
+    scene.addItem(child4);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder),
+             (QList<QGraphicsItem *>() << child1 << child2 << child3 << child4));
+
+    // Remove and append
+    scene.removeItem(child2);
+    scene.addItem(child2);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child1 << child3 << child4 << child2));
+
+    // Move child2 before child1
+    child2->stackBefore(child1);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child1 << child3 << child4));
+    child2->stackBefore(child2);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child1 << child3 << child4));
+    child1->setZValue(1);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child3 << child4 << child1));
+    child1->stackBefore(child2); // no effect
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child3 << child4 << child1));
+    child1->setZValue(0);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child1 << child3 << child4));
+    child4->stackBefore(child1);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child4 << child1 << child3));
+    child4->setZValue(1);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child1 << child3 << child4));
+    child3->stackBefore(child1);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child3 << child1 << child4));
+    child4->setZValue(0);
+    QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList<QGraphicsItem *>() << child2 << child4 << child3 << child1));
+}
+
 QTEST_MAIN(tst_QGraphicsItem)
 #include "tst_qgraphicsitem.moc"