qgraphicsscenebsptreeindex.cpp

Absolute File Name:/home/qt/qt5_coco/qt5/qtbase/src/widgets/graphicsview/qgraphicsscenebsptreeindex.cpp
Switch to Source codePreprocessed file
LineSourceCount
1-
2-
3-
4-
5-
6-
7-
8-
9-
10static inline int intmaxlog(int n)-
11{-
12 return (n > 0 ? qMax(qCeil(qLn(qreal(n)) / qLn(qreal(2))), 5) : 0);-
13}-
14-
15-
16-
17-
18QGraphicsSceneBspTreeIndexPrivate::QGraphicsSceneBspTreeIndexPrivate(QGraphicsScene *scene)-
19 : QGraphicsSceneIndexPrivate(scene),-
20 bspTreeDepth(0),-
21 indexTimerId(0),-
22 restartIndexTimer(false),-
23 regenerateIndex(true),-
24 lastItemCount(0),-
25 purgePending(false),-
26 sortCacheEnabled(false),-
27 updatingSortCache(false)-
28{-
29}-
30void QGraphicsSceneBspTreeIndexPrivate::_q_updateIndex()-
31{-
32 QGraphicsSceneBspTreeIndex * const q = q_func();-
33 if (!indexTimerId)-
34 return;-
35-
36 q->killTimer(indexTimerId);-
37 indexTimerId = 0;-
38-
39 purgeRemovedItems();-
40-
41-
42 for (int i = 0; i < unindexedItems.size(); ++i) {-
43 if (QGraphicsItem *item = unindexedItems.at(i)) {-
44 ((!(!item->d_ptr->itemDiscovered)) ? qt_assert("!item->d_ptr->itemDiscovered",__FILE__,126134) : qt_noop());-
45 if (!freeItemIndexes.isEmpty()) {-
46 int freeIndex = freeItemIndexes.takeFirst();-
47 item->d_func()->index = freeIndex;-
48 indexedItems[freeIndex] = item;-
49 } else {-
50 item->d_func()->index = indexedItems.size();-
51 indexedItems << item;-
52 }-
53 }-
54 }-
55-
56-
57 if (bspTreeDepth == 0) {-
58 int oldDepth = intmaxlog(lastItemCount);-
59 bspTreeDepth = intmaxlog(indexedItems.size());-
60 static const int slack = 100;-
61 if (bsp.leafCount() == 0 || (oldDepth != bspTreeDepth && qAbs(lastItemCount - indexedItems.size()) > slack)) {-
62-
63 regenerateIndex = true;-
64 }-
65 }-
66-
67-
68 if (regenerateIndex) {-
69 regenerateIndex = false;-
70 bsp.initialize(sceneRect, bspTreeDepth);-
71 unindexedItems = indexedItems;-
72 lastItemCount = indexedItems.size();-
73 }-
74-
75-
76 for (int i = 0; i < unindexedItems.size(); ++i) {-
77 if (QGraphicsItem *item = unindexedItems.at(i)) {-
78 if (item->d_ptr->itemIsUntransformable()) {-
79 untransformableItems << item;-
80 continue;-
81 }-
82 if (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren-
83 || item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren)-
84 continue;-
85-
86 bsp.insertItem(item, item->d_ptr->sceneEffectiveBoundingRect());-
87 }-
88 }-
89 unindexedItems.clear();-
90}-
91-
92-
93-
94-
95-
96-
97-
98void QGraphicsSceneBspTreeIndexPrivate::purgeRemovedItems()-
99{-
100 if (!purgePending && removedItems.isEmpty())-
101 return;-
102-
103-
104 bsp.removeItems(removedItems);-
105-
106 removedItems.clear();-
107 freeItemIndexes.clear();-
108 for (int i = 0; i < indexedItems.size(); ++i) {-
109 if (!indexedItems.at(i))-
110 freeItemIndexes << i;-
111 }-
112 purgePending = false;-
113}-
114-
115-
116-
117-
118-
119-
120void QGraphicsSceneBspTreeIndexPrivate::startIndexTimer(int interval)-
121{-
122 QGraphicsSceneBspTreeIndex * const q = q_func();-
123 if (indexTimerId) {-
124 restartIndexTimer = true;-
125 } else {-
126 indexTimerId = q->startTimer(interval);-
127 }-
128}-
129-
130-
131-
132-
133void QGraphicsSceneBspTreeIndexPrivate::resetIndex()-
134{-
135 purgeRemovedItems();-
136 for (int i = 0; i < indexedItems.size(); ++i) {-
137 if (QGraphicsItem *item = indexedItems.at(i)) {-
138 item->d_ptr->index = -1;-
139 ((!(!item->d_ptr->itemDiscovered)) ? qt_assert("!item->d_ptr->itemDiscovered",__FILE__,221229) : qt_noop());-
140 unindexedItems << item;-
141 }-
142 }-
143 indexedItems.clear();-
144 freeItemIndexes.clear();-
145 untransformableItems.clear();-
146 regenerateIndex = true;-
147 startIndexTimer();-
148}-
149-
150-
151-
152-
153void QGraphicsSceneBspTreeIndexPrivate::climbTree(QGraphicsItem *item, int *stackingOrder)-
154{-
155 if (!item->d_ptr->children.isEmpty()) {-
156 QList<QGraphicsItem *> childList = item->d_ptr->children;-
157 std::sort(childList.begin(), childList.end(), qt_closestLeaf);-
158 for (int i = 0; i < childList.size(); ++i) {-
159 QGraphicsItem *item = childList.at(i);-
160 if (!(item->flags() & QGraphicsItem::ItemStacksBehindParent))-
161 climbTree(childList.at(i), stackingOrder);-
162 }-
163 item->d_ptr->globalStackingOrder = (*stackingOrder)++;-
164 for (int i = 0; i < childList.size(); ++i) {-
165 QGraphicsItem *item = childList.at(i);-
166 if (item->flags() & QGraphicsItem::ItemStacksBehindParent)-
167 climbTree(childList.at(i), stackingOrder);-
168 }-
169 } else {-
170 item->d_ptr->globalStackingOrder = (*stackingOrder)++;-
171 }-
172}-
173-
174-
175-
176-
177void QGraphicsSceneBspTreeIndexPrivate::_q_updateSortCache()-
178{-
179 QGraphicsSceneBspTreeIndex * const q = q_func();-
180 _q_updateIndex();-
181-
182 if (!sortCacheEnabled || !updatingSortCache)-
183 return;-
184-
185 updatingSortCache = false;-
186 int stackingOrder = 0;-
187-
188 QList<QGraphicsItem *> topLevels;-
189 const QList<QGraphicsItem *> items = q->items();-
190 for (int i = 0; i < items.size(); ++i) {-
191 QGraphicsItem *item = items.at(i);-
192 if (item && !item->d_ptr->parent)-
193 topLevels << item;-
194 }-
195-
196 std::sort(topLevels.begin(), topLevels.end(), qt_closestLeaf);-
197 for (int i = 0; i < topLevels.size(); ++i)-
198 climbTree(topLevels.at(i), &stackingOrder);-
199}-
200-
201-
202-
203-
204void QGraphicsSceneBspTreeIndexPrivate::invalidateSortCache()-
205{-
206 QGraphicsSceneBspTreeIndex * const q = q_func();-
207 if (!sortCacheEnabled || updatingSortCache)-
208 return;-
209-
210 updatingSortCache = true;-
211 QMetaObject::invokeMethod(q, "_q_updateSortCache", Qt::QueuedConnection);-
212}-
213-
214void QGraphicsSceneBspTreeIndexPrivate::addItem(QGraphicsItem *item, bool recursive)-
215{-
216 if (!item)-
217 return;-
218-
219-
220 purgeRemovedItems();-
221-
222-
223-
224 item->d_ptr->globalStackingOrder = -1;-
225 invalidateSortCache();-
226-
227-
228-
229-
230 if (item->d_ptr->index == -1) {-
231 ((!(!unindexedItems.contains(item))) ? qt_assert("!unindexedItems.contains(item)",__FILE__,313321) : qt_noop());-
232 unindexedItems << item;-
233 startIndexTimer(0);-
234 } else {-
235 ((!(indexedItems.contains(item))) ? qt_assert("indexedItems.contains(item)",__FILE__,317325) : qt_noop());-
236 QMessageLogger(__FILE__, 318326, __PRETTY_FUNCTION__).warning("QGraphicsSceneBspTreeIndex::addItem: item has already been added to this BSP");-
237 }-
238-
239 if (recursive) {-
240 for (int i = 0; i < item->d_ptr->children.size(); ++i)-
241 addItem(item->d_ptr->children.at(i), recursive);-
242 }-
243}-
244-
245void QGraphicsSceneBspTreeIndexPrivate::removeItem(QGraphicsItem *item, bool recursive,-
246 bool moveToUnindexedItems)-
247{-
248 if (!item)-
249 return;-
250-
251 if (item->d_ptr->index != -1) {-
252 ((!(item->d_ptr->index < indexedItems.size())) ? qt_assert("item->d_ptr->index < indexedItems.size()",__FILE__,334342) : qt_noop());-
253 ((!(indexedItems.at(item->d_ptr->index) == item)) ? qt_assert("indexedItems.at(item->d_ptr->index) == item",__FILE__,335343) : qt_noop());-
254 ((!(!item->d_ptr->itemDiscovered)) ? qt_assert("!item->d_ptr->itemDiscovered",__FILE__,336344) : qt_noop());-
255 freeItemIndexes << item->d_ptr->index;-
256 indexedItems[item->d_ptr->index] = 0;-
257 item->d_ptr->index = -1;-
258-
259 if (item->d_ptr->itemIsUntransformable()) {-
260 untransformableItems.removeOne(item);-
261 } else if (item->d_ptr->inDestructor) {-
262-
263 purgePending = true;-
264 removedItems << item;-
265 } else if (!(item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren-
266 || item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren)) {-
267 bsp.removeItem(item, item->d_ptr->sceneEffectiveBoundingRect());-
268 }-
269 } else {-
270 unindexedItems.removeOne(item);-
271 }-
272 invalidateSortCache();-
273-
274 ((!(item->d_ptr->index == -1)) ? qt_assert("item->d_ptr->index == -1",__FILE__,356364) : qt_noop());-
275 ((!(!indexedItems.contains(item))) ? qt_assert("!indexedItems.contains(item)",__FILE__,357365) : qt_noop());-
276 ((!(!unindexedItems.contains(item))) ? qt_assert("!unindexedItems.contains(item)",__FILE__,358366) : qt_noop());-
277 ((!(!untransformableItems.contains(item))) ? qt_assert("!untransformableItems.contains(item)",__FILE__,359367) : qt_noop());-
278-
279 if (moveToUnindexedItems)-
280 addItem(item);-
281-
282 if (recursive) {-
283 for (int i = 0; i < item->d_ptr->children.size(); ++i)-
284 removeItem(item->d_ptr->children.at(i), recursive, moveToUnindexedItems);-
285 }-
286}-
287-
288QList<QGraphicsItem *> QGraphicsSceneBspTreeIndexPrivate::estimateItems(const QRectF &rect, Qt::SortOrder order,-
289 bool onlyTopLevelItems)-
290{-
291 QGraphicsSceneBspTreeIndex * const q = q_func();-
292 if (onlyTopLevelItems && rect.isNull())-
293 return q->QGraphicsSceneIndex::estimateTopLevelItems(rect, order);-
294-
295 purgeRemovedItems();-
296 _q_updateSortCache();-
297 ((!(unindexedItems.isEmpty())) ? qt_assert("unindexedItems.isEmpty()",__FILE__,379387) : qt_noop());-
298-
299 QList<QGraphicsItem *> rectItems = bsp.items(rect, onlyTopLevelItems);-
300 if (onlyTopLevelItems) {-
301 for (int i = 0; i < untransformableItems.size(); ++i) {-
302 QGraphicsItem *item = untransformableItems.at(i);-
303 if (!item->d_ptr->parent) {-
304 rectItems << item;-
305 } else {-
306 item = item->topLevelItem();-
307 if (!rectItems.contains(item))-
308 rectItems << item;-
309 }-
310 }-
311 } else {-
312 rectItems += untransformableItems;-
313 }-
314-
315 sortItems(&rectItems, order, sortCacheEnabled, onlyTopLevelItems);-
316 return rectItems;-
317}-
318-
319-
320-
321-
322-
323-
324void QGraphicsSceneBspTreeIndexPrivate::sortItems(QList<QGraphicsItem *> *itemList, Qt::SortOrder order,-
325 bool sortCacheEnabled, bool onlyTopLevelItems)-
326{-
327 if (order == Qt::SortOrder(-1))-
328 return;-
329-
330 if (onlyTopLevelItems) {-
331 if (order == Qt::DescendingOrder)-
332 std::sort(itemList->begin(), itemList->end(), qt_closestLeaf);-
333 else if (order == Qt::AscendingOrder)-
334 std::sort(itemList->begin(), itemList->end(), qt_notclosestLeaf);-
335 return;-
336 }-
337-
338 if (sortCacheEnabled) {-
339 if (order == Qt::DescendingOrder) {-
340 std::sort(itemList->begin(), itemList->end(), closestItemFirst_withCache);-
341 } else if (order == Qt::AscendingOrder) {-
342 std::sort(itemList->begin(), itemList->end(), closestItemLast_withCache);-
343 }-
344 } else {-
345 if (order == Qt::DescendingOrder) {-
346 std::sort(itemList->begin(), itemList->end(), qt_closestItemFirst);-
347 } else if (order == Qt::AscendingOrder) {-
348 std::sort(itemList->begin(), itemList->end(), qt_closestItemLast);-
349 }-
350 }-
351}-
352-
353-
354-
355-
356QGraphicsSceneBspTreeIndex::QGraphicsSceneBspTreeIndex(QGraphicsScene *scene)-
357 : QGraphicsSceneIndex(*new QGraphicsSceneBspTreeIndexPrivate(scene), scene)-
358{-
359-
360}-
361-
362QGraphicsSceneBspTreeIndex::~QGraphicsSceneBspTreeIndex()-
363{-
364 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
365 for (int i = 0; i < d->indexedItems.size(); ++i) {-
366-
367 if (QGraphicsItem *item = d->indexedItems.at(i)) {-
368 ((!(!item->d_ptr->itemDiscovered)) ? qt_assert("!item->d_ptr->itemDiscovered",__FILE__,450458) : qt_noop());-
369 item->d_ptr->index = -1;-
370 }-
371 }-
372}-
373-
374-
375-
376-
377-
378void QGraphicsSceneBspTreeIndex::clear()-
379{-
380 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
381 d->bsp.clear();-
382 d->lastItemCount = 0;-
383 d->freeItemIndexes.clear();-
384 for (int i = 0; i < d->indexedItems.size(); ++i) {-
385-
386 if (QGraphicsItem *item = d->indexedItems.at(i)) {-
387 ((!(!item->d_ptr->itemDiscovered)) ? qt_assert("!item->d_ptr->itemDiscovered",__FILE__,469477) : qt_noop());-
388 item->d_ptr->index = -1;-
389 }-
390 }-
391 d->indexedItems.clear();-
392 d->unindexedItems.clear();-
393 d->untransformableItems.clear();-
394 d->regenerateIndex = true;-
395}-
396-
397-
398-
399-
400void QGraphicsSceneBspTreeIndex::addItem(QGraphicsItem *item)-
401{-
402 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
403 d->addItem(item);-
404}-
405-
406-
407-
408-
409void QGraphicsSceneBspTreeIndex::removeItem(QGraphicsItem *item)-
410{-
411 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
412 d->removeItem(item);-
413}-
414-
415-
416-
417-
418-
419void QGraphicsSceneBspTreeIndex::prepareBoundingRectChange(const QGraphicsItem *item)-
420{-
421 if (!item)-
422 return;-
423-
424 if (item->d_ptr->index == -1 || item->d_ptr->itemIsUntransformable()-
425 || (item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren-
426 || item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren)) {-
427 return;-
428 }-
429-
430 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
431 QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);-
432 d->removeItem(thatItem, false, true);-
433 for (int i = 0; i < item->d_ptr->children.size(); ++i)-
434 prepareBoundingRectChange(item->d_ptr->children.at(i));-
435}-
436QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateItems(const QRectF &rect, Qt::SortOrder order) const-
437{-
438 const QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
439 return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order);-
440}-
441-
442QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::estimateTopLevelItems(const QRectF &rect, Qt::SortOrder order) const-
443{-
444 const QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
445 return const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->estimateItems(rect, order, true);-
446}-
447-
448-
449-
450-
451-
452-
453QList<QGraphicsItem *> QGraphicsSceneBspTreeIndex::items(Qt::SortOrder order) const-
454{-
455 const QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
456 const_cast<QGraphicsSceneBspTreeIndexPrivate*>(d)->purgeRemovedItems();-
457 QList<QGraphicsItem *> itemList;-
458 ifitemList.reserve(d->freeItemIndexesindexedItems.isEmpty()) {-
if (size() + d->unindexedItems.isEmpty()) {
itemListsize());
459-
460-
461-
462 QGraphicsItem *null = d->indexedItemsnullptr;-
463-
464-
465 } else {-
itemList =std::remove_copy(d->indexedItems+.cbegin(), d->unindexedItems;
}
} else {
forindexedItems.cend(),
466 std::back_inserter(QForeachContainer<typename QtPrivateitemList), null);-
467 std::remove_reference<decltyperemove_copy(d->indexedItems +d->unindexedItems)>::type> _container_((d->indexedItems +.cbegin(), d->unindexedItems)); _container_.control && _container_.i != _container_.e; ++_container_.i, _container_.control ^= 1) for (QGraphicsItem *item = *_container_.i; _container_.control; _container_.control = 0) {-
ifcend(),
468 std::back_inserter(item)itemList<< item;-
}
}), null);
469-
470 d->sortItems(&itemList, order, d->sortCacheEnabled);-
471 return
never executed: return itemList;
 itemList;
never executed: return itemList;
0
472}-
473int QGraphicsSceneBspTreeIndex::bspTreeDepth() const-
474{-
475 const QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
476 return d->bspTreeDepth;-
477}-
478-
479void QGraphicsSceneBspTreeIndex::setBspTreeDepth(int depth)-
480{-
481 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
482 if (d->bspTreeDepth == depth)-
483 return;-
484 d->bspTreeDepth = depth;-
485 d->resetIndex();-
486}-
487-
488-
489-
490-
491-
492-
493-
494void QGraphicsSceneBspTreeIndex::updateSceneRect(const QRectF &rect)-
495{-
496 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
497 d->sceneRect = rect;-
498 d->resetIndex();-
499}-
500-
501-
502-
503-
504-
505-
506-
507void QGraphicsSceneBspTreeIndex::itemChange(const QGraphicsItem *item, QGraphicsItem::GraphicsItemChange change, const void *const value)-
508{-
509 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
510 switch (change) {-
511 case QGraphicsItem::ItemFlagsChange: {-
512-
513 QGraphicsItem::GraphicsItemFlags newFlags = *static_cast<const QGraphicsItem::GraphicsItemFlags *>(value);-
514 bool ignoredTransform = item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations;-
515 bool willIgnoreTransform = newFlags & QGraphicsItem::ItemIgnoresTransformations;-
516 bool clipsChildren = item->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape-
517 || item->d_ptr->flags & QGraphicsItem::ItemContainsChildrenInShape;-
518 bool willClipChildren = newFlags & QGraphicsItem::ItemClipsChildrenToShape-
519 || newFlags & QGraphicsItem::ItemContainsChildrenInShape;-
520 if ((ignoredTransform != willIgnoreTransform) || (clipsChildren != willClipChildren)) {-
521 QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);-
522-
523-
524-
525-
526 d->removeItem(thatItem, true, true);-
527 }-
528 break;-
529 }-
530 case QGraphicsItem::ItemZValueChange:-
531 d->invalidateSortCache();-
532 break;-
533 case QGraphicsItem::ItemParentChange: {-
534 d->invalidateSortCache();-
535-
536 const QGraphicsItem *newParent = static_cast<const QGraphicsItem *>(value);-
537 bool ignoredTransform = item->d_ptr->itemIsUntransformable();-
538 bool willIgnoreTransform = (item->d_ptr->flags & QGraphicsItem::ItemIgnoresTransformations)-
539 || (newParent && newParent->d_ptr->itemIsUntransformable());-
540 bool ancestorClippedChildren = item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren-
541 || item->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren;-
542 bool ancestorWillClipChildren = newParent-
543 && ((newParent->d_ptr->flags & QGraphicsItem::ItemClipsChildrenToShape-
544 || newParent->d_ptr->flags & QGraphicsItem::ItemContainsChildrenInShape)-
545 || (newParent->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorClipsChildren-
546 || newParent->d_ptr->ancestorFlags & QGraphicsItemPrivate::AncestorContainsChildren));-
547 if ((ignoredTransform != willIgnoreTransform) || (ancestorClippedChildren != ancestorWillClipChildren)) {-
548 QGraphicsItem *thatItem = const_cast<QGraphicsItem *>(item);-
549-
550-
551-
552-
553 d->removeItem(thatItem, true, true);-
554 }-
555 break;-
556 }-
557 default:-
558 break;-
559 }-
560}-
561-
562-
563-
564-
565-
566-
567-
568bool QGraphicsSceneBspTreeIndex::event(QEvent *event)-
569{-
570 QGraphicsSceneBspTreeIndexPrivate * const d = d_func();-
571 if (event->type() == QEvent::Timer) {-
572 if (d->indexTimerId && static_cast<QTimerEvent *>(event)->timerId() == d->indexTimerId) {-
573 if (d->restartIndexTimer) {-
574 d->restartIndexTimer = false;-
575 } else {-
576-
577 d->_q_updateIndex();-
578 }-
579 }-
580 }-
581 return QObject::event(event);-
582}-
583-
584-
585-
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9