#include <qgraphicsscenebsptreeindex_p.h>

Inheritance diagram for QGraphicsSceneBspTreeIndexPrivate:

Public Functions
void	_q_updateIndex ()
	This method will update the BSP index by removing the items from the temporary unindexed list and add them in the indexedItems list. More...

void	_q_updateSortCache ()

void	addItem (QGraphicsItem *item, bool recursive=false)

QList< QGraphicsItem * >	estimateItems (const QRectF &, Qt::SortOrder, bool b=false)

void	invalidateSortCache ()

void	purgeRemovedItems ()
	Removes stale pointers from all data structures. More...

	QGraphicsSceneBspTreeIndexPrivate (QGraphicsScene *scene)
	Constructs a private scene bsp index. More...

void	removeItem (QGraphicsItem *item, bool recursive=false, bool moveToUnindexedItems=false)

void	resetIndex ()

void	startIndexTimer (int interval=QGRAPHICSSCENE_INDEXTIMER_TIMEOUT)
	Starts or restarts the timer used for reindexing unindexed items. More...

Public Functions inherited from QGraphicsSceneIndexPrivate
void	init ()

void	items_helper (const QRectF &rect, QGraphicsSceneIndexIntersector intersector, QList< QGraphicsItem > *items, const QTransform &viewTransform, Qt::ItemSelectionMode mode, Qt::SortOrder order) const

	QGraphicsSceneIndexPrivate (QGraphicsScene *scene)
	Constructs a private scene index. More...

void	recursive_items_helper (QGraphicsItem item, QRectF exposeRect, QGraphicsSceneIndexIntersector intersector, QList< QGraphicsItem > items, const QTransform &viewTransform, Qt::ItemSelectionMode mode, qreal parentOpacity=1.0) const
	This function returns the items in ascending order. More...

	~QGraphicsSceneIndexPrivate ()
	Destructor of private scene index. More...

Public Functions inherited from QObjectPrivate
void	_q_reregisterTimers (void *pointer)

void	addConnection (int signal, Connection *c)

void	cleanConnectionLists ()

void	connectNotify (const char *signal)

void	deleteChildren ()

void	disconnectNotify (const char *signal)

bool	isSender (const QObject receiver, const char signal) const

bool	isSignalConnected (uint signalIdx) const
	Returns true if the signal with index signal_index from object sender is connected. More...

void	moveToThread_helper ()

	QObjectPrivate (int version=QObjectPrivateVersion)

QObjectList	receiverList (const char *signal) const

QObjectList	senderList () const

void	setParent_helper (QObject *)

void	setThreadData_helper (QThreadData currentData, QThreadData targetData)

int	signalIndex (const char *signalName) const
	Returns the signal index used in the internal connectionLists vector. More...

virtual	~QObjectPrivate ()

Public Functions inherited from QObjectData
virtual	~QObjectData ()=0

Static Public Functions
static void	climbTree (QGraphicsItem item, int stackingOrder)

static bool	closestItemFirst_withCache (const QGraphicsItem item1, const QGraphicsItem item2)

static bool	closestItemLast_withCache (const QGraphicsItem item1, const QGraphicsItem item2)

static void	sortItems (QList< QGraphicsItem > itemList, Qt::SortOrder order, bool cached, bool onlyTopLevelItems=false)
	Sort a list of itemList in a specific order and use the cache if requested. More...

Static Public Functions inherited from QGraphicsSceneIndexPrivate
static bool	itemCollidesWithPath (const QGraphicsItem *item, const QPainterPath &path, Qt::ItemSelectionMode mode)
	Checks if item collides with the path and mode, but also checks that if it doesn't collide, maybe its frame rect will. More...

Static Public Functions inherited from QObjectPrivate
static void	clearGuards (QObject *)

static QObjectPrivate *	get (QObject *o)

static void	resetCurrentSender (QObject receiver, Sender currentSender, Sender *previousSender)

static Sender *	setCurrentSender (QObject receiver, Sender sender)

static void	signalSignature (const QMetaMethod &signal, QVarLengthArray< char > *result)

Public Variables
QGraphicsSceneBspTree	bsp

int	bspTreeDepth

QList< int >	freeItemIndexes

QList< QGraphicsItem * >	indexedItems

int	indexTimerId

int	lastItemCount

bool	purgePending

bool	regenerateIndex

QSet< QGraphicsItem * >	removedItems

bool	restartIndexTimer

QRectF	sceneRect

bool	sortCacheEnabled

QList< QGraphicsItem * >	unindexedItems

QList< QGraphicsItem * >	untransformableItems

bool	updatingSortCache

Public Variables inherited from QGraphicsSceneIndexPrivate
QGraphicsSceneIndexPathIntersector *	pathIntersector

QGraphicsSceneIndexPointIntersector *	pointIntersector

QGraphicsSceneIndexRectIntersector *	rectIntersector

QGraphicsScene *	scene

Public Variables inherited from QObjectPrivate
union {
QObject * currentChildBeingDeleted

QAbstractDeclarativeData * declarativeData

};

quint32	connectedSignals [2]

QObjectConnectionListVector *	connectionLists

Sender *	currentSender

QList< QPointer< QObject > >	eventFilters

ExtraData *	extraData

QString	objectName

Connection *	senders

QAtomicPointer< QtSharedPointer::ExternalRefCountData >	sharedRefcount

QThreadData *	threadData

void *	unused

Public Variables inherited from QObjectData
uint	blockSig: 1

QObjectList	children

uint	hasGuards: 1

uint	inEventHandler: 1

uint	inThreadChangeEvent: 1

uint	isWidget: 1

QMetaObject *	metaObject

uint	ownObjectName: 1

QObject *	parent

uint	pendTimer: 1

int	postedEvents

QObject *	q_ptr

uint	receiveChildEvents: 1

uint	sendChildEvents: 1

uint	unused: 22

uint	wasDeleted: 1

Additional Inherited Members
Public Types inherited from QObjectPrivate
typedef void(*	StaticMetaCallFunction) (QObject , QMetaObject::Call, int, void *)

Detailed Description

Definition at line 112 of file qgraphicsscenebsptreeindex_p.h.

Constructors and Destructors

◆ QGraphicsSceneBspTreeIndexPrivate()

QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate ( QGraphicsScene * scene )

Constructs a private scene bsp index.

Definition at line 101 of file qgraphicsscenebsptreeindex.cpp.

     : QGraphicsSceneIndexPrivate(scene),
     bspTreeDepth(0),
     indexTimerId(0),
     restartIndexTimer(false),
     regenerateIndex(true),
     lastItemCount(0),
     purgePending(false),
     sortCacheEnabled(false),
     updatingSortCache(false)
 {
 }

Functions

◆ _q_updateIndex()

void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex ( )

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.

Warning: This function is not part of the public interface.

Definition at line 123 of file qgraphicsscenebsptreeindex.cpp.

Referenced by _q_updateSortCache().

 {
     Q_Q(QGraphicsSceneBspTreeIndex);
     if (!indexTimerId)
         return;
 
     q->killTimer(indexTimerId);
     indexTimerId = 0;
 
     purgeRemovedItems();
 
      // Add unindexedItems to indexedItems
     for (int i = 0; i < unindexedItems.size(); ++i) {
         if (QGraphicsItem *item = unindexedItems.at(i)) {
             Q_ASSERT(!item->d_ptr->itemDiscovered);
             if (!freeItemIndexes.isEmpty()) {
                 int freeIndex = freeItemIndexes.takeFirst();
                 item->d_func()->index = freeIndex;
                 indexedItems[freeIndex] = item;
             } else {
                 item->d_func()->index = indexedItems.size();
                 indexedItems << item;
             }
         }
     }
 
     // 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(sceneRect, bspTreeDepth);
         unindexedItems = indexedItems;
         lastItemCount = indexedItems.size();
     }
 
     // Insert all unindexed items into the tree.
     for (int i = 0; i < unindexedItems.size(); ++i) {
         if (QGraphicsItem *item = unindexedItems.at(i)) {
             if (item->d_ptr->itemIsUntransformable()) {
                 untransformableItems << item;
                 continue;
             }
             if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)
                 continue;
 
             bsp.insertItem(item, item->d_ptr->sceneEffectiveBoundingRect());
         }
     }
     unindexedItems.clear();
 }

◆ _q_updateSortCache()

void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache ( )

Warning: This function is not part of the public interface.

Definition at line 275 of file qgraphicsscenebsptreeindex.cpp.

Referenced by estimateItems().

 {
     Q_Q(QGraphicsSceneBspTreeIndex);
     _q_updateIndex();
 
     if (!sortCacheEnabled || !updatingSortCache)
         return;
 
     updatingSortCache = false;
     int stackingOrder = 0;
 
     QList<QGraphicsItem *> topLevels;
     const QList<QGraphicsItem *> items = q->items();
     for (int i = 0; i < items.size(); ++i) {
         QGraphicsItem *item = items.at(i);
         if (item && !item->d_ptr->parent)
             topLevels << item;
     }
 
     qSort(topLevels.begin(), topLevels.end(), qt_closestLeaf);
     for (int i = 0; i < topLevels.size(); ++i)
         climbTree(topLevels.at(i), &stackingOrder);
 }

◆ addItem()

void QGraphicsSceneBspTreeIndexPrivate::addItem	(	QGraphicsItem *	item,
		bool	recursive = `false`
	)

Definition at line 312 of file qgraphicsscenebsptreeindex.cpp.

Referenced by removeItem().

 {
     if (!item)
         return;
 
     // Prevent reusing a recently deleted pointer: purge all removed item from our lists.
     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;
     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.
     if (item->d_ptr->index == -1) {
         Q_ASSERT(!unindexedItems.contains(item));
         unindexedItems << item;
         startIndexTimer(0);
     } else {
         Q_ASSERT(indexedItems.contains(item));
         qWarning("QGraphicsSceneBspTreeIndex::addItem: item has already been added to this BSP");
     }
 
     if (recursive) {
         for (int i = 0; i < item->d_ptr->children.size(); ++i)
             addItem(item->d_ptr->children.at(i), recursive);
     }
 }

◆ climbTree()

void QGraphicsSceneBspTreeIndexPrivate::climbTree	(	QGraphicsItem *	item,
		int *	stackingOrder
	)

static

Warning: This function is not part of the public interface.

Definition at line 251 of file qgraphicsscenebsptreeindex.cpp.

Referenced by _q_updateSortCache().

 {
     if (!item->d_ptr->children.isEmpty()) {
         QList<QGraphicsItem *> 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)++;
     }
 }

◆ closestItemFirst_withCache()

static bool QGraphicsSceneBspTreeIndexPrivate::closestItemFirst_withCache	(	const QGraphicsItem *	item1,
		const QGraphicsItem *	item2
	)

inlinestatic

Definition at line 149 of file qgraphicsscenebsptreeindex_p.h.

Referenced by sortItems().

     {
         return item1->d_ptr->globalStackingOrder < item2->d_ptr->globalStackingOrder;
     }

◆ closestItemLast_withCache()

static bool QGraphicsSceneBspTreeIndexPrivate::closestItemLast_withCache	(	const QGraphicsItem *	item1,
		const QGraphicsItem *	item2
	)

inlinestatic

Definition at line 153 of file qgraphicsscenebsptreeindex_p.h.

Referenced by sortItems().

     {
         return item1->d_ptr->globalStackingOrder >= item2->d_ptr->globalStackingOrder;
     }

◆ estimateItems()

QList< QGraphicsItem * > QGraphicsSceneBspTreeIndexPrivate::estimateItems	(	const QRectF &	rect,
		Qt::SortOrder	order,
		bool	b = `false`
	)

Definition at line 385 of file qgraphicsscenebsptreeindex.cpp.

 {
     Q_Q(QGraphicsSceneBspTreeIndex);
     if (onlyTopLevelItems && rect.isNull())
         return q->QGraphicsSceneIndex::estimateTopLevelItems(rect, order);
 
     purgeRemovedItems();
     _q_updateSortCache();
     Q_ASSERT(unindexedItems.isEmpty());
 
     QList<QGraphicsItem *> rectItems = bsp.items(rect, onlyTopLevelItems);
     if (onlyTopLevelItems) {
         for (int i = 0; i < untransformableItems.size(); ++i) {
             QGraphicsItem *item = untransformableItems.at(i);
             if (!item->d_ptr->parent) {
                 rectItems << item;
             } else {
                 item = item->topLevelItem();
                 if (!rectItems.contains(item))
                     rectItems << item;
             }
         }
     } else {
         rectItems += untransformableItems;
     }
 
     sortItems(&rectItems, order, sortCacheEnabled, onlyTopLevelItems);
     return rectItems;
 }

◆ invalidateSortCache()

void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache ( )

Warning: This function is not part of the public interface.

Definition at line 302 of file qgraphicsscenebsptreeindex.cpp.

Referenced by addItem(), and removeItem().

 {
     Q_Q(QGraphicsSceneBspTreeIndex);
     if (!sortCacheEnabled || updatingSortCache)
         return;
 
     updatingSortCache = true;
     QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);
 }

◆ purgeRemovedItems()

void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems ( )

Removes stale pointers from all data structures.

Warning: This function is not part of the public interface.

Definition at line 193 of file qgraphicsscenebsptreeindex.cpp.

Referenced by _q_updateIndex(), addItem(), estimateItems(), and resetIndex().

 {
     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;
 }

◆ removeItem()

void QGraphicsSceneBspTreeIndexPrivate::removeItem	(	QGraphicsItem *	item,
		bool	recursive = `false`,
		bool	moveToUnindexedItems = `false`
	)

Definition at line 343 of file qgraphicsscenebsptreeindex.cpp.

 {
     if (!item)
         return;
 
     if (item->d_ptr->index != -1) {
         Q_ASSERT(item->d_ptr->index < indexedItems.size());
         Q_ASSERT(indexedItems.at(item->d_ptr->index) == item);
         Q_ASSERT(!item->d_ptr->itemDiscovered);
         freeItemIndexes << item->d_ptr->index;
         indexedItems[item->d_ptr->index] = 0;
         item->d_ptr->index = -1;
 
         if (item->d_ptr->itemIsUntransformable()) {
             untransformableItems.removeOne(item);
         } else if (item->d_ptr->inDestructor) {
             // Avoid virtual function calls from the destructor.
             purgePending = true;
             removedItems << item;
         } else if (!(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren)) {
             bsp.removeItem(item, item->d_ptr->sceneEffectiveBoundingRect());
         }
     } else {
         unindexedItems.removeOne(item);
     }
     invalidateSortCache(); // ### Only do this when removing from BSP?
 
     Q_ASSERT(item->d_ptr->index == -1);
     Q_ASSERT(!indexedItems.contains(item));
     Q_ASSERT(!unindexedItems.contains(item));
     Q_ASSERT(!untransformableItems.contains(item));
 
     if (moveToUnindexedItems)
         addItem(item);
 
     if (recursive) {
         for (int i = 0; i < item->d_ptr->children.size(); ++i)
             removeItem(item->d_ptr->children.at(i), recursive, moveToUnindexedItems);
     }
 }

◆ resetIndex()

void QGraphicsSceneBspTreeIndexPrivate::resetIndex ( )

Warning: This function is not part of the public interface.

Definition at line 231 of file qgraphicsscenebsptreeindex.cpp.

 {
     purgeRemovedItems();
     for (int i = 0; i < indexedItems.size(); ++i) {
         if (QGraphicsItem *item = indexedItems.at(i)) {
             item->d_ptr->index = -1;
             Q_ASSERT(!item->d_ptr->itemDiscovered);
             unindexedItems << item;
         }
     }
     indexedItems.clear();
     freeItemIndexes.clear();
     untransformableItems.clear();
     regenerateIndex = true;
     startIndexTimer();
 }

◆ sortItems()

void QGraphicsSceneBspTreeIndexPrivate::sortItems	(	QList< QGraphicsItem >	itemList,
		Qt::SortOrder	order,
		bool	sortCacheEnabled,
		bool	onlyTopLevelItems = `false`
	)

static

Sort a list of itemList in a specific order and use the cache if requested.

Warning: This function is not part of the public interface.

Definition at line 421 of file qgraphicsscenebsptreeindex.cpp.

Referenced by estimateItems().

 {
     if (order == Qt::SortOrder(-1))
         return;
 
     if (onlyTopLevelItems) {
         if (order == Qt::DescendingOrder)
             qSort(itemList->begin(), itemList->end(), qt_closestLeaf);
         else if (order == Qt::AscendingOrder)
             qSort(itemList->begin(), itemList->end(), qt_notclosestLeaf);
         return;
     }
 
     if (sortCacheEnabled) {
         if (order == Qt::DescendingOrder) {
             qSort(itemList->begin(), itemList->end(), closestItemFirst_withCache);
         } else if (order == Qt::AscendingOrder) {
             qSort(itemList->begin(), itemList->end(), closestItemLast_withCache);
         }
     } else {
         if (order == Qt::DescendingOrder) {
             qSort(itemList->begin(), itemList->end(), qt_closestItemFirst);
         } else if (order == Qt::AscendingOrder) {
             qSort(itemList->begin(), itemList->end(), qt_closestItemLast);
         }
     }
 }

◆ startIndexTimer()

void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer ( int interval = QGRAPHICSSCENE_INDEXTIMER_TIMEOUT )

Starts or restarts the timer used for reindexing unindexed items.

Warning: This function is not part of the public interface.

Definition at line 218 of file qgraphicsscenebsptreeindex.cpp.

Referenced by addItem(), and resetIndex().

 {
     Q_Q(QGraphicsSceneBspTreeIndex);
     if (indexTimerId) {
         restartIndexTimer = true;
     } else {
         indexTimerId = q->startTimer(interval);
     }
 }