From 8a0e002ccc762ef3edbc3c9ad91b4d6017cb91bb Mon Sep 17 00:00:00 2001 From: Alexis Menard Date: Wed, 17 Jun 2009 14:15:14 +0200 Subject: Make eveything internal for now but ready to see the light. --- src/gui/graphicsview/graphicsview.pri | 6 +- src/gui/graphicsview/qgraphicsitem.cpp | 2 +- src/gui/graphicsview/qgraphicsscene.cpp | 7 +- src/gui/graphicsview/qgraphicsscene_p.h | 1 - .../graphicsview/qgraphicsscenebsptreeindex.cpp | 761 +++++++++++++++++++++ src/gui/graphicsview/qgraphicsscenebsptreeindex.h | 119 ++++ .../graphicsview/qgraphicsscenebsptreeindex_p.cpp | 760 -------------------- .../graphicsview/qgraphicsscenebsptreeindex_p.h | 137 ++-- .../graphicsview/qgraphicsscenebsptreeindex_p_p.h | 150 ---- src/gui/graphicsview/qgraphicssceneindex.cpp | 2 +- src/gui/graphicsview/qgraphicssceneindex.h | 13 +- src/gui/graphicsview/qgraphicsscenelinearindex.cpp | 3 +- src/gui/graphicsview/qgraphicsscenelinearindex.h | 124 ++++ src/gui/graphicsview/qgraphicsscenelinearindex_p.h | 118 ---- 14 files changed, 1122 insertions(+), 1081 deletions(-) create mode 100644 src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp create mode 100644 src/gui/graphicsview/qgraphicsscenebsptreeindex.h delete mode 100644 src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp delete mode 100644 src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h create mode 100644 src/gui/graphicsview/qgraphicsscenelinearindex.h delete mode 100644 src/gui/graphicsview/qgraphicsscenelinearindex_p.h diff --git a/src/gui/graphicsview/graphicsview.pri b/src/gui/graphicsview/graphicsview.pri index a4d142a..5ac1c54 100644 --- a/src/gui/graphicsview/graphicsview.pri +++ b/src/gui/graphicsview/graphicsview.pri @@ -5,11 +5,11 @@ HEADERS += graphicsview/qgraphicsitem.h \ graphicsview/qgraphicsscene.h \ graphicsview/qgraphicsscene_p.h \ graphicsview/qgraphicsscene_bsp_p.h \ - graphicsview/qgraphicsscenelinearindex_p.h \ + graphicsview/qgraphicsscenelinearindex.h \ graphicsview/qgraphicssceneindex.h \ graphicsview/qgraphicssceneindex_p.h \ + graphicsview/qgraphicsscenebsptreeindex.h \ graphicsview/qgraphicsscenebsptreeindex_p.h \ - graphicsview/qgraphicsscenebsptreeindex_p_p.h \ graphicsview/qgraphicssceneevent.h \ graphicsview/qgraphicsview_p.h \ graphicsview/qgraphicsview.h @@ -17,7 +17,7 @@ SOURCES += graphicsview/qgraphicsitem.cpp \ graphicsview/qgraphicsitemanimation.cpp \ graphicsview/qgraphicsscene.cpp \ graphicsview/qgraphicsscene_bsp.cpp \ - graphicsview/qgraphicsscenebsptreeindex_p.cpp \ + graphicsview/qgraphicsscenebsptreeindex.cpp \ graphicsview/qgraphicsscenelinearindex.cpp \ graphicsview/qgraphicssceneindex.cpp \ graphicsview/qgraphicssceneevent.cpp \ diff --git a/src/gui/graphicsview/qgraphicsitem.cpp b/src/gui/graphicsview/qgraphicsitem.cpp index 39ad447..593d7be 100644 --- a/src/gui/graphicsview/qgraphicsitem.cpp +++ b/src/gui/graphicsview/qgraphicsitem.cpp @@ -554,7 +554,7 @@ #include "qgraphicsview.h" #include "qgraphicswidget.h" #include "qgraphicsproxywidget.h" -#include "qgraphicsscenebsptreeindex_p_p.h" +#include "qgraphicsscenebsptreeindex_p.h" #include #include #include diff --git a/src/gui/graphicsview/qgraphicsscene.cpp b/src/gui/graphicsview/qgraphicsscene.cpp index 5a3028c..a33cb3e 100644 --- a/src/gui/graphicsview/qgraphicsscene.cpp +++ b/src/gui/graphicsview/qgraphicsscene.cpp @@ -220,7 +220,8 @@ #include "qgraphicswidget.h" #include "qgraphicswidget_p.h" #include "qgraphicssceneindex.h" -#include "qgraphicsscenebsptreeindex_p_p.h" +#include "qgraphicsscenebsptreeindex.h" +#include "qgraphicsscenelinearindex.h" #include #include @@ -1574,6 +1575,8 @@ void QGraphicsScene::setItemIndexMethod(ItemIndexMethod method) } /*! + \internal + \brief the item indexing method. This method allow to apply an indexing algorithm \a index to the scene, to speed up item discovery functions like items() and itemAt(). @@ -1595,6 +1598,8 @@ void QGraphicsScene::setSceneIndex(QGraphicsSceneIndex *index) } /*! + \internal + This method return the current indexing algorithm of the scene. \sa setSceneIndex(), QGraphicsSceneIndex diff --git a/src/gui/graphicsview/qgraphicsscene_p.h b/src/gui/graphicsview/qgraphicsscene_p.h index 72ae158..563e016 100644 --- a/src/gui/graphicsview/qgraphicsscene_p.h +++ b/src/gui/graphicsview/qgraphicsscene_p.h @@ -58,7 +58,6 @@ #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW #include "qgraphicsscenebsptreeindex_p.h" -#include "qgraphicsscenelinearindex_p.h" #include "qgraphicssceneindex.h" #include "qgraphicsview.h" #include "qgraphicsitem_p.h" diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp new file mode 100644 index 0000000..76fd218 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex.cpp @@ -0,0 +1,761 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +/*! + \class QGraphicsSceneBspTreeIndex + \brief The QGraphicsSceneBspTreeIndex class provides an implementation of + a BSP indexing algorithm for discovering items in QGraphicsScene. + \since 4.6 + \ingroup multimedia + \ingroup graphicsview-api + \mainclass + \internal + + QGraphicsSceneBspTreeIndex index use a BSP(Binary Space Partitioning) + implementation to discover items quickly. This implementation is + very efficient for static scene. It has a depth that you can set. + The depth directly affects performance and memory usage; the latter + growing exponentially with the depth of the tree. With an optimal tree + depth, the index can instantly determine the locality of items, even + for scenes with thousands or millions of items. This also greatly improves + rendering performance. + + By default, the value is 0, in which case Qt will guess a reasonable + default depth based on the size, location and number of items in the + scene. If these parameters change frequently, however, you may experience + slowdowns as the index retunes the depth internally. You can avoid + potential slowdowns by fixating the tree depth through setting this + property. + + The depth of the tree and the size of the scene rectangle decide the + granularity of the scene's partitioning. The size of each scene segment is + determined by the following algorithm: + + The BSP tree has an optimal size when each segment contains between 0 and + 10 items. + + \sa QGraphicsScene, QGraphicsView, QGraphicsSceneIndex +*/ + +#include "qgraphicsscenebsptreeindex.h" + +#ifndef QT_NO_GRAPHICSVIEW + +#include "qgraphicsscenebsptreeindex_p.h" +#include "qgraphicssceneindex_p.h" +#include "qgraphicsitem_p.h" +#include "qgraphicsscene_p.h" + +#include + +#include + +QT_BEGIN_NAMESPACE + +static inline int intmaxlog(int n) +{ + return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0); +} + +/*! + Constructs a private scene bsp index. +*/ +QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene) + : QGraphicsSceneIndexPrivate(scene), + bspTreeDepth(0), + indexTimerId(0), + restartIndexTimer(false), + regenerateIndex(true), + lastItemCount(0), + purgePending(false), + sortCacheEnabled(false), + updatingSortCache(false) +{ +} + + +/*! + This method will update the BSP index by removing the items from the temporary + unindexed list and add them in the indexedItems list. This will also + update the growingItemsBoundingRect if needed. This will update the BSP + implementation as well. + + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex() +{ + Q_Q(QGraphicsSceneBspTreeIndex); + if (!indexTimerId) + return; + + QGraphicsScenePrivate * scenePrivate = q->scene()->d_func(); + 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 = scenePrivate->growingItemsBoundingRect; + scenePrivate->growingItemsBoundingRect |= unindexedItemsBoundingRect; + + // Determine whether we should regenerate the BSP tree. + if (bspTreeDepth == 0) { + int oldDepth = intmaxlog(lastItemCount); + bspTreeDepth = intmaxlog(indexedItems.size()); + static const int slack = 100; + if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - indexedItems.size()) > slack)) { + // ### Crude algorithm. + regenerateIndex = true; + } + } + + // Regenerate the tree. + if (regenerateIndex) { + regenerateIndex = false; + bsp.initialize(q->scene()->sceneRect(), bspTreeDepth); + unindexedItems = indexedItems; + lastItemCount = indexedItems.size(); + q->scene()->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. + scenePrivate->largestUntransformableItem = QRectF(); + } + + // 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; + + bsp.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. + scenePrivate->largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect(); + } + } + } + unindexedItems.clear(); + + // Notify scene rect changes. + if (!scenePrivate->hasSceneRect && scenePrivate->growingItemsBoundingRect != oldGrowingItemsBoundingRect) + emit q->scene()->sceneRectChanged(scenePrivate->growingItemsBoundingRect); +} + + +/*! + \internal + + Removes stale pointers from all data structures. +*/ +void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems() +{ + if (!purgePending && removedItems.isEmpty()) + return; + + // Remove stale items from the BSP tree. + bsp.removeItems(removedItems); + // Purge this list. + removedItems.clear(); + freeItemIndexes.clear(); + for (int i = 0; i < indexedItems.size(); ++i) { + if (!indexedItems.at(i)) + freeItemIndexes << i; + } + purgePending = false; +} + +/*! + \internal + + Starts or restarts the timer used for reindexing unindexed items. +*/ +void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer(int interval) +{ + Q_Q(QGraphicsSceneBspTreeIndex); + if (indexTimerId) { + restartIndexTimer = true; + } else { + indexTimerId = q->startTimer(interval); + } +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::resetIndex() +{ + purgeRemovedItems(); + 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(); +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder) +{ + if (!item->d_ptr->children.isEmpty()) { + QList 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)++; + } +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache() +{ + Q_Q(QGraphicsSceneBspTreeIndex); + _q_updateIndex(); + + if (!sortCacheEnabled || !updatingSortCache) + return; + + updatingSortCache = false; + int stackingOrder = 0; + + QList topLevels; + + for (int i = 0; i < q->items().count(); ++i) { + QGraphicsItem *item = q->items().at(i); + if (item && 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); +} + +/*! + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache() +{ + Q_Q(QGraphicsSceneBspTreeIndex); + if (!sortCacheEnabled || updatingSortCache) + return; + + updatingSortCache = true; + QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection); +} + +/*! + Returns true if \a item1 is on top of \a item2. + + \internal +*/ +bool QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2) +{ + // Siblings? Just check their z-values. + const QGraphicsItemPrivate *d1 = item1->d_ptr; + const QGraphicsItemPrivate *d2 = item2->d_ptr; + 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 QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2) +{ + return closestItemFirst_withoutCache(item2, item1); +} + +/*! + Sort a list of \a itemList in a specific \a order and use the cache if requested. + + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList *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); + } + } +} + +/*! + Constructs a BSP scene index for the given \a scene. +*/ +QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene) + : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene) +{ + +} + +/*! + \reimp + Return the rect indexed by the BSP index. +*/ +QRectF QGraphicsSceneBspTreeIndex::indexedRect() const +{ + Q_D(const QGraphicsSceneBspTreeIndex); + const_cast(d)->_q_updateIndex(); + return scene()->d_func()->hasSceneRect ? scene()->d_func()->sceneRect : scene()->d_func()->growingItemsBoundingRect; +} + +/*! + \reimp + Clear the all the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::clear() +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->bsp.clear(); + d->lastItemCount = 0; + d->freeItemIndexes.clear(); + d->indexedItems.clear(); + d->unindexedItems.clear(); +} + +/*! + Add the \a item into the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + // 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. + // Update the scene's sort cache settings. + item->d_ptr->globalStackingOrder = -1; + d->invalidateSortCache(); + + // 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); +} + +/*! + This really add the item in the BSP. + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::addToIndex(QGraphicsItem *item) +{ + if (item->d_func()->index != -1) { + bsp.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(); + } +} + +/*! + Remove the \a item from the BSP index. +*/ +void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + // Note: This will access item's sceneBoundingRect(), which (as this is + // C++) is why we cannot call removeItem() from QGraphicsItem's + // destructor. + d->removeFromIndex(item); + + // Invalidate any sort caching; arrival of a new item means we need to + // resort. + d->invalidateSortCache(); + + // Remove from our item lists. + int index = item->d_func()->index; + if (index != -1) { + d->freeItemIndexes << index; + d->indexedItems[index] = 0; + } else { + d->unindexedItems.removeAll(item); + } +} + +/*! + \reimp + Delete the \a item from the BSP index (without accessing its boundingRect). +*/ +void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + // Invalidate any sort caching; arrival of a new item means we need to + // resort. + d->invalidateSortCache(); + + int index = item->d_func()->index; + if (index != -1) { + // Important: The index is useless until purgeRemovedItems() is + // called. + d->indexedItems[index] = (QGraphicsItem *)0; + if (!d->purgePending) { + d->purgePending = true; + scene()->update(); + } + d->removedItems << item; + } else { + // Recently added items are purged immediately. unindexedItems() never + // contains stale items. + d->unindexedItems.removeAll(item); + scene()->update(); + } +} + +/*! + Really remove the item from the BSP + \internal +*/ +void QGraphicsSceneBspTreeIndexPrivate::removeFromIndex(QGraphicsItem *item) +{ + if (item->d_func()->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) { + // ### remove from child index only if applicable + return; + } + int index = item->d_func()->index; + if (index != -1) { + bsp.removeItem(item, item->sceneBoundingRect()); + freeItemIndexes << index; + indexedItems[index] = 0; + item->d_func()->index = -1; + unindexedItems << item; + + //prepareGeometryChange will call prepareBoundingRectChange + foreach (QGraphicsItem *child, item->children()) + child->prepareGeometryChange(); + } + startIndexTimer(); +} + +/*! + \reimp + Update the BSP when the \a item 's bounding rect has changed. +*/ +void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item) +{ + Q_D(QGraphicsSceneBspTreeIndex); + // Note: This will access item's sceneBoundingRect(), which (as this is + // C++) is why we cannot call removeItem() from QGraphicsItem's + // destructor. + d->removeFromIndex(const_cast(item)); +} + +/*! + Returns an estimation visible items that are either inside or + intersect with the specified \a rect and return a list sorted using \a order. + + \a deviceTransform is the transformation apply to the view. + +*/ +QList QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const +{ + Q_D(const QGraphicsSceneBspTreeIndex); + const_cast(d)->purgeRemovedItems(); + const_cast(d)->_q_updateSortCache(); + + QList rectItems = d->bsp.items(rect); + // Fill in with any unindexed items + for (int i = 0; i < d->unindexedItems.size(); ++i) { + if (QGraphicsItem *item = d->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; + rectItems << item; + } + } + } + } + + // Reset the discovered state of all discovered items + for (int i = 0; i < rectItems.size(); ++i) + rectItems.at(i)->d_func()->itemDiscovered = 0; + + d->sortItems(&rectItems, order, d->sortCacheEnabled); + + return rectItems; +} + + +/*! + \fn QList QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order = Qt::AscendingOrder) const; + + Return all items in the BSP index and sort them using \a order. +*/ +QList QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) const +{ + Q_D(const QGraphicsSceneBspTreeIndex); + const_cast(d)->purgeRemovedItems(); + QList itemList; + // If freeItemIndexes is empty, we know there are no holes in indexedItems and + // unindexedItems. + if (d->freeItemIndexes.isEmpty()) { + if (d->unindexedItems.isEmpty()) { + itemList = d->indexedItems; + } else { + itemList = d->indexedItems + d->unindexedItems; + } + } else { + // Rebuild the list of items to avoid holes. ### We could also just + // compress the item lists at this point. + foreach (QGraphicsItem *item, d->indexedItems + d->unindexedItems) { + if (item) + itemList << item; + } + } + if (order != -1) { + //We sort descending order + d->sortItems(&itemList, order, d->sortCacheEnabled); + } + return itemList; +} + +/*! + \property QGraphicsSceneBspTreeIndex::bspTreeDepth + \brief the depth of the BSP index tree + \since 4.6 + + This value determines the depth of BSP tree. The depth + directly affects performance and memory usage; the latter + growing exponentially with the depth of the tree. With an optimal tree + depth, the index can instantly determine the locality of items, even + for scenes with thousands or millions of items. This also greatly improves + rendering performance. + + By default, the value is 0, in which case Qt will guess a reasonable + default depth based on the size, location and number of items in the + scene. If these parameters change frequently, however, you may experience + slowdowns as the index retunes the depth internally. You can avoid + potential slowdowns by fixating the tree depth through setting this + property. + + The depth of the tree and the size of the scene rectangle decide the + granularity of the scene's partitioning. The size of each scene segment is + determined by the following algorithm: + + The BSP tree has an optimal size when each segment contains between 0 and + 10 items. + +*/ +int QGraphicsSceneBspTreeIndex::bspTreeDepth() +{ + Q_D(const QGraphicsSceneBspTreeIndex); + return d->bspTreeDepth; +} + +void QGraphicsSceneBspTreeIndex::setBspTreeDepth(int depth) +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->bspTreeDepth = depth; + d->resetIndex(); +} + +/*! + \reimp + + This method react to the \a rect change of the scene and + reset the BSP tree index. +*/ +void QGraphicsSceneBspTreeIndex::sceneRectChanged(const QRectF &rect) +{ + Q_D(QGraphicsSceneBspTreeIndex); + d->sceneRect = rect; + d->resetIndex(); +} + +/*! + \reimp + + This method react to the \a change of the \a item and use the \a value to + update the BSP tree if necessary. + +*/ +void QGraphicsSceneBspTreeIndex::itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value) +{ + Q_D(QGraphicsSceneBspTreeIndex); + switch (change) { + case QGraphicsItem::ItemZValueChange: + case QGraphicsItem::ItemParentChange: { + d->invalidateSortCache(); + break; + } + default: + break; + } + return QGraphicsSceneIndex::itemChanged(item, change, value); +} +/*! + \reimp + + Used to catch the timer event. + + \internal +*/ +bool QGraphicsSceneBspTreeIndex::event(QEvent *event) +{ + Q_D(QGraphicsSceneBspTreeIndex); + switch (event->type()) { + case QEvent::Timer: + if (d->indexTimerId && static_cast(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; +} + +QT_END_NAMESPACE + +#include "moc_qgraphicsscenebsptreeindex.cpp" + +#endif // QT_NO_GRAPHICSVIEW + diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex.h new file mode 100644 index 0000000..0444a30 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex.h @@ -0,0 +1,119 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of qapplication_*.cpp, qwidget*.cpp and qfiledialog.cpp. This header +// file may change from version to version without notice, or even be removed. +// +// We mean it. +// + +#ifndef QGRAPHICSBSPTREEINDEX_H +#define QGRAPHICSBSPTREEINDEX_H + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Gui) + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include +#include +#include +#include +#include + +#include "qgraphicsscene_bsp_p.h" + +class QGraphicsSceneBspTreeIndexPrivate; + +class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex +{ + Q_OBJECT + Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth) +public: + QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0); + QRectF indexedRect() const; + + QList estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const; + + QList items(Qt::SortOrder order = Qt::AscendingOrder) const; + + int bspTreeDepth(); + void setBspTreeDepth(int depth); + +protected: + bool event(QEvent *event); + void clear(); + + void addItem(QGraphicsItem *item); + void removeItem(QGraphicsItem *item); + void deleteItem(QGraphicsItem *item); + void prepareBoundingRectChange(const QGraphicsItem *item); + + void sceneRectChanged(const QRectF &rect); + void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value); + +private : + Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex) + Q_DISABLE_COPY(QGraphicsSceneBspTreeIndex) + Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache()) + Q_PRIVATE_SLOT(d_func(), void _q_updateIndex()) + + friend class QGraphicsScene; + friend class QGraphicsScenePrivate; +}; + +#endif // QT_NO_GRAPHICSVIEW + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QGRAPHICSBSPTREEINDEX_H diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp deleted file mode 100644 index b19248a..0000000 --- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.cpp +++ /dev/null @@ -1,760 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). -** Contact: Qt Software Information (qt-info@nokia.com) -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** No Commercial Usage -** This file contains pre-release code and may not be distributed. -** You may use this file in accordance with the terms and conditions -** contained in the either Technology Preview License Agreement or the -** Beta Release License Agreement. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 2.1 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 2.1 requirements -** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -** -** In addition, as a special exception, Nokia gives you certain -** additional rights. These rights are described in the Nokia Qt LGPL -** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this -** package. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 3.0 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU General Public License version 3.0 requirements will be -** met: http://www.gnu.org/copyleft/gpl.html. -** -** If you are unsure which license is appropriate for your use, please -** contact the sales department at qt-sales@nokia.com. -** $QT_END_LICENSE$ -** -****************************************************************************/ - -/*! - \class QGraphicsSceneBspTreeIndex - \brief The QGraphicsSceneBspTreeIndex class provides an implementation of - a BSP indexing algorithm for discovering items in QGraphicsScene. - \since 4.6 - \ingroup multimedia - \ingroup graphicsview-api - \mainclass - - QGraphicsSceneBspTreeIndex index use a BSP(Binary Space Partitioning) - implementation to discover items quickly. This implementation is - very efficient for static scene. It has a depth that you can set. - The depth directly affects performance and memory usage; the latter - growing exponentially with the depth of the tree. With an optimal tree - depth, the index can instantly determine the locality of items, even - for scenes with thousands or millions of items. This also greatly improves - rendering performance. - - By default, the value is 0, in which case Qt will guess a reasonable - default depth based on the size, location and number of items in the - scene. If these parameters change frequently, however, you may experience - slowdowns as the index retunes the depth internally. You can avoid - potential slowdowns by fixating the tree depth through setting this - property. - - The depth of the tree and the size of the scene rectangle decide the - granularity of the scene's partitioning. The size of each scene segment is - determined by the following algorithm: - - The BSP tree has an optimal size when each segment contains between 0 and - 10 items. - - \sa QGraphicsScene, QGraphicsView, QGraphicsSceneIndex -*/ - -#include "qgraphicsscenebsptreeindex_p.h" - -#ifndef QT_NO_GRAPHICSVIEW - -#include "qgraphicsscenebsptreeindex_p_p.h" -#include "qgraphicssceneindex_p.h" -#include "qgraphicsitem_p.h" -#include "qgraphicsscene_p.h" - -#include - -#include - -QT_BEGIN_NAMESPACE - -static inline int intmaxlog(int n) -{ - return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0); -} - -/*! - Constructs a private scene bsp index. -*/ -QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene) - : QGraphicsSceneIndexPrivate(scene), - bspTreeDepth(0), - indexTimerId(0), - restartIndexTimer(false), - regenerateIndex(true), - lastItemCount(0), - purgePending(false), - sortCacheEnabled(false), - updatingSortCache(false) -{ -} - - -/*! - This method will update the BSP index by removing the items from the temporary - unindexed list and add them in the indexedItems list. This will also - update the growingItemsBoundingRect if needed. This will update the BSP - implementation as well. - - \internal -*/ -void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex() -{ - Q_Q(QGraphicsSceneBspTreeIndex); - if (!indexTimerId) - return; - - QGraphicsScenePrivate * scenePrivate = q->scene()->d_func(); - 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 = scenePrivate->growingItemsBoundingRect; - scenePrivate->growingItemsBoundingRect |= unindexedItemsBoundingRect; - - // Determine whether we should regenerate the BSP tree. - if (bspTreeDepth == 0) { - int oldDepth = intmaxlog(lastItemCount); - bspTreeDepth = intmaxlog(indexedItems.size()); - static const int slack = 100; - if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - indexedItems.size()) > slack)) { - // ### Crude algorithm. - regenerateIndex = true; - } - } - - // Regenerate the tree. - if (regenerateIndex) { - regenerateIndex = false; - bsp.initialize(q->scene()->sceneRect(), bspTreeDepth); - unindexedItems = indexedItems; - lastItemCount = indexedItems.size(); - q->scene()->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. - scenePrivate->largestUntransformableItem = QRectF(); - } - - // 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; - - bsp.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. - scenePrivate->largestUntransformableItem |= item->mapToItem(topmostUntransformable, item->boundingRect()).boundingRect(); - } - } - } - unindexedItems.clear(); - - // Notify scene rect changes. - if (!scenePrivate->hasSceneRect && scenePrivate->growingItemsBoundingRect != oldGrowingItemsBoundingRect) - emit q->scene()->sceneRectChanged(scenePrivate->growingItemsBoundingRect); -} - - -/*! - \internal - - Removes stale pointers from all data structures. -*/ -void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems() -{ - if (!purgePending && removedItems.isEmpty()) - return; - - // Remove stale items from the BSP tree. - bsp.removeItems(removedItems); - // Purge this list. - removedItems.clear(); - freeItemIndexes.clear(); - for (int i = 0; i < indexedItems.size(); ++i) { - if (!indexedItems.at(i)) - freeItemIndexes << i; - } - purgePending = false; -} - -/*! - \internal - - Starts or restarts the timer used for reindexing unindexed items. -*/ -void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer(int interval) -{ - Q_Q(QGraphicsSceneBspTreeIndex); - if (indexTimerId) { - restartIndexTimer = true; - } else { - indexTimerId = q->startTimer(interval); - } -} - -/*! - \internal -*/ -void QGraphicsSceneBspTreeIndexPrivate::resetIndex() -{ - purgeRemovedItems(); - 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(); -} - -/*! - \internal -*/ -void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder) -{ - if (!item->d_ptr->children.isEmpty()) { - QList 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)++; - } -} - -/*! - \internal -*/ -void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache() -{ - Q_Q(QGraphicsSceneBspTreeIndex); - _q_updateIndex(); - - if (!sortCacheEnabled || !updatingSortCache) - return; - - updatingSortCache = false; - int stackingOrder = 0; - - QList topLevels; - - for (int i = 0; i < q->items().count(); ++i) { - QGraphicsItem *item = q->items().at(i); - if (item && 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); -} - -/*! - \internal -*/ -void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache() -{ - Q_Q(QGraphicsSceneBspTreeIndex); - if (!sortCacheEnabled || updatingSortCache) - return; - - updatingSortCache = true; - QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection); -} - -/*! - Returns true if \a item1 is on top of \a item2. - - \internal -*/ -bool QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2) -{ - // Siblings? Just check their z-values. - const QGraphicsItemPrivate *d1 = item1->d_ptr; - const QGraphicsItemPrivate *d2 = item2->d_ptr; - 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 QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2) -{ - return closestItemFirst_withoutCache(item2, item1); -} - -/*! - Sort a list of \a itemList in a specific \a order and use the cache if requested. - - \internal -*/ -void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList *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); - } - } -} - -/*! - Constructs a BSP scene index for the given \a scene. -*/ -QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene) - : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene) -{ - -} - -/*! - \reimp - Return the rect indexed by the BSP index. -*/ -QRectF QGraphicsSceneBspTreeIndex::indexedRect() const -{ - Q_D(const QGraphicsSceneBspTreeIndex); - const_cast(d)->_q_updateIndex(); - return scene()->d_func()->hasSceneRect ? scene()->d_func()->sceneRect : scene()->d_func()->growingItemsBoundingRect; -} - -/*! - \reimp - Clear the all the BSP index. -*/ -void QGraphicsSceneBspTreeIndex::clear() -{ - Q_D(QGraphicsSceneBspTreeIndex); - d->bsp.clear(); - d->lastItemCount = 0; - d->freeItemIndexes.clear(); - d->indexedItems.clear(); - d->unindexedItems.clear(); -} - -/*! - Add the \a item into the BSP index. -*/ -void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item) -{ - Q_D(QGraphicsSceneBspTreeIndex); - // 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. - // Update the scene's sort cache settings. - item->d_ptr->globalStackingOrder = -1; - d->invalidateSortCache(); - - // 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); -} - -/*! - This really add the item in the BSP. - \internal -*/ -void QGraphicsSceneBspTreeIndexPrivate::addToIndex(QGraphicsItem *item) -{ - if (item->d_func()->index != -1) { - bsp.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(); - } -} - -/*! - Remove the \a item from the BSP index. -*/ -void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item) -{ - Q_D(QGraphicsSceneBspTreeIndex); - // Note: This will access item's sceneBoundingRect(), which (as this is - // C++) is why we cannot call removeItem() from QGraphicsItem's - // destructor. - d->removeFromIndex(item); - - // Invalidate any sort caching; arrival of a new item means we need to - // resort. - d->invalidateSortCache(); - - // Remove from our item lists. - int index = item->d_func()->index; - if (index != -1) { - d->freeItemIndexes << index; - d->indexedItems[index] = 0; - } else { - d->unindexedItems.removeAll(item); - } -} - -/*! - \reimp - Delete the \a item from the BSP index (without accessing its boundingRect). -*/ -void QGraphicsSceneBspTreeIndex::deleteItem(QGraphicsItem *item) -{ - Q_D(QGraphicsSceneBspTreeIndex); - // Invalidate any sort caching; arrival of a new item means we need to - // resort. - d->invalidateSortCache(); - - int index = item->d_func()->index; - if (index != -1) { - // Important: The index is useless until purgeRemovedItems() is - // called. - d->indexedItems[index] = (QGraphicsItem *)0; - if (!d->purgePending) { - d->purgePending = true; - scene()->update(); - } - d->removedItems << item; - } else { - // Recently added items are purged immediately. unindexedItems() never - // contains stale items. - d->unindexedItems.removeAll(item); - scene()->update(); - } -} - -/*! - Really remove the item from the BSP - \internal -*/ -void QGraphicsSceneBspTreeIndexPrivate::removeFromIndex(QGraphicsItem *item) -{ - if (item->d_func()->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren) { - // ### remove from child index only if applicable - return; - } - int index = item->d_func()->index; - if (index != -1) { - bsp.removeItem(item, item->sceneBoundingRect()); - freeItemIndexes << index; - indexedItems[index] = 0; - item->d_func()->index = -1; - unindexedItems << item; - - //prepareGeometryChange will call prepareBoundingRectChange - foreach (QGraphicsItem *child, item->children()) - child->prepareGeometryChange(); - } - startIndexTimer(); -} - -/*! - \reimp - Update the BSP when the \a item 's bounding rect has changed. -*/ -void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item) -{ - Q_D(QGraphicsSceneBspTreeIndex); - // Note: This will access item's sceneBoundingRect(), which (as this is - // C++) is why we cannot call removeItem() from QGraphicsItem's - // destructor. - d->removeFromIndex(const_cast(item)); -} - -/*! - Returns an estimation visible items that are either inside or - intersect with the specified \a rect and return a list sorted using \a order. - - \a deviceTransform is the transformation apply to the view. - -*/ -QList QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const -{ - Q_D(const QGraphicsSceneBspTreeIndex); - const_cast(d)->purgeRemovedItems(); - const_cast(d)->_q_updateSortCache(); - - QList rectItems = d->bsp.items(rect); - // Fill in with any unindexed items - for (int i = 0; i < d->unindexedItems.size(); ++i) { - if (QGraphicsItem *item = d->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; - rectItems << item; - } - } - } - } - - // Reset the discovered state of all discovered items - for (int i = 0; i < rectItems.size(); ++i) - rectItems.at(i)->d_func()->itemDiscovered = 0; - - d->sortItems(&rectItems, order, d->sortCacheEnabled); - - return rectItems; -} - - -/*! - \fn QList QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order = Qt::AscendingOrder) const; - - Return all items in the BSP index and sort them using \a order. -*/ -QList QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) const -{ - Q_D(const QGraphicsSceneBspTreeIndex); - const_cast(d)->purgeRemovedItems(); - QList itemList; - // If freeItemIndexes is empty, we know there are no holes in indexedItems and - // unindexedItems. - if (d->freeItemIndexes.isEmpty()) { - if (d->unindexedItems.isEmpty()) { - itemList = d->indexedItems; - } else { - itemList = d->indexedItems + d->unindexedItems; - } - } else { - // Rebuild the list of items to avoid holes. ### We could also just - // compress the item lists at this point. - foreach (QGraphicsItem *item, d->indexedItems + d->unindexedItems) { - if (item) - itemList << item; - } - } - if (order != -1) { - //We sort descending order - d->sortItems(&itemList, order, d->sortCacheEnabled); - } - return itemList; -} - -/*! - \property QGraphicsSceneBspTreeIndex::bspTreeDepth - \brief the depth of the BSP index tree - \since 4.6 - - This value determines the depth of BSP tree. The depth - directly affects performance and memory usage; the latter - growing exponentially with the depth of the tree. With an optimal tree - depth, the index can instantly determine the locality of items, even - for scenes with thousands or millions of items. This also greatly improves - rendering performance. - - By default, the value is 0, in which case Qt will guess a reasonable - default depth based on the size, location and number of items in the - scene. If these parameters change frequently, however, you may experience - slowdowns as the index retunes the depth internally. You can avoid - potential slowdowns by fixating the tree depth through setting this - property. - - The depth of the tree and the size of the scene rectangle decide the - granularity of the scene's partitioning. The size of each scene segment is - determined by the following algorithm: - - The BSP tree has an optimal size when each segment contains between 0 and - 10 items. - -*/ -int QGraphicsSceneBspTreeIndex::bspTreeDepth() -{ - Q_D(const QGraphicsSceneBspTreeIndex); - return d->bspTreeDepth; -} - -void QGraphicsSceneBspTreeIndex::setBspTreeDepth(int depth) -{ - Q_D(QGraphicsSceneBspTreeIndex); - d->bspTreeDepth = depth; - d->resetIndex(); -} - -/*! - \reimp - - This method react to the \a rect change of the scene and - reset the BSP tree index. -*/ -void QGraphicsSceneBspTreeIndex::sceneRectChanged(const QRectF &rect) -{ - Q_D(QGraphicsSceneBspTreeIndex); - d->sceneRect = rect; - d->resetIndex(); -} - -/*! - \reimp - - This method react to the \a change of the \a item and use the \a value to - update the BSP tree if necessary. - -*/ -void QGraphicsSceneBspTreeIndex::itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value) -{ - Q_D(QGraphicsSceneBspTreeIndex); - switch (change) { - case QGraphicsItem::ItemZValueChange: - case QGraphicsItem::ItemParentChange: { - d->invalidateSortCache(); - break; - } - default: - break; - } - return QGraphicsSceneIndex::itemChanged(item, change, value); -} -/*! - \reimp - - Used to catch the timer event. - - \internal -*/ -bool QGraphicsSceneBspTreeIndex::event(QEvent *event) -{ - Q_D(QGraphicsSceneBspTreeIndex); - switch (event->type()) { - case QEvent::Timer: - if (d->indexTimerId && static_cast(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; -} - -QT_END_NAMESPACE - -#include "moc_qgraphicsscenebsptreeindex_p.cpp" - -#endif // QT_NO_GRAPHICSVIEW - diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h index 40b8f0b..6bafbc8 100644 --- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h +++ b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p.h @@ -39,63 +39,112 @@ ** ****************************************************************************/ -#include - -#ifndef QGRAPHICSBSPTREEINDEX_H -#define QGRAPHICSBSPTREEINDEX_H +#ifndef QGRAPHICSSCENEBSPTREEINDEX_P_H +#define QGRAPHICSSCENEBSPTREEINDEX_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of qapplication_*.cpp, qwidget*.cpp and qfiledialog.cpp. This header +// file may change from version to version without notice, or even be removed. +// +// We mean it. +// + +#include "qgraphicsscenebsptreeindex.h" #if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW +#include +#include + QT_BEGIN_NAMESPACE -#include -#include -#include -#include -#include +static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; -#include "qgraphicsscene_bsp_p.h" +class QGraphicsScene; -class QGraphicsSceneBspTreeIndexPrivate; -class Q_AUTOTEST_EXPORT QGraphicsSceneBspTreeIndex : public QGraphicsSceneIndex +class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate { - Q_OBJECT - Q_PROPERTY(int bspTreeDepth READ bspTreeDepth WRITE setBspTreeDepth) + Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex) public: - QGraphicsSceneBspTreeIndex(QGraphicsScene *scene = 0); - QRectF indexedRect() const; - - QList estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const; - - QList items(Qt::SortOrder order = Qt::AscendingOrder) const; - - int bspTreeDepth(); - void setBspTreeDepth(int depth); - -protected: - bool event(QEvent *event); - void clear(); - - void addItem(QGraphicsItem *item); - void removeItem(QGraphicsItem *item); - void deleteItem(QGraphicsItem *item); - void prepareBoundingRectChange(const QGraphicsItem *item); + QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene); + + QGraphicsSceneBspTree bsp; + QRectF sceneRect; + int bspTreeDepth; + int indexTimerId; + bool restartIndexTimer; + bool regenerateIndex; + int lastItemCount; + + QList indexedItems; + QList unindexedItems; + QList freeItemIndexes; + + bool purgePending; + QSet removedItems; + void purgeRemovedItems(); + + void _q_updateIndex(); + void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT); + void resetIndex(); + + void addToIndex(QGraphicsItem *item); + void removeFromIndex(QGraphicsItem *item); + + void _q_updateSortCache(); + bool sortCacheEnabled; + bool updatingSortCache; + void invalidateSortCache(); + + static void climbTree(QGraphicsItem *item, int *stackingOrder); + static bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2); + static bool closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2); + + static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2) + { + return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder; + } + static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2) + { + return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder; + } + + static void sortItems(QList *itemList, Qt::SortOrder order, bool cached); +}; - void sceneRectChanged(const QRectF &rect); - void itemChanged(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const QVariant &value); -private : - Q_DECLARE_PRIVATE(QGraphicsSceneBspTreeIndex) - Q_DISABLE_COPY(QGraphicsSceneBspTreeIndex) - Q_PRIVATE_SLOT(d_func(), void _q_updateSortCache()) - Q_PRIVATE_SLOT(d_func(), void _q_updateIndex()) +/*! + \internal +*/ +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; + const QGraphicsItemPrivate *d2 = item2->d_ptr; + 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; +} + +/*! + \internal +*/ +static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2) +{ + return qt_closestLeaf(item2, item1); +} - friend class QGraphicsScene; - friend class QGraphicsScenePrivate; -}; QT_END_NAMESPACE -#endif // QT_NO_GRAPHICSVIEW +#endif // QGRAPHICSSCENEBSPTREEINDEX_P_H + +#endif -#endif // QGRAPHICSBSPTREEINDEX_H diff --git a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h b/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h deleted file mode 100644 index 30f6e26..0000000 --- a/src/gui/graphicsview/qgraphicsscenebsptreeindex_p_p.h +++ /dev/null @@ -1,150 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). -** Contact: Qt Software Information (qt-info@nokia.com) -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** No Commercial Usage -** This file contains pre-release code and may not be distributed. -** You may use this file in accordance with the terms and conditions -** contained in the either Technology Preview License Agreement or the -** Beta Release License Agreement. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 2.1 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 2.1 requirements -** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -** -** In addition, as a special exception, Nokia gives you certain -** additional rights. These rights are described in the Nokia Qt LGPL -** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this -** package. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 3.0 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU General Public License version 3.0 requirements will be -** met: http://www.gnu.org/copyleft/gpl.html. -** -** If you are unsure which license is appropriate for your use, please -** contact the sales department at qt-sales@nokia.com. -** $QT_END_LICENSE$ -** -****************************************************************************/ - -#ifndef QGRAPHICSSCENEBSPTREEINDEX_P_P_H -#define QGRAPHICSSCENEBSPTREEINDEX_P_P_H - -// -// W A R N I N G -// ------------- -// -// This file is not part of the Qt API. It exists for the convenience -// of qapplication_*.cpp, qwidget*.cpp and qfiledialog.cpp. This header -// file may change from version to version without notice, or even be removed. -// -// We mean it. -// - -#include "qgraphicsscenebsptreeindex_p.h" - -#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW - -#include -#include - -QT_BEGIN_NAMESPACE - -static const int QGRAPHICSSCENE_INDEXTIMER_TIMEOUT = 2000; - -class QGraphicsScene; - -class QGraphicsSceneBspTreeIndexPrivate : public QGraphicsSceneIndexPrivate -{ - Q_DECLARE_PUBLIC(QGraphicsSceneBspTreeIndex) -public: - QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene); - - QGraphicsSceneBspTree bsp; - QRectF sceneRect; - int bspTreeDepth; - int indexTimerId; - bool restartIndexTimer; - bool regenerateIndex; - int lastItemCount; - - QList indexedItems; - QList unindexedItems; - QList freeItemIndexes; - - bool purgePending; - QSet removedItems; - void purgeRemovedItems(); - - void _q_updateIndex(); - void startIndexTimer(int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT); - void resetIndex(); - - void addToIndex(QGraphicsItem *item); - void removeFromIndex(QGraphicsItem *item); - - void _q_updateSortCache(); - bool sortCacheEnabled; - bool updatingSortCache; - void invalidateSortCache(); - - static void climbTree(QGraphicsItem *item, int *stackingOrder); - static bool closestItemFirst_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2); - static bool closestItemLast_withoutCache(const QGraphicsItem *item1, const QGraphicsItem *item2); - - static inline bool closestItemFirst_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2) - { - return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder; - } - static inline bool closestItemLast_withCache(const QGraphicsItem *item1, const QGraphicsItem *item2) - { - return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder; - } - - static void sortItems(QList *itemList, Qt::SortOrder order, bool cached); -}; - - -/*! - \internal -*/ -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; - const QGraphicsItemPrivate *d2 = item2->d_ptr; - 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; -} - -/*! - \internal -*/ -static inline bool qt_notclosestLeaf(const QGraphicsItem *item1, const QGraphicsItem *item2) -{ - return qt_closestLeaf(item2, item1); -} - - -QT_END_NAMESPACE - -#endif // QGRAPHICSSCENEBSPTREEINDEX_P_P_H - -#endif - diff --git a/src/gui/graphicsview/qgraphicssceneindex.cpp b/src/gui/graphicsview/qgraphicssceneindex.cpp index 05ec28b..966d8fe 100644 --- a/src/gui/graphicsview/qgraphicssceneindex.cpp +++ b/src/gui/graphicsview/qgraphicssceneindex.cpp @@ -46,6 +46,7 @@ \ingroup multimedia \ingroup graphicsview-api \mainclass + \internal The QGraphicsSceneIndex class provides a base class to implement a custom indexing algorithm for discovering items in QGraphicsScene. You @@ -57,7 +58,6 @@ #include "qgraphicssceneindex.h" #include "qgraphicssceneindex_p.h" -#include "qgraphicsscenebsptreeindex_p_p.h" #include "qgraphicsscene.h" #include "qgraphicsitem_p.h" #include "qgraphicsscene_p.h" diff --git a/src/gui/graphicsview/qgraphicssceneindex.h b/src/gui/graphicsview/qgraphicssceneindex.h index 084a623..c0e415c 100644 --- a/src/gui/graphicsview/qgraphicssceneindex.h +++ b/src/gui/graphicsview/qgraphicssceneindex.h @@ -42,6 +42,17 @@ #ifndef QGRAPHICSSCENEINDEX_H #define QGRAPHICSSCENEINDEX_H +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of qapplication_*.cpp, qwidget*.cpp and qfiledialog.cpp. This header +// file may change from version to version without notice, or even be removed. +// +// We mean it. +// + #include #include #include @@ -61,7 +72,7 @@ class QRectF; class QPointF; template class QList; -class Q_GUI_EXPORT QGraphicsSceneIndex: public QObject +class Q_AUTOTEST_EXPORT QGraphicsSceneIndex: public QObject { Q_OBJECT diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex.cpp b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp index 1c898bc..5504493 100644 --- a/src/gui/graphicsview/qgraphicsscenelinearindex.cpp +++ b/src/gui/graphicsview/qgraphicsscenelinearindex.cpp @@ -1,4 +1,4 @@ -#include "qgraphicsscenelinearindex_p.h" +#include "qgraphicsscenelinearindex.h" /*! \class QGraphicsSceneLinearIndex @@ -8,6 +8,7 @@ \ingroup multimedia \ingroup graphicsview-api \mainclass + \internal QGraphicsSceneLinearIndex index is default linear implementation to discover items. It basically store all items in a list and return them to the scene. diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex.h b/src/gui/graphicsview/qgraphicsscenelinearindex.h new file mode 100644 index 0000000..b793d98 --- /dev/null +++ b/src/gui/graphicsview/qgraphicsscenelinearindex.h @@ -0,0 +1,124 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** Contact: Qt Software Information (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the either Technology Preview License Agreement or the +** Beta Release License Agreement. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain +** additional rights. These rights are described in the Nokia Qt LGPL +** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this +** package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3.0 as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU General Public License version 3.0 requirements will be +** met: http://www.gnu.org/copyleft/gpl.html. +** +** If you are unsure which license is appropriate for your use, please +** contact the sales department at qt-sales@nokia.com. +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QGRAPHICSSCENELINEARINDEX_H +#define QGRAPHICSSCENELINEARINDEX_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include + +QT_BEGIN_HEADER + +QT_BEGIN_NAMESPACE + +QT_MODULE(Gui) + +#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW + +#include +#include +#include +#include + +class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex +{ + Q_OBJECT + +public: + QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0): QGraphicsSceneIndex(scene) + { + } + + QList items(Qt::SortOrder order = Qt::AscendingOrder) const { + Q_UNUSED(order); + return m_items; + } + + virtual QList estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const { + Q_UNUSED(rect); + Q_UNUSED(order); + Q_UNUSED(deviceTransform); + return m_items; + } + + virtual QRectF indexedRect() const { + return m_sceneRect; + } + +protected : + void sceneRectChanged(const QRectF &rect) { + m_sceneRect = rect; + } + + virtual void clear() { + m_items.clear(); + } + + virtual void addItem(QGraphicsItem *item) { + m_items << item; + } + + virtual void removeItem(QGraphicsItem *item) { + m_items.removeAll(item); + } + +private: + QRectF m_sceneRect; + QList m_items; +}; + +#endif // QT_NO_GRAPHICSVIEW + +QT_END_NAMESPACE + +QT_END_HEADER + +#endif // QGRAPHICSSCENELINEARINDEX_H diff --git a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h b/src/gui/graphicsview/qgraphicsscenelinearindex_p.h deleted file mode 100644 index d21475c..0000000 --- a/src/gui/graphicsview/qgraphicsscenelinearindex_p.h +++ /dev/null @@ -1,118 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). -** Contact: Qt Software Information (qt-info@nokia.com) -** -** This file is part of the QtGui module of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** No Commercial Usage -** This file contains pre-release code and may not be distributed. -** You may use this file in accordance with the terms and conditions -** contained in the either Technology Preview License Agreement or the -** Beta Release License Agreement. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 2.1 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 2.1 requirements -** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -** -** In addition, as a special exception, Nokia gives you certain -** additional rights. These rights are described in the Nokia Qt LGPL -** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this -** package. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 3.0 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU General Public License version 3.0 requirements will be -** met: http://www.gnu.org/copyleft/gpl.html. -** -** If you are unsure which license is appropriate for your use, please -** contact the sales department at qt-sales@nokia.com. -** $QT_END_LICENSE$ -** -****************************************************************************/ - -#ifndef QGRAPHICSSCENELINEARINDEX_P_H -#define QGRAPHICSSCENELINEARINDEX_P_H - -// -// W A R N I N G -// ------------- -// -// This file is not part of the Qt API. It exists for the convenience -// of other Qt classes. This header file may change from version to -// version without notice, or even be removed. -// -// We mean it. -// - -#include - -#if !defined(QT_NO_GRAPHICSVIEW) || (QT_EDITION & QT_MODULE_GRAPHICSVIEW) != QT_MODULE_GRAPHICSVIEW - -#include -#include -#include -#include - -QT_BEGIN_NAMESPACE - -class Q_AUTOTEST_EXPORT QGraphicsSceneLinearIndex : public QGraphicsSceneIndex -{ - Q_OBJECT - -public: - QGraphicsSceneLinearIndex(QGraphicsScene *scene = 0): QGraphicsSceneIndex(scene) - { - } - - QList items(Qt::SortOrder order = Qt::AscendingOrder) const { - Q_UNUSED(order); - return m_items; - } - - virtual QList estimateItems(const QRectF &rect, Qt::SortOrder order, const QTransform &deviceTransform) const { - Q_UNUSED(rect); - Q_UNUSED(order); - Q_UNUSED(deviceTransform); - return m_items; - } - - virtual QRectF indexedRect() const { - return m_sceneRect; - } - -protected : - void sceneRectChanged(const QRectF &rect) { - m_sceneRect = rect; - } - - virtual void clear() { - m_items.clear(); - } - - virtual void addItem(QGraphicsItem *item) { - m_items << item; - } - - virtual void removeItem(QGraphicsItem *item) { - m_items.removeAll(item); - } - -private: - QRectF m_sceneRect; - QList m_items; -}; - -QT_END_NAMESPACE - -#endif // QT_NO_GRAPHICSVIEW - -#endif // QGRAPHICSSCENELINEARINDEX_P_H -- cgit v0.12