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

1 files changed, 39 insertions, 2 deletions

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.
 */