1	/*
2	SPDX-FileCopyrightText: 2009 Stephen Kelly <steveire@gmail.com>
3	SPDX-FileCopyrightText: 2016 Ableton AG <info@ableton.com>
4	SPDX-FileContributor: Stephen Kelly <stephen.kelly@ableton.com>
5
6	SPDX-License-Identifier: LGPL-2.0-or-later
7	*/
8
9	#include "kselectionproxymodel.h"
10
11	#include <QItemSelectionRange>
12	#include <QPointer>
13	#include <QStringList>
14
15	#include "kbihash_p.h"
16	#include "kmodelindexproxymapper.h"
17	#include "kvoidpointerfactory_p.h"
18
19	typedef KBiHash<QPersistentModelIndex, QModelIndex> SourceProxyIndexMapping;
20	typedef KBiHash<void *, QModelIndex> ParentMapping;
21	typedef KHash2Map<QPersistentModelIndex, int> SourceIndexProxyRowMapping;
22
23	/**
24	Return true if @p idx is a descendant of one of the indexes in @p list.
25	Note that this returns false if @p list contains @p idx.
26	*/
27	template<typename ModelIndex>
28	bool isDescendantOf(const QList<ModelIndex> &list, const QModelIndex &idx)
29	{
30	if (!idx.isValid()) {
31	return false;
32	}
33
34	if (list.contains(idx)) {
35	return false;
36	}
37
38	QModelIndex parent = idx.parent();
39	while (parent.isValid()) {
40	if (list.contains(parent)) {
41	return true;
42	}
43	parent = parent.parent();
44	}
45	return false;
46	}
47
48	static bool isDescendantOf(const QItemSelection &selection, const QModelIndex &descendant)
49	{
50	if (!descendant.isValid()) {
51	return false;
52	}
53
54	if (selection.contains(index: descendant)) {
55	return false;
56	}
57
58	QModelIndex parent = descendant.parent();
59	while (parent.isValid()) {
60	if (selection.contains(index: parent)) {
61	return true;
62	}
63
64	parent = parent.parent();
65	}
66	return false;
67	}
68
69	static bool isDescendantOf(const QItemSelectionRange &range, const QModelIndex &descendant)
70	{
71	if (!descendant.isValid()) {
72	return false;
73	}
74
75	if (range.contains(index: descendant)) {
76	return false;
77	}
78
79	QModelIndex parent = descendant.parent();
80	while (parent.isValid()) {
81	if (range.contains(index: parent)) {
82	return true;
83	}
84
85	parent = parent.parent();
86	}
87	return false;
88	}
89
90	static int _getRootListRow(const QList<QModelIndexList> &rootAncestors, const QModelIndex &index)
91	{
92	QModelIndex commonParent = index;
93	QModelIndex youngestAncestor;
94
95	int firstCommonParent = -1;
96	int bestParentRow = -1;
97	while (commonParent.isValid()) {
98	youngestAncestor = commonParent;
99	commonParent = commonParent.parent();
100
101	for (int i = 0; i < rootAncestors.size(); ++i) {
102	const QModelIndexList ancestorList = rootAncestors.at(i);
103
104	const int parentRow = ancestorList.indexOf(t: commonParent);
105
106	if (parentRow < 0) {
107	continue;
108	}
109
110	if (parentRow > bestParentRow) {
111	firstCommonParent = i;
112	bestParentRow = parentRow;
113	}
114	}
115
116	if (firstCommonParent >= 0) {
117	break;
118	}
119	}
120
121	// If @p list is non-empty, the invalid QModelIndex() will at least be found in ancestorList.
122	Q_ASSERT(firstCommonParent >= 0);
123
124	const QModelIndexList firstAnsList = rootAncestors.at(i: firstCommonParent);
125
126	const QModelIndex eldestSibling = firstAnsList.value(i: bestParentRow + 1);
127
128	if (eldestSibling.isValid()) {
129	// firstCommonParent is a sibling of one of the ancestors of @p index.
130	// It is the first index to share a common parent with one of the ancestors of @p index.
131	if (eldestSibling.row() >= youngestAncestor.row()) {
132	return firstCommonParent;
133	}
134	}
135
136	int siblingOffset = 1;
137
138	// The same commonParent might be common to several root indexes.
139	// If this is the last in the list, it's the only match. We instruct the model
140	// to insert the new index after it ( + siblingOffset).
141	if (rootAncestors.size() <= firstCommonParent + siblingOffset) {
142	return firstCommonParent + siblingOffset;
143	}
144
145	// A
146	// - B
147	// - C
148	// - D
149	// - E
150	// F
151	//
152	// F is selected, then C then D. When inserting D into the model, the commonParent is B (the parent of C).
153	// The next existing sibling of B is F (in the proxy model). bestParentRow will then refer to an index on
154	// the level of a child of F (which doesn't exist - Boom!). If it doesn't exist, then we've already found
155	// the place to insert D
156	QModelIndexList ansList = rootAncestors.at(i: firstCommonParent + siblingOffset);
157	if (ansList.size() <= bestParentRow) {
158	return firstCommonParent + siblingOffset;
159	}
160
161	QModelIndex nextParent = ansList.at(i: bestParentRow);
162	while (nextParent == commonParent) {
163	if (ansList.size() < bestParentRow + 1)
164	// If the list is longer, it means that at the end of it is a descendant of the new index.
165	// We insert the ancestors items first in that case.
166	{
167	break;
168	}
169
170	const QModelIndex nextSibling = ansList.value(i: bestParentRow + 1);
171
172	if (!nextSibling.isValid()) {
173	continue;
174	}
175
176	if (youngestAncestor.row() <= nextSibling.row()) {
177	break;
178	}
179
180	siblingOffset++;
181
182	if (rootAncestors.size() <= firstCommonParent + siblingOffset) {
183	break;
184	}
185
186	ansList = rootAncestors.at(i: firstCommonParent + siblingOffset);
187
188	// In the scenario above, E is selected after D, causing this loop to be entered,
189	// and requiring a similar result if the next sibling in the proxy model does not have children.
190	if (ansList.size() <= bestParentRow) {
191	break;
192	}
193
194	nextParent = ansList.at(i: bestParentRow);
195	}
196
197	return firstCommonParent + siblingOffset;
198	}
199
200	/**
201	Determines the correct location to insert @p index into @p list.
202	*/
203	static int getRootListRow(const QList<QPersistentModelIndex> &list, const QModelIndex &index)
204	{
205	if (!index.isValid()) {
206	return -1;
207	}
208
209	if (list.isEmpty()) {
210	return 0;
211	}
212
213	// What's going on?
214	// Consider a tree like
215	//
216	// A
217	// - B
218	// - - C
219	// - - - D
220	// - E
221	// - F
222	// - - G
223	// - - - H
224	// - I
225	// - - J
226	// - K
227	//
228	// If D, E and J are already selected, and H is newly selected, we need to put H between E and J in the proxy model.
229	// To figure that out, we create a list for each already selected index of its ancestors. Then,
230	// we climb the ancestors of H until we reach an index with siblings which have a descendant
231	// selected (F above has siblings B, E and I which have descendants which are already selected).
232	// Those child indexes are traversed to find the right sibling to put F beside.
233	//
234	// i.e., new items are inserted in the expected location.
235
236	QList<QModelIndexList> rootAncestors;
237	for (const auto &root : list) {
238	QModelIndexList ancestors;
239	ancestors.append(t: root);
240	QModelIndex parent = root.parent();
241	while (parent.isValid()) {
242	ancestors.prepend(t: parent);
243	parent = parent.parent();
244	}
245	ancestors.prepend(t: QModelIndex());
246	rootAncestors.append(t: ancestors);
247	}
248	return _getRootListRow(rootAncestors, index);
249	}
250
251	/**
252	Returns a selection in which no descendants of selected indexes are also themselves selected.
253	For example,
254	@code
255	A
256	- B
257	C
258	D
259	@endcode
260	If A, B and D are selected in @p selection, the returned selection contains only A and D.
261	*/
262	static QItemSelection getRootRanges(const QItemSelection &_selection)
263	{
264	QItemSelection rootSelection;
265	QItemSelection selection = _selection;
266	QList<QItemSelectionRange>::iterator it = selection.begin();
267	while (it != selection.end()) {
268	if (!it->topLeft().parent().isValid()) {
269	rootSelection.append(t: *it);
270	it = selection.erase(pos: it);
271	} else {
272	++it;
273	}
274	}
275
276	it = selection.begin();
277	while (it != selection.end()) {
278	const QItemSelectionRange range = *it;
279	it = selection.erase(pos: it);
280
281	if (isDescendantOf(selection: rootSelection, descendant: range.topLeft()) || isDescendantOf(selection, descendant: range.topLeft())) {
282	continue;
283	}
284
285	rootSelection << range;
286	}
287	return rootSelection;
288	}
289
290	/**
291	*/
292	struct RangeLessThan {
293	bool operator()(const QItemSelectionRange &left, const QItemSelectionRange &right) const
294	{
295	if (right.model() == left.model()) {
296	// parent has to be calculated, so we only do so once.
297	const QModelIndex topLeftParent = left.parent();
298	const QModelIndex otherTopLeftParent = right.parent();
299	if (topLeftParent == otherTopLeftParent) {
300	if (right.top() == left.top()) {
301	if (right.left() == left.left()) {
302	if (right.bottom() == left.bottom()) {
303	return left.right() < right.right();
304	}
305	return left.bottom() < right.bottom();
306	}
307	return left.left() < right.left();
308	}
309	return left.top() < right.top();
310	}
311	return topLeftParent < otherTopLeftParent;
312	}
313	return left.model() < right.model();
314	}
315	};
316
317	static QItemSelection stableNormalizeSelection(const QItemSelection &selection)
318	{
319	if (selection.size() <= 1) {
320	return selection;
321	}
322
323	QItemSelection::const_iterator it = selection.begin();
324	const QItemSelection::const_iterator end = selection.end();
325
326	Q_ASSERT(it != end);
327	QItemSelection::const_iterator scout = it + 1;
328
329	QItemSelection result;
330	while (scout != end) {
331	Q_ASSERT(it != end);
332	int bottom = it->bottom();
333	while (scout != end && it->parent() == scout->parent() && bottom + 1 == scout->top()) {
334	bottom = scout->bottom();
335	++scout;
336	}
337	if (bottom != it->bottom()) {
338	const QModelIndex topLeft = it->topLeft();
339	result << QItemSelectionRange(topLeft, topLeft.sibling(arow: bottom, acolumn: it->right()));
340	}
341	Q_ASSERT(it != scout);
342	if (scout == end) {
343	break;
344	}
345	if (it + 1 == scout) {
346	result << *it;
347	}
348	it = scout;
349	++scout;
350	if (scout == end) {
351	result << *it;
352	}
353	}
354	return result;
355	}
356
357	static QItemSelection kNormalizeSelection(QItemSelection selection)
358	{
359	if (selection.size() <= 1) {
360	return selection;
361	}
362
363	// KSelectionProxyModel has a strong assumption that
364	// the views always select rows, so usually the
365	// @p selection here contains ranges that span all
366	// columns. However, if a QSortFilterProxyModel
367	// is used too, it splits up the complete ranges into
368	// one index per range. That confuses the data structures
369	// held by this proxy (which keeps track of indexes in the
370	// first column). As this proxy already assumes that if the
371	// zeroth column is selected, then its entire row is selected,
372	// we can safely remove the ranges which do not include
373	// column 0 without a loss of functionality.
374	QItemSelection::iterator i = selection.begin();
375	while (i != selection.end()) {
376	if (i->left() > 0) {
377	i = selection.erase(pos: i);
378	} else {
379	++i;
380	}
381	}
382
383	RangeLessThan lt;
384	std::sort(first: selection.begin(), last: selection.end(), comp: lt);
385	return stableNormalizeSelection(selection);
386	}
387
388	class KSelectionProxyModelPrivate
389	{
390	public:
391	KSelectionProxyModelPrivate(KSelectionProxyModel *model)
392	: q_ptr(model)
393	, m_indexMapper(nullptr)
394	, m_startWithChildTrees(false)
395	, m_omitChildren(false)
396	, m_omitDescendants(false)
397	, m_includeAllSelected(false)
398	, m_rowsInserted(false)
399	, m_rowsRemoved(false)
400	, m_recreateFirstChildMappingOnRemoval(false)
401	, m_rowsMoved(false)
402	, m_resetting(false)
403	, m_sourceModelResetting(false)
404	, m_doubleResetting(false)
405	, m_layoutChanging(false)
406	, m_ignoreNextLayoutAboutToBeChanged(false)
407	, m_ignoreNextLayoutChanged(false)
408	, m_selectionModel(nullptr)
409	, m_filterBehavior(KSelectionProxyModel::InvalidBehavior)
410	{
411	}
412
413	Q_DECLARE_PUBLIC(KSelectionProxyModel)
414	KSelectionProxyModel *const q_ptr;
415
416	// A unique id is generated for each parent. It is used for the internalPointer of its children in the proxy
417	// This is used to store a unique id for QModelIndexes in the proxy which have children.
418	// If an index newly gets children it is added to this hash. If its last child is removed it is removed from this map.
419	// If this map contains an index, that index hasChildren(). This hash is populated when new rows are inserted in the
420	// source model, or a new selection is made.
421	mutable ParentMapping m_parentIds;
422	// This mapping maps indexes with children in the source to indexes with children in the proxy.
423	// The order of indexes in this list is not relevant.
424	mutable SourceProxyIndexMapping m_mappedParents;
425
426	KVoidPointerFactory<> m_voidPointerFactory;
427
428	/**
429	Keeping Persistent indexes from this model in this model breaks in certain situations
430	such as after source insert, but before calling endInsertRows in this model. In such a state,
431	the persistent indexes are not updated, but the methods assume they are already up-to-date.
432
433	Instead of using persistentindexes for proxy indexes in m_mappedParents, we maintain them ourselves with this method.
434
435	m_mappedParents and m_parentIds are affected.
436
437	@p parent and @p start refer to the proxy model. Any rows >= @p start will be updated.
438	@p offset is the amount that affected indexes will be changed.
439	*/
440	void updateInternalIndexes(const QModelIndex &parent, int start, int offset);
441
442	/**
443	* Updates stored indexes in the proxy. Any proxy row >= @p start is changed by @p offset.
444	*
445	* This is only called to update indexes in the top level of the proxy. Most commonly that is
446	*
447	* m_mappedParents, m_parentIds and m_mappedFirstChildren are affected.
448	*/
449	void updateInternalTopIndexes(int start, int offset);
450
451	void updateFirstChildMapping(const QModelIndex &parent, int offset);
452
453	bool isFlat() const
454	{
455	return m_omitChildren || (m_omitDescendants && m_startWithChildTrees);
456	}
457
458	/**
459	* Tries to ensure that @p parent is a mapped parent in the proxy.
460	* Returns true if parent is mappable in the model, and false otherwise.
461	*/
462	bool ensureMappable(const QModelIndex &parent) const;
463	bool parentIsMappable(const QModelIndex &parent) const
464	{
465	return parentAlreadyMapped(parent) || m_rootIndexList.contains(t: parent);
466	}
467
468	/**
469	* Maps @p parent to source if it is already mapped, and otherwise returns an invalid QModelIndex.
470	*/
471	QModelIndex mapFromSource(const QModelIndex &parent) const;
472
473	/**
474	Creates mappings in m_parentIds and m_mappedParents between the source and the proxy.
475
476	This is not recursive
477	*/
478	void createParentMappings(const QModelIndex &parent, int start, int end) const;
479	void createFirstChildMapping(const QModelIndex &parent, int proxyRow) const;
480	bool firstChildAlreadyMapped(const QModelIndex &firstChild) const;
481	bool parentAlreadyMapped(const QModelIndex &parent) const;
482	void removeFirstChildMappings(int start, int end);
483	void removeParentMappings(const QModelIndex &parent, int start, int end);
484
485	/**
486	Given a QModelIndex in the proxy, return the corresponding QModelIndex in the source.
487
488	This method works only if the index has children in the proxy model which already has a mapping from the source.
489
490	This means that if the proxy is a flat list, this method will always return QModelIndex(). Additionally, it means that m_mappedParents is not populated
491	automatically and must be populated manually.
492
493	No new mapping is created by this method.
494	*/
495	QModelIndex mapParentToSource(const QModelIndex &proxyParent) const;
496
497	/**
498	Given a QModelIndex in the source model, return the corresponding QModelIndex in the proxy.
499
500	This method works only if the index has children in the proxy model which already has a mapping from the source.
501
502	No new mapping is created by this method.
503	*/
504	QModelIndex mapParentFromSource(const QModelIndex &sourceParent) const;
505
506	QModelIndex mapTopLevelToSource(int row, int column) const;
507	QModelIndex mapTopLevelFromSource(const QModelIndex &sourceIndex) const;
508	QModelIndex createTopLevelIndex(int row, int column) const;
509	int topLevelRowCount() const;
510
511	void *parentId(const QModelIndex &proxyParent) const
512	{
513	return m_parentIds.rightToLeft(u: proxyParent);
514	}
515	QModelIndex parentForId(void *id) const
516	{
517	return m_parentIds.leftToRight(t: id);
518	}
519
520	// Only populated if m_startWithChildTrees.
521
522	mutable SourceIndexProxyRowMapping m_mappedFirstChildren;
523
524	// Source list is the selection in the source model.
525	QList<QPersistentModelIndex> m_rootIndexList;
526
527	KModelIndexProxyMapper *m_indexMapper;
528
529	QPair<int, int> beginRemoveRows(const QModelIndex &parent, int start, int end) const;
530	QPair<int, int> beginInsertRows(const QModelIndex &parent, int start, int end) const;
531	void endRemoveRows(const QModelIndex &sourceParent, int proxyStart, int proxyEnd);
532	void endInsertRows(const QModelIndex &parent, int start, int end);
533
534	void sourceRowsAboutToBeInserted(const QModelIndex &parent, int start, int end);
535	void sourceRowsInserted(const QModelIndex &parent, int start, int end);
536	void sourceRowsAboutToBeRemoved(const QModelIndex &parent, int start, int end);
537	void sourceRowsRemoved(const QModelIndex &parent, int start, int end);
538	void sourceRowsAboutToBeMoved(const QModelIndex &parent, int start, int end, const QModelIndex &destParent, int destRow);
539	void sourceRowsMoved(const QModelIndex &parent, int start, int end, const QModelIndex &destParent, int destRow);
540	void sourceModelAboutToBeReset();
541	void sourceModelReset();
542	void sourceLayoutAboutToBeChanged();
543	void sourceLayoutChanged();
544	void emitContinuousRanges(const QModelIndex &sourceFirst, const QModelIndex &sourceLast, const QModelIndex &proxyFirst, const QModelIndex &proxyLast);
545	void sourceDataChanged(const QModelIndex &topLeft, const QModelIndex &bottomRight);
546
547	void removeSelectionFromProxy(const QItemSelection &selection);
548
549	void selectionChanged(const QItemSelection &selected, const QItemSelection &deselected);
550	void sourceModelDestroyed();
551
552	void resetInternalData();
553
554	bool rootWillBeRemoved(const QItemSelection &selection, const QModelIndex &root);
555
556	/**
557	When items are inserted or removed in the m_startWithChildTrees configuration,
558	this method helps find the startRow for use emitting the signals from the proxy.
559	*/
560	int getProxyInitialRow(const QModelIndex &parent) const;
561
562	/**
563	If m_startWithChildTrees is true, this method returns the row in the proxy model to insert newIndex
564	items.
565
566	This is a special case because the items above rootListRow in the list are not in the model, but
567	their children are. Those children must be counted.
568
569	If m_startWithChildTrees is false, this method returns @p rootListRow.
570	*/
571	int getTargetRow(int rootListRow);
572
573	/**
574	Inserts the indexes in @p list into the proxy model.
575	*/
576	void insertSelectionIntoProxy(const QItemSelection &selection);
577
578	bool m_startWithChildTrees;
579	bool m_omitChildren;
580	bool m_omitDescendants;
581	bool m_includeAllSelected;
582	bool m_rowsInserted;
583	bool m_rowsRemoved;
584	bool m_recreateFirstChildMappingOnRemoval;
585	QPair<int, int> m_proxyRemoveRows;
586	bool m_rowsMoved;
587	bool m_resetting;
588	bool m_sourceModelResetting;
589	bool m_doubleResetting;
590	bool m_layoutChanging;
591	bool m_ignoreNextLayoutAboutToBeChanged;
592	bool m_ignoreNextLayoutChanged;
593	QPointer<QItemSelectionModel> m_selectionModel;
594
595	KSelectionProxyModel::FilterBehavior m_filterBehavior;
596
597	QList<QPersistentModelIndex> m_layoutChangePersistentIndexes;
598	QModelIndexList m_proxyIndexes;
599
600	struct PendingSelectionChange {
601	PendingSelectionChange()
602	{
603	}
604	PendingSelectionChange(const QItemSelection &selected_, const QItemSelection &deselected_)
605	: selected(selected_)
606	, deselected(deselected_)
607	{
608	}
609	QItemSelection selected;
610	QItemSelection deselected;
611	};
612	QList<PendingSelectionChange> m_pendingSelectionChanges;
613	QMetaObject::Connection selectionModelModelAboutToBeResetConnection;
614	QMetaObject::Connection selectionModelModelResetConnection;
615	};
616
617	void KSelectionProxyModelPrivate::emitContinuousRanges(const QModelIndex &sourceFirst,
618	const QModelIndex &sourceLast,
619	const QModelIndex &proxyFirst,
620	const QModelIndex &proxyLast)
621	{
622	Q_Q(KSelectionProxyModel);
623
624	Q_ASSERT(sourceFirst.model() == q->sourceModel());
625	Q_ASSERT(sourceLast.model() == q->sourceModel());
626	Q_ASSERT(proxyFirst.model() == q);
627	Q_ASSERT(proxyLast.model() == q);
628
629	const int proxyRangeSize = proxyLast.row() - proxyFirst.row();
630	const int sourceRangeSize = sourceLast.row() - sourceFirst.row();
631
632	if (proxyRangeSize == sourceRangeSize) {
633	Q_EMIT q->dataChanged(topLeft: proxyFirst, bottomRight: proxyLast);
634	return;
635	}
636
637	// TODO: Loop to skip descendant ranges.
638	// int lastRow;
639	//
640	// const QModelIndex sourceHalfWay = sourceFirst.sibling(sourceFirst.row() + (sourceRangeSize / 2));
641	// const QModelIndex proxyHalfWay = proxyFirst.sibling(proxyFirst.row() + (proxyRangeSize / 2));
642	// const QModelIndex mappedSourceHalfway = q->mapToSource(proxyHalfWay);
643	//
644	// const int halfProxyRange = mappedSourceHalfway.row() - proxyFirst.row();
645	// const int halfSourceRange = sourceHalfWay.row() - sourceFirst.row();
646	//
647	// if (proxyRangeSize == sourceRangeSize)
648	// {
649	// Q_EMIT q->dataChanged(proxyFirst, proxyLast.sibling(proxyFirst.row() + proxyRangeSize, proxyLast.column()));
650	// return;
651	// }
652
653	Q_EMIT q->dataChanged(topLeft: proxyFirst, bottomRight: proxyLast);
654	}
655
656	void KSelectionProxyModelPrivate::sourceDataChanged(const QModelIndex &topLeft, const QModelIndex &bottomRight)
657	{
658	Q_Q(KSelectionProxyModel);
659
660	Q_ASSERT(topLeft.model() == q->sourceModel());
661	Q_ASSERT(bottomRight.model() == q->sourceModel());
662
663	const QModelIndex sourceRangeParent = topLeft.parent();
664	if (!sourceRangeParent.isValid() && m_startWithChildTrees && !m_rootIndexList.contains(t: sourceRangeParent)) {
665	return;
666	}
667
668	const QModelIndex proxyTopLeft = q->mapFromSource(sourceIndex: topLeft);
669	const QModelIndex proxyBottomRight = q->mapFromSource(sourceIndex: bottomRight);
670
671	const QModelIndex proxyRangeParent = proxyTopLeft.parent();
672
673	if (!m_omitChildren && m_omitDescendants && m_startWithChildTrees && m_includeAllSelected) {
674	// ChildrenOfExactSelection
675	if (proxyTopLeft.isValid()) {
676	emitContinuousRanges(sourceFirst: topLeft, sourceLast: bottomRight, proxyFirst: proxyTopLeft, proxyLast: proxyBottomRight);
677	}
678	return;
679	}
680
681	if ((m_omitChildren && !m_startWithChildTrees && m_includeAllSelected) || (!proxyRangeParent.isValid() && !m_startWithChildTrees)) {
682	// Exact selection and SubTreeRoots and SubTrees in top level
683	// Emit continuous ranges.
684	QList<int> changedRows;
685	for (int row = topLeft.row(); row <= bottomRight.row(); ++row) {
686	const QModelIndex index = q->sourceModel()->index(row, column: topLeft.column(), parent: topLeft.parent());
687	const int idx = m_rootIndexList.indexOf(t: index);
688	if (idx != -1) {
689	changedRows.append(t: idx);
690	}
691	}
692	if (changedRows.isEmpty()) {
693	return;
694	}
695	int first = changedRows.first();
696	int previous = first;
697	QList<int>::const_iterator it = changedRows.constBegin();
698	const QList<int>::const_iterator end = changedRows.constEnd();
699	for (; it != end; ++it) {
700	if (*it == previous + 1) {
701	++previous;
702	} else {
703	const QModelIndex _top = q->index(first, topLeft.column());
704	const QModelIndex _bottom = q->index(previous, bottomRight.column());
705	Q_EMIT q->dataChanged(topLeft: _top, bottomRight: _bottom);
706	previous = first = *it;
707	}
708	}
709	if (first != previous) {
710	const QModelIndex _top = q->index(first, topLeft.column());
711	const QModelIndex _bottom = q->index(previous, bottomRight.column());
712	Q_EMIT q->dataChanged(topLeft: _top, bottomRight: _bottom);
713	}
714	return;
715	}
716	if (proxyRangeParent.isValid()) {
717	if (m_omitChildren && !m_startWithChildTrees && !m_includeAllSelected)
718	// SubTreeRoots
719	{
720	return;
721	}
722	if (!proxyTopLeft.isValid()) {
723	return;
724	}
725	// SubTrees and SubTreesWithoutRoots
726	Q_EMIT q->dataChanged(topLeft: proxyTopLeft, bottomRight: proxyBottomRight);
727	return;
728	}
729
730	if (m_startWithChildTrees && !m_omitChildren && !m_includeAllSelected && !m_omitDescendants) {
731	// SubTreesWithoutRoots
732	if (proxyTopLeft.isValid()) {
733	Q_EMIT q->dataChanged(topLeft: proxyTopLeft, bottomRight: proxyBottomRight);
734	}
735	return;
736	}
737	}
738
739	void KSelectionProxyModelPrivate::sourceLayoutAboutToBeChanged()
740	{
741	Q_Q(KSelectionProxyModel);
742
743	if (m_ignoreNextLayoutAboutToBeChanged) {
744	m_ignoreNextLayoutAboutToBeChanged = false;
745	return;
746	}
747
748	if (m_rootIndexList.isEmpty()) {
749	return;
750	}
751
752	Q_EMIT q->layoutAboutToBeChanged();
753
754	QItemSelection selection;
755	for (const auto &rootIndex : std::as_const(t&: m_rootIndexList)) {
756	// This will be optimized later.
757	Q_EMIT q->rootIndexAboutToBeRemoved(removeRootIndex: rootIndex, KSelectionProxyModel::QPrivateSignal());
758	selection.append(t: QItemSelectionRange(rootIndex, rootIndex));
759	}
760
761	selection = kNormalizeSelection(selection);
762	Q_EMIT q->rootSelectionAboutToBeRemoved(selection, KSelectionProxyModel::QPrivateSignal());
763
764	QPersistentModelIndex srcPersistentIndex;
765	const auto lst = q->persistentIndexList();
766	for (const QModelIndex &proxyPersistentIndex : lst) {
767	m_proxyIndexes << proxyPersistentIndex;
768	Q_ASSERT(proxyPersistentIndex.isValid());
769	srcPersistentIndex = q->mapToSource(proxyIndex: proxyPersistentIndex);
770	Q_ASSERT(srcPersistentIndex.isValid());
771	m_layoutChangePersistentIndexes << srcPersistentIndex;
772	}
773
774	m_rootIndexList.clear();
775	}
776
777	void KSelectionProxyModelPrivate::sourceLayoutChanged()
778	{
779	Q_Q(KSelectionProxyModel);
780
781	if (m_ignoreNextLayoutChanged) {
782	m_ignoreNextLayoutChanged = false;
783	return;
784	}
785
786	if (!m_selectionModel || !m_selectionModel->hasSelection()) {
787	return;
788	}
789
790	// Handling this signal is slow.
791	// The problem is that anything can happen between emissions of layoutAboutToBeChanged and layoutChanged.
792	// We can't assume anything is the same about the structure anymore. items have been sorted, items which
793	// were parents before are now not, items which were not parents before now are, items which used to be the
794	// first child are now the Nth child and items which used to be the Nth child are now the first child.
795	// We effectively can't update our mapping because we don't have enough information to update everything.
796	// The only way we would have is if we take a persistent index of the entire source model
797	// on sourceLayoutAboutToBeChanged and then examine it here. That would be far too expensive.
798	// Instead we just have to clear the entire mapping and recreate it.
799
800	m_rootIndexList.clear();
801	m_mappedFirstChildren.clear();
802	m_mappedParents.clear();
803	m_parentIds.clear();
804
805	m_resetting = true;
806	m_layoutChanging = true;
807	selectionChanged(selected: m_selectionModel->selection(), deselected: QItemSelection());
808	m_resetting = false;
809	m_layoutChanging = false;
810
811	for (int i = 0; i < m_proxyIndexes.size(); ++i) {
812	q->changePersistentIndex(from: m_proxyIndexes.at(i), to: q->mapFromSource(sourceIndex: m_layoutChangePersistentIndexes.at(i)));
813	}
814
815	m_layoutChangePersistentIndexes.clear();
816	m_proxyIndexes.clear();
817
818	Q_EMIT q->layoutChanged();
819	}
820
821	void KSelectionProxyModelPrivate::resetInternalData()
822	{
823	m_rootIndexList.clear();
824	m_layoutChangePersistentIndexes.clear();
825	m_proxyIndexes.clear();
826	m_mappedParents.clear();
827	m_parentIds.clear();
828	m_mappedFirstChildren.clear();
829	m_voidPointerFactory.clear();
830	}
831
832	void KSelectionProxyModelPrivate::sourceModelDestroyed()
833	{
834	// There is very little we can do here.
835	resetInternalData();
836	m_resetting = false;
837	m_sourceModelResetting = false;
838	}
839
840	void KSelectionProxyModelPrivate::sourceModelAboutToBeReset()
841	{
842	Q_Q(KSelectionProxyModel);
843
844	// We might be resetting as a result of the selection source model resetting.
845	// If so we don't want to emit
846	// sourceModelAboutToBeReset
847	// sourceModelAboutToBeReset
848	// sourceModelReset
849	// sourceModelReset
850	// So we ensure that we just emit one.
851	if (m_resetting) {
852	// If both the source model and the selection source model are reset,
853	// We want to begin our reset before the first one is reset and end
854	// it after the second one is reset.
855	m_doubleResetting = true;
856	return;
857	}
858
859	q->beginResetModel();
860	m_resetting = true;
861	m_sourceModelResetting = true;
862	}
863
864	void KSelectionProxyModelPrivate::sourceModelReset()
865	{
866	Q_Q(KSelectionProxyModel);
867
868	if (m_doubleResetting) {
869	m_doubleResetting = false;
870	return;
871	}
872
873	resetInternalData();
874	m_sourceModelResetting = false;
875	m_resetting = false;
876	selectionChanged(selected: m_selectionModel->selection(), deselected: QItemSelection());
877	q->endResetModel();
878	}
879
880	int KSelectionProxyModelPrivate::getProxyInitialRow(const QModelIndex &parent) const
881	{
882	Q_ASSERT(m_rootIndexList.contains(parent));
883
884	// The difficulty here is that parent and parent.parent() might both be in the m_rootIndexList.
885
886	// - A
887	// - B
888	// - - C
889	// - - D
890	// - - - E
891
892	// Consider that B and D are selected. The proxy model is:
893
894	// - C
895	// - D
896	// - E
897
898	// Then D gets a new child at 0. In that case we require adding F between D and E.
899
900	// Consider instead that D gets removed. Then @p parent will be B.
901
902	Q_Q(const KSelectionProxyModel);
903
904	Q_ASSERT(parent.model() == q->sourceModel());
905
906	int parentPosition = m_rootIndexList.indexOf(t: parent);
907
908	QModelIndex parentAbove;
909
910	// If parentPosition == 0, then parent.parent() is not also in the model. (ordering is preserved)
911	while (parentPosition > 0) {
912	parentPosition--;
913
914	parentAbove = m_rootIndexList.at(i: parentPosition);
915	Q_ASSERT(parentAbove.isValid());
916
917	int rows = q->sourceModel()->rowCount(parent: parentAbove);
918	if (rows > 0) {
919	QModelIndex sourceIndexAbove = q->sourceModel()->index(row: rows - 1, column: 0, parent: parentAbove);
920	Q_ASSERT(sourceIndexAbove.isValid());
921	QModelIndex proxyChildAbove = mapFromSource(parent: sourceIndexAbove);
922	Q_ASSERT(proxyChildAbove.isValid());
923	return proxyChildAbove.row() + 1;
924	}
925	}
926	return 0;
927	}
928
929	void KSelectionProxyModelPrivate::updateFirstChildMapping(const QModelIndex &parent, int offset)
930	{
931	Q_Q(KSelectionProxyModel);
932
933	Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
934
935	static const int column = 0;
936	static const int row = 0;
937
938	const QPersistentModelIndex srcIndex = q->sourceModel()->index(row, column, parent);
939
940	const QPersistentModelIndex previousFirstChild = q->sourceModel()->index(row: offset, column, parent);
941
942	SourceIndexProxyRowMapping::left_iterator it = m_mappedFirstChildren.findLeft(t: previousFirstChild);
943	if (it == m_mappedFirstChildren.leftEnd()) {
944	return;
945	}
946
947	Q_ASSERT(srcIndex.isValid());
948	const int proxyRow = it.value();
949	Q_ASSERT(proxyRow >= 0);
950
951	m_mappedFirstChildren.eraseLeft(it);
952
953	// The proxy row in the mapping has already been updated by the offset in updateInternalTopIndexes
954	// so we restore it by applying the reverse.
955	m_mappedFirstChildren.insert(t: srcIndex, u: proxyRow - offset);
956	}
957
958	QPair<int, int> KSelectionProxyModelPrivate::beginInsertRows(const QModelIndex &parent, int start, int end) const
959	{
960	const QModelIndex proxyParent = mapFromSource(parent);
961
962	if (!proxyParent.isValid()) {
963	if (!m_startWithChildTrees) {
964	return qMakePair(value1: -1, value2: -1);
965	}
966
967	if (!m_rootIndexList.contains(t: parent)) {
968	return qMakePair(value1: -1, value2: -1);
969	}
970	}
971
972	if (!m_startWithChildTrees) {
973	// SubTrees
974	if (proxyParent.isValid()) {
975	return qMakePair(value1&: start, value2&: end);
976	}
977	return qMakePair(value1: -1, value2: -1);
978	}
979
980	if (!m_includeAllSelected && proxyParent.isValid()) {
981	// SubTreesWithoutRoots deeper than topLevel
982	return qMakePair(value1&: start, value2&: end);
983	}
984
985	if (!m_rootIndexList.contains(t: parent)) {
986	return qMakePair(value1: -1, value2: -1);
987	}
988
989	const int proxyStartRow = getProxyInitialRow(parent) + start;
990	return qMakePair(value1: proxyStartRow, value2: proxyStartRow + (end - start));
991	}
992
993	void KSelectionProxyModelPrivate::sourceRowsAboutToBeInserted(const QModelIndex &parent, int start, int end)
994	{
995	Q_Q(KSelectionProxyModel);
996
997	Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
998
999	if (!m_selectionModel || !m_selectionModel->hasSelection()) {
1000	return;
1001	}
1002
1003	if (m_omitChildren)
1004	// ExactSelection and SubTreeRoots
1005	{
1006	return;
1007	}
1008
1009	// topLevel insertions can be ignored because topLevel items would need to be selected to affect the proxy.
1010	if (!parent.isValid()) {
1011	return;
1012	}
1013
1014	QPair<int, int> pair = beginInsertRows(parent, start, end);
1015	if (pair.first == -1) {
1016	return;
1017	}
1018
1019	const QModelIndex proxyParent = m_startWithChildTrees ? QModelIndex() : mapFromSource(parent);
1020
1021	m_rowsInserted = true;
1022	q->beginInsertRows(parent: proxyParent, first: pair.first, last: pair.second);
1023	}
1024
1025	void KSelectionProxyModelPrivate::endInsertRows(const QModelIndex &parent, int start, int end)
1026	{
1027	Q_Q(const KSelectionProxyModel);
1028	const QModelIndex proxyParent = mapFromSource(parent);
1029	const int offset = end - start + 1;
1030
1031	const bool isNewParent = (q->sourceModel()->rowCount(parent) == offset);
1032
1033	if (m_startWithChildTrees && m_rootIndexList.contains(t: parent)) {
1034	const int proxyInitialRow = getProxyInitialRow(parent);
1035	Q_ASSERT(proxyInitialRow >= 0);
1036	const int proxyStartRow = proxyInitialRow + start;
1037
1038	updateInternalTopIndexes(start: proxyStartRow, offset);
1039	if (isNewParent) {
1040	createFirstChildMapping(parent, proxyRow: proxyStartRow);
1041	} else if (start == 0)
1042	// We already have a first child mapping, but what we have mapped is not the first child anymore
1043	// so we need to update it.
1044	{
1045	updateFirstChildMapping(parent, offset: end + 1);
1046	}
1047	} else {
1048	Q_ASSERT(proxyParent.isValid());
1049	if (!isNewParent) {
1050	updateInternalIndexes(parent: proxyParent, start, offset);
1051	} else {
1052	createParentMappings(parent: parent.parent(), start: parent.row(), end: parent.row());
1053	}
1054	}
1055	createParentMappings(parent, start, end);
1056	}
1057
1058	void KSelectionProxyModelPrivate::sourceRowsInserted(const QModelIndex &parent, int start, int end)
1059	{
1060	Q_Q(KSelectionProxyModel);
1061
1062	Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1063
1064	if (!m_rowsInserted) {
1065	return;
1066	}
1067	m_rowsInserted = false;
1068	endInsertRows(parent, start, end);
1069	q->endInsertRows();
1070	for (const PendingSelectionChange &pendingChange : std::as_const(t&: m_pendingSelectionChanges)) {
1071	selectionChanged(selected: pendingChange.selected, deselected: pendingChange.deselected);
1072	}
1073	m_pendingSelectionChanges.clear();
1074	}
1075
1076	static bool rootWillBeRemovedFrom(const QModelIndex &ancestor, int start, int end, const QModelIndex &root)
1077	{
1078	Q_ASSERT(root.isValid());
1079
1080	auto parent = root;
1081	while (parent.isValid()) {
1082	auto prev = parent;
1083	parent = parent.parent();
1084	if (parent == ancestor) {
1085	return (prev.row() <= end && prev.row() >= start);
1086	}
1087	}
1088	return false;
1089	}
1090
1091	bool KSelectionProxyModelPrivate::rootWillBeRemoved(const QItemSelection &selection, const QModelIndex &root)
1092	{
1093	Q_ASSERT(root.isValid());
1094
1095	for (auto &r : selection) {
1096	if (m_includeAllSelected) {
1097	if (r.parent() == root.parent() && root.row() <= r.bottom() && root.row() >= r.top()) {
1098	return true;
1099	}
1100	} else {
1101	if (rootWillBeRemovedFrom(ancestor: r.parent(), start: r.top(), end: r.bottom(), root)) {
1102	return true;
1103	}
1104	}
1105	}
1106	return false;
1107	}
1108
1109	QPair<int, int> KSelectionProxyModelPrivate::beginRemoveRows(const QModelIndex &parent, int start, int end) const
1110	{
1111	Q_Q(const KSelectionProxyModel);
1112
1113	if (!m_includeAllSelected && !m_omitChildren) {
1114	// SubTrees and SubTreesWithoutRoots
1115	const QModelIndex proxyParent = mapParentFromSource(sourceParent: parent);
1116	if (proxyParent.isValid()) {
1117	return qMakePair(value1&: start, value2&: end);
1118	}
1119	}
1120
1121	if (m_startWithChildTrees && m_rootIndexList.contains(t: parent)) {
1122	const int proxyStartRow = getProxyInitialRow(parent) + start;
1123	const int proxyEndRow = proxyStartRow + (end - start);
1124	return qMakePair(value1: proxyStartRow, value2: proxyEndRow);
1125	}
1126
1127	QList<QPersistentModelIndex>::const_iterator rootIt = m_rootIndexList.constBegin();
1128	const QList<QPersistentModelIndex>::const_iterator rootEnd = m_rootIndexList.constEnd();
1129	int proxyStartRemove = 0;
1130
1131	for (; rootIt != rootEnd; ++rootIt) {
1132	if (rootWillBeRemovedFrom(ancestor: parent, start, end, root: *rootIt)) {
1133	break;
1134	} else {
1135	if (m_startWithChildTrees) {
1136	proxyStartRemove += q->sourceModel()->rowCount(parent: *rootIt);
1137	} else {
1138	++proxyStartRemove;
1139	}
1140	}
1141	}
1142
1143	if (rootIt == rootEnd) {
1144	return qMakePair(value1: -1, value2: -1);
1145	}
1146
1147	int proxyEndRemove = proxyStartRemove;
1148
1149	for (; rootIt != rootEnd; ++rootIt) {
1150	if (!rootWillBeRemovedFrom(ancestor: parent, start, end, root: *rootIt)) {
1151	break;
1152	}
1153	if (m_startWithChildTrees) {
1154	proxyEndRemove += q->sourceModel()->rowCount(parent: *rootIt);
1155	} else {
1156	++proxyEndRemove;
1157	}
1158	}
1159
1160	--proxyEndRemove;
1161	if (proxyEndRemove >= proxyStartRemove) {
1162	return qMakePair(value1&: proxyStartRemove, value2&: proxyEndRemove);
1163	}
1164	return qMakePair(value1: -1, value2: -1);
1165	}
1166
1167	void KSelectionProxyModelPrivate::sourceRowsAboutToBeRemoved(const QModelIndex &parent, int start, int end)
1168	{
1169	Q_Q(KSelectionProxyModel);
1170
1171	Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1172
1173	if (!m_selectionModel || !m_selectionModel->hasSelection()) {
1174	return;
1175	}
1176
1177	QPair<int, int> pair = beginRemoveRows(parent, start, end);
1178	if (pair.first == -1) {
1179	return;
1180	}
1181
1182	const QModelIndex proxyParent = mapParentFromSource(sourceParent: parent);
1183
1184	m_rowsRemoved = true;
1185	m_proxyRemoveRows = pair;
1186	m_recreateFirstChildMappingOnRemoval = m_mappedFirstChildren.leftContains(t: q->sourceModel()->index(row: start, column: 0, parent));
1187	q->beginRemoveRows(parent: proxyParent, first: pair.first, last: pair.second);
1188	}
1189
1190	void KSelectionProxyModelPrivate::endRemoveRows(const QModelIndex &sourceParent, int proxyStart, int proxyEnd)
1191	{
1192	const QModelIndex proxyParent = mapParentFromSource(sourceParent);
1193
1194	// We need to make sure to remove entries from the mappings before updating internal indexes.
1195
1196	// - A
1197	// - - B
1198	// - C
1199	// - - D
1200
1201	// If A and C are selected, B and D are in the proxy. B maps to row 0 and D maps to row 1.
1202	// If B is then deleted leaving only D in the proxy, D needs to be updated to be a mapping
1203	// to row 0 instead of row 1. If that is done before removing the mapping for B, then the mapping
1204	// for D would overwrite the mapping for B and then the code for removing mappings would incorrectly
1205	// remove D.
1206	// So we first remove B and then update D.
1207
1208	{
1209	SourceProxyIndexMapping::right_iterator it = m_mappedParents.rightBegin();
1210
1211	while (it != m_mappedParents.rightEnd()) {
1212	if (!it.value().isValid()) {
1213	m_parentIds.removeRight(u: it.key());
1214	it = m_mappedParents.eraseRight(it);
1215	} else {
1216	++it;
1217	}
1218	}
1219	}
1220
1221	{
1222	// Depending on what is selected at the time, a single removal in the source could invalidate
1223	// many mapped first child items at once.
1224
1225	// - A
1226	// - B
1227	// - - C
1228	// - - D
1229	// - - - E
1230	// - - - F
1231	// - - - - G
1232	// - - - - H
1233
1234	// If D and F are selected, the proxy contains E, F, G, H. If B is then deleted E to H will
1235	// be removed, including both first child mappings at E and G.
1236
1237	if (!proxyParent.isValid()) {
1238	removeFirstChildMappings(start: proxyStart, end: proxyEnd);
1239	}
1240	}
1241
1242	if (proxyParent.isValid()) {
1243	updateInternalIndexes(parent: proxyParent, start: proxyEnd + 1, offset: -1 * (proxyEnd - proxyStart + 1));
1244	} else {
1245	updateInternalTopIndexes(start: proxyEnd + 1, offset: -1 * (proxyEnd - proxyStart + 1));
1246	}
1247
1248	QList<QPersistentModelIndex>::iterator rootIt = m_rootIndexList.begin();
1249	while (rootIt != m_rootIndexList.end()) {
1250	if (!rootIt->isValid()) {
1251	rootIt = m_rootIndexList.erase(pos: rootIt);
1252	} else {
1253	++rootIt;
1254	}
1255	}
1256	}
1257
1258	void KSelectionProxyModelPrivate::sourceRowsRemoved(const QModelIndex &parent, int start, int end)
1259	{
1260	Q_Q(KSelectionProxyModel);
1261	Q_UNUSED(end)
1262	Q_UNUSED(start)
1263
1264	Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1265
1266	if (!m_selectionModel) {
1267	return;
1268	}
1269
1270	if (!m_rowsRemoved) {
1271	return;
1272	}
1273	m_rowsRemoved = false;
1274
1275	Q_ASSERT(m_proxyRemoveRows.first >= 0);
1276	Q_ASSERT(m_proxyRemoveRows.second >= 0);
1277	endRemoveRows(sourceParent: parent, proxyStart: m_proxyRemoveRows.first, proxyEnd: m_proxyRemoveRows.second);
1278	if (m_recreateFirstChildMappingOnRemoval && q->sourceModel()->hasChildren(parent))
1279	// The private endRemoveRows call might remove the first child mapping for parent, so
1280	// we create it again in that case.
1281	{
1282	createFirstChildMapping(parent, proxyRow: m_proxyRemoveRows.first);
1283	}
1284	m_recreateFirstChildMappingOnRemoval = false;
1285
1286	m_proxyRemoveRows = qMakePair(value1: -1, value2: -1);
1287	q->endRemoveRows();
1288	}
1289
1290	void KSelectionProxyModelPrivate::sourceRowsAboutToBeMoved(const QModelIndex &srcParent, int srcStart, int srcEnd, const QModelIndex &destParent, int destRow)
1291	{
1292	Q_UNUSED(srcParent)
1293	Q_UNUSED(srcStart)
1294	Q_UNUSED(srcEnd)
1295	Q_UNUSED(destParent)
1296	Q_UNUSED(destRow)
1297	// we cheat and just act like the layout changed; this might benefit from some
1298	// optimization
1299	sourceLayoutAboutToBeChanged();
1300	}
1301
1302	void KSelectionProxyModelPrivate::sourceRowsMoved(const QModelIndex &srcParent, int srcStart, int srcEnd, const QModelIndex &destParent, int destRow)
1303	{
1304	Q_UNUSED(srcParent)
1305	Q_UNUSED(srcStart)
1306	Q_UNUSED(srcEnd)
1307	Q_UNUSED(destParent)
1308	Q_UNUSED(destRow)
1309	// we cheat and just act like the layout changed; this might benefit from some
1310	// optimization
1311	sourceLayoutChanged();
1312	}
1313
1314	QModelIndex KSelectionProxyModelPrivate::mapParentToSource(const QModelIndex &proxyParent) const
1315	{
1316	return m_mappedParents.rightToLeft(u: proxyParent);
1317	}
1318
1319	QModelIndex KSelectionProxyModelPrivate::mapParentFromSource(const QModelIndex &sourceParent) const
1320	{
1321	return m_mappedParents.leftToRight(t: sourceParent);
1322	}
1323
1324	static bool
1325	indexIsValid(bool startWithChildTrees, int row, const QList<QPersistentModelIndex> &rootIndexList, const SourceIndexProxyRowMapping &mappedFirstChildren)
1326	{
1327	if (!startWithChildTrees) {
1328	Q_ASSERT(rootIndexList.size() > row);
1329	} else {
1330	Q_ASSERT(!mappedFirstChildren.isEmpty());
1331
1332	SourceIndexProxyRowMapping::right_const_iterator result = std::prev(x: mappedFirstChildren.rightUpperBound(key: row));
1333
1334	Q_ASSERT(result != mappedFirstChildren.rightEnd());
1335	const int proxyFirstRow = result.key();
1336	const QModelIndex sourceFirstChild = result.value();
1337	Q_ASSERT(proxyFirstRow >= 0);
1338	Q_ASSERT(sourceFirstChild.isValid());
1339	Q_ASSERT(sourceFirstChild.parent().isValid());
1340	Q_ASSERT(row <= proxyFirstRow + sourceFirstChild.model()->rowCount(sourceFirstChild.parent()));
1341	}
1342	return true;
1343	}
1344
1345	QModelIndex KSelectionProxyModelPrivate::createTopLevelIndex(int row, int column) const
1346	{
1347	Q_Q(const KSelectionProxyModel);
1348
1349	Q_ASSERT(indexIsValid(m_startWithChildTrees, row, m_rootIndexList, m_mappedFirstChildren));
1350	return q->createIndex(arow: row, acolumn: column);
1351	}
1352
1353	QModelIndex KSelectionProxyModelPrivate::mapTopLevelFromSource(const QModelIndex &sourceIndex) const
1354	{
1355	Q_Q(const KSelectionProxyModel);
1356
1357	const QModelIndex sourceParent = sourceIndex.parent();
1358	const int row = m_rootIndexList.indexOf(t: sourceIndex);
1359	if (row == -1) {
1360	return QModelIndex();
1361	}
1362
1363	if (!m_startWithChildTrees) {
1364	Q_ASSERT(m_rootIndexList.size() > row);
1365	return q->createIndex(arow: row, acolumn: sourceIndex.column());
1366	}
1367	if (!m_rootIndexList.contains(t: sourceParent)) {
1368	return QModelIndex();
1369	}
1370
1371	const QModelIndex firstChild = q->sourceModel()->index(row: 0, column: 0, parent: sourceParent);
1372	const int firstProxyRow = m_mappedFirstChildren.leftToRight(t: firstChild);
1373
1374	return q->createIndex(arow: firstProxyRow + sourceIndex.row(), acolumn: sourceIndex.column());
1375	}
1376
1377	QModelIndex KSelectionProxyModelPrivate::mapFromSource(const QModelIndex &sourceIndex) const
1378	{
1379	Q_Q(const KSelectionProxyModel);
1380
1381	const QModelIndex maybeMapped = mapParentFromSource(sourceParent: sourceIndex);
1382	if (maybeMapped.isValid()) {
1383	// Q_ASSERT((!d->m_startWithChildTrees && d->m_rootIndexList.contains(maybeMapped)) ? maybeMapped.row() < 0 : true );
1384	return maybeMapped;
1385	}
1386	const QModelIndex sourceParent = sourceIndex.parent();
1387
1388	const QModelIndex proxyParent = mapParentFromSource(sourceParent);
1389	if (proxyParent.isValid()) {
1390	void *const parentId = m_parentIds.rightToLeft(u: proxyParent);
1391	static const int column = 0;
1392	return q->createIndex(arow: sourceIndex.row(), acolumn: column, adata: parentId);
1393	}
1394
1395	const QModelIndex firstChild = q->sourceModel()->index(row: 0, column: 0, parent: sourceParent);
1396
1397	if (m_mappedFirstChildren.leftContains(t: firstChild)) {
1398	const int firstProxyRow = m_mappedFirstChildren.leftToRight(t: firstChild);
1399	return q->createIndex(arow: firstProxyRow + sourceIndex.row(), acolumn: sourceIndex.column());
1400	}
1401	return mapTopLevelFromSource(sourceIndex);
1402	}
1403
1404	int KSelectionProxyModelPrivate::topLevelRowCount() const
1405	{
1406	Q_Q(const KSelectionProxyModel);
1407
1408	if (!m_startWithChildTrees) {
1409	return m_rootIndexList.size();
1410	}
1411
1412	if (m_mappedFirstChildren.isEmpty()) {
1413	return 0;
1414	}
1415
1416	const SourceIndexProxyRowMapping::right_const_iterator result = std::prev(x: m_mappedFirstChildren.rightConstEnd());
1417
1418	const int proxyFirstRow = result.key();
1419	const QModelIndex sourceFirstChild = result.value();
1420	Q_ASSERT(sourceFirstChild.isValid());
1421	const QModelIndex sourceParent = sourceFirstChild.parent();
1422	Q_ASSERT(sourceParent.isValid());
1423	return q->sourceModel()->rowCount(parent: sourceParent) + proxyFirstRow;
1424	}
1425
1426	bool KSelectionProxyModelPrivate::ensureMappable(const QModelIndex &parent) const
1427	{
1428	Q_Q(const KSelectionProxyModel);
1429
1430	if (isFlat()) {
1431	return true;
1432	}
1433
1434	if (parentIsMappable(parent)) {
1435	return true;
1436	}
1437
1438	QModelIndex ancestor = parent.parent();
1439	QModelIndexList ancestorList;
1440	while (ancestor.isValid()) {
1441	if (parentIsMappable(parent: ancestor)) {
1442	break;
1443	} else {
1444	ancestorList.prepend(t: ancestor);
1445	}
1446
1447	ancestor = ancestor.parent();
1448	}
1449
1450	if (!ancestor.isValid())
1451	// @p parent is not a descendant of m_rootIndexList.
1452	{
1453	return false;
1454	}
1455
1456	// sourceIndex can be mapped to the proxy. We just need to create mappings for its ancestors first.
1457	for (int i = 0; i < ancestorList.size(); ++i) {
1458	const QModelIndex existingAncestor = mapParentFromSource(sourceParent: ancestor);
1459	Q_ASSERT(existingAncestor.isValid());
1460
1461	void *const ansId = m_parentIds.rightToLeft(u: existingAncestor);
1462	const QModelIndex newSourceParent = ancestorList.at(i);
1463	const QModelIndex newProxyParent = q->createIndex(arow: newSourceParent.row(), acolumn: newSourceParent.column(), adata: ansId);
1464
1465	void *const newId = m_voidPointerFactory.createPointer();
1466	m_parentIds.insert(t: newId, u: newProxyParent);
1467	m_mappedParents.insert(t: QPersistentModelIndex(newSourceParent), u: newProxyParent);
1468	ancestor = newSourceParent;
1469	}
1470	return true;
1471	}
1472
1473	void KSelectionProxyModelPrivate::updateInternalTopIndexes(int start, int offset)
1474	{
1475	updateInternalIndexes(parent: QModelIndex(), start, offset);
1476
1477	QHash<QPersistentModelIndex, int> updates;
1478	{
1479	SourceIndexProxyRowMapping::right_iterator it = m_mappedFirstChildren.rightLowerBound(key: start);
1480	const SourceIndexProxyRowMapping::right_iterator end = m_mappedFirstChildren.rightEnd();
1481
1482	for (; it != end; ++it) {
1483	updates.insert(key: *it, value: it.key() + offset);
1484	}
1485	}
1486	{
1487	QHash<QPersistentModelIndex, int>::const_iterator it = updates.constBegin();
1488	const QHash<QPersistentModelIndex, int>::const_iterator end = updates.constEnd();
1489
1490	for (; it != end; ++it) {
1491	m_mappedFirstChildren.insert(t: it.key(), u: it.value());
1492	}
1493	}
1494	}
1495
1496	void KSelectionProxyModelPrivate::updateInternalIndexes(const QModelIndex &parent, int start, int offset)
1497	{
1498	Q_Q(KSelectionProxyModel);
1499
1500	Q_ASSERT(start + offset >= 0);
1501	Q_ASSERT(parent.isValid() ? parent.model() == q : true);
1502
1503	if (isFlat()) {
1504	return;
1505	}
1506
1507	SourceProxyIndexMapping::left_iterator mappedParentIt = m_mappedParents.leftBegin();
1508
1509	QHash<void *, QModelIndex> updatedParentIds;
1510	QHash<QPersistentModelIndex, QModelIndex> updatedParents;
1511
1512	for (; mappedParentIt != m_mappedParents.leftEnd(); ++mappedParentIt) {
1513	const QModelIndex proxyIndex = mappedParentIt.value();
1514	Q_ASSERT(proxyIndex.isValid());
1515
1516	if (proxyIndex.row() < start) {
1517	continue;
1518	}
1519
1520	const QModelIndex proxyParent = proxyIndex.parent();
1521
1522	if (parent.isValid()) {
1523	if (proxyParent != parent) {
1524	continue;
1525	}
1526	} else {
1527	if (proxyParent.isValid()) {
1528	continue;
1529	}
1530	}
1531	Q_ASSERT(m_parentIds.rightContains(proxyIndex));
1532	void *const key = m_parentIds.rightToLeft(u: proxyIndex);
1533
1534	const QModelIndex newIndex = q->createIndex(arow: proxyIndex.row() + offset, acolumn: proxyIndex.column(), adata: proxyIndex.internalPointer());
1535
1536	Q_ASSERT(newIndex.isValid());
1537
1538	updatedParentIds.insert(key, value: newIndex);
1539	updatedParents.insert(key: mappedParentIt.key(), value: newIndex);
1540	}
1541
1542	{
1543	QHash<QPersistentModelIndex, QModelIndex>::const_iterator it = updatedParents.constBegin();
1544	const QHash<QPersistentModelIndex, QModelIndex>::const_iterator end = updatedParents.constEnd();
1545	for (; it != end; ++it) {
1546	m_mappedParents.insert(t: it.key(), u: it.value());
1547	}
1548	}
1549
1550	{
1551	QHash<void *, QModelIndex>::const_iterator it = updatedParentIds.constBegin();
1552	const QHash<void *, QModelIndex>::const_iterator end = updatedParentIds.constEnd();
1553	for (; it != end; ++it) {
1554	m_parentIds.insert(t: it.key(), u: it.value());
1555	}
1556	}
1557	}
1558
1559	bool KSelectionProxyModelPrivate::parentAlreadyMapped(const QModelIndex &parent) const
1560	{
1561	Q_Q(const KSelectionProxyModel);
1562	Q_UNUSED(q) // except in Q_ASSERT
1563	Q_ASSERT(parent.model() == q->sourceModel());
1564	return m_mappedParents.leftContains(t: parent);
1565	}
1566
1567	bool KSelectionProxyModelPrivate::firstChildAlreadyMapped(const QModelIndex &firstChild) const
1568	{
1569	Q_Q(const KSelectionProxyModel);
1570	Q_UNUSED(q) // except in Q_ASSERT
1571	Q_ASSERT(firstChild.model() == q->sourceModel());
1572	return m_mappedFirstChildren.leftContains(t: firstChild);
1573	}
1574
1575	void KSelectionProxyModelPrivate::createFirstChildMapping(const QModelIndex &parent, int proxyRow) const
1576	{
1577	Q_Q(const KSelectionProxyModel);
1578
1579	Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1580
1581	static const int column = 0;
1582	static const int row = 0;
1583
1584	const QPersistentModelIndex srcIndex = q->sourceModel()->index(row, column, parent);
1585
1586	if (firstChildAlreadyMapped(firstChild: srcIndex)) {
1587	return;
1588	}
1589
1590	Q_ASSERT(srcIndex.isValid());
1591	m_mappedFirstChildren.insert(t: srcIndex, u: proxyRow);
1592	}
1593
1594	void KSelectionProxyModelPrivate::createParentMappings(const QModelIndex &parent, int start, int end) const
1595	{
1596	if (isFlat()) {
1597	return;
1598	}
1599
1600	Q_Q(const KSelectionProxyModel);
1601
1602	Q_ASSERT(parent.isValid() ? parent.model() == q->sourceModel() : true);
1603
1604	static const int column = 0;
1605
1606	for (int row = start; row <= end; ++row) {
1607	const QModelIndex srcIndex = q->sourceModel()->index(row, column, parent);
1608	Q_ASSERT(srcIndex.isValid());
1609	if (!q->sourceModel()->hasChildren(parent: srcIndex) || parentAlreadyMapped(parent: srcIndex)) {
1610	continue;
1611	}
1612
1613	const QModelIndex proxyIndex = mapFromSource(sourceIndex: srcIndex);
1614	if (!proxyIndex.isValid()) {
1615	return; // If one of them is not mapped, its siblings won't be either
1616	}
1617
1618	void *const newId = m_voidPointerFactory.createPointer();
1619	m_parentIds.insert(t: newId, u: proxyIndex);
1620	Q_ASSERT(srcIndex.isValid());
1621	m_mappedParents.insert(t: QPersistentModelIndex(srcIndex), u: proxyIndex);
1622	}
1623	}
1624
1625	void KSelectionProxyModelPrivate::removeFirstChildMappings(int start, int end)
1626	{
1627	SourceIndexProxyRowMapping::right_iterator it = m_mappedFirstChildren.rightLowerBound(key: start);
1628	const SourceIndexProxyRowMapping::right_iterator endIt = m_mappedFirstChildren.rightUpperBound(key: end);
1629	while (it != endIt) {
1630	it = m_mappedFirstChildren.eraseRight(it);
1631	}
1632	}
1633
1634	void KSelectionProxyModelPrivate::removeParentMappings(const QModelIndex &parent, int start, int end)
1635	{
1636	Q_Q(KSelectionProxyModel);
1637
1638	Q_ASSERT(parent.isValid() ? parent.model() == q : true);
1639
1640	// collect all removals first, as executing them recursively will invalidate our iterators
1641	struct RemovalInfo {
1642	QPersistentModelIndex idx;
1643	QModelIndex sourceIdx;
1644	};
1645	std::vector<RemovalInfo> removals;
1646	removals.reserve(n: end - start + 1);
1647	for (auto it = m_mappedParents.rightBegin(); it != m_mappedParents.rightEnd(); ++it) {
1648	if (it.key().row() >= start && it.key().row() <= end) {
1649	const QModelIndex sourceParent = it.value();
1650	const QModelIndex proxyGrandParent = mapParentFromSource(sourceParent: sourceParent.parent());
1651	if (proxyGrandParent == parent) {
1652	removals.push_back(x: {.idx: it.key(), .sourceIdx: it.value()});
1653	}
1654	}
1655	}
1656
1657	// execute the removals
1658	const bool flatList = isFlat();
1659	for (const auto &r : removals) {
1660	if (!flatList) {
1661	removeParentMappings(parent: r.idx, start: 0, end: q->sourceModel()->rowCount(parent: r.sourceIdx) - 1);
1662	}
1663	m_parentIds.removeRight(u: r.idx);
1664	m_mappedParents.removeRight(u: r.idx);
1665	}
1666	}
1667
1668	QModelIndex KSelectionProxyModelPrivate::mapTopLevelToSource(int row, int column) const
1669	{
1670	if (!m_startWithChildTrees) {
1671	const QModelIndex idx = m_rootIndexList.at(i: row);
1672	return idx.sibling(arow: idx.row(), acolumn: column);
1673	}
1674
1675	if (m_mappedFirstChildren.isEmpty()) {
1676	return QModelIndex();
1677	}
1678
1679	SourceIndexProxyRowMapping::right_iterator result = std::prev(x: m_mappedFirstChildren.rightUpperBound(key: row));
1680
1681	Q_ASSERT(result != m_mappedFirstChildren.rightEnd());
1682
1683	const int proxyFirstRow = result.key();
1684	const QModelIndex sourceFirstChild = result.value();
1685	Q_ASSERT(sourceFirstChild.isValid());
1686	return sourceFirstChild.sibling(arow: row - proxyFirstRow, acolumn: column);
1687	}
1688
1689	void KSelectionProxyModelPrivate::removeSelectionFromProxy(const QItemSelection &selection)
1690	{
1691	Q_Q(KSelectionProxyModel);
1692	if (selection.isEmpty()) {
1693	return;
1694	}
1695
1696	QList<QPersistentModelIndex>::iterator rootIt = m_rootIndexList.begin();
1697	const QList<QPersistentModelIndex>::iterator rootEnd = m_rootIndexList.end();
1698	int proxyStartRemove = 0;
1699
1700	for (; rootIt != rootEnd; ++rootIt) {
1701	if (rootWillBeRemoved(selection, root: *rootIt)) {
1702	break;
1703	} else {
1704	if (m_startWithChildTrees) {
1705	auto rc = q->sourceModel()->rowCount(parent: *rootIt);
1706	proxyStartRemove += rc;
1707	} else {
1708	++proxyStartRemove;
1709	}
1710	}
1711	}
1712
1713	if (rootIt == rootEnd) {
1714	return;
1715	}
1716
1717	int proxyEndRemove = proxyStartRemove;
1718
1719	QList<QPersistentModelIndex>::iterator rootRemoveStart = rootIt;
1720
1721	for (; rootIt != rootEnd; ++rootIt) {
1722	if (!rootWillBeRemoved(selection, root: *rootIt)) {
1723	break;
1724	}
1725	q->rootIndexAboutToBeRemoved(removeRootIndex: *rootIt, KSelectionProxyModel::QPrivateSignal());
1726	if (m_startWithChildTrees) {
1727	auto rc = q->sourceModel()->rowCount(parent: *rootIt);
1728	proxyEndRemove += rc;
1729	} else {
1730	++proxyEndRemove;
1731	}
1732	}
1733
1734	--proxyEndRemove;
1735	if (proxyEndRemove >= proxyStartRemove) {
1736	q->beginRemoveRows(parent: QModelIndex(), first: proxyStartRemove, last: proxyEndRemove);
1737
1738	rootIt = m_rootIndexList.erase(abegin: rootRemoveStart, aend: rootIt);
1739
1740	removeParentMappings(parent: QModelIndex(), start: proxyStartRemove, end: proxyEndRemove);
1741	if (m_startWithChildTrees) {
1742	removeFirstChildMappings(start: proxyStartRemove, end: proxyEndRemove);
1743	}
1744	updateInternalTopIndexes(start: proxyEndRemove + 1, offset: -1 * (proxyEndRemove - proxyStartRemove + 1));
1745
1746	q->endRemoveRows();
1747	} else {
1748	rootIt = m_rootIndexList.erase(abegin: rootRemoveStart, aend: rootIt);
1749	}
1750	if (rootIt != rootEnd) {
1751	removeSelectionFromProxy(selection);
1752	}
1753	}
1754
1755	void KSelectionProxyModelPrivate::selectionChanged(const QItemSelection &_selected, const QItemSelection &_deselected)
1756	{
1757	Q_Q(KSelectionProxyModel);
1758
1759	if (!q->sourceModel() || (_selected.isEmpty() && _deselected.isEmpty())) {
1760	return;
1761	}
1762
1763	if (m_sourceModelResetting) {
1764	return;
1765	}
1766
1767	if (m_rowsInserted || m_rowsRemoved) {
1768	m_pendingSelectionChanges.append(t: PendingSelectionChange(_selected, _deselected));
1769	return;
1770	}
1771
1772	// Any deselected indexes in the m_rootIndexList are removed. Then, any
1773	// indexes in the selected range which are not a descendant of one of the already selected indexes
1774	// are inserted into the model.
1775	//
1776	// All ranges from the selection model need to be split into individual rows. Ranges which are contiguous in
1777	// the selection model may not be contiguous in the source model if there's a sort filter proxy model in the chain.
1778	//
1779	// Some descendants of deselected indexes may still be selected. The ranges in m_selectionModel->selection()
1780	// are examined. If any of the ranges are descendants of one of the
1781	// indexes in deselected, they are added to the ranges to be inserted into the model.
1782	//
1783	// The new indexes are inserted in sorted order.
1784
1785	const QItemSelection selected = kNormalizeSelection(selection: m_indexMapper->mapSelectionRightToLeft(selection: _selected));
1786	const QItemSelection deselected = kNormalizeSelection(selection: m_indexMapper->mapSelectionRightToLeft(selection: _deselected));
1787
1788	#if QT_VERSION < 0x040800
1789	// The QItemSelectionModel sometimes doesn't remove deselected items from its selection
1790	// Fixed in Qt 4.8 : http://qt.gitorious.org/qt/qt/merge_requests/2403
1791	QItemSelection reportedSelection = m_selectionModel->selection();
1792	reportedSelection.merge(deselected, QItemSelectionModel::Deselect);
1793	QItemSelection fullSelection = m_indexMapper->mapSelectionRightToLeft(reportedSelection);
1794	#else
1795	QItemSelection fullSelection = m_indexMapper->mapSelectionRightToLeft(selection: m_selectionModel->selection());
1796	#endif
1797
1798	fullSelection = kNormalizeSelection(selection: fullSelection);
1799
1800	QItemSelection newRootRanges;
1801	QItemSelection removedRootRanges;
1802	if (!m_includeAllSelected) {
1803	newRootRanges = getRootRanges(selection: selected);
1804
1805	QItemSelection existingSelection = fullSelection;
1806	// What was selected before the selection was made.
1807	existingSelection.merge(other: selected, command: QItemSelectionModel::Deselect);
1808
1809	// This is similar to m_rootRanges, but that m_rootRanges at this point still contains the roots
1810	// of deselected and existingRootRanges does not.
1811
1812	const QItemSelection existingRootRanges = getRootRanges(selection: existingSelection);
1813	{
1814	QMutableListIterator<QItemSelectionRange> i(newRootRanges);
1815	while (i.hasNext()) {
1816	const QItemSelectionRange range = i.next();
1817	const QModelIndex topLeft = range.topLeft();
1818	if (isDescendantOf(selection: existingRootRanges, descendant: topLeft)) {
1819	i.remove();
1820	}
1821	}
1822	}
1823
1824	QItemSelection exposedSelection;
1825	{
1826	QItemSelection deselectedRootRanges = getRootRanges(selection: deselected);
1827	QListIterator<QItemSelectionRange> i(deselectedRootRanges);
1828	while (i.hasNext()) {
1829	const QItemSelectionRange range = i.next();
1830	const QModelIndex topLeft = range.topLeft();
1831	// Consider this:
1832	//
1833	// - A
1834	// - - B
1835	// - - - C
1836	// - - - - D
1837	//
1838	// B and D were selected, then B was deselected and C was selected in one go.
1839	if (!isDescendantOf(selection: existingRootRanges, descendant: topLeft)) {
1840	// B is topLeft and fullSelection contains D.
1841	// B is not a descendant of D.
1842
1843	// range is not a descendant of the selection, but maybe the selection is a descendant of range.
1844	// no need to check selected here. That's already in newRootRanges.
1845	// existingRootRanges and newRootRanges do not overlap.
1846	for (const QItemSelectionRange &selectedRange : existingRootRanges) {
1847	const QModelIndex selectedRangeTopLeft = selectedRange.topLeft();
1848	// existingSelection (and selectedRangeTopLeft) is D.
1849	// D is a descendant of B, so when B was removed, D might have been exposed as a root.
1850	if (isDescendantOf(range, descendant: selectedRangeTopLeft)
1851	// But D is also a descendant of part of the new selection C, which is already set to be a new root
1852	// so D would not be added to exposedSelection because C is in newRootRanges.
1853	&& !isDescendantOf(selection: newRootRanges, descendant: selectedRangeTopLeft)) {
1854	exposedSelection.append(t: selectedRange);
1855	}
1856	}
1857	removedRootRanges << range;
1858	}
1859	}
1860	}
1861
1862	QItemSelection obscuredRanges;
1863	{
1864	QListIterator<QItemSelectionRange> i(existingRootRanges);
1865	while (i.hasNext()) {
1866	const QItemSelectionRange range = i.next();
1867	if (isDescendantOf(selection: newRootRanges, descendant: range.topLeft())) {
1868	obscuredRanges << range;
1869	}
1870	}
1871	}
1872	removedRootRanges << getRootRanges(selection: obscuredRanges);
1873	newRootRanges << getRootRanges(selection: exposedSelection);
1874
1875	removedRootRanges = kNormalizeSelection(selection: removedRootRanges);
1876	newRootRanges = kNormalizeSelection(selection: newRootRanges);
1877	} else {
1878	removedRootRanges = deselected;
1879	newRootRanges = selected;
1880	}
1881
1882	removeSelectionFromProxy(selection: removedRootRanges);
1883
1884	if (!m_selectionModel->hasSelection()) {
1885	Q_ASSERT(m_rootIndexList.isEmpty());
1886	Q_ASSERT(m_mappedFirstChildren.isEmpty());
1887	Q_ASSERT(m_mappedParents.isEmpty());
1888	Q_ASSERT(m_parentIds.isEmpty());
1889	}
1890
1891	insertSelectionIntoProxy(selection: newRootRanges);
1892	}
1893
1894	int KSelectionProxyModelPrivate::getTargetRow(int rootListRow)
1895	{
1896	Q_Q(KSelectionProxyModel);
1897	if (!m_startWithChildTrees) {
1898	return rootListRow;
1899	}
1900
1901	--rootListRow;
1902	while (rootListRow >= 0) {
1903	const QModelIndex idx = m_rootIndexList.at(i: rootListRow);
1904	Q_ASSERT(idx.isValid());
1905	const int rowCount = q->sourceModel()->rowCount(parent: idx);
1906	if (rowCount > 0) {
1907	static const int column = 0;
1908	const QModelIndex srcIdx = q->sourceModel()->index(row: rowCount - 1, column, parent: idx);
1909	const QModelIndex proxyLastChild = mapFromSource(sourceIndex: srcIdx);
1910	return proxyLastChild.row() + 1;
1911	}
1912	--rootListRow;
1913	}
1914	return 0;
1915	}
1916
1917	void KSelectionProxyModelPrivate::insertSelectionIntoProxy(const QItemSelection &selection)
1918	{
1919	Q_Q(KSelectionProxyModel);
1920
1921	if (selection.isEmpty()) {
1922	return;
1923	}
1924
1925	const auto lst = selection.indexes();
1926	for (const QModelIndex &newIndex : lst) {
1927	Q_ASSERT(newIndex.model() == q->sourceModel());
1928	if (newIndex.column() > 0) {
1929	continue;
1930	}
1931	if (m_startWithChildTrees) {
1932	const int rootListRow = getRootListRow(list: m_rootIndexList, index: newIndex);
1933	Q_ASSERT(q->sourceModel() == newIndex.model());
1934	const int rowCount = q->sourceModel()->rowCount(parent: newIndex);
1935	const int startRow = getTargetRow(rootListRow);
1936
1937	if (rowCount == 0) {
1938	// Even if the newindex doesn't have any children to put into the model yet,
1939	// We still need to make sure its future children are inserted into the model.
1940	m_rootIndexList.insert(i: rootListRow, t: newIndex);
1941	if (!m_resetting || m_layoutChanging) {
1942	Q_EMIT q->rootIndexAdded(newIndex, KSelectionProxyModel::QPrivateSignal());
1943	}
1944	continue;
1945	}
1946	if (!m_resetting) {
1947	q->beginInsertRows(parent: QModelIndex(), first: startRow, last: startRow + rowCount - 1);
1948	}
1949	Q_ASSERT(newIndex.isValid());
1950	m_rootIndexList.insert(i: rootListRow, t: newIndex);
1951	if (!m_resetting || m_layoutChanging) {
1952	Q_EMIT q->rootIndexAdded(newIndex, KSelectionProxyModel::QPrivateSignal());
1953	}
1954
1955	int _start = 0;
1956	for (int i = 0; i < rootListRow; ++i) {
1957	_start += q->sourceModel()->rowCount(parent: m_rootIndexList.at(i));
1958	}
1959
1960	updateInternalTopIndexes(start: _start, offset: rowCount);
1961	createFirstChildMapping(parent: newIndex, proxyRow: _start);
1962	createParentMappings(parent: newIndex, start: 0, end: rowCount - 1);
1963
1964	if (!m_resetting) {
1965	q->endInsertRows();
1966	}
1967
1968	} else {
1969	const int row = getRootListRow(list: m_rootIndexList, index: newIndex);
1970	if (!m_resetting) {
1971	q->beginInsertRows(parent: QModelIndex(), first: row, last: row);
1972	}
1973
1974	Q_ASSERT(newIndex.isValid());
1975	m_rootIndexList.insert(i: row, t: newIndex);
1976
1977	if (!m_resetting || m_layoutChanging) {
1978	Q_EMIT q->rootIndexAdded(newIndex, KSelectionProxyModel::QPrivateSignal());
1979	}
1980	Q_ASSERT(m_rootIndexList.size() > row);
1981	updateInternalIndexes(parent: QModelIndex(), start: row, offset: 1);
1982	createParentMappings(parent: newIndex.parent(), start: newIndex.row(), end: newIndex.row());
1983
1984	if (!m_resetting) {
1985	q->endInsertRows();
1986	}
1987	}
1988	}
1989	Q_EMIT q->rootSelectionAdded(selection, KSelectionProxyModel::QPrivateSignal());
1990	}
1991
1992	KSelectionProxyModel::KSelectionProxyModel(QItemSelectionModel *selectionModel, QObject *parent)
1993	: QAbstractProxyModel(parent)
1994	, d_ptr(new KSelectionProxyModelPrivate(this))
1995	{
1996	setSelectionModel(selectionModel);
1997	}
1998
1999	KSelectionProxyModel::KSelectionProxyModel()
2000	: QAbstractProxyModel(nullptr)
2001	, d_ptr(new KSelectionProxyModelPrivate(this))
2002	{
2003	}
2004
2005	KSelectionProxyModel::~KSelectionProxyModel() = default;
2006
2007	void KSelectionProxyModel::setFilterBehavior(FilterBehavior behavior)
2008	{
2009	Q_D(KSelectionProxyModel);
2010
2011	Q_ASSERT(behavior != InvalidBehavior);
2012	if (behavior == InvalidBehavior) {
2013	return;
2014	}
2015	if (d->m_filterBehavior != behavior) {
2016	beginResetModel();
2017
2018	d->m_filterBehavior = behavior;
2019
2020	switch (behavior) {
2021	case InvalidBehavior: {
2022	Q_ASSERT(!"InvalidBehavior can't be used here");
2023	return;
2024	}
2025	case SubTrees: {
2026	d->m_omitChildren = false;
2027	d->m_omitDescendants = false;
2028	d->m_startWithChildTrees = false;
2029	d->m_includeAllSelected = false;
2030	break;
2031	}
2032	case SubTreeRoots: {
2033	d->m_omitChildren = true;
2034	d->m_startWithChildTrees = false;
2035	d->m_includeAllSelected = false;
2036	break;
2037	}
2038	case SubTreesWithoutRoots: {
2039	d->m_omitChildren = false;
2040	d->m_omitDescendants = false;
2041	d->m_startWithChildTrees = true;
2042	d->m_includeAllSelected = false;
2043	break;
2044	}
2045	case ExactSelection: {
2046	d->m_omitChildren = true;
2047	d->m_startWithChildTrees = false;
2048	d->m_includeAllSelected = true;
2049	break;
2050	}
2051	case ChildrenOfExactSelection: {
2052	d->m_omitChildren = false;
2053	d->m_omitDescendants = true;
2054	d->m_startWithChildTrees = true;
2055	d->m_includeAllSelected = true;
2056	break;
2057	}
2058	}
2059	Q_EMIT filterBehaviorChanged(QPrivateSignal());
2060	d->resetInternalData();
2061	if (d->m_selectionModel) {
2062	d->selectionChanged(selected: d->m_selectionModel->selection(), deselected: QItemSelection());
2063	}
2064
2065	endResetModel();
2066	}
2067	}
2068
2069	KSelectionProxyModel::FilterBehavior KSelectionProxyModel::filterBehavior() const
2070	{
2071	Q_D(const KSelectionProxyModel);
2072	return d->m_filterBehavior;
2073	}
2074
2075	void KSelectionProxyModel::setSourceModel(QAbstractItemModel *_sourceModel)
2076	{
2077	Q_D(KSelectionProxyModel);
2078
2079	Q_ASSERT(_sourceModel != this);
2080
2081	if (_sourceModel == sourceModel()) {
2082	return;
2083	}
2084
2085	beginResetModel();
2086	d->m_resetting = true;
2087
2088	if (auto *oldSourceModel = sourceModel()) {
2089	disconnect(sender: oldSourceModel, signal: nullptr, receiver: this, member: nullptr);
2090	}
2091
2092	// Must be called before QAbstractProxyModel::setSourceModel because it emit some signals.
2093	d->resetInternalData();
2094	QAbstractProxyModel::setSourceModel(_sourceModel);
2095	if (_sourceModel) {
2096	if (d->m_selectionModel) {
2097	delete d->m_indexMapper;
2098	d->m_indexMapper = new KModelIndexProxyMapper(_sourceModel, d->m_selectionModel->model(), this);
2099	if (d->m_selectionModel->hasSelection()) {
2100	d->selectionChanged(selected: d->m_selectionModel->selection(), deselected: QItemSelection());
2101	}
2102	}
2103
2104	connect(sender: _sourceModel, signal: &QAbstractItemModel::rowsAboutToBeInserted, context: this, slot: [d](const QModelIndex &parent, int start, int end) {
2105	d->sourceRowsAboutToBeInserted(parent, start, end);
2106	});
2107
2108	connect(sender: _sourceModel, signal: &QAbstractItemModel::rowsInserted, context: this, slot: [d](const QModelIndex &parent, int start, int end) {
2109	d->sourceRowsInserted(parent, start, end);
2110	});
2111
2112	connect(sender: _sourceModel, signal: &QAbstractItemModel::rowsAboutToBeRemoved, context: this, slot: [d](const QModelIndex &parent, int start, int end) {
2113	d->sourceRowsAboutToBeRemoved(parent, start, end);
2114	});
2115
2116	connect(sender: _sourceModel, signal: &QAbstractItemModel::rowsRemoved, context: this, slot: [d](const QModelIndex &parent, int start, int end) {
2117	d->sourceRowsRemoved(parent, start, end);
2118	});
2119
2120	connect(sender: _sourceModel,
2121	signal: &QAbstractItemModel::rowsAboutToBeMoved,
2122	context: this,
2123	slot: [d](const QModelIndex &parent, int start, int end, const QModelIndex &destParent, int destRow) {
2124	d->sourceRowsAboutToBeMoved(srcParent: parent, srcStart: start, srcEnd: end, destParent, destRow);
2125	});
2126
2127	connect(sender: _sourceModel,
2128	signal: &QAbstractItemModel::rowsMoved,
2129	context: this,
2130	slot: [d](const QModelIndex &parent, int start, int end, const QModelIndex &destParent, int destRow) {
2131	d->sourceRowsMoved(srcParent: parent, srcStart: start, srcEnd: end, destParent, destRow);
2132	});
2133
2134	connect(sender: _sourceModel, signal: &QAbstractItemModel::modelAboutToBeReset, context: this, slot: [d]() {
2135	d->sourceModelAboutToBeReset();
2136	});
2137
2138	connect(sender: _sourceModel, signal: &QAbstractItemModel::modelReset, context: this, slot: [d]() {
2139	d->sourceModelReset();
2140	});
2141
2142	connect(sender: _sourceModel, signal: &QAbstractItemModel::dataChanged, context: this, slot: [d](const QModelIndex &topLeft, const QModelIndex &bottomRight) {
2143	d->sourceDataChanged(topLeft, bottomRight);
2144	});
2145
2146	connect(sender: _sourceModel, signal: &QAbstractItemModel::layoutAboutToBeChanged, context: this, slot: [d]() {
2147	d->sourceLayoutAboutToBeChanged();
2148	});
2149
2150	connect(sender: _sourceModel, signal: &QAbstractItemModel::layoutChanged, context: this, slot: [d]() {
2151	d->sourceLayoutChanged();
2152	});
2153
2154	connect(sender: _sourceModel, signal: &QObject::destroyed, context: this, slot: [d]() {
2155	d->sourceModelDestroyed();
2156	});
2157	}
2158
2159	d->m_resetting = false;
2160	endResetModel();
2161	}
2162
2163	QModelIndex KSelectionProxyModel::mapToSource(const QModelIndex &proxyIndex) const
2164	{
2165	Q_D(const KSelectionProxyModel);
2166
2167	if (!proxyIndex.isValid() || !sourceModel() || d->m_rootIndexList.isEmpty()) {
2168	return QModelIndex();
2169	}
2170
2171	Q_ASSERT(proxyIndex.model() == this);
2172
2173	if (proxyIndex.internalPointer() == nullptr) {
2174	return d->mapTopLevelToSource(row: proxyIndex.row(), column: proxyIndex.column());
2175	}
2176
2177	const QModelIndex proxyParent = d->parentForId(id: proxyIndex.internalPointer());
2178	Q_ASSERT(proxyParent.isValid());
2179	const QModelIndex sourceParent = d->mapParentToSource(proxyParent);
2180	Q_ASSERT(sourceParent.isValid());
2181	return sourceModel()->index(row: proxyIndex.row(), column: proxyIndex.column(), parent: sourceParent);
2182	}
2183
2184	QModelIndex KSelectionProxyModel::mapFromSource(const QModelIndex &sourceIndex) const
2185	{
2186	Q_D(const KSelectionProxyModel);
2187
2188	if (!sourceModel() || !sourceIndex.isValid() || d->m_rootIndexList.isEmpty()) {
2189	return QModelIndex();
2190	}
2191
2192	Q_ASSERT(sourceIndex.model() == sourceModel());
2193
2194	if (!sourceIndex.isValid()) {
2195	return QModelIndex();
2196	}
2197
2198	if (!d->ensureMappable(parent: sourceIndex)) {
2199	return QModelIndex();
2200	}
2201
2202	return d->mapFromSource(sourceIndex);
2203	}
2204
2205	int KSelectionProxyModel::rowCount(const QModelIndex &index) const
2206	{
2207	Q_D(const KSelectionProxyModel);
2208
2209	if (!sourceModel() || index.column() > 0 || d->m_rootIndexList.isEmpty()) {
2210	return 0;
2211	}
2212
2213	Q_ASSERT(index.isValid() ? index.model() == this : true);
2214	if (!index.isValid()) {
2215	return d->topLevelRowCount();
2216	}
2217
2218	// index is valid
2219	if (d->isFlat()) {
2220	return 0;
2221	}
2222
2223	QModelIndex sourceParent = d->mapParentToSource(proxyParent: index);
2224
2225	if (!sourceParent.isValid() && sourceModel()->hasChildren(parent: sourceParent)) {
2226	sourceParent = mapToSource(proxyIndex: index.parent());
2227	d->createParentMappings(parent: sourceParent, start: 0, end: sourceModel()->rowCount(parent: sourceParent) - 1);
2228	sourceParent = d->mapParentToSource(proxyParent: index);
2229	}
2230
2231	if (!sourceParent.isValid()) {
2232	return 0;
2233	}
2234
2235	return sourceModel()->rowCount(parent: sourceParent);
2236	}
2237
2238	QModelIndex KSelectionProxyModel::index(int row, int column, const QModelIndex &parent) const
2239	{
2240	Q_D(const KSelectionProxyModel);
2241
2242	if (!sourceModel() || d->m_rootIndexList.isEmpty() || !hasIndex(row, column, parent)) {
2243	return QModelIndex();
2244	}
2245
2246	Q_ASSERT(parent.isValid() ? parent.model() == this : true);
2247
2248	if (!parent.isValid()) {
2249	return d->createTopLevelIndex(row, column);
2250	}
2251
2252	void *const parentId = d->parentId(proxyParent: parent);
2253	Q_ASSERT(parentId);
2254	return createIndex(arow: row, acolumn: column, adata: parentId);
2255	}
2256
2257	QModelIndex KSelectionProxyModel::parent(const QModelIndex &index) const
2258	{
2259	Q_D(const KSelectionProxyModel);
2260
2261	if (!sourceModel() || !index.isValid() || d->m_rootIndexList.isEmpty()) {
2262	return QModelIndex();
2263	}
2264
2265	Q_ASSERT(index.model() == this);
2266
2267	return d->parentForId(id: index.internalPointer());
2268	}
2269
2270	Qt::ItemFlags KSelectionProxyModel::flags(const QModelIndex &index) const
2271	{
2272	if (!index.isValid() || !sourceModel()) {
2273	return QAbstractProxyModel::flags(index);
2274	}
2275
2276	Q_ASSERT(index.model() == this);
2277
2278	const QModelIndex srcIndex = mapToSource(proxyIndex: index);
2279	Q_ASSERT(srcIndex.isValid());
2280	return sourceModel()->flags(index: srcIndex);
2281	}
2282
2283	QVariant KSelectionProxyModel::data(const QModelIndex &index, int role) const
2284	{
2285	if (!sourceModel()) {
2286	return QVariant();
2287	}
2288
2289	if (index.isValid()) {
2290	Q_ASSERT(index.model() == this);
2291	const QModelIndex idx = mapToSource(proxyIndex: index);
2292	return idx.data(arole: role);
2293	}
2294	return sourceModel()->data(index, role);
2295	}
2296
2297	QVariant KSelectionProxyModel::headerData(int section, Qt::Orientation orientation, int role) const
2298	{
2299	if (!sourceModel()) {
2300	return QVariant();
2301	}
2302	return sourceModel()->headerData(section, orientation, role);
2303	}
2304
2305	QMimeData *KSelectionProxyModel::mimeData(const QModelIndexList &indexes) const
2306	{
2307	if (!sourceModel()) {
2308	return QAbstractProxyModel::mimeData(indexes);
2309	}
2310	QModelIndexList sourceIndexes;
2311	for (const QModelIndex &index : indexes) {
2312	sourceIndexes << mapToSource(proxyIndex: index);
2313	}
2314	return sourceModel()->mimeData(indexes: sourceIndexes);
2315	}
2316
2317	QStringList KSelectionProxyModel::mimeTypes() const
2318	{
2319	if (!sourceModel()) {
2320	return QAbstractProxyModel::mimeTypes();
2321	}
2322	return sourceModel()->mimeTypes();
2323	}
2324
2325	Qt::DropActions KSelectionProxyModel::supportedDropActions() const
2326	{
2327	if (!sourceModel()) {
2328	return QAbstractProxyModel::supportedDropActions();
2329	}
2330	return sourceModel()->supportedDropActions();
2331	}
2332
2333	bool KSelectionProxyModel::hasChildren(const QModelIndex &parent) const
2334	{
2335	Q_D(const KSelectionProxyModel);
2336
2337	if (d->m_rootIndexList.isEmpty() || !sourceModel()) {
2338	return false;
2339	}
2340
2341	if (parent.isValid()) {
2342	Q_ASSERT(parent.model() == this);
2343	if (d->isFlat()) {
2344	return false;
2345	}
2346	return sourceModel()->hasChildren(parent: mapToSource(proxyIndex: parent));
2347	}
2348
2349	if (!d->m_startWithChildTrees) {
2350	return true;
2351	}
2352
2353	return !d->m_mappedFirstChildren.isEmpty();
2354	}
2355
2356	int KSelectionProxyModel::columnCount(const QModelIndex &index) const
2357	{
2358	if (!sourceModel() || index.column() > 0) {
2359	return 0;
2360	}
2361
2362	return sourceModel()->columnCount(parent: mapToSource(proxyIndex: index));
2363	}
2364
2365	QItemSelectionModel *KSelectionProxyModel::selectionModel() const
2366	{
2367	Q_D(const KSelectionProxyModel);
2368	return d->m_selectionModel;
2369	}
2370
2371	void KSelectionProxyModel::setSelectionModel(QItemSelectionModel *itemSelectionModel)
2372	{
2373	Q_D(KSelectionProxyModel);
2374	if (d->m_selectionModel != itemSelectionModel) {
2375	if (d->m_selectionModel) {
2376	disconnect(sender: d->m_selectionModel,
2377	SIGNAL(selectionChanged(QItemSelection, QItemSelection)),
2378	receiver: this,
2379	SLOT(selectionChanged(QItemSelection, QItemSelection)));
2380	}
2381
2382	d->m_selectionModel = itemSelectionModel;
2383	Q_EMIT selectionModelChanged(QPrivateSignal());
2384
2385	if (d->m_selectionModel) {
2386	connect(asender: d->m_selectionModel, SIGNAL(selectionChanged(QItemSelection, QItemSelection)), SLOT(selectionChanged(QItemSelection, QItemSelection)));
2387
2388	auto handleSelectionModelModel = [&, d] {
2389	beginResetModel();
2390	if (d->selectionModelModelAboutToBeResetConnection) {
2391	disconnect(d->selectionModelModelAboutToBeResetConnection);
2392	}
2393	if (d->selectionModelModelResetConnection) {
2394	disconnect(d->selectionModelModelResetConnection);
2395	}
2396	if (d->m_selectionModel->model()) {
2397	d->selectionModelModelAboutToBeResetConnection =
2398	connect(sender: d->m_selectionModel->model(), SIGNAL(modelAboutToBeReset()), receiver: this, SLOT(sourceModelAboutToBeReset()));
2399	d->selectionModelModelResetConnection = connect(sender: d->m_selectionModel->model(), SIGNAL(modelReset()), receiver: this, SLOT(sourceModelReset()));
2400	d->m_rootIndexList.clear();
2401	delete d->m_indexMapper;
2402	d->m_indexMapper = new KModelIndexProxyMapper(sourceModel(), d->m_selectionModel->model(), this);
2403	}
2404	endResetModel();
2405	};
2406	connect(sender: d->m_selectionModel.data(), signal: &QItemSelectionModel::modelChanged, context: this, slot&: handleSelectionModelModel);
2407	handleSelectionModelModel();
2408	}
2409
2410	if (sourceModel()) {
2411	delete d->m_indexMapper;
2412	d->m_indexMapper = new KModelIndexProxyMapper(sourceModel(), d->m_selectionModel->model(), this);
2413	if (d->m_selectionModel->hasSelection()) {
2414	d->selectionChanged(selected: d->m_selectionModel->selection(), deselected: QItemSelection());
2415	}
2416	}
2417	}
2418	}
2419
2420	bool KSelectionProxyModel::dropMimeData(const QMimeData *data, Qt::DropAction action, int row, int column, const QModelIndex &parent)
2421	{
2422	Q_D(const KSelectionProxyModel);
2423	if (!sourceModel() || d->m_rootIndexList.isEmpty()) {
2424	return false;
2425	}
2426
2427	if ((row == -1) && (column == -1)) {
2428	return sourceModel()->dropMimeData(data, action, row: -1, column: -1, parent: mapToSource(proxyIndex: parent));
2429	}
2430
2431	int source_destination_row = -1;
2432	int source_destination_column = -1;
2433	QModelIndex source_parent;
2434
2435	if (row == rowCount(index: parent)) {
2436	source_parent = mapToSource(proxyIndex: parent);
2437	source_destination_row = sourceModel()->rowCount(parent: source_parent);
2438	} else {
2439	const QModelIndex proxy_index = index(row, column, parent);
2440	const QModelIndex source_index = mapToSource(proxyIndex: proxy_index);
2441	source_destination_row = source_index.row();
2442	source_destination_column = source_index.column();
2443	source_parent = source_index.parent();
2444	}
2445	return sourceModel()->dropMimeData(data, action, row: source_destination_row, column: source_destination_column, parent: source_parent);
2446	}
2447
2448	QList<QPersistentModelIndex> KSelectionProxyModel::sourceRootIndexes() const
2449	{
2450	Q_D(const KSelectionProxyModel);
2451	return d->m_rootIndexList;
2452	}
2453
2454	QModelIndexList KSelectionProxyModel::match(const QModelIndex &start, int role, const QVariant &value, int hits, Qt::MatchFlags flags) const
2455	{
2456	if (role < Qt::UserRole) {
2457	return QAbstractProxyModel::match(start, role, value, hits, flags);
2458	}
2459
2460	QModelIndexList list;
2461	QModelIndex proxyIndex;
2462	const auto lst = sourceModel()->match(start: mapToSource(proxyIndex: start), role, value, hits, flags);
2463	for (const QModelIndex &idx : lst) {
2464	proxyIndex = mapFromSource(sourceIndex: idx);
2465	if (proxyIndex.isValid()) {
2466	list << proxyIndex;
2467	}
2468	}
2469	return list;
2470	}
2471
2472	QItemSelection KSelectionProxyModel::mapSelectionFromSource(const QItemSelection &selection) const
2473	{
2474	Q_D(const KSelectionProxyModel);
2475	if (!d->m_startWithChildTrees && d->m_includeAllSelected) {
2476	// QAbstractProxyModel::mapSelectionFromSource puts invalid ranges in the result
2477	// without checking. We can't have that.
2478	QItemSelection proxySelection;
2479	for (const QItemSelectionRange &range : selection) {
2480	QModelIndex proxyTopLeft = mapFromSource(sourceIndex: range.topLeft());
2481	if (!proxyTopLeft.isValid()) {
2482	continue;
2483	}
2484	QModelIndex proxyBottomRight = mapFromSource(sourceIndex: range.bottomRight());
2485	Q_ASSERT(proxyBottomRight.isValid());
2486	proxySelection.append(t: QItemSelectionRange(proxyTopLeft, proxyBottomRight));
2487	}
2488	return proxySelection;
2489	}
2490
2491	QItemSelection proxySelection;
2492	QItemSelection::const_iterator it = selection.constBegin();
2493	const QItemSelection::const_iterator end = selection.constEnd();
2494	for (; it != end; ++it) {
2495	const QModelIndex proxyTopLeft = mapFromSource(sourceIndex: it->topLeft());
2496	if (!proxyTopLeft.isValid()) {
2497	continue;
2498	}
2499
2500	if (it->height() == 1 && it->width() == 1) {
2501	proxySelection.append(t: QItemSelectionRange(proxyTopLeft, proxyTopLeft));
2502	} else {
2503	proxySelection.append(t: QItemSelectionRange(proxyTopLeft, d->mapFromSource(sourceIndex: it->bottomRight())));
2504	}
2505	}
2506	return proxySelection;
2507	}
2508
2509	QItemSelection KSelectionProxyModel::mapSelectionToSource(const QItemSelection &selection) const
2510	{
2511	Q_D(const KSelectionProxyModel);
2512
2513	if (selection.isEmpty()) {
2514	return selection;
2515	}
2516
2517	if (!d->m_startWithChildTrees && d->m_includeAllSelected) {
2518	// QAbstractProxyModel::mapSelectionFromSource puts invalid ranges in the result
2519	// without checking. We can't have that.
2520	QItemSelection sourceSelection;
2521	for (const QItemSelectionRange &range : selection) {
2522	QModelIndex sourceTopLeft = mapToSource(proxyIndex: range.topLeft());
2523	Q_ASSERT(sourceTopLeft.isValid());
2524
2525	QModelIndex sourceBottomRight = mapToSource(proxyIndex: range.bottomRight());
2526	Q_ASSERT(sourceBottomRight.isValid());
2527	sourceSelection.append(t: QItemSelectionRange(sourceTopLeft, sourceBottomRight));
2528	}
2529	return sourceSelection;
2530	}
2531
2532	QItemSelection sourceSelection;
2533	QItemSelection extraSelection;
2534	QItemSelection::const_iterator it = selection.constBegin();
2535	const QItemSelection::const_iterator end = selection.constEnd();
2536	for (; it != end; ++it) {
2537	const QModelIndex sourceTopLeft = mapToSource(proxyIndex: it->topLeft());
2538	if (it->height() == 1 && it->width() == 1) {
2539	sourceSelection.append(t: QItemSelectionRange(sourceTopLeft, sourceTopLeft));
2540	} else if (it->parent().isValid()) {
2541	sourceSelection.append(t: QItemSelectionRange(sourceTopLeft, mapToSource(proxyIndex: it->bottomRight())));
2542	} else {
2543	// A contiguous selection in the proxy might not be contiguous in the source if it
2544	// is at the top level of the proxy.
2545	if (d->m_startWithChildTrees) {
2546	const QModelIndex sourceParent = mapFromSource(sourceIndex: sourceTopLeft);
2547	Q_ASSERT(sourceParent.isValid());
2548	const int rowCount = sourceModel()->rowCount(parent: sourceParent);
2549	if (rowCount < it->bottom()) {
2550	Q_ASSERT(sourceTopLeft.isValid());
2551	Q_ASSERT(it->bottomRight().isValid());
2552	const QModelIndex sourceBottomRight = mapToSource(proxyIndex: it->bottomRight());
2553	Q_ASSERT(sourceBottomRight.isValid());
2554	sourceSelection.append(t: QItemSelectionRange(sourceTopLeft, sourceBottomRight));
2555	continue;
2556	}
2557	// Store the contiguous part...
2558	const QModelIndex sourceBottomRight = sourceModel()->index(row: rowCount - 1, column: it->right(), parent: sourceParent);
2559	Q_ASSERT(sourceTopLeft.isValid());
2560	Q_ASSERT(sourceBottomRight.isValid());
2561	sourceSelection.append(t: QItemSelectionRange(sourceTopLeft, sourceBottomRight));
2562	// ... and the rest will be processed later.
2563	extraSelection.append(t: QItemSelectionRange(createIndex(arow: it->top() - rowCount, acolumn: it->right()), it->bottomRight()));
2564	} else {
2565	QItemSelection topSelection;
2566	const QModelIndex idx = createIndex(arow: it->top(), acolumn: it->right());
2567	const QModelIndex sourceIdx = mapToSource(proxyIndex: idx);
2568	Q_ASSERT(sourceIdx.isValid());
2569	topSelection.append(t: QItemSelectionRange(sourceTopLeft, sourceIdx));
2570	for (int i = it->top() + 1; i <= it->bottom(); ++i) {
2571	const QModelIndex left = mapToSource(proxyIndex: createIndex(arow: i, acolumn: 0));
2572	const QModelIndex right = mapToSource(proxyIndex: createIndex(arow: i, acolumn: it->right()));
2573	Q_ASSERT(left.isValid());
2574	Q_ASSERT(right.isValid());
2575	topSelection.append(t: QItemSelectionRange(left, right));
2576	}
2577	sourceSelection += kNormalizeSelection(selection: topSelection);
2578	}
2579	}
2580	}
2581	sourceSelection << mapSelectionToSource(selection: extraSelection);
2582	return sourceSelection;
2583	}
2584
2585	#include "moc_kselectionproxymodel.cpp"
2586