From 45bf804ce2feec74bd7787a64d72184da9458254 Mon Sep 17 00:00:00 2001 From: Andreas Aardal Hanssen Date: Thu, 24 Sep 2009 16:25:14 +0200 Subject: 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 --- src/gui/graphicsview/qgraphicsitem.cpp | 97 +++++++++++++++++++++++++- src/gui/graphicsview/qgraphicsitem.h | 1 + src/gui/graphicsview/qgraphicsitem_p.h | 26 ++++++- src/gui/graphicsview/qgraphicsscene.cpp | 41 ++++++++++- src/gui/graphicsview/qgraphicsscene_p.h | 5 ++ tests/auto/qgraphicsitem/tst_qgraphicsitem.cpp | 79 +++++++++++++++++++++ 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::children() const */ QList QGraphicsItem::childItems() const { + const_cast(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 *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 unpolishedItems; QList topLevelItems; bool needSortTopLevelItems; + bool holesInTopLevelSiblingIndex; + bool topLevelSequentialOrdering; + QMap 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() << 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() << child1 << child3 << child4 << child2)); + + // Move child2 before child1 + child2->stackBefore(child1); + QCOMPARE(parent.childItems(), (QList() << child2 << child1 << child3 << child4)); + child2->stackBefore(child2); + QCOMPARE(parent.childItems(), (QList() << child2 << child1 << child3 << child4)); + child1->setZValue(1); + QCOMPARE(parent.childItems(), (QList() << child2 << child3 << child4 << child1)); + child1->stackBefore(child2); // no effect + QCOMPARE(parent.childItems(), (QList() << child2 << child3 << child4 << child1)); + child1->setZValue(0); + QCOMPARE(parent.childItems(), (QList() << child2 << child1 << child3 << child4)); + child4->stackBefore(child1); + QCOMPARE(parent.childItems(), (QList() << child2 << child4 << child1 << child3)); + child4->setZValue(1); + QCOMPARE(parent.childItems(), (QList() << child2 << child1 << child3 << child4)); + child3->stackBefore(child1); + QCOMPARE(parent.childItems(), (QList() << child2 << child3 << child1 << child4)); + child4->setZValue(0); + QCOMPARE(parent.childItems(), (QList() << 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() << child1 << child2 << child3 << child4)); + + // Remove and append + scene.removeItem(child2); + scene.addItem(child2); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child1 << child3 << child4 << child2)); + + // Move child2 before child1 + child2->stackBefore(child1); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child1 << child3 << child4)); + child2->stackBefore(child2); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child1 << child3 << child4)); + child1->setZValue(1); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child3 << child4 << child1)); + child1->stackBefore(child2); // no effect + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child3 << child4 << child1)); + child1->setZValue(0); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child1 << child3 << child4)); + child4->stackBefore(child1); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child4 << child1 << child3)); + child4->setZValue(1); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child1 << child3 << child4)); + child3->stackBefore(child1); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child3 << child1 << child4)); + child4->setZValue(0); + QCOMPARE(scene.items(QPointF(2, 2), Qt::IntersectsItemBoundingRect, Qt::AscendingOrder), (QList() << child2 << child4 << child3 << child1)); +} + QTEST_MAIN(tst_QGraphicsItem) #include "tst_qgraphicsitem.moc" -- cgit v0.12