1	// Copyright (C) 2021 The Qt Company Ltd.
2	// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4	#include "qitemselectionmodel.h"
5	#include "qitemselectionmodel_p.h"
6
7	#include <private/qitemselectionmodel_p.h>
8	#include <private/qabstractitemmodel_p.h>
9	#include <private/qduplicatetracker_p.h>
10	#include <private/qoffsetstringarray_p.h>
11	#include <qdebug.h>
12
13	#include <algorithm>
14	#include <functional>
15
16	QT_BEGIN_NAMESPACE
17
18	QT_IMPL_METATYPE_EXTERN(QItemSelectionRange)
19	QT_IMPL_METATYPE_EXTERN(QItemSelection)
20
21	/*!
22	\class QItemSelectionRange
23	\inmodule QtCore
24
25	\brief The QItemSelectionRange class manages information about a
26	range of selected items in a model.
27
28	\ingroup model-view
29
30	\compares equality
31
32	A QItemSelectionRange contains information about a range of
33	selected items in a model. A range of items is a contiguous array
34	of model items, extending to cover a number of adjacent rows and
35	columns with a common parent item; this can be visualized as a
36	two-dimensional block of cells in a table. A selection range has a
37	top(), left() a bottom(), right() and a parent().
38
39	The QItemSelectionRange class is one of the \l{Model/View Classes}
40	and is part of Qt's \l{Model/View Programming}{model/view framework}.
41
42	The model items contained in the selection range can be obtained
43	using the indexes() function. Use QItemSelectionModel::selectedIndexes()
44	to get a list of all selected items for a view.
45
46	You can determine whether a given model item lies within a
47	particular range by using the contains() function. Ranges can also
48	be compared using the overloaded operators for equality and
49	inequality, and the intersects() function allows you to determine
50	whether two ranges overlap.
51
52	\sa {Model/View Programming}, QAbstractItemModel, QItemSelection,
53	QItemSelectionModel
54	*/
55
56	/*!
57	\fn QItemSelectionRange::QItemSelectionRange()
58
59	Constructs an empty selection range.
60	*/
61
62	/*!
63	\fn QItemSelectionRange::QItemSelectionRange(const QModelIndex &topLeft, const QModelIndex &bottomRight)
64
65	Constructs a new selection range containing only the index specified
66	by the \a topLeft and the index \a bottomRight.
67
68	*/
69
70	/*!
71	\fn QItemSelectionRange::QItemSelectionRange(const QModelIndex &index)
72
73	Constructs a new selection range containing only the model item specified
74	by the model index \a index.
75	*/
76
77	/*!
78	\fn QItemSelectionRange::swap(QItemSelectionRange &other)
79	\since 5.6
80	\memberswap{selection range's contents}
81	*/
82
83	/*!
84	\fn int QItemSelectionRange::top() const
85
86	Returns the row index corresponding to the uppermost selected row in the
87	selection range.
88
89	*/
90
91	/*!
92	\fn int QItemSelectionRange::left() const
93
94	Returns the column index corresponding to the leftmost selected column in the
95	selection range.
96	*/
97
98	/*!
99	\fn int QItemSelectionRange::bottom() const
100
101	Returns the row index corresponding to the lowermost selected row in the
102	selection range.
103
104	*/
105
106	/*!
107	\fn int QItemSelectionRange::right() const
108
109	Returns the column index corresponding to the rightmost selected column in
110	the selection range.
111
112	*/
113
114	/*!
115	\fn int QItemSelectionRange::width() const
116
117	Returns the number of selected columns in the selection range.
118
119	*/
120
121	/*!
122	\fn int QItemSelectionRange::height() const
123
124	Returns the number of selected rows in the selection range.
125
126	*/
127
128	/*!
129	\fn const QAbstractItemModel *QItemSelectionRange::model() const
130
131	Returns the model that the items in the selection range belong to.
132	*/
133
134	/*!
135	\fn QModelIndex QItemSelectionRange::topLeft() const
136
137	Returns the index for the item located at the top-left corner of
138	the selection range.
139
140	\sa top(), left(), bottomRight()
141	*/
142
143	/*!
144	\fn QModelIndex QItemSelectionRange::bottomRight() const
145
146	Returns the index for the item located at the bottom-right corner
147	of the selection range.
148
149	\sa bottom(), right(), topLeft()
150	*/
151
152	/*!
153	\fn QModelIndex QItemSelectionRange::parent() const
154
155	Returns the parent model item index of the items in the selection range.
156
157	*/
158
159	/*!
160	\fn bool QItemSelectionRange::contains(const QModelIndex &index) const
161
162	Returns \c true if the model item specified by the \a index lies within the
163	range of selected items; otherwise returns \c false.
164	*/
165
166	/*!
167	\fn bool QItemSelectionRange::contains(int row, int column,
168	const QModelIndex &parentIndex) const
169	\overload
170
171	Returns \c true if the model item specified by (\a row, \a column)
172	and with \a parentIndex as the parent item lies within the range
173	of selected items; otherwise returns \c false.
174	*/
175
176	/*!
177	\fn bool QItemSelectionRange::intersects(const QItemSelectionRange &other) const
178
179	Returns \c true if this selection range intersects (overlaps with) the \a other
180	range given; otherwise returns \c false.
181
182	*/
183	bool QItemSelectionRange::intersects(const QItemSelectionRange &other) const
184	{
185	// isValid() and parent() last since they are more expensive
186	return (model() == other.model()
187	&& ((top() <= other.top() && bottom() >= other.top())
188	|| (top() >= other.top() && top() <= other.bottom()))
189	&& ((left() <= other.left() && right() >= other.left())
190	|| (left() >= other.left() && left() <= other.right()))
191	&& parent() == other.parent()
192	&& isValid() && other.isValid()
193	);
194	}
195
196	/*!
197	\fn QItemSelectionRange QItemSelectionRange::intersected(const QItemSelectionRange &other) const
198	\since 4.2
199
200	Returns a new selection range containing only the items that are found in
201	both the selection range and the \a other selection range.
202	*/
203
204	QItemSelectionRange QItemSelectionRange::intersected(const QItemSelectionRange &other) const
205	{
206	if (model() == other.model() && parent() == other.parent()) {
207	QModelIndex topLeft = model()->index(row: qMax(a: top(), b: other.top()),
208	column: qMax(a: left(), b: other.left()),
209	parent: other.parent());
210	QModelIndex bottomRight = model()->index(row: qMin(a: bottom(), b: other.bottom()),
211	column: qMin(a: right(), b: other.right()),
212	parent: other.parent());
213	return QItemSelectionRange(topLeft, bottomRight);
214	}
215	return QItemSelectionRange();
216	}
217
218	/*!
219	\fn bool QItemSelectionRange::operator==(const QItemSelectionRange &lhs, const QItemSelectionRange &rhs)
220
221	Returns \c true if \a lhs selection range is exactly the same as the \a rhs
222	range given; otherwise returns \c false.
223
224	*/
225
226	/*!
227	\fn bool QItemSelectionRange::operator!=(const QItemSelectionRange &lhs, const QItemSelectionRange &rhs)
228
229	Returns \c true if \a lhs selection range differs from the \a rhs range given;
230	otherwise returns \c false.
231
232	*/
233
234	/*!
235	\fn bool QItemSelectionRange::isValid() const
236
237	Returns \c true if the selection range is valid; otherwise returns \c false.
238
239	*/
240
241	static void rowLengthsFromRange(const QItemSelectionRange &range, QList<std::pair<QPersistentModelIndex, uint>> &result)
242	{
243	if (range.isValid() && range.model()) {
244	const QModelIndex topLeft = range.topLeft();
245	const int bottom = range.bottom();
246	const uint width = range.width();
247	const int column = topLeft.column();
248	for (int row = topLeft.row(); row <= bottom; ++row) {
249	// We don't need to keep track of ItemIsSelectable and ItemIsEnabled here. That is
250	// required in indexesFromRange() because that method is called from public API
251	// which requires the limitation.
252	result.emplace_back(args: topLeft.sibling(arow: row, acolumn: column), args: width);
253	}
254	}
255	}
256
257	static bool isSelectableAndEnabled(Qt::ItemFlags flags)
258	{
259	return flags.testFlags(flags: Qt::ItemIsSelectable | Qt::ItemIsEnabled);
260	}
261
262	template<typename ModelIndexContainer>
263	static void indexesFromRange(const QItemSelectionRange &range, ModelIndexContainer &result)
264	{
265	if (range.isValid() && range.model()) {
266	const QModelIndex topLeft = range.topLeft();
267	const int bottom = range.bottom();
268	const int right = range.right();
269	for (int row = topLeft.row(); row <= bottom; ++row) {
270	const QModelIndex columnLeader = topLeft.sibling(arow: row, acolumn: topLeft.column());
271	for (int column = topLeft.column(); column <= right; ++column) {
272	QModelIndex index = columnLeader.sibling(arow: row, acolumn: column);
273	if (isSelectableAndEnabled(flags: range.model()->flags(index)))
274	result.push_back(index);
275	}
276	}
277	}
278	}
279
280	template<typename ModelIndexContainer>
281	static ModelIndexContainer qSelectionIndexes(const QItemSelection &selection)
282	{
283	ModelIndexContainer result;
284	for (const auto &range : selection)
285	indexesFromRange(range, result);
286	return result;
287	}
288
289	/*!
290	Returns \c true if the selection range contains either no items
291	or only items which are either disabled or marked as not selectable.
292
293	\since 4.7
294	*/
295
296	bool QItemSelectionRange::isEmpty() const
297	{
298	if (!isValid() || !model())
299	return true;
300
301	for (int column = left(); column <= right(); ++column) {
302	for (int row = top(); row <= bottom(); ++row) {
303	QModelIndex index = model()->index(row, column, parent: parent());
304	if (isSelectableAndEnabled(flags: model()->flags(index)))
305	return false;
306	}
307	}
308	return true;
309	}
310
311	/*!
312	Returns the list of model index items stored in the selection.
313	*/
314
315	QModelIndexList QItemSelectionRange::indexes() const
316	{
317	QModelIndexList result;
318	indexesFromRange(range: *this, result);
319	return result;
320	}
321
322	/*!
323	\class QItemSelection
324	\inmodule QtCore
325
326	\brief The QItemSelection class manages information about selected items in a model.
327
328	\ingroup model-view
329
330	A QItemSelection describes the items in a model that have been
331	selected by the user. A QItemSelection is basically a list of
332	selection ranges, see QItemSelectionRange. It provides functions for
333	creating and manipulating selections, and selecting a range of items
334	from a model.
335
336	The QItemSelection class is one of the \l{Model/View Classes}
337	and is part of Qt's \l{Model/View Programming}{model/view framework}.
338
339	An item selection can be constructed and initialized to contain a
340	range of items from an existing model. The following example constructs
341	a selection that contains a range of items from the given \c model,
342	beginning at the \c topLeft, and ending at the \c bottomRight.
343
344	\snippet code/src_gui_itemviews_qitemselectionmodel.cpp 0
345
346	An empty item selection can be constructed, and later populated as
347	required. So, if the model is going to be unavailable when we construct
348	the item selection, we can rewrite the above code in the following way:
349
350	\snippet code/src_gui_itemviews_qitemselectionmodel.cpp 1
351
352	QItemSelection saves memory, and avoids unnecessary work, by working with
353	selection ranges rather than recording the model item index for each
354	item in the selection. Generally, an instance of this class will contain
355	a list of non-overlapping selection ranges.
356
357	Use merge() to merge one item selection into another without making
358	overlapping ranges. Use split() to split one selection range into
359	smaller ranges based on a another selection range.
360
361	\sa {Model/View Programming}, QItemSelectionModel
362	*/
363
364	/*!
365	\fn QItemSelection::QItemSelection()
366
367	Constructs an empty selection.
368	*/
369
370	/*!
371	Constructs an item selection that extends from the top-left model item,
372	specified by the \a topLeft index, to the bottom-right item, specified
373	by \a bottomRight.
374	*/
375	QItemSelection::QItemSelection(const QModelIndex &topLeft, const QModelIndex &bottomRight)
376	{
377	select(topLeft, bottomRight);
378	}
379
380	/*!
381	Adds the items in the range that extends from the top-left model
382	item, specified by the \a topLeft index, to the bottom-right item,
383	specified by \a bottomRight to the list.
384
385	\note \a topLeft and \a bottomRight must have the same parent.
386	*/
387	void QItemSelection::select(const QModelIndex &topLeft, const QModelIndex &bottomRight)
388	{
389	if (!topLeft.isValid() || !bottomRight.isValid())
390	return;
391
392	if ((topLeft.model() != bottomRight.model())
393	|| topLeft.parent() != bottomRight.parent()) {
394	qWarning(msg: "Can't select indexes from different model or with different parents");
395	return;
396	}
397	if (topLeft.row() > bottomRight.row() || topLeft.column() > bottomRight.column()) {
398	int top = qMin(a: topLeft.row(), b: bottomRight.row());
399	int bottom = qMax(a: topLeft.row(), b: bottomRight.row());
400	int left = qMin(a: topLeft.column(), b: bottomRight.column());
401	int right = qMax(a: topLeft.column(), b: bottomRight.column());
402	QModelIndex tl = topLeft.sibling(arow: top, acolumn: left);
403	QModelIndex br = bottomRight.sibling(arow: bottom, acolumn: right);
404	append(t: QItemSelectionRange(tl, br));
405	return;
406	}
407	append(t: QItemSelectionRange(topLeft, bottomRight));
408	}
409
410	/*!
411	Returns \c true if the selection contains the given \a index; otherwise
412	returns \c false.
413	*/
414
415	bool QItemSelection::contains(const QModelIndex &index) const
416	{
417	if (isSelectableAndEnabled(flags: index.flags())) {
418	QList<QItemSelectionRange>::const_iterator it = begin();
419	for (; it != end(); ++it)
420	if ((*it).contains(index))
421	return true;
422	}
423	return false;
424	}
425
426	/*!
427	Returns a list of model indexes that correspond to the selected items.
428	*/
429
430	QModelIndexList QItemSelection::indexes() const
431	{
432	return qSelectionIndexes<QModelIndexList>(selection: *this);
433	}
434
435	static QList<std::pair<QPersistentModelIndex, uint>> qSelectionPersistentRowLengths(const QItemSelection &sel)
436	{
437	QList<std::pair<QPersistentModelIndex, uint>> result;
438	for (const QItemSelectionRange &range : sel)
439	rowLengthsFromRange(range, result);
440	return result;
441	}
442
443	/*!
444	Merges the \a other selection with this QItemSelection using the
445	\a command given. This method guarantees that no ranges are overlapping.
446
447	Note that only QItemSelectionModel::Select,
448	QItemSelectionModel::Deselect, and QItemSelectionModel::Toggle are
449	supported.
450
451	\sa split()
452	*/
453	void QItemSelection::merge(const QItemSelection &other, QItemSelectionModel::SelectionFlags command)
454	{
455	if (other.isEmpty() ||
456	!(command & QItemSelectionModel::Select ||
457	command & QItemSelectionModel::Deselect ||
458	command & QItemSelectionModel::Toggle))
459	return;
460
461	QItemSelection newSelection;
462	newSelection.reserve(asize: other.size());
463	// Collect intersections
464	QItemSelection intersections;
465	for (const auto &range : other) {
466	if (!range.isValid())
467	continue;
468	newSelection.push_back(t: range);
469	for (int t = 0; t < size(); ++t) {
470	if (range.intersects(other: at(i: t)))
471	intersections.append(t: at(i: t).intersected(other: range));
472	}
473	}
474
475	// Split the old (and new) ranges using the intersections
476	for (int i = 0; i < intersections.size(); ++i) { // for each intersection
477	for (int t = 0; t < size();) { // splitt each old range
478	if (at(i: t).intersects(other: intersections.at(i))) {
479	split(range: at(i: t), other: intersections.at(i), result: this);
480	removeAt(i: t);
481	} else {
482	++t;
483	}
484	}
485	// only split newSelection if Toggle is specified
486	for (int n = 0; (command & QItemSelectionModel::Toggle) && n < newSelection.size();) {
487	if (newSelection.at(i: n).intersects(other: intersections.at(i))) {
488	split(range: newSelection.at(i: n), other: intersections.at(i), result: &newSelection);
489	newSelection.removeAt(i: n);
490	} else {
491	++n;
492	}
493	}
494	}
495	// do not add newSelection for Deselect
496	if (!(command & QItemSelectionModel::Deselect))
497	operator+=(l: newSelection);
498	}
499
500	/*!
501	Splits the selection \a range using the selection \a other range.
502	Removes all items in \a other from \a range and puts the result in \a result.
503	This can be compared with the semantics of the \e subtract operation of a set.
504	\sa merge()
505	*/
506
507	void QItemSelection::split(const QItemSelectionRange &range,
508	const QItemSelectionRange &other, QItemSelection *result)
509	{
510	if (range.parent() != other.parent() || range.model() != other.model())
511	return;
512
513	QModelIndex parent = other.parent();
514	int top = range.top();
515	int left = range.left();
516	int bottom = range.bottom();
517	int right = range.right();
518	int other_top = other.top();
519	int other_left = other.left();
520	int other_bottom = other.bottom();
521	int other_right = other.right();
522	const QAbstractItemModel *model = range.model();
523	Q_ASSERT(model);
524	if (other_top > top) {
525	QModelIndex tl = model->index(row: top, column: left, parent);
526	QModelIndex br = model->index(row: other_top - 1, column: right, parent);
527	result->append(t: QItemSelectionRange(tl, br));
528	top = other_top;
529	}
530	if (other_bottom < bottom) {
531	QModelIndex tl = model->index(row: other_bottom + 1, column: left, parent);
532	QModelIndex br = model->index(row: bottom, column: right, parent);
533	result->append(t: QItemSelectionRange(tl, br));
534	bottom = other_bottom;
535	}
536	if (other_left > left) {
537	QModelIndex tl = model->index(row: top, column: left, parent);
538	QModelIndex br = model->index(row: bottom, column: other_left - 1, parent);
539	result->append(t: QItemSelectionRange(tl, br));
540	left = other_left;
541	}
542	if (other_right < right) {
543	QModelIndex tl = model->index(row: top, column: other_right + 1, parent);
544	QModelIndex br = model->index(row: bottom, column: right, parent);
545	result->append(t: QItemSelectionRange(tl, br));
546	right = other_right;
547	}
548	}
549
550	QItemSelectionModelPrivate::~QItemSelectionModelPrivate()
551	= default;
552
553	void QItemSelectionModelPrivate::initModel(QAbstractItemModel *m)
554	{
555	Q_Q(QItemSelectionModel);
556	const QAbstractItemModel *oldModel = model.valueBypassingBindings();
557	if (oldModel == m)
558	return;
559
560	if (oldModel) {
561	q->reset();
562	disconnectModel();
563	}
564
565	// Caller has to call notify(), unless calling during construction (the common case).
566	model.setValueBypassingBindings(m);
567
568	if (m) {
569	connections = std::array<QMetaObject::Connection, 12> {
570	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::rowsAboutToBeRemoved,
571	receiverPrivate: this, slot: &QItemSelectionModelPrivate::rowsAboutToBeRemoved),
572	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::columnsAboutToBeRemoved,
573	receiverPrivate: this, slot: &QItemSelectionModelPrivate::columnsAboutToBeRemoved),
574	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::rowsAboutToBeInserted,
575	receiverPrivate: this, slot: &QItemSelectionModelPrivate::rowsAboutToBeInserted),
576	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::columnsAboutToBeInserted,
577	receiverPrivate: this, slot: &QItemSelectionModelPrivate::columnsAboutToBeInserted),
578	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::rowsAboutToBeMoved,
579	receiverPrivate: this, slot: &QItemSelectionModelPrivate::triggerLayoutToBeChanged),
580	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::columnsAboutToBeMoved,
581	receiverPrivate: this, slot: &QItemSelectionModelPrivate::triggerLayoutToBeChanged),
582	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::rowsMoved,
583	receiverPrivate: this, slot: &QItemSelectionModelPrivate::triggerLayoutChanged),
584	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::columnsMoved,
585	receiverPrivate: this, slot: &QItemSelectionModelPrivate::triggerLayoutChanged),
586	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::layoutAboutToBeChanged,
587	receiverPrivate: this, slot: &QItemSelectionModelPrivate::layoutAboutToBeChanged),
588	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::layoutChanged,
589	receiverPrivate: this, slot: &QItemSelectionModelPrivate::layoutChanged),
590	QObject::connect(sender: m, signal: &QAbstractItemModel::modelReset,
591	context: q, slot: &QItemSelectionModel::reset),
592	QObjectPrivate::connect(sender: m, signal: &QAbstractItemModel::destroyed,
593	receiverPrivate: this, slot: &QItemSelectionModelPrivate::modelDestroyed)
594	};
595	}
596	}
597
598	void QItemSelectionModelPrivate::disconnectModel()
599	{
600	for (auto &connection : connections)
601	QObject::disconnect(connection);
602	}
603
604	/*!
605	\internal
606
607	returns a QItemSelection where all ranges have been expanded to:
608	Rows: left: 0 and right: columnCount()-1
609	Columns: top: 0 and bottom: rowCount()-1
610	*/
611
612	QItemSelection QItemSelectionModelPrivate::expandSelection(const QItemSelection &selection,
613	QItemSelectionModel::SelectionFlags command) const
614	{
615	if (selection.isEmpty() && !((command & QItemSelectionModel::Rows) ||
616	(command & QItemSelectionModel::Columns)))
617	return selection;
618
619	QItemSelection expanded;
620	if (command & QItemSelectionModel::Rows) {
621	for (int i = 0; i < selection.size(); ++i) {
622	QModelIndex parent = selection.at(i).parent();
623	int colCount = model->columnCount(parent);
624	QModelIndex tl = model->index(row: selection.at(i).top(), column: 0, parent);
625	QModelIndex br = model->index(row: selection.at(i).bottom(), column: colCount - 1, parent);
626	//we need to merge because the same row could have already been inserted
627	expanded.merge(other: QItemSelection(tl, br), command: QItemSelectionModel::Select);
628	}
629	}
630	if (command & QItemSelectionModel::Columns) {
631	for (int i = 0; i < selection.size(); ++i) {
632	QModelIndex parent = selection.at(i).parent();
633	int rowCount = model->rowCount(parent);
634	QModelIndex tl = model->index(row: 0, column: selection.at(i).left(), parent);
635	QModelIndex br = model->index(row: rowCount - 1, column: selection.at(i).right(), parent);
636	//we need to merge because the same column could have already been inserted
637	expanded.merge(other: QItemSelection(tl, br), command: QItemSelectionModel::Select);
638	}
639	}
640	return expanded;
641	}
642
643	/*!
644	\internal
645	*/
646	void QItemSelectionModelPrivate::rowsAboutToBeRemoved(const QModelIndex &parent,
647	int start, int end)
648	{
649	Q_Q(QItemSelectionModel);
650	Q_ASSERT(start <= end);
651	finalize();
652
653	// update current index
654	if (currentIndex.isValid() && parent == currentIndex.parent()
655	&& currentIndex.row() >= start && currentIndex.row() <= end) {
656	QModelIndex old = currentIndex;
657	if (start > 0) {
658	// there are rows left above the change
659	currentIndex = model->index(row: start - 1, column: old.column(), parent);
660	} else if (model.value() && end < model->rowCount(parent) - 1) {
661	// there are rows left below the change
662	currentIndex = model->index(row: end + 1, column: old.column(), parent);
663	} else {
664	// there are no rows left in the table
665	currentIndex = QModelIndex();
666	}
667	emit q->currentChanged(current: currentIndex, previous: old);
668	emit q->currentRowChanged(current: currentIndex, previous: old);
669	if (currentIndex.column() != old.column())
670	emit q->currentColumnChanged(current: currentIndex, previous: old);
671	}
672
673	QItemSelection deselected;
674	QItemSelection newParts;
675	bool indexesOfSelectionChanged = false;
676	QItemSelection::iterator it = ranges.begin();
677	while (it != ranges.end()) {
678	if (it->topLeft().parent() != parent) { // Check parents until reaching root or contained in range
679	QModelIndex itParent = it->topLeft().parent();
680	while (itParent.isValid() && itParent.parent() != parent)
681	itParent = itParent.parent();
682
683	if (itParent.isValid() && start <= itParent.row() && itParent.row() <= end) {
684	deselected.append(t: *it);
685	it = ranges.erase(pos: it);
686	} else {
687	if (itParent.isValid() && end < itParent.row())
688	indexesOfSelectionChanged = true;
689	++it;
690	}
691	} else if (start <= it->bottom() && it->bottom() <= end // Full inclusion
692	&& start <= it->top() && it->top() <= end) {
693	deselected.append(t: *it);
694	it = ranges.erase(pos: it);
695	} else if (start <= it->top() && it->top() <= end) { // Top intersection
696	deselected.append(t: QItemSelectionRange(it->topLeft(), model->index(row: end, column: it->right(), parent: it->parent())));
697	*it = QItemSelectionRange(model->index(row: end + 1, column: it->left(), parent: it->parent()), it->bottomRight());
698	++it;
699	} else if (start <= it->bottom() && it->bottom() <= end) { // Bottom intersection
700	deselected.append(t: QItemSelectionRange(model->index(row: start, column: it->left(), parent: it->parent()), it->bottomRight()));
701	*it = QItemSelectionRange(it->topLeft(), model->index(row: start - 1, column: it->right(), parent: it->parent()));
702	++it;
703	} else if (it->top() < start && end < it->bottom()) { // Middle intersection
704	// If the parent contains (1, 2, 3, 4, 5, 6, 7, 8) and [3, 4, 5, 6] is selected,
705	// and [4, 5] is removed, we need to split [3, 4, 5, 6] into [3], [4, 5] and [6].
706	// [4, 5] is appended to deselected, and [3] and [6] remain part of the selection
707	// in ranges.
708	const QItemSelectionRange removedRange(model->index(row: start, column: it->left(), parent: it->parent()),
709	model->index(row: end, column: it->right(), parent: it->parent()));
710	deselected.append(t: removedRange);
711	QItemSelection::split(range: *it, other: removedRange, result: &newParts);
712	it = ranges.erase(pos: it);
713	} else if (end < it->top()) { // deleted row before selection
714	indexesOfSelectionChanged = true;
715	++it;
716	} else {
717	++it;
718	}
719	}
720	ranges.append(l: newParts);
721
722	if (!deselected.isEmpty() || indexesOfSelectionChanged)
723	emit q->selectionChanged(selected: QItemSelection(), deselected);
724	}
725
726	/*!
727	\internal
728	*/
729	void QItemSelectionModelPrivate::columnsAboutToBeRemoved(const QModelIndex &parent,
730	int start, int end)
731	{
732	Q_Q(QItemSelectionModel);
733
734	// update current index
735	if (currentIndex.isValid() && parent == currentIndex.parent()
736	&& currentIndex.column() >= start && currentIndex.column() <= end) {
737	QModelIndex old = currentIndex;
738	if (start > 0) {
739	// there are columns to the left of the change
740	currentIndex = model->index(row: old.row(), column: start - 1, parent);
741	} else if (model.value() && end < model->columnCount() - 1) {
742	// there are columns to the right of the change
743	currentIndex = model->index(row: old.row(), column: end + 1, parent);
744	} else {
745	// there are no columns left in the table
746	currentIndex = QModelIndex();
747	}
748	emit q->currentChanged(current: currentIndex, previous: old);
749	if (currentIndex.row() != old.row())
750	emit q->currentRowChanged(current: currentIndex, previous: old);
751	emit q->currentColumnChanged(current: currentIndex, previous: old);
752	}
753
754	// update selections
755	QModelIndex tl = model->index(row: 0, column: start, parent);
756	QModelIndex br = model->index(row: model->rowCount(parent) - 1, column: end, parent);
757	q->select(selection: QItemSelection(tl, br), command: QItemSelectionModel::Deselect);
758	finalize();
759	}
760
761	/*!
762	\internal
763
764	Split selection ranges if columns are about to be inserted in the middle.
765	*/
766	void QItemSelectionModelPrivate::columnsAboutToBeInserted(const QModelIndex &parent,
767	int start, int end)
768	{
769	Q_UNUSED(end);
770	finalize();
771	QList<QItemSelectionRange> split;
772	QList<QItemSelectionRange>::iterator it = ranges.begin();
773	for (; it != ranges.end(); ) {
774	const QModelIndex &itParent = it->parent();
775	if ((*it).isValid() && itParent == parent
776	&& (*it).left() < start && (*it).right() >= start) {
777	QModelIndex bottomMiddle = model->index(row: (*it).bottom(), column: start - 1, parent: itParent);
778	QItemSelectionRange left((*it).topLeft(), bottomMiddle);
779	QModelIndex topMiddle = model->index(row: (*it).top(), column: start, parent: itParent);
780	QItemSelectionRange right(topMiddle, (*it).bottomRight());
781	it = ranges.erase(pos: it);
782	split.append(t: left);
783	split.append(t: right);
784	} else {
785	++it;
786	}
787	}
788	ranges += split;
789	}
790
791	/*!
792	\internal
793
794	Split selection ranges if rows are about to be inserted in the middle.
795	*/
796	void QItemSelectionModelPrivate::rowsAboutToBeInserted(const QModelIndex &parent,
797	int start, int end)
798	{
799	Q_Q(QItemSelectionModel);
800	Q_UNUSED(end);
801	finalize();
802	QList<QItemSelectionRange> split;
803	QList<QItemSelectionRange>::iterator it = ranges.begin();
804	bool indexesOfSelectionChanged = false;
805	for (; it != ranges.end(); ) {
806	const QModelIndex &itParent = it->parent();
807	if ((*it).isValid() && itParent == parent
808	&& (*it).top() < start && (*it).bottom() >= start) {
809	QModelIndex middleRight = model->index(row: start - 1, column: (*it).right(), parent: itParent);
810	QItemSelectionRange top((*it).topLeft(), middleRight);
811	QModelIndex middleLeft = model->index(row: start, column: (*it).left(), parent: itParent);
812	QItemSelectionRange bottom(middleLeft, (*it).bottomRight());
813	it = ranges.erase(pos: it);
814	split.append(t: top);
815	split.append(t: bottom);
816	} else if ((*it).isValid() && itParent == parent // insertion before selection
817	&& (*it).top() >= start) {
818	indexesOfSelectionChanged = true;
819	++it;
820	} else {
821	++it;
822	}
823	}
824	ranges += split;
825
826	if (indexesOfSelectionChanged)
827	emit q->selectionChanged(selected: QItemSelection(), deselected: QItemSelection());
828	}
829
830	/*!
831	\internal
832
833	Split selection into individual (persistent) indexes. This is done in
834	preparation for the layoutChanged() signal, where the indexes can be
835	merged again.
836	*/
837	void QItemSelectionModelPrivate::layoutAboutToBeChanged(const QList<QPersistentModelIndex> &,
838	QAbstractItemModel::LayoutChangeHint hint)
839	{
840	savedPersistentIndexes.clear();
841	savedPersistentCurrentIndexes.clear();
842	savedPersistentRowLengths.clear();
843	savedPersistentCurrentRowLengths.clear();
844
845	// optimization for when all indexes are selected
846	// (only if there is lots of items (1000) because this is not entirely correct)
847	if (ranges.isEmpty() && currentSelection.size() == 1) {
848	QItemSelectionRange range = currentSelection.constFirst();
849	QModelIndex parent = range.parent();
850	tableRowCount = model->rowCount(parent);
851	tableColCount = model->columnCount(parent);
852	if (tableRowCount * tableColCount > 1000
853	&& range.top() == 0
854	&& range.left() == 0
855	&& range.bottom() == tableRowCount - 1
856	&& range.right() == tableColCount - 1) {
857	tableSelected = true;
858	tableParent = parent;
859	return;
860	}
861	}
862	tableSelected = false;
863
864	if (hint == QAbstractItemModel::VerticalSortHint) {
865	// Special case when we know we're sorting vertically. We can assume that all indexes for columns
866	// are displaced the same way, and therefore we only need to track an index from one column per
867	// row with a QPersistentModelIndex together with the length of items to the right of it
868	// which are displaced the same way.
869	// An algorithm which contains the same assumption is used to process layoutChanged.
870	savedPersistentRowLengths = qSelectionPersistentRowLengths(sel: ranges);
871	savedPersistentCurrentRowLengths = qSelectionPersistentRowLengths(sel: currentSelection);
872	} else {
873	savedPersistentIndexes = qSelectionIndexes<QList<QPersistentModelIndex>>(selection: ranges);
874	savedPersistentCurrentIndexes = qSelectionIndexes<QList<QPersistentModelIndex>>(selection: currentSelection);
875	}
876	}
877	/*!
878	\internal
879	*/
880	static QItemSelection mergeRowLengths(const QList<std::pair<QPersistentModelIndex, uint>> &rowLengths)
881	{
882	if (rowLengths.isEmpty())
883	return QItemSelection();
884
885	QItemSelection result;
886	int i = 0;
887	while (i < rowLengths.size()) {
888	const QPersistentModelIndex &tl = rowLengths.at(i).first;
889	if (!tl.isValid()) {
890	++i;
891	continue;
892	}
893	QPersistentModelIndex br = tl;
894	const uint length = rowLengths.at(i).second;
895	while (++i < rowLengths.size()) {
896	const QPersistentModelIndex &next = rowLengths.at(i).first;
897	if (!next.isValid())
898	continue;
899	const uint nextLength = rowLengths.at(i).second;
900	if ((nextLength == length)
901	&& (next.row() == br.row() + 1)
902	&& (next.column() == br.column())
903	&& (next.parent() == br.parent())) {
904	br = next;
905	} else {
906	break;
907	}
908	}
909	result.append(t: QItemSelectionRange(tl, br.sibling(row: br.row(), column: br.column() + length - 1)));
910	}
911	return result;
912	}
913
914	/*!
915	\internal
916
917	Merges \a indexes into an item selection made up of ranges.
918	Assumes that the indexes are sorted.
919	*/
920	static QItemSelection mergeIndexes(const QList<QPersistentModelIndex> &indexes)
921	{
922	QItemSelection colSpans;
923	// merge columns
924	int i = 0;
925	while (i < indexes.size()) {
926	const QPersistentModelIndex &tl = indexes.at(i);
927	if (!tl.isValid()) {
928	++i;
929	continue;
930	}
931	QPersistentModelIndex br = tl;
932	QModelIndex brParent = br.parent();
933	int brRow = br.row();
934	int brColumn = br.column();
935	while (++i < indexes.size()) {
936	const QPersistentModelIndex &next = indexes.at(i);
937	if (!next.isValid())
938	continue;
939	const QModelIndex nextParent = next.parent();
940	const int nextRow = next.row();
941	const int nextColumn = next.column();
942	if ((nextParent == brParent)
943	&& (nextRow == brRow)
944	&& (nextColumn == brColumn + 1)) {
945	br = next;
946	brParent = nextParent;
947	brRow = nextRow;
948	brColumn = nextColumn;
949	} else {
950	break;
951	}
952	}
953	colSpans.append(t: QItemSelectionRange(tl, br));
954	}
955	// merge rows
956	QItemSelection rowSpans;
957	i = 0;
958	while (i < colSpans.size()) {
959	QModelIndex tl = colSpans.at(i).topLeft();
960	QModelIndex br = colSpans.at(i).bottomRight();
961	QModelIndex prevTl = tl;
962	while (++i < colSpans.size()) {
963	QModelIndex nextTl = colSpans.at(i).topLeft();
964	QModelIndex nextBr = colSpans.at(i).bottomRight();
965
966	if (nextTl.parent() != tl.parent())
967	break; // we can't merge selection ranges from different parents
968
969	if ((nextTl.column() == prevTl.column()) && (nextBr.column() == br.column())
970	&& (nextTl.row() == prevTl.row() + 1) && (nextBr.row() == br.row() + 1)) {
971	br = nextBr;
972	prevTl = nextTl;
973	} else {
974	break;
975	}
976	}
977	rowSpans.append(t: QItemSelectionRange(tl, br));
978	}
979	return rowSpans;
980	}
981
982	/*!
983	\internal
984
985	Sort predicate function for QItemSelectionModelPrivate::layoutChanged(),
986	sorting by parent first in addition to operator<(). This is to prevent
987	fragmentation of the selection by grouping indexes with the same row, column
988	of different parents next to each other, which may happen when a selection
989	spans sub-trees.
990	*/
991	static bool qt_PersistentModelIndexLessThan(const QPersistentModelIndex &i1, const QPersistentModelIndex &i2)
992	{
993	const QModelIndex parent1 = i1.parent();
994	const QModelIndex parent2 = i2.parent();
995	return parent1 == parent2 ? i1 < i2 : parent1 < parent2;
996	}
997
998	/*!
999	\internal
1000
1001	Merge the selected indexes into selection ranges again.
1002	*/
1003	void QItemSelectionModelPrivate::layoutChanged(const QList<QPersistentModelIndex> &, QAbstractItemModel::LayoutChangeHint hint)
1004	{
1005	// special case for when all indexes are selected
1006	if (tableSelected && tableColCount == model->columnCount(parent: tableParent)
1007	&& tableRowCount == model->rowCount(parent: tableParent)) {
1008	ranges.clear();
1009	currentSelection.clear();
1010	int bottom = tableRowCount - 1;
1011	int right = tableColCount - 1;
1012	QModelIndex tl = model->index(row: 0, column: 0, parent: tableParent);
1013	QModelIndex br = model->index(row: bottom, column: right, parent: tableParent);
1014	currentSelection << QItemSelectionRange(tl, br);
1015	tableParent = QModelIndex();
1016	tableSelected = false;
1017	return;
1018	}
1019
1020	if ((hint != QAbstractItemModel::VerticalSortHint && savedPersistentCurrentIndexes.isEmpty() && savedPersistentIndexes.isEmpty())
1021	|| (hint == QAbstractItemModel::VerticalSortHint && savedPersistentRowLengths.isEmpty() && savedPersistentCurrentRowLengths.isEmpty())) {
1022	// either the selection was actually empty, or we
1023	// didn't get the layoutAboutToBeChanged() signal
1024	return;
1025	}
1026
1027	// clear the "old" selection
1028	ranges.clear();
1029	currentSelection.clear();
1030
1031	if (hint != QAbstractItemModel::VerticalSortHint) {
1032	// sort the "new" selection, as preparation for merging
1033	std::stable_sort(first: savedPersistentIndexes.begin(), last: savedPersistentIndexes.end(),
1034	comp: qt_PersistentModelIndexLessThan);
1035	std::stable_sort(first: savedPersistentCurrentIndexes.begin(), last: savedPersistentCurrentIndexes.end(),
1036	comp: qt_PersistentModelIndexLessThan);
1037
1038	// update the selection by merging the individual indexes
1039	ranges = mergeIndexes(indexes: savedPersistentIndexes);
1040	currentSelection = mergeIndexes(indexes: savedPersistentCurrentIndexes);
1041
1042	// release the persistent indexes
1043	savedPersistentIndexes.clear();
1044	savedPersistentCurrentIndexes.clear();
1045	} else {
1046	// sort the "new" selection, as preparation for merging
1047	std::stable_sort(first: savedPersistentRowLengths.begin(), last: savedPersistentRowLengths.end());
1048	std::stable_sort(first: savedPersistentCurrentRowLengths.begin(), last: savedPersistentCurrentRowLengths.end());
1049
1050	// update the selection by merging the individual indexes
1051	ranges = mergeRowLengths(rowLengths: savedPersistentRowLengths);
1052	currentSelection = mergeRowLengths(rowLengths: savedPersistentCurrentRowLengths);
1053
1054	// release the persistent indexes
1055	savedPersistentRowLengths.clear();
1056	savedPersistentCurrentRowLengths.clear();
1057	}
1058	}
1059
1060	/*!
1061	\internal
1062
1063	Called when the used model gets destroyed.
1064
1065	It is impossible to have a correct implementation here.
1066	In the following situation, there are two contradicting rules:
1067
1068	\code
1069	QProperty<QAbstractItemModel *> leader(mymodel);
1070	QItemSelectionModel myItemSelectionModel;
1071	myItemSelectionModel.bindableModel().setBinding([&](){ return leader.value(); }
1072	delete mymodel;
1073	QAbstractItemModel *returnedModel = myItemSelectionModel.model();
1074	\endcode
1075
1076	What should returnedModel be in this situation?
1077
1078	Rules for bindable properties say that myItemSelectionModel.model()
1079	should return the same as leader.value(), namely the pointer to the now deleted model.
1080
1081	However, backward compatibility requires myItemSelectionModel.model() to return a
1082	nullptr, because that was done in the past after the model used was deleted.
1083
1084	We decide to break the new rule, imposed by bindable properties, and not break the old
1085	rule, because that may break existing code.
1086	*/
1087	void QItemSelectionModelPrivate::modelDestroyed()
1088	{
1089	model.setValueBypassingBindings(nullptr);
1090	disconnectModel();
1091	model.notify();
1092	}
1093
1094	/*!
1095	\class QItemSelectionModel
1096	\inmodule QtCore
1097
1098	\brief The QItemSelectionModel class keeps track of a view's selected items.
1099
1100	\ingroup model-view
1101
1102	A QItemSelectionModel keeps track of the selected items in a view, or
1103	in several views onto the same model. It also keeps track of the
1104	currently selected item in a view.
1105
1106	The QItemSelectionModel class is one of the \l{Model/View Classes}
1107	and is part of Qt's \l{Model/View Programming}{model/view framework}.
1108
1109	The selected items are stored using ranges. Whenever you want to
1110	modify the selected items use select() and provide either a
1111	QItemSelection, or a QModelIndex and a QItemSelectionModel::SelectionFlag.
1112
1113	The QItemSelectionModel takes a two layer approach to selection
1114	management, dealing with both selected items that have been committed
1115	and items that are part of the current selection. The current
1116	selected items are part of the current interactive selection (for
1117	example with rubber-band selection or keyboard-shift selections).
1118
1119	To update the currently selected items, use the bitwise OR of
1120	QItemSelectionModel::Current and any of the other SelectionFlags.
1121	If you omit the QItemSelectionModel::Current command, a new current
1122	selection will be created, and the previous one added to the whole
1123	selection. All functions operate on both layers; for example,
1124	\l {QTableWidget::selectedItems()}{selecteditems()} will return items from both layers.
1125
1126	\note Since 5.5, \l{QItemSelectionModel::model()}{model},
1127	\l{QItemSelectionModel::hasSelection()}{hasSelection}, and
1128	\l{QItemSelectionModel::currentIndex()}{currentIndex} are meta-object properties.
1129
1130	\sa {Model/View Programming}, QAbstractItemModel
1131	*/
1132
1133	/*!
1134	Constructs a selection model that operates on the specified item \a model.
1135	*/
1136	QItemSelectionModel::QItemSelectionModel(QAbstractItemModel *model)
1137	: QObject(*new QItemSelectionModelPrivate, model)
1138	{
1139	d_func()->initModel(m: model);
1140	}
1141
1142	/*!
1143	Constructs a selection model that operates on the specified item \a model with \a parent.
1144	*/
1145	QItemSelectionModel::QItemSelectionModel(QAbstractItemModel *model, QObject *parent)
1146	: QObject(*new QItemSelectionModelPrivate, parent)
1147	{
1148	d_func()->initModel(m: model);
1149	}
1150
1151	/*!
1152	\internal
1153	*/
1154	QItemSelectionModel::QItemSelectionModel(QItemSelectionModelPrivate &dd, QAbstractItemModel *model)
1155	: QObject(dd, model)
1156	{
1157	dd.initModel(m: model);
1158	}
1159
1160	/*!
1161	Destroys the selection model.
1162	*/
1163	QItemSelectionModel::~QItemSelectionModel()
1164	{
1165	}
1166
1167	/*!
1168	Selects the model item \a index using the specified \a command, and emits
1169	selectionChanged().
1170
1171	\sa QItemSelectionModel::SelectionFlags
1172	*/
1173	void QItemSelectionModel::select(const QModelIndex &index, QItemSelectionModel::SelectionFlags command)
1174	{
1175	QItemSelection selection(index, index);
1176	select(selection, command);
1177	}
1178
1179	/*!
1180	\fn void QItemSelectionModel::currentChanged(const QModelIndex &current, const QModelIndex &previous)
1181
1182	This signal is emitted whenever the current item changes. The \a previous
1183	model item index is replaced by the \a current index as the selection's
1184	current item.
1185
1186	Note that this signal will not be emitted when the item model is reset.
1187
1188	\sa currentIndex(), setCurrentIndex(), selectionChanged()
1189	*/
1190
1191	/*!
1192	\fn void QItemSelectionModel::currentColumnChanged(const QModelIndex &current, const QModelIndex &previous)
1193
1194	This signal is emitted if the \a current item changes and its column is
1195	different to the column of the \a previous current item.
1196
1197	Note that this signal will not be emitted when the item model is reset.
1198
1199	\sa currentChanged(), currentRowChanged(), currentIndex(), setCurrentIndex()
1200	*/
1201
1202	/*!
1203	\fn void QItemSelectionModel::currentRowChanged(const QModelIndex &current, const QModelIndex &previous)
1204
1205	This signal is emitted if the \a current item changes and its row is
1206	different to the row of the \a previous current item.
1207
1208	Note that this signal will not be emitted when the item model is reset.
1209
1210	\sa currentChanged(), currentColumnChanged(), currentIndex(), setCurrentIndex()
1211	*/
1212
1213	/*!
1214	\fn void QItemSelectionModel::selectionChanged(const QItemSelection &selected, const QItemSelection &deselected)
1215
1216	This signal is emitted whenever the selection changes. The change in the
1217	selection is represented as an item selection of \a deselected items and
1218	an item selection of \a selected items.
1219
1220	Note the that the current index changes independently from the selection.
1221	Also note that this signal will not be emitted when the item model is reset.
1222
1223	Items which stay selected but change their index are not included in
1224	\a selected and \a deselected. Thus, this signal might be emitted with both
1225	\a selected and \a deselected empty, if only the indices of selected items
1226	change.
1227
1228	\sa select(), currentChanged()
1229	*/
1230
1231	/*!
1232	\fn void QItemSelectionModel::modelChanged(QAbstractItemModel *model)
1233	\since 5.5
1234
1235	This signal is emitted when the \a model is successfully set with setModel().
1236
1237	\sa model(), setModel()
1238	*/
1239
1240
1241	/*!
1242	\enum QItemSelectionModel::SelectionFlag
1243
1244	This enum describes the way the selection model will be updated.
1245
1246	\value NoUpdate No selection will be made.
1247	\value Clear The complete selection will be cleared.
1248	\value Select All specified indexes will be selected.
1249	\value Deselect All specified indexes will be deselected.
1250	\value Toggle All specified indexes will be selected or
1251	deselected depending on their current state.
1252	\value Current The current selection will be updated.
1253	\value Rows All indexes will be expanded to span rows.
1254	\value Columns All indexes will be expanded to span columns.
1255	\value SelectCurrent A combination of Select and Current, provided for
1256	convenience.
1257	\value ToggleCurrent A combination of Toggle and Current, provided for
1258	convenience.
1259	\value ClearAndSelect A combination of Clear and Select, provided for
1260	convenience.
1261	*/
1262
1263	namespace {
1264	namespace QtFunctionObjects {
1265	struct IsNotValid {
1266	typedef bool result_type;
1267	struct is_transparent : std::true_type {};
1268	template <typename T>
1269	constexpr bool operator()(T &t) const noexcept(noexcept(t.isValid()))
1270	{ return !t.isValid(); }
1271	template <typename T>
1272	constexpr bool operator()(T *t) const noexcept(noexcept(t->isValid()))
1273	{ return !t->isValid(); }
1274	};
1275	}
1276	} // unnamed namespace
1277
1278	/*!
1279	Selects the item \a selection using the specified \a command, and emits
1280	selectionChanged().
1281
1282	\sa QItemSelectionModel::SelectionFlag
1283	*/
1284	void QItemSelectionModel::select(const QItemSelection &selection, QItemSelectionModel::SelectionFlags command)
1285	{
1286	Q_D(QItemSelectionModel);
1287	if (!d->model.value()) {
1288	qWarning(msg: "QItemSelectionModel: Selecting when no model has been set will result in a no-op.");
1289	return;
1290	}
1291	if (command == NoUpdate)
1292	return;
1293
1294	// store old selection
1295	QItemSelection sel = selection;
1296	// If d->ranges is non-empty when the source model is reset the persistent indexes
1297	// it contains will be invalid. We can't clear them in a modelReset slot because that might already
1298	// be too late if another model observer is connected to the same modelReset slot and is invoked first
1299	// it might call select() on this selection model before any such QItemSelectionModelPrivate::modelReset() slot
1300	// is invoked, so it would not be cleared yet. We clear it invalid ranges in it here.
1301	d->ranges.removeIf(pred: QtFunctionObjects::IsNotValid());
1302
1303	QItemSelection old = d->ranges;
1304	old.merge(other: d->currentSelection, command: d->currentCommand);
1305
1306	// expand selection according to SelectionBehavior
1307	if (command & Rows || command & Columns)
1308	sel = d->expandSelection(selection: sel, command);
1309
1310	// clear ranges and currentSelection
1311	if (command & Clear) {
1312	d->ranges.clear();
1313	d->currentSelection.clear();
1314	}
1315
1316	// merge and clear currentSelection if Current was not set (ie. start new currentSelection)
1317	if (!(command & Current))
1318	d->finalize();
1319
1320	// update currentSelection
1321	if (command & Toggle || command & Select || command & Deselect) {
1322	d->currentCommand = command;
1323	d->currentSelection = sel;
1324	}
1325
1326	// generate new selection, compare with old and emit selectionChanged()
1327	QItemSelection newSelection = d->ranges;
1328	newSelection.merge(other: d->currentSelection, command: d->currentCommand);
1329	emitSelectionChanged(newSelection, oldSelection: old);
1330	}
1331
1332	/*!
1333	Clears the selection model. Emits selectionChanged() and currentChanged().
1334	*/
1335	void QItemSelectionModel::clear()
1336	{
1337	clearSelection();
1338	clearCurrentIndex();
1339	}
1340
1341	/*!
1342	Clears the current index. Emits currentChanged().
1343	*/
1344	void QItemSelectionModel::clearCurrentIndex()
1345	{
1346	Q_D(QItemSelectionModel);
1347	QModelIndex previous = d->currentIndex;
1348	d->currentIndex = QModelIndex();
1349	if (previous.isValid()) {
1350	emit currentChanged(current: d->currentIndex, previous);
1351	emit currentRowChanged(current: d->currentIndex, previous);
1352	emit currentColumnChanged(current: d->currentIndex, previous);
1353	}
1354	}
1355
1356	/*!
1357	Clears the selection model. Does not emit any signals.
1358	*/
1359	void QItemSelectionModel::reset()
1360	{
1361	const QSignalBlocker blocker(this);
1362	clear();
1363	}
1364
1365	/*!
1366	\since 4.2
1367	Clears the selection in the selection model. Emits selectionChanged().
1368	*/
1369	void QItemSelectionModel::clearSelection()
1370	{
1371	Q_D(QItemSelectionModel);
1372	if (d->ranges.size() == 0 && d->currentSelection.size() == 0)
1373	return;
1374
1375	select(selection: QItemSelection(), command: Clear);
1376	}
1377
1378
1379	/*!
1380	Sets the model item \a index to be the current item, and emits
1381	currentChanged(). The current item is used for keyboard navigation and
1382	focus indication; it is independent of any selected items, although a
1383	selected item can also be the current item.
1384
1385	Depending on the specified \a command, the \a index can also become part
1386	of the current selection.
1387	\sa select()
1388	*/
1389	void QItemSelectionModel::setCurrentIndex(const QModelIndex &index, QItemSelectionModel::SelectionFlags command)
1390	{
1391	Q_D(QItemSelectionModel);
1392	if (!d->model.value()) {
1393	qWarning(msg: "QItemSelectionModel: Setting the current index when no model has been set will result in a no-op.");
1394	return;
1395	}
1396	if (index == d->currentIndex) {
1397	if (command != NoUpdate)
1398	select(index, command); // select item
1399	return;
1400	}
1401	QPersistentModelIndex previous = d->currentIndex;
1402	d->currentIndex = index; // set current before emitting selection changed below
1403	if (command != NoUpdate)
1404	select(index: d->currentIndex, command); // select item
1405	emit currentChanged(current: d->currentIndex, previous);
1406	if (d->currentIndex.row() != previous.row() ||
1407	d->currentIndex.parent() != previous.parent())
1408	emit currentRowChanged(current: d->currentIndex, previous);
1409	if (d->currentIndex.column() != previous.column() ||
1410	d->currentIndex.parent() != previous.parent())
1411	emit currentColumnChanged(current: d->currentIndex, previous);
1412	}
1413
1414	/*!
1415	Returns the model item index for the current item, or an invalid index
1416	if there is no current item.
1417	*/
1418	QModelIndex QItemSelectionModel::currentIndex() const
1419	{
1420	return static_cast<QModelIndex>(d_func()->currentIndex);
1421	}
1422
1423	/*!
1424	Returns \c true if the given model item \a index is selected.
1425	*/
1426	bool QItemSelectionModel::isSelected(const QModelIndex &index) const
1427	{
1428	Q_D(const QItemSelectionModel);
1429	if (d->model != index.model() || !index.isValid())
1430	return false;
1431
1432	bool selected = false;
1433	// search model ranges
1434	QList<QItemSelectionRange>::const_iterator it = d->ranges.begin();
1435	for (; it != d->ranges.end(); ++it) {
1436	if ((*it).isValid() && (*it).contains(index)) {
1437	selected = true;
1438	break;
1439	}
1440	}
1441
1442	// check currentSelection
1443	if (d->currentSelection.size()) {
1444	if ((d->currentCommand & Deselect) && selected)
1445	selected = !d->currentSelection.contains(index);
1446	else if (d->currentCommand & Toggle)
1447	selected ^= d->currentSelection.contains(index);
1448	else if ((d->currentCommand & Select) && !selected)
1449	selected = d->currentSelection.contains(index);
1450	}
1451
1452	if (selected)
1453	return isSelectableAndEnabled(flags: d->model->flags(index));
1454
1455	return false;
1456	}
1457
1458	/*!
1459	Returns \c true if all items are selected in the \a row with the given
1460	\a parent.
1461
1462	Note that this function is usually faster than calling isSelected()
1463	on all items in the same row and that unselectable items are
1464	ignored.
1465
1466	\note Since Qt 5.15, the default argument for \a parent is an empty
1467	model index.
1468	*/
1469	bool QItemSelectionModel::isRowSelected(int row, const QModelIndex &parent) const
1470	{
1471	Q_D(const QItemSelectionModel);
1472	if (!d->model.value())
1473	return false;
1474	if (parent.isValid() && d->model != parent.model())
1475	return false;
1476
1477	// return false if row exist in currentSelection (Deselect)
1478	if (d->currentCommand & Deselect && d->currentSelection.size()) {
1479	for (int i=0; i<d->currentSelection.size(); ++i) {
1480	if (d->currentSelection.at(i).parent() == parent &&
1481	row >= d->currentSelection.at(i).top() &&
1482	row <= d->currentSelection.at(i).bottom())
1483	return false;
1484	}
1485	}
1486	// return false if ranges in both currentSelection and ranges
1487	// intersect and have the same row contained
1488	if (d->currentCommand & Toggle && d->currentSelection.size()) {
1489	for (int i=0; i<d->currentSelection.size(); ++i)
1490	if (d->currentSelection.at(i).top() <= row &&
1491	d->currentSelection.at(i).bottom() >= row)
1492	for (int j=0; j<d->ranges.size(); ++j)
1493	if (d->ranges.at(i: j).top() <= row && d->ranges.at(i: j).bottom() >= row
1494	&& d->currentSelection.at(i).intersected(other: d->ranges.at(i: j)).isValid())
1495	return false;
1496	}
1497
1498	auto isSelectable = [&](int row, int column) {
1499	return isSelectableAndEnabled(flags: d->model->index(row, column, parent).flags());
1500	};
1501
1502	const int colCount = d->model->columnCount(parent);
1503	int unselectable = 0;
1504	// add ranges and currentSelection and check through them all
1505	QList<QItemSelectionRange>::const_iterator it;
1506	QList<QItemSelectionRange> joined = d->ranges;
1507	if (d->currentSelection.size())
1508	joined += d->currentSelection;
1509	for (int column = 0; column < colCount; ++column) {
1510	if (!isSelectable(row, column)) {
1511	++unselectable;
1512	continue;
1513	}
1514
1515	for (it = joined.constBegin(); it != joined.constEnd(); ++it) {
1516	if ((*it).contains(row, column, parentIndex: parent)) {
1517	for (int i = column; i <= (*it).right(); ++i) {
1518	if (!isSelectable(row, i))
1519	++unselectable;
1520	}
1521
1522	column = qMax(a: column, b: (*it).right());
1523	break;
1524	}
1525	}
1526	if (it == joined.constEnd())
1527	return false;
1528	}
1529	return unselectable < colCount;
1530	}
1531
1532	/*!
1533	Returns \c true if all items are selected in the \a column with the given
1534	\a parent.
1535
1536	Note that this function is usually faster than calling isSelected()
1537	on all items in the same column and that unselectable items are
1538	ignored.
1539
1540	\note Since Qt 5.15, the default argument for \a parent is an empty
1541	model index.
1542	*/
1543	bool QItemSelectionModel::isColumnSelected(int column, const QModelIndex &parent) const
1544	{
1545	Q_D(const QItemSelectionModel);
1546	if (!d->model.value())
1547	return false;
1548	if (parent.isValid() && d->model != parent.model())
1549	return false;
1550
1551	// return false if column exist in currentSelection (Deselect)
1552	if (d->currentCommand & Deselect && d->currentSelection.size()) {
1553	for (int i = 0; i < d->currentSelection.size(); ++i) {
1554	if (d->currentSelection.at(i).parent() == parent &&
1555	column >= d->currentSelection.at(i).left() &&
1556	column <= d->currentSelection.at(i).right())
1557	return false;
1558	}
1559	}
1560	// return false if ranges in both currentSelection and the selection model
1561	// intersect and have the same column contained
1562	if (d->currentCommand & Toggle && d->currentSelection.size()) {
1563	for (int i = 0; i < d->currentSelection.size(); ++i) {
1564	if (d->currentSelection.at(i).left() <= column &&
1565	d->currentSelection.at(i).right() >= column) {
1566	for (int j = 0; j < d->ranges.size(); ++j) {
1567	if (d->ranges.at(i: j).left() <= column && d->ranges.at(i: j).right() >= column
1568	&& d->currentSelection.at(i).intersected(other: d->ranges.at(i: j)).isValid()) {
1569	return false;
1570	}
1571	}
1572	}
1573	}
1574	}
1575
1576	auto isSelectable = [&](int row, int column) {
1577	return isSelectableAndEnabled(flags: d->model->index(row, column, parent).flags());
1578	};
1579	const int rowCount = d->model->rowCount(parent);
1580	int unselectable = 0;
1581
1582	// add ranges and currentSelection and check through them all
1583	QList<QItemSelectionRange>::const_iterator it;
1584	QList<QItemSelectionRange> joined = d->ranges;
1585	if (d->currentSelection.size())
1586	joined += d->currentSelection;
1587	for (int row = 0; row < rowCount; ++row) {
1588	if (!isSelectable(row, column)) {
1589	++unselectable;
1590	continue;
1591	}
1592	for (it = joined.constBegin(); it != joined.constEnd(); ++it) {
1593	if ((*it).contains(row, column, parentIndex: parent)) {
1594	for (int i = row; i <= (*it).bottom(); ++i) {
1595	if (!isSelectable(i, column)) {
1596	++unselectable;
1597	}
1598	}
1599	row = qMax(a: row, b: (*it).bottom());
1600	break;
1601	}
1602	}
1603	if (it == joined.constEnd())
1604	return false;
1605	}
1606	return unselectable < rowCount;
1607	}
1608
1609	/*!
1610	Returns \c true if there are any items selected in the \a row with the given
1611	\a parent.
1612
1613	\note Since Qt 5.15, the default argument for \a parent is an empty
1614	model index.
1615	*/
1616	bool QItemSelectionModel::rowIntersectsSelection(int row, const QModelIndex &parent) const
1617	{
1618	Q_D(const QItemSelectionModel);
1619	if (!d->model.value())
1620	return false;
1621	if (parent.isValid() && d->model != parent.model())
1622	return false;
1623
1624	QItemSelection sel = d->ranges;
1625	sel.merge(other: d->currentSelection, command: d->currentCommand);
1626	for (const QItemSelectionRange &range : std::as_const(t&: sel)) {
1627	if (range.parent() != parent)
1628	return false;
1629	int top = range.top();
1630	int bottom = range.bottom();
1631	int left = range.left();
1632	int right = range.right();
1633	if (top <= row && bottom >= row) {
1634	for (int j = left; j <= right; j++) {
1635	if (isSelectableAndEnabled(flags: d->model->index(row, column: j, parent).flags()))
1636	return true;
1637	}
1638	}
1639	}
1640
1641	return false;
1642	}
1643
1644	/*!
1645	Returns \c true if there are any items selected in the \a column with the given
1646	\a parent.
1647
1648	\note Since Qt 5.15, the default argument for \a parent is an empty
1649	model index.
1650	*/
1651	bool QItemSelectionModel::columnIntersectsSelection(int column, const QModelIndex &parent) const
1652	{
1653	Q_D(const QItemSelectionModel);
1654	if (!d->model.value())
1655	return false;
1656	if (parent.isValid() && d->model != parent.model())
1657	return false;
1658
1659	QItemSelection sel = d->ranges;
1660	sel.merge(other: d->currentSelection, command: d->currentCommand);
1661	for (const QItemSelectionRange &range : std::as_const(t&: sel)) {
1662	if (range.parent() != parent)
1663	return false;
1664	int top = range.top();
1665	int bottom = range.bottom();
1666	int left = range.left();
1667	int right = range.right();
1668	if (left <= column && right >= column) {
1669	for (int j = top; j <= bottom; j++) {
1670	if (isSelectableAndEnabled(flags: d->model->index(row: j, column, parent).flags()))
1671	return true;
1672	}
1673	}
1674	}
1675
1676	return false;
1677	}
1678
1679	/*!
1680	\internal
1681
1682	Check whether the selection is empty.
1683	In contrast to selection.isEmpty(), this takes into account
1684	whether items are enabled and whether they are selectable.
1685	*/
1686	static bool selectionIsEmpty(const QItemSelection &selection)
1687	{
1688	return std::all_of(first: selection.begin(), last: selection.end(),
1689	pred: [](const QItemSelectionRange &r) { return r.isEmpty(); });
1690	}
1691
1692	/*!
1693	\since 4.2
1694
1695	Returns \c true if the selection model contains any selected item,
1696	otherwise returns \c false.
1697	*/
1698	bool QItemSelectionModel::hasSelection() const
1699	{
1700	Q_D(const QItemSelectionModel);
1701
1702	// QTreeModel unfortunately sorts itself lazily.
1703	// When it sorts itself, it emits are layoutChanged signal.
1704	// This layoutChanged signal invalidates d->ranges here.
1705	// So QTreeModel must not sort itself while we are iterating over
1706	// d->ranges here. It sorts itself in executePendingOperations,
1707	// thus preventing the sort to happen inside of selectionIsEmpty below.
1708	// Sad story, read more in QTBUG-94546
1709	const QAbstractItemModel *model = QItemSelectionModel::model();
1710	if (model != nullptr) {
1711	auto model_p = static_cast<const QAbstractItemModelPrivate *>(QObjectPrivate::get(o: model));
1712	model_p->executePendingOperations();
1713	}
1714
1715	if (d->currentCommand & (Toggle | Deselect)) {
1716	QItemSelection sel = d->ranges;
1717	sel.merge(other: d->currentSelection, command: d->currentCommand);
1718	return !selectionIsEmpty(selection: sel);
1719	} else {
1720	return !(selectionIsEmpty(selection: d->ranges) && selectionIsEmpty(selection: d->currentSelection));
1721	}
1722	}
1723
1724	/*!
1725	Returns a list of all selected model item indexes. The list contains no
1726	duplicates, and is not sorted.
1727	*/
1728	QModelIndexList QItemSelectionModel::selectedIndexes() const
1729	{
1730	Q_D(const QItemSelectionModel);
1731	QItemSelection selected = d->ranges;
1732	selected.merge(other: d->currentSelection, command: d->currentCommand);
1733	return selected.indexes();
1734	}
1735
1736	struct RowOrColumnDefinition {
1737	QModelIndex parent;
1738	int rowOrColumn;
1739
1740	friend bool operator==(const RowOrColumnDefinition &lhs, const RowOrColumnDefinition &rhs) noexcept
1741	{ return lhs.parent == rhs.parent && lhs.rowOrColumn == rhs.rowOrColumn; }
1742	friend bool operator!=(const RowOrColumnDefinition &lhs, const RowOrColumnDefinition &rhs) noexcept
1743	{ return !operator==(lhs, rhs); }
1744	};
1745	size_t qHash(const RowOrColumnDefinition &key, size_t seed = 0) noexcept
1746	{
1747	QtPrivate::QHashCombine hash;
1748	seed = hash(seed, key.parent);
1749	seed = hash(seed, key.rowOrColumn);
1750	return seed;
1751	}
1752
1753	QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH_BY_CREF(RowOrColumnDefinition)
1754
1755	/*!
1756	\since 4.2
1757	Returns the indexes in the given \a column for the rows where all columns are selected.
1758
1759	\sa selectedIndexes(), selectedColumns()
1760	*/
1761
1762	QModelIndexList QItemSelectionModel::selectedRows(int column) const
1763	{
1764	QModelIndexList indexes;
1765
1766	QDuplicateTracker<RowOrColumnDefinition> rowsSeen;
1767
1768	const QItemSelection ranges = selection();
1769	for (int i = 0; i < ranges.size(); ++i) {
1770	const QItemSelectionRange &range = ranges.at(i);
1771	QModelIndex parent = range.parent();
1772	for (int row = range.top(); row <= range.bottom(); row++) {
1773	if (!rowsSeen.hasSeen(s: {.parent: parent, .rowOrColumn: row})) {
1774	if (isRowSelected(row, parent)) {
1775	indexes.append(t: model()->index(row, column, parent));
1776	}
1777	}
1778	}
1779	}
1780
1781	return indexes;
1782	}
1783
1784	/*!
1785	\since 4.2
1786	Returns the indexes in the given \a row for columns where all rows are selected.
1787
1788	\sa selectedIndexes(), selectedRows()
1789	*/
1790
1791	QModelIndexList QItemSelectionModel::selectedColumns(int row) const
1792	{
1793	QModelIndexList indexes;
1794
1795	QDuplicateTracker<RowOrColumnDefinition> columnsSeen;
1796
1797	const QItemSelection ranges = selection();
1798	for (int i = 0; i < ranges.size(); ++i) {
1799	const QItemSelectionRange &range = ranges.at(i);
1800	QModelIndex parent = range.parent();
1801	for (int column = range.left(); column <= range.right(); column++) {
1802	if (!columnsSeen.hasSeen(s: {.parent: parent, .rowOrColumn: column})) {
1803	if (isColumnSelected(column, parent)) {
1804	indexes.append(t: model()->index(row, column, parent));
1805	}
1806	}
1807	}
1808	}
1809
1810	return indexes;
1811	}
1812
1813	/*!
1814	Returns the selection ranges stored in the selection model.
1815	*/
1816	const QItemSelection QItemSelectionModel::selection() const
1817	{
1818	Q_D(const QItemSelectionModel);
1819	QItemSelection selected = d->ranges;
1820	selected.merge(other: d->currentSelection, command: d->currentCommand);
1821	// make sure we have no invalid ranges
1822	// ### should probably be handled more generic somewhere else
1823	selected.removeIf(pred: QtFunctionObjects::IsNotValid());
1824	return selected;
1825	}
1826
1827	/*!
1828	\since 5.5
1829
1830	\property QItemSelectionModel::hasSelection
1831	\internal
1832	*/
1833	/*!
1834	\since 5.5
1835
1836	\property QItemSelectionModel::currentIndex
1837	\internal
1838	*/
1839	/*!
1840	\since 5.5
1841
1842	\property QItemSelectionModel::selectedIndexes
1843	*/
1844
1845	/*!
1846	\since 5.5
1847
1848	\property QItemSelectionModel::selection
1849	\internal
1850	*/
1851	/*!
1852	\since 5.5
1853
1854	\property QItemSelectionModel::model
1855	\internal
1856	*/
1857	/*!
1858	\since 5.5
1859
1860	Returns the item model operated on by the selection model.
1861	*/
1862	QAbstractItemModel *QItemSelectionModel::model()
1863	{
1864	return d_func()->model.value();
1865	}
1866
1867	/*!
1868	Returns the item model operated on by the selection model.
1869	*/
1870	const QAbstractItemModel *QItemSelectionModel::model() const
1871	{
1872	return d_func()->model.value();
1873	}
1874
1875	QBindable<QAbstractItemModel *> QItemSelectionModel::bindableModel()
1876	{
1877	return &d_func()->model;
1878	}
1879
1880	/*!
1881	\since 5.5
1882
1883	Sets the model to \a model. The modelChanged() signal will be emitted.
1884
1885	\sa model(), modelChanged()
1886	*/
1887	void QItemSelectionModel::setModel(QAbstractItemModel *model)
1888	{
1889	Q_D(QItemSelectionModel);
1890	d->model.removeBindingUnlessInWrapper();
1891	if (d->model.valueBypassingBindings() == model)
1892	return;
1893	d->initModel(m: model);
1894	d->model.notify();
1895	}
1896
1897	/*!
1898	Compares the two selections \a newSelection and \a oldSelection
1899	and emits selectionChanged() with the deselected and selected items.
1900	*/
1901	void QItemSelectionModel::emitSelectionChanged(const QItemSelection &newSelection,
1902	const QItemSelection &oldSelection)
1903	{
1904	// if both selections are empty or equal we return
1905	if ((oldSelection.isEmpty() && newSelection.isEmpty()) ||
1906	oldSelection == newSelection)
1907	return;
1908
1909	// if either selection is empty we do not need to compare
1910	if (oldSelection.isEmpty() || newSelection.isEmpty()) {
1911	emit selectionChanged(selected: newSelection, deselected: oldSelection);
1912	return;
1913	}
1914
1915	QItemSelection deselected = oldSelection;
1916	QItemSelection selected = newSelection;
1917
1918	// remove equal ranges
1919	bool advance;
1920	for (int o = 0; o < deselected.size(); ++o) {
1921	advance = true;
1922	for (int s = 0; s < selected.size() && o < deselected.size();) {
1923	if (deselected.at(i: o) == selected.at(i: s)) {
1924	deselected.removeAt(i: o);
1925	selected.removeAt(i: s);
1926	advance = false;
1927	} else {
1928	++s;
1929	}
1930	}
1931	if (advance)
1932	++o;
1933	}
1934
1935	// find intersections
1936	QItemSelection intersections;
1937	for (int o = 0; o < deselected.size(); ++o) {
1938	for (int s = 0; s < selected.size(); ++s) {
1939	if (deselected.at(i: o).intersects(other: selected.at(i: s)))
1940	intersections.append(t: deselected.at(i: o).intersected(other: selected.at(i: s)));
1941	}
1942	}
1943
1944	// compare remaining ranges with intersections and split them to find deselected and selected
1945	for (int i = 0; i < intersections.size(); ++i) {
1946	// split deselected
1947	for (int o = 0; o < deselected.size();) {
1948	if (deselected.at(i: o).intersects(other: intersections.at(i))) {
1949	QItemSelection::split(range: deselected.at(i: o), other: intersections.at(i), result: &deselected);
1950	deselected.removeAt(i: o);
1951	} else {
1952	++o;
1953	}
1954	}
1955	// split selected
1956	for (int s = 0; s < selected.size();) {
1957	if (selected.at(i: s).intersects(other: intersections.at(i))) {
1958	QItemSelection::split(range: selected.at(i: s), other: intersections.at(i), result: &selected);
1959	selected.removeAt(i: s);
1960	} else {
1961	++s;
1962	}
1963	}
1964	}
1965
1966	if (!selected.isEmpty() || !deselected.isEmpty())
1967	emit selectionChanged(selected, deselected);
1968	}
1969
1970	#ifndef QT_NO_DEBUG_STREAM
1971	QDebug operator<<(QDebug dbg, const QItemSelectionRange &range)
1972	{
1973	QDebugStateSaver saver(dbg);
1974	dbg.nospace() << "QItemSelectionRange(" << range.topLeft()
1975	<< ',' << range.bottomRight() << ')';
1976	return dbg;
1977	}
1978	#endif
1979
1980	QT_END_NAMESPACE
1981
1982	#include "moc_qitemselectionmodel.cpp"
1983