Don't call virtual methods after the source model is destroyed.
[qt:qt.git] / src / gui / itemviews / qsortfilterproxymodel.cpp
1 /****************************************************************************
2 **
3 ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/legal
5 **
6 ** This file is part of the QtGui module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and Digia.  For licensing terms and
14 ** conditions see http://qt.digia.com/licensing.  For further information
15 ** use the contact form at http://qt.digia.com/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 2.1 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL included in the
21 ** packaging of this file.  Please review the following information to
22 ** ensure the GNU Lesser General Public License version 2.1 requirements
23 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 **
25 ** In addition, as a special exception, Digia gives you certain additional
26 ** rights.  These rights are described in the Digia Qt LGPL Exception
27 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 **
29 ** GNU General Public License Usage
30 ** Alternatively, this file may be used under the terms of the GNU
31 ** General Public License version 3.0 as published by the Free Software
32 ** Foundation and appearing in the file LICENSE.GPL included in the
33 ** packaging of this file.  Please review the following information to
34 ** ensure the GNU General Public License version 3.0 requirements will be
35 ** met: http://www.gnu.org/copyleft/gpl.html.
36 **
37 **
38 ** $QT_END_LICENSE$
39 **
40 ****************************************************************************/
41
42 #include "qsortfilterproxymodel.h"
43
44 #ifndef QT_NO_SORTFILTERPROXYMODEL
45
46 #include "qitemselectionmodel.h"
47 #include <qsize.h>
48 #include <qdebug.h>
49 #include <qdatetime.h>
50 #include <qpair.h>
51 #include <qstringlist.h>
52 #include <private/qabstractitemmodel_p.h>
53 #include <private/qabstractproxymodel_p.h>
54
55 QT_BEGIN_NAMESPACE
56
57 typedef QList<QPair<QModelIndex, QPersistentModelIndex> > QModelIndexPairList;
58
59 static inline QSet<int> qVectorToSet(const QVector<int> &vector)
60 {
61     QSet<int> set;
62     set.reserve(vector.size());
63     for(int i=0; i < vector.size(); ++i)
64         set << vector.at(i);
65     return set;
66 }
67
68 class QSortFilterProxyModelLessThan
69 {
70 public:
71     inline QSortFilterProxyModelLessThan(int column, const QModelIndex &parent,
72                                        const QAbstractItemModel *source,
73                                        const QSortFilterProxyModel *proxy)
74         : sort_column(column), source_parent(parent), source_model(source), proxy_model(proxy) {}
75
76     inline bool operator()(int r1, int r2) const
77     {
78         QModelIndex i1 = source_model->index(r1, sort_column, source_parent);
79         QModelIndex i2 = source_model->index(r2, sort_column, source_parent);
80         return proxy_model->lessThan(i1, i2);
81     }
82
83 private:
84     int sort_column;
85     QModelIndex source_parent;
86     const QAbstractItemModel *source_model;
87     const QSortFilterProxyModel *proxy_model;
88 };
89
90 class QSortFilterProxyModelGreaterThan
91 {
92 public:
93     inline QSortFilterProxyModelGreaterThan(int column, const QModelIndex &parent,
94                                           const QAbstractItemModel *source,
95                                           const QSortFilterProxyModel *proxy)
96         : sort_column(column), source_parent(parent),
97           source_model(source), proxy_model(proxy) {}
98
99     inline bool operator()(int r1, int r2) const
100     {
101         QModelIndex i1 = source_model->index(r1, sort_column, source_parent);
102         QModelIndex i2 = source_model->index(r2, sort_column, source_parent);
103         return proxy_model->lessThan(i2, i1);
104     }
105
106 private:
107     int sort_column;
108     QModelIndex source_parent;
109     const QAbstractItemModel *source_model;
110     const QSortFilterProxyModel *proxy_model;
111 };
112
113
114 //this struct is used to store what are the rows that are removed
115 //between a call to rowsAboutToBeRemoved and rowsRemoved
116 //it avoids readding rows to the mapping that are currently being removed
117 struct QRowsRemoval
118 {
119     QRowsRemoval(const QModelIndex &parent_source, int start, int end) : parent_source(parent_source), start(start), end(end)
120     {
121     }
122
123     QRowsRemoval() : start(-1), end(-1)
124     {
125     }
126
127     bool contains(QModelIndex parent, int row)
128     {
129         do {
130             if (parent == parent_source)
131                 return row >= start && row <= end;
132             row = parent.row();
133             parent = parent.parent();
134         } while (row >= 0);
135         return false;
136     }
137 private:
138     QModelIndex parent_source;
139     int start;
140     int end;
141 };
142
143 class QSortFilterProxyModelPrivate : public QAbstractProxyModelPrivate
144 {
145     Q_DECLARE_PUBLIC(QSortFilterProxyModel)
146
147 public:
148     struct Mapping {
149         QVector<int> source_rows;
150         QVector<int> source_columns;
151         QVector<int> proxy_rows;
152         QVector<int> proxy_columns;
153         QVector<QModelIndex> mapped_children;
154         QHash<QModelIndex, Mapping *>::const_iterator map_iter;
155     };
156
157     mutable QHash<QModelIndex, Mapping*> source_index_mapping;
158
159     int source_sort_column;
160     int proxy_sort_column;
161     Qt::SortOrder sort_order;
162     Qt::CaseSensitivity sort_casesensitivity;
163     int sort_role;
164     bool sort_localeaware;
165
166     int filter_column;
167     QRegExp filter_regexp;
168     int filter_role;
169
170     bool dynamic_sortfilter;
171     QRowsRemoval itemsBeingRemoved;
172
173     QModelIndexPairList saved_persistent_indexes;
174
175     QHash<QModelIndex, Mapping *>::const_iterator create_mapping(
176         const QModelIndex &source_parent) const;
177     QModelIndex proxy_to_source(const QModelIndex &proxyIndex) const;
178     QModelIndex source_to_proxy(const QModelIndex &sourceIndex) const;
179     bool can_create_mapping(const QModelIndex &source_parent) const;
180
181     void remove_from_mapping(const QModelIndex &source_parent);
182
183     inline QHash<QModelIndex, Mapping *>::const_iterator index_to_iterator(
184         const QModelIndex &proxy_index) const
185     {
186         Q_ASSERT(proxy_index.isValid());
187         Q_ASSERT(proxy_index.model() == q_func());
188         const void *p = proxy_index.internalPointer();
189         Q_ASSERT(p);
190         QHash<QModelIndex, Mapping *>::const_iterator it =
191             static_cast<const Mapping*>(p)->map_iter;
192         Q_ASSERT(it != source_index_mapping.constEnd());
193         Q_ASSERT(it.value());
194         return it;
195     }
196
197     inline QModelIndex create_index(int row, int column,
198                                     QHash<QModelIndex, Mapping*>::const_iterator it) const
199     {
200         return q_func()->createIndex(row, column, *it);
201     }
202
203     void _q_sourceDataChanged(const QModelIndex &source_top_left,
204                            const QModelIndex &source_bottom_right);
205     void _q_sourceHeaderDataChanged(Qt::Orientation orientation, int start, int end);
206
207     void _q_sourceAboutToBeReset();
208     void _q_sourceReset();
209
210     void _q_sourceLayoutAboutToBeChanged();
211     void _q_sourceLayoutChanged();
212
213     void _q_sourceRowsAboutToBeInserted(const QModelIndex &source_parent,
214                                         int start, int end);
215     void _q_sourceRowsInserted(const QModelIndex &source_parent,
216                                int start, int end);
217     void _q_sourceRowsAboutToBeRemoved(const QModelIndex &source_parent,
218                                        int start, int end);
219     void _q_sourceRowsRemoved(const QModelIndex &source_parent,
220                               int start, int end);
221     void _q_sourceColumnsAboutToBeInserted(const QModelIndex &source_parent,
222                                            int start, int end);
223     void _q_sourceColumnsInserted(const QModelIndex &source_parent,
224                                   int start, int end);
225     void _q_sourceColumnsAboutToBeRemoved(const QModelIndex &source_parent,
226                                           int start, int end);
227     void _q_sourceColumnsRemoved(const QModelIndex &source_parent,
228                                  int start, int end);
229
230     void _q_clearMapping();
231
232     void sort();
233     bool update_source_sort_column();
234     void sort_source_rows(QVector<int> &source_rows,
235                           const QModelIndex &source_parent) const;
236     QVector<QPair<int, QVector<int > > > proxy_intervals_for_source_items_to_add(
237         const QVector<int> &proxy_to_source, const QVector<int> &source_items,
238         const QModelIndex &source_parent, Qt::Orientation orient) const;
239     QVector<QPair<int, int > > proxy_intervals_for_source_items(
240         const QVector<int> &source_to_proxy, const QVector<int> &source_items) const;
241     void insert_source_items(
242         QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,
243         const QVector<int> &source_items, const QModelIndex &source_parent,
244         Qt::Orientation orient, bool emit_signal = true);
245     void remove_source_items(
246         QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,
247         const QVector<int> &source_items, const QModelIndex &source_parent,
248         Qt::Orientation orient, bool emit_signal = true);
249     void remove_proxy_interval(
250         QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,
251         int proxy_start, int proxy_end, const QModelIndex &proxy_parent,
252         Qt::Orientation orient, bool emit_signal = true);
253     void build_source_to_proxy_mapping(
254         const QVector<int> &proxy_to_source, QVector<int> &source_to_proxy) const;
255     void source_items_inserted(const QModelIndex &source_parent,
256                                int start, int end, Qt::Orientation orient);
257     void source_items_about_to_be_removed(const QModelIndex &source_parent,
258                                           int start, int end, Qt::Orientation orient);
259     void source_items_removed(const QModelIndex &source_parent,
260                               int start, int end, Qt::Orientation orient);
261     void proxy_item_range(
262         const QVector<int> &source_to_proxy, const QVector<int> &source_items,
263         int &proxy_low, int &proxy_high) const;
264
265     QModelIndexPairList store_persistent_indexes();
266     void update_persistent_indexes(const QModelIndexPairList &source_indexes);
267
268     void filter_changed(const QModelIndex &source_parent = QModelIndex());
269     QSet<int> handle_filter_changed(
270         QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,
271         const QModelIndex &source_parent, Qt::Orientation orient);
272
273     void updateChildrenMapping(const QModelIndex &source_parent, Mapping *parent_mapping,
274                                Qt::Orientation orient, int start, int end, int delta_item_count, bool remove);
275
276     virtual void _q_sourceModelDestroyed();
277 };
278
279 typedef QHash<QModelIndex, QSortFilterProxyModelPrivate::Mapping *> IndexMap;
280
281 void QSortFilterProxyModelPrivate::_q_sourceModelDestroyed()
282 {
283     QAbstractProxyModelPrivate::_q_sourceModelDestroyed();
284     qDeleteAll(source_index_mapping);
285     source_index_mapping.clear();
286 }
287
288 void QSortFilterProxyModelPrivate::remove_from_mapping(const QModelIndex &source_parent)
289 {
290     if (Mapping *m = source_index_mapping.take(source_parent)) {
291         for (int i = 0; i < m->mapped_children.size(); ++i)
292             remove_from_mapping(m->mapped_children.at(i));
293         delete m;
294     }
295 }
296
297 void QSortFilterProxyModelPrivate::_q_clearMapping()
298 {
299     // store the persistent indexes
300     QModelIndexPairList source_indexes = store_persistent_indexes();
301
302     qDeleteAll(source_index_mapping);
303     source_index_mapping.clear();
304     if (dynamic_sortfilter && update_source_sort_column()) {
305         //update_source_sort_column might have created wrong mapping so we have to clear it again
306         qDeleteAll(source_index_mapping);
307         source_index_mapping.clear();
308     }
309
310     // update the persistent indexes
311     update_persistent_indexes(source_indexes);
312 }
313
314 IndexMap::const_iterator QSortFilterProxyModelPrivate::create_mapping(
315     const QModelIndex &source_parent) const
316 {
317     Q_Q(const QSortFilterProxyModel);
318
319     IndexMap::const_iterator it = source_index_mapping.constFind(source_parent);
320     if (it != source_index_mapping.constEnd()) // was mapped already
321         return it;
322
323     Mapping *m = new Mapping;
324
325     int source_rows = model->rowCount(source_parent);
326     m->source_rows.reserve(source_rows);
327     for (int i = 0; i < source_rows; ++i) {
328         if (q->filterAcceptsRow(i, source_parent))
329             m->source_rows.append(i);
330     }
331     int source_cols = model->columnCount(source_parent);
332     m->source_columns.reserve(source_cols);
333     for (int i = 0; i < source_cols; ++i) {
334         if (q->filterAcceptsColumn(i, source_parent))
335             m->source_columns.append(i);
336     }
337
338     sort_source_rows(m->source_rows, source_parent);
339     m->proxy_rows.resize(source_rows);
340     build_source_to_proxy_mapping(m->source_rows, m->proxy_rows);
341     m->proxy_columns.resize(source_cols);
342     build_source_to_proxy_mapping(m->source_columns, m->proxy_columns);
343
344     it = IndexMap::const_iterator(source_index_mapping.insert(source_parent, m));
345     m->map_iter = it;
346
347     if (source_parent.isValid()) {
348         QModelIndex source_grand_parent = source_parent.parent();
349         IndexMap::const_iterator it2 = create_mapping(source_grand_parent);
350         Q_ASSERT(it2 != source_index_mapping.constEnd());
351         it2.value()->mapped_children.append(source_parent);
352     }
353
354     Q_ASSERT(it != source_index_mapping.constEnd());
355     Q_ASSERT(it.value());
356
357     return it;
358 }
359
360 QModelIndex QSortFilterProxyModelPrivate::proxy_to_source(const QModelIndex &proxy_index) const
361 {
362     if (!proxy_index.isValid())
363         return QModelIndex(); // for now; we may want to be able to set a root index later
364     if (proxy_index.model() != q_func()) {
365         qWarning() << "QSortFilterProxyModel: index from wrong model passed to mapToSource";
366         Q_ASSERT(!"QSortFilterProxyModel: index from wrong model passed to mapToSource");
367         return QModelIndex();
368     }
369     IndexMap::const_iterator it = index_to_iterator(proxy_index);
370     Mapping *m = it.value();
371     if ((proxy_index.row() >= m->source_rows.size()) || (proxy_index.column() >= m->source_columns.size()))
372         return QModelIndex();
373     int source_row = m->source_rows.at(proxy_index.row());
374     int source_col = m->source_columns.at(proxy_index.column());
375     return model->index(source_row, source_col, it.key());
376 }
377
378 QModelIndex QSortFilterProxyModelPrivate::source_to_proxy(const QModelIndex &source_index) const
379 {
380     if (!source_index.isValid())
381         return QModelIndex(); // for now; we may want to be able to set a root index later
382     if (source_index.model() != model) {
383         qWarning() << "QSortFilterProxyModel: index from wrong model passed to mapFromSource";
384         Q_ASSERT(!"QSortFilterProxyModel: index from wrong model passed to mapFromSource");
385         return QModelIndex();
386     }
387     QModelIndex source_parent = source_index.parent();
388     IndexMap::const_iterator it = create_mapping(source_parent);
389     Mapping *m = it.value();
390     if ((source_index.row() >= m->proxy_rows.size()) || (source_index.column() >= m->proxy_columns.size()))
391         return QModelIndex();
392     int proxy_row = m->proxy_rows.at(source_index.row());
393     int proxy_column = m->proxy_columns.at(source_index.column());
394     if (proxy_row == -1 || proxy_column == -1)
395         return QModelIndex();
396     return create_index(proxy_row, proxy_column, it);
397 }
398
399 bool QSortFilterProxyModelPrivate::can_create_mapping(const QModelIndex &source_parent) const
400 {
401     if (source_parent.isValid()) {
402         QModelIndex source_grand_parent = source_parent.parent();
403         IndexMap::const_iterator it = source_index_mapping.constFind(source_grand_parent);
404         if (it == source_index_mapping.constEnd()) {
405             // Don't care, since we don't have mapping for the grand parent
406             return false;
407         }
408         Mapping *gm = it.value();
409         if (gm->proxy_rows.at(source_parent.row()) == -1 ||
410             gm->proxy_columns.at(source_parent.column()) == -1) {
411             // Don't care, since parent is filtered
412             return false;
413         }
414     }
415     return true;
416 }
417
418 /*!
419   \internal
420
421   Sorts the existing mappings.
422 */
423 void QSortFilterProxyModelPrivate::sort()
424 {
425     Q_Q(QSortFilterProxyModel);
426     emit q->layoutAboutToBeChanged();
427     QModelIndexPairList source_indexes = store_persistent_indexes();
428     IndexMap::const_iterator it = source_index_mapping.constBegin();
429     for (; it != source_index_mapping.constEnd(); ++it) {
430         QModelIndex source_parent = it.key();
431         Mapping *m = it.value();
432         sort_source_rows(m->source_rows, source_parent);
433         build_source_to_proxy_mapping(m->source_rows, m->proxy_rows);
434     }
435     update_persistent_indexes(source_indexes);
436     emit q->layoutChanged();
437 }
438
439 /*!
440   \internal
441
442     update the source_sort_column according to the proxy_sort_column
443     return true if the column was changed
444 */
445 bool QSortFilterProxyModelPrivate::update_source_sort_column()
446 {
447     Q_Q(QSortFilterProxyModel);
448     QModelIndex proxy_index = q->index(0, proxy_sort_column, QModelIndex());
449     int old_source_sort_colum = source_sort_column;
450     source_sort_column = q->mapToSource(proxy_index).column();
451     return old_source_sort_colum != source_sort_column;
452 }
453
454
455 /*!
456   \internal
457
458   Sorts the given \a source_rows according to current sort column and order.
459 */
460 void QSortFilterProxyModelPrivate::sort_source_rows(
461     QVector<int> &source_rows, const QModelIndex &source_parent) const
462 {
463     Q_Q(const QSortFilterProxyModel);
464     if (source_sort_column >= 0) {
465         if (sort_order == Qt::AscendingOrder) {
466             QSortFilterProxyModelLessThan lt(source_sort_column, source_parent, model, q);
467             qStableSort(source_rows.begin(), source_rows.end(), lt);
468         } else {
469             QSortFilterProxyModelGreaterThan gt(source_sort_column, source_parent, model, q);
470             qStableSort(source_rows.begin(), source_rows.end(), gt);
471         }
472     } else { // restore the source model order
473         qStableSort(source_rows.begin(), source_rows.end());
474     }
475 }
476
477 /*!
478   \internal
479
480   Given source-to-proxy mapping \a source_to_proxy and the set of
481   source items \a source_items (which are part of that mapping),
482   determines the corresponding proxy item intervals that should
483   be removed from the proxy model.
484
485   The result is a vector of pairs, where each pair represents a
486   (start, end) tuple, sorted in ascending order.
487 */
488 QVector<QPair<int, int > > QSortFilterProxyModelPrivate::proxy_intervals_for_source_items(
489     const QVector<int> &source_to_proxy, const QVector<int> &source_items) const
490 {
491     QVector<QPair<int, int> > proxy_intervals;
492     if (source_items.isEmpty())
493         return proxy_intervals;
494
495     int source_items_index = 0;
496     while (source_items_index < source_items.size()) {
497         int first_proxy_item = source_to_proxy.at(source_items.at(source_items_index));
498         Q_ASSERT(first_proxy_item != -1);
499         int last_proxy_item = first_proxy_item;
500         ++source_items_index;
501         // Find end of interval
502         while ((source_items_index < source_items.size())
503                && (source_to_proxy.at(source_items.at(source_items_index)) == last_proxy_item + 1)) {
504             ++last_proxy_item;
505             ++source_items_index;
506         }
507         // Add interval to result
508         proxy_intervals.append(QPair<int, int>(first_proxy_item, last_proxy_item));
509     }
510     qStableSort(proxy_intervals.begin(), proxy_intervals.end());
511     return proxy_intervals;
512 }
513
514 /*!
515   \internal
516
517   Given source-to-proxy mapping \a src_to_proxy and proxy-to-source mapping
518   \a proxy_to_source, removes \a source_items from this proxy model.
519   The corresponding proxy items are removed in intervals, so that the proper
520   rows/columnsRemoved(start, end) signals will be generated.
521 */
522 void QSortFilterProxyModelPrivate::remove_source_items(
523     QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,
524     const QVector<int> &source_items, const QModelIndex &source_parent,
525     Qt::Orientation orient, bool emit_signal)
526 {
527     Q_Q(QSortFilterProxyModel);
528     QModelIndex proxy_parent = q->mapFromSource(source_parent);
529     if (!proxy_parent.isValid() && source_parent.isValid())
530         return; // nothing to do (already removed)
531
532     QVector<QPair<int, int> > proxy_intervals;
533     proxy_intervals = proxy_intervals_for_source_items(source_to_proxy, source_items);
534
535     for (int i = proxy_intervals.size()-1; i >= 0; --i) {
536         QPair<int, int> interval = proxy_intervals.at(i);
537         int proxy_start = interval.first;
538         int proxy_end = interval.second;
539         remove_proxy_interval(source_to_proxy, proxy_to_source, proxy_start, proxy_end,
540                               proxy_parent, orient, emit_signal);
541     }
542 }
543
544 /*!
545   \internal
546
547   Given source-to-proxy mapping \a source_to_proxy and proxy-to-source mapping
548   \a proxy_to_source, removes items from \a proxy_start to \a proxy_end
549   (inclusive) from this proxy model.
550 */
551 void QSortFilterProxyModelPrivate::remove_proxy_interval(
552     QVector<int> &source_to_proxy, QVector<int> &proxy_to_source, int proxy_start, int proxy_end,
553     const QModelIndex &proxy_parent, Qt::Orientation orient, bool emit_signal)
554 {
555     Q_Q(QSortFilterProxyModel);
556     if (emit_signal) {
557         if (orient == Qt::Vertical)
558             q->beginRemoveRows(proxy_parent, proxy_start, proxy_end);
559         else
560             q->beginRemoveColumns(proxy_parent, proxy_start, proxy_end);
561     }
562
563     // Remove items from proxy-to-source mapping
564     proxy_to_source.remove(proxy_start, proxy_end - proxy_start + 1);
565
566     build_source_to_proxy_mapping(proxy_to_source, source_to_proxy);
567
568     if (emit_signal) {
569         if (orient == Qt::Vertical)
570             q->endRemoveRows();
571         else
572             q->endRemoveColumns();
573     }
574 }
575
576 /*!
577   \internal
578
579   Given proxy-to-source mapping \a proxy_to_source and a set of
580   unmapped source items \a source_items, determines the proxy item
581   intervals at which the subsets of source items should be inserted
582   (but does not actually add them to the mapping).
583
584   The result is a vector of pairs, each pair representing a tuple (start,
585   items), where items is a vector containing the (sorted) source items that
586   should be inserted at that proxy model location.
587 */
588 QVector<QPair<int, QVector<int > > > QSortFilterProxyModelPrivate::proxy_intervals_for_source_items_to_add(
589     const QVector<int> &proxy_to_source, const QVector<int> &source_items,
590     const QModelIndex &source_parent, Qt::Orientation orient) const
591 {
592     Q_Q(const QSortFilterProxyModel);
593     QVector<QPair<int, QVector<int> > > proxy_intervals;
594     if (source_items.isEmpty())
595         return proxy_intervals;
596
597     int proxy_low = 0;
598     int proxy_item = 0;
599     int source_items_index = 0;
600     QVector<int> source_items_in_interval;
601     bool compare = (orient == Qt::Vertical && source_sort_column >= 0 && dynamic_sortfilter);
602     while (source_items_index < source_items.size()) {
603         source_items_in_interval.clear();
604         int first_new_source_item = source_items.at(source_items_index);
605         source_items_in_interval.append(first_new_source_item);
606         ++source_items_index;
607
608         // Find proxy item at which insertion should be started
609         int proxy_high = proxy_to_source.size() - 1;
610         QModelIndex i1 = compare ? model->index(first_new_source_item, source_sort_column, source_parent) : QModelIndex();
611         while (proxy_low <= proxy_high) {
612             proxy_item = (proxy_low + proxy_high) / 2;
613             if (compare) {
614                 QModelIndex i2 = model->index(proxy_to_source.at(proxy_item), source_sort_column, source_parent);
615                 if ((sort_order == Qt::AscendingOrder) ? q->lessThan(i1, i2) : q->lessThan(i2, i1))
616                     proxy_high = proxy_item - 1;
617                 else
618                     proxy_low = proxy_item + 1;
619             } else {
620                 if (first_new_source_item < proxy_to_source.at(proxy_item))
621                     proxy_high = proxy_item - 1;
622                 else
623                     proxy_low = proxy_item + 1;
624             }
625         }
626         proxy_item = proxy_low;
627
628         // Find the sequence of new source items that should be inserted here
629         if (proxy_item >= proxy_to_source.size()) {
630             for ( ; source_items_index < source_items.size(); ++source_items_index)
631                 source_items_in_interval.append(source_items.at(source_items_index));
632         } else {
633             i1 = compare ? model->index(proxy_to_source.at(proxy_item), source_sort_column, source_parent) : QModelIndex();
634             for ( ; source_items_index < source_items.size(); ++source_items_index) {
635                 int new_source_item = source_items.at(source_items_index);
636                 if (compare) {
637                     QModelIndex i2 = model->index(new_source_item, source_sort_column, source_parent);
638                     if ((sort_order == Qt::AscendingOrder) ? q->lessThan(i1, i2) : q->lessThan(i2, i1))
639                         break;
640                 } else {
641                     if (proxy_to_source.at(proxy_item) < new_source_item)
642                         break;
643                 }
644                 source_items_in_interval.append(new_source_item);
645             }
646         }
647
648         // Add interval to result
649         proxy_intervals.append(QPair<int, QVector<int> >(proxy_item, source_items_in_interval));
650     }
651     return proxy_intervals;
652 }
653
654 /*!
655   \internal
656
657   Given source-to-proxy mapping \a source_to_proxy and proxy-to-source mapping
658   \a proxy_to_source, inserts the given \a source_items into this proxy model.
659   The source items are inserted in intervals (based on some sorted order), so
660   that the proper rows/columnsInserted(start, end) signals will be generated.
661 */
662 void QSortFilterProxyModelPrivate::insert_source_items(
663     QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,
664     const QVector<int> &source_items, const QModelIndex &source_parent,
665     Qt::Orientation orient, bool emit_signal)
666 {
667     Q_Q(QSortFilterProxyModel);
668     QModelIndex proxy_parent = q->mapFromSource(source_parent);
669     if (!proxy_parent.isValid() && source_parent.isValid())
670         return; // nothing to do (source_parent is not mapped)
671
672     QVector<QPair<int, QVector<int> > > proxy_intervals;
673     proxy_intervals = proxy_intervals_for_source_items_to_add(
674         proxy_to_source, source_items, source_parent, orient);
675
676     for (int i = proxy_intervals.size()-1; i >= 0; --i) {
677         QPair<int, QVector<int> > interval = proxy_intervals.at(i);
678         int proxy_start = interval.first;
679         QVector<int> source_items = interval.second;
680         int proxy_end = proxy_start + source_items.size() - 1;
681
682         if (emit_signal) {
683             if (orient == Qt::Vertical)
684                 q->beginInsertRows(proxy_parent, proxy_start, proxy_end);
685             else
686                 q->beginInsertColumns(proxy_parent, proxy_start, proxy_end);
687         }
688
689         for (int i = 0; i < source_items.size(); ++i)
690             proxy_to_source.insert(proxy_start + i, source_items.at(i));
691
692         build_source_to_proxy_mapping(proxy_to_source, source_to_proxy);
693
694         if (emit_signal) {
695             if (orient == Qt::Vertical)
696                 q->endInsertRows();
697             else
698                 q->endInsertColumns();
699         }
700     }
701 }
702
703 /*!
704   \internal
705
706   Handles source model items insertion (columnsInserted(), rowsInserted()).
707   Determines
708   1) which of the inserted items to also insert into proxy model (filtering),
709   2) where to insert the items into the proxy model (sorting),
710   then inserts those items.
711   The items are inserted into the proxy model in intervals (based on
712   sorted order), so that the proper rows/columnsInserted(start, end)
713   signals will be generated.
714 */
715 void QSortFilterProxyModelPrivate::source_items_inserted(
716     const QModelIndex &source_parent, int start, int end, Qt::Orientation orient)
717 {
718     Q_Q(QSortFilterProxyModel);
719     if ((start < 0) || (end < 0))
720         return;
721     IndexMap::const_iterator it = source_index_mapping.constFind(source_parent);
722     if (it == source_index_mapping.constEnd()) {
723         if (!can_create_mapping(source_parent))
724             return;
725         it = create_mapping(source_parent);
726         Mapping *m = it.value();
727         QModelIndex proxy_parent = q->mapFromSource(source_parent);
728         if (m->source_rows.count() > 0) {
729             q->beginInsertRows(proxy_parent, 0, m->source_rows.count() - 1);
730             q->endInsertRows();
731         }
732         if (m->source_columns.count() > 0) {
733             q->beginInsertColumns(proxy_parent, 0, m->source_columns.count() - 1);
734             q->endInsertColumns();
735         }
736         return;
737     }
738
739     Mapping *m = it.value();
740     QVector<int> &source_to_proxy = (orient == Qt::Vertical) ? m->proxy_rows : m->proxy_columns;
741     QVector<int> &proxy_to_source = (orient == Qt::Vertical) ? m->source_rows : m->source_columns;
742
743     int delta_item_count = end - start + 1;
744     int old_item_count = source_to_proxy.size();
745
746     updateChildrenMapping(source_parent, m, orient, start, end, delta_item_count, false);
747
748     // Expand source-to-proxy mapping to account for new items
749     if (start < 0 || start > source_to_proxy.size()) {
750         qWarning("QSortFilterProxyModel: invalid inserted rows reported by source model");
751         remove_from_mapping(source_parent);
752         return;
753     }
754     source_to_proxy.insert(start, delta_item_count, -1);
755
756     if (start < old_item_count) {
757         // Adjust existing "stale" indexes in proxy-to-source mapping
758         int proxy_count = proxy_to_source.size();
759         for (int proxy_item = 0; proxy_item < proxy_count; ++proxy_item) {
760             int source_item = proxy_to_source.at(proxy_item);
761             if (source_item >= start)
762                 proxy_to_source.replace(proxy_item, source_item + delta_item_count);
763         }
764         build_source_to_proxy_mapping(proxy_to_source, source_to_proxy);
765     }
766
767     // Figure out which items to add to mapping based on filter
768     QVector<int> source_items;
769     for (int i = start; i <= end; ++i) {
770         if ((orient == Qt::Vertical)
771             ? q->filterAcceptsRow(i, source_parent)
772             : q->filterAcceptsColumn(i, source_parent)) {
773             source_items.append(i);
774         }
775     }
776
777     if (model->rowCount(source_parent) == delta_item_count) {
778         // Items were inserted where there were none before.
779         // If it was new rows make sure to create mappings for columns so that a
780         // valid mapping can be retrieved later and vice-versa.
781
782         QVector<int> &orthogonal_proxy_to_source = (orient == Qt::Horizontal) ? m->source_rows : m->source_columns;
783         QVector<int> &orthogonal_source_to_proxy = (orient == Qt::Horizontal) ? m->proxy_rows : m->proxy_columns;
784
785         if (orthogonal_source_to_proxy.isEmpty()) {
786             const int ortho_end = (orient == Qt::Horizontal) ? model->rowCount(source_parent) : model->columnCount(source_parent);
787
788             orthogonal_source_to_proxy.resize(ortho_end);
789
790             for (int ortho_item = 0; ortho_item < ortho_end; ++ortho_item) {
791                 if ((orient == Qt::Horizontal) ? q->filterAcceptsRow(ortho_item, source_parent)
792                         : q->filterAcceptsColumn(ortho_item, source_parent)) {
793                     orthogonal_proxy_to_source.append(ortho_item);
794                 }
795             }
796             if (orient == Qt::Horizontal) {
797                 // We're reacting to columnsInserted, but we've just inserted new rows. Sort them.
798                 sort_source_rows(orthogonal_proxy_to_source, source_parent);
799             }
800             build_source_to_proxy_mapping(orthogonal_proxy_to_source, orthogonal_source_to_proxy);
801         }
802     }
803
804     // Sort and insert the items
805     if (orient == Qt::Vertical) // Only sort rows
806         sort_source_rows(source_items, source_parent);
807     insert_source_items(source_to_proxy, proxy_to_source, source_items, source_parent, orient);
808 }
809
810 /*!
811   \internal
812
813   Handles source model items removal
814   (columnsAboutToBeRemoved(), rowsAboutToBeRemoved()).
815 */
816 void QSortFilterProxyModelPrivate::source_items_about_to_be_removed(
817     const QModelIndex &source_parent, int start, int end, Qt::Orientation orient)
818 {
819     if ((start < 0) || (end < 0))
820         return;
821     IndexMap::const_iterator it = source_index_mapping.constFind(source_parent);
822     if (it == source_index_mapping.constEnd()) {
823         // Don't care, since we don't have mapping for this index
824         return;
825     }
826
827     Mapping *m = it.value();
828     QVector<int> &source_to_proxy = (orient == Qt::Vertical) ? m->proxy_rows : m->proxy_columns;
829     QVector<int> &proxy_to_source = (orient == Qt::Vertical) ? m->source_rows : m->source_columns;
830
831     // figure out which items to remove
832     QVector<int> source_items_to_remove;
833     int proxy_count = proxy_to_source.size();
834     for (int proxy_item = 0; proxy_item < proxy_count; ++proxy_item) {
835         int source_item = proxy_to_source.at(proxy_item);
836         if ((source_item >= start) && (source_item <= end))
837             source_items_to_remove.append(source_item);
838     }
839
840     remove_source_items(source_to_proxy, proxy_to_source, source_items_to_remove,
841                         source_parent, orient);
842 }
843
844 /*!
845   \internal
846
847   Handles source model items removal (columnsRemoved(), rowsRemoved()).
848 */
849 void QSortFilterProxyModelPrivate::source_items_removed(
850     const QModelIndex &source_parent, int start, int end, Qt::Orientation orient)
851 {
852     if ((start < 0) || (end < 0))
853         return;
854     IndexMap::const_iterator it = source_index_mapping.constFind(source_parent);
855     if (it == source_index_mapping.constEnd()) {
856         // Don't care, since we don't have mapping for this index
857         return;
858     }
859
860     Mapping *m = it.value();
861     QVector<int> &source_to_proxy = (orient == Qt::Vertical) ? m->proxy_rows : m->proxy_columns;
862     QVector<int> &proxy_to_source = (orient == Qt::Vertical) ? m->source_rows : m->source_columns;
863
864     if (end >= source_to_proxy.size())
865         end = source_to_proxy.size() - 1;
866
867     // Shrink the source-to-proxy mapping to reflect the new item count
868     int delta_item_count = end - start + 1;
869     source_to_proxy.remove(start, delta_item_count);
870
871     int proxy_count = proxy_to_source.size();
872     if (proxy_count > source_to_proxy.size()) {
873         // mapping is in an inconsistent state -- redo the whole mapping
874         qWarning("QSortFilterProxyModel: inconsistent changes reported by source model");
875         remove_from_mapping(source_parent);
876         Q_Q(QSortFilterProxyModel);
877         q->reset();
878         return;
879     }
880
881     // Adjust "stale" indexes in proxy-to-source mapping
882     for (int proxy_item = 0; proxy_item < proxy_count; ++proxy_item) {
883         int source_item = proxy_to_source.at(proxy_item);
884         if (source_item >= start) {
885             Q_ASSERT(source_item - delta_item_count >= 0);
886             proxy_to_source.replace(proxy_item, source_item - delta_item_count);
887         }
888     }
889     build_source_to_proxy_mapping(proxy_to_source, source_to_proxy);
890
891     updateChildrenMapping(source_parent, m, orient, start, end, delta_item_count, true);
892
893 }
894
895
896 /*!
897   \internal
898   updates the mapping of the children when inserting or removing items
899 */
900 void QSortFilterProxyModelPrivate::updateChildrenMapping(const QModelIndex &source_parent, Mapping *parent_mapping,
901                                                          Qt::Orientation orient, int start, int end, int delta_item_count, bool remove)
902 {
903     // see if any mapped children should be (re)moved
904     QVector<QPair<QModelIndex, Mapping*> > moved_source_index_mappings;
905     QVector<QModelIndex>::iterator it2 = parent_mapping->mapped_children.begin();
906     for ( ; it2 != parent_mapping->mapped_children.end();) {
907         const QModelIndex source_child_index = *it2;
908         const int pos = (orient == Qt::Vertical)
909                         ? source_child_index.row()
910                         : source_child_index.column();
911         if (pos < start) {
912             // not affected
913             ++it2;
914         } else if (remove && pos <= end) {
915             // in the removed interval
916             it2 = parent_mapping->mapped_children.erase(it2);
917             remove_from_mapping(source_child_index);
918         } else {
919             // below the removed items -- recompute the index
920             QModelIndex new_index;
921             const int newpos = remove ? pos - delta_item_count : pos + delta_item_count;
922             if (orient == Qt::Vertical) {
923                 new_index = model->index(newpos,
924                                          source_child_index.column(),
925                                          source_parent);
926             } else {
927                 new_index = model->index(source_child_index.row(),
928                                          newpos,
929                                          source_parent);
930             }
931             *it2 = new_index;
932             ++it2;
933
934             // update mapping
935             Mapping *cm = source_index_mapping.take(source_child_index);
936             Q_ASSERT(cm);
937             // we do not reinsert right away, because the new index might be identical with another, old index
938             moved_source_index_mappings.append(QPair<QModelIndex, Mapping*>(new_index, cm));
939         }
940     }
941
942     // reinsert moved, mapped indexes
943     QVector<QPair<QModelIndex, Mapping*> >::iterator it = moved_source_index_mappings.begin();
944     for (; it != moved_source_index_mappings.end(); ++it) {
945 #ifdef QT_STRICT_ITERATORS
946         source_index_mapping.insert((*it).first, (*it).second);
947         (*it).second->map_iter = source_index_mapping.constFind((*it).first);
948 #else
949         (*it).second->map_iter = source_index_mapping.insert((*it).first, (*it).second);
950 #endif
951     }
952 }
953
954 /*!
955   \internal
956 */
957 void QSortFilterProxyModelPrivate::proxy_item_range(
958     const QVector<int> &source_to_proxy, const QVector<int> &source_items,
959     int &proxy_low, int &proxy_high) const
960 {
961     proxy_low = INT_MAX;
962     proxy_high = INT_MIN;
963     for (int i = 0; i < source_items.count(); ++i) {
964         int proxy_item = source_to_proxy.at(source_items.at(i));
965         Q_ASSERT(proxy_item != -1);
966         if (proxy_item < proxy_low)
967             proxy_low = proxy_item;
968         if (proxy_item > proxy_high)
969             proxy_high = proxy_item;
970     }
971 }
972
973 /*!
974   \internal
975 */
976 void QSortFilterProxyModelPrivate::build_source_to_proxy_mapping(
977     const QVector<int> &proxy_to_source, QVector<int> &source_to_proxy) const
978 {
979     source_to_proxy.fill(-1);
980     int proxy_count = proxy_to_source.size();
981     for (int i = 0; i < proxy_count; ++i)
982         source_to_proxy[proxy_to_source.at(i)] = i;
983 }
984
985 /*!
986   \internal
987
988   Maps the persistent proxy indexes to source indexes and
989   returns the list of source indexes.
990 */
991 QModelIndexPairList QSortFilterProxyModelPrivate::store_persistent_indexes()
992 {
993     Q_Q(QSortFilterProxyModel);
994     QModelIndexPairList source_indexes;
995     foreach (QPersistentModelIndexData *data, persistent.indexes) {
996         QModelIndex proxy_index = data->index;
997         QModelIndex source_index = q->mapToSource(proxy_index);
998         source_indexes.append(qMakePair(proxy_index, QPersistentModelIndex(source_index)));
999     }
1000     return source_indexes;
1001 }
1002
1003 /*!
1004   \internal
1005
1006   Maps \a source_indexes to proxy indexes and stores those
1007   as persistent indexes.
1008 */
1009 void QSortFilterProxyModelPrivate::update_persistent_indexes(
1010         const QModelIndexPairList &source_indexes)
1011 {
1012     Q_Q(QSortFilterProxyModel);
1013     QModelIndexList from, to;
1014     for (int i = 0; i < source_indexes.count(); ++i) {
1015         QModelIndex source_index = source_indexes.at(i).second;
1016         QModelIndex old_proxy_index = source_indexes.at(i).first;
1017         create_mapping(source_index.parent());
1018         QModelIndex proxy_index = q->mapFromSource(source_index);
1019         from << old_proxy_index;
1020         to << proxy_index;
1021     }
1022     q->changePersistentIndexList(from, to);
1023 }
1024
1025
1026 /*!
1027   \internal
1028
1029   Updates the proxy model (adds/removes rows) based on the
1030   new filter.
1031 */
1032 void QSortFilterProxyModelPrivate::filter_changed(const QModelIndex &source_parent)
1033 {
1034     IndexMap::const_iterator it = source_index_mapping.constFind(source_parent);
1035     if (it == source_index_mapping.constEnd())
1036         return;
1037     Mapping *m = it.value();
1038     QSet<int> rows_removed = handle_filter_changed(m->proxy_rows, m->source_rows, source_parent, Qt::Vertical);
1039     QSet<int> columns_removed = handle_filter_changed(m->proxy_columns, m->source_columns, source_parent, Qt::Horizontal);
1040
1041     // We need to iterate over a copy of m->mapped_children because otherwise it may be changed by other code, invalidating
1042     // the iterator it2.
1043     // The m->mapped_children vector can be appended to with indexes which are no longer filtered
1044     // out (in create_mapping) when this function recurses for child indexes.
1045     const QVector<QModelIndex> mappedChildren = m->mapped_children;
1046     QVector<int> indexesToRemove;
1047     for (int i = 0; i < mappedChildren.size(); ++i) {
1048         const QModelIndex source_child_index = mappedChildren.at(i);
1049         if (rows_removed.contains(source_child_index.row()) || columns_removed.contains(source_child_index.column())) {
1050             indexesToRemove.push_back(i);
1051             remove_from_mapping(source_child_index);
1052         } else {
1053             filter_changed(source_child_index);
1054         }
1055     }
1056     QVector<int>::const_iterator removeIt = indexesToRemove.constEnd();
1057     const QVector<int>::const_iterator removeBegin = indexesToRemove.constBegin();
1058
1059     // We can't just remove these items from mappedChildren while iterating above and then
1060     // do something like m->mapped_children = mappedChildren, because mapped_children might
1061     // be appended to in create_mapping, and we would lose those new items.
1062     // Because they are always appended in create_mapping, we can still remove them by
1063     // position here.
1064     while (removeIt != removeBegin) {
1065         --removeIt;
1066         m->mapped_children.remove(*removeIt);
1067     }
1068 }
1069
1070 /*!
1071   \internal
1072   returns the removed items indexes
1073 */
1074 QSet<int> QSortFilterProxyModelPrivate::handle_filter_changed(
1075     QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,
1076     const QModelIndex &source_parent, Qt::Orientation orient)
1077 {
1078     Q_Q(QSortFilterProxyModel);
1079     // Figure out which mapped items to remove
1080     QVector<int> source_items_remove;
1081     for (int i = 0; i < proxy_to_source.count(); ++i) {
1082         const int source_item = proxy_to_source.at(i);
1083         if ((orient == Qt::Vertical)
1084             ? !q->filterAcceptsRow(source_item, source_parent)
1085             : !q->filterAcceptsColumn(source_item, source_parent)) {
1086             // This source item does not satisfy the filter, so it must be removed
1087             source_items_remove.append(source_item);
1088         }
1089     }
1090     // Figure out which non-mapped items to insert
1091     QVector<int> source_items_insert;
1092     int source_count = source_to_proxy.size();
1093     for (int source_item = 0; source_item < source_count; ++source_item) {
1094         if (source_to_proxy.at(source_item) == -1) {
1095             if ((orient == Qt::Vertical)
1096                 ? q->filterAcceptsRow(source_item, source_parent)
1097                 : q->filterAcceptsColumn(source_item, source_parent)) {
1098                 // This source item satisfies the filter, so it must be added
1099                 source_items_insert.append(source_item);
1100             }
1101         }
1102     }
1103     if (!source_items_remove.isEmpty() || !source_items_insert.isEmpty()) {
1104         // Do item removal and insertion
1105         remove_source_items(source_to_proxy, proxy_to_source,
1106                             source_items_remove, source_parent, orient);
1107         if (orient == Qt::Vertical)
1108             sort_source_rows(source_items_insert, source_parent);
1109         insert_source_items(source_to_proxy, proxy_to_source,
1110                             source_items_insert, source_parent, orient);
1111     }
1112     return qVectorToSet(source_items_remove);
1113 }
1114
1115 void QSortFilterProxyModelPrivate::_q_sourceDataChanged(const QModelIndex &source_top_left,
1116                                                         const QModelIndex &source_bottom_right)
1117 {
1118     Q_Q(QSortFilterProxyModel);
1119     if (!source_top_left.isValid() || !source_bottom_right.isValid())
1120         return;
1121     QModelIndex source_parent = source_top_left.parent();
1122     IndexMap::const_iterator it = source_index_mapping.find(source_parent);
1123     if (it == source_index_mapping.constEnd()) {
1124         // Don't care, since we don't have mapping for this index
1125         return;
1126     }
1127     Mapping *m = it.value();
1128
1129     // Figure out how the source changes affect us
1130     QVector<int> source_rows_remove;
1131     QVector<int> source_rows_insert;
1132     QVector<int> source_rows_change;
1133     QVector<int> source_rows_resort;
1134     int end = qMin(source_bottom_right.row(), m->proxy_rows.count() - 1);
1135     for (int source_row = source_top_left.row(); source_row <= end; ++source_row) {
1136         if (dynamic_sortfilter) {
1137             if (m->proxy_rows.at(source_row) != -1) {
1138                 if (!q->filterAcceptsRow(source_row, source_parent)) {
1139                     // This source row no longer satisfies the filter, so it must be removed
1140                     source_rows_remove.append(source_row);
1141                 } else if (source_sort_column >= source_top_left.column() && source_sort_column <= source_bottom_right.column()) {
1142                     // This source row has changed in a way that may affect sorted order
1143                     source_rows_resort.append(source_row);
1144                 } else {
1145                     // This row has simply changed, without affecting filtering nor sorting
1146                     source_rows_change.append(source_row);
1147                 }
1148             } else {
1149                 if (!itemsBeingRemoved.contains(source_parent, source_row) && q->filterAcceptsRow(source_row, source_parent)) {
1150                     // This source row now satisfies the filter, so it must be added
1151                     source_rows_insert.append(source_row);
1152                 }
1153             }
1154         } else {
1155             if (m->proxy_rows.at(source_row) != -1)
1156                 source_rows_change.append(source_row);
1157         }
1158     }
1159
1160     if (!source_rows_remove.isEmpty()) {
1161         remove_source_items(m->proxy_rows, m->source_rows,
1162                             source_rows_remove, source_parent, Qt::Vertical);
1163         QSet<int> source_rows_remove_set = qVectorToSet(source_rows_remove);
1164         QVector<QModelIndex>::iterator it = m->mapped_children.end();
1165         while (it != m->mapped_children.begin()) {
1166             --it;
1167             const QModelIndex source_child_index = *it;
1168             if (source_rows_remove_set.contains(source_child_index.row())) {
1169                 it = m->mapped_children.erase(it);
1170                 remove_from_mapping(source_child_index);
1171             }
1172         }
1173     }
1174
1175     if (!source_rows_resort.isEmpty()) {
1176         // Re-sort the rows
1177         emit q->layoutAboutToBeChanged();
1178         QModelIndexPairList source_indexes = store_persistent_indexes();
1179         remove_source_items(m->proxy_rows, m->source_rows, source_rows_resort,
1180                             source_parent, Qt::Vertical, false);
1181         sort_source_rows(source_rows_resort, source_parent);
1182         insert_source_items(m->proxy_rows, m->source_rows, source_rows_resort,
1183                             source_parent, Qt::Vertical, false);
1184         update_persistent_indexes(source_indexes);
1185         emit q->layoutChanged();
1186         // Make sure we also emit dataChanged for the rows
1187         source_rows_change += source_rows_resort;
1188     }
1189
1190     if (!source_rows_change.isEmpty()) {
1191         // Find the proxy row range
1192         int proxy_start_row;
1193         int proxy_end_row;
1194         proxy_item_range(m->proxy_rows, source_rows_change,
1195                          proxy_start_row, proxy_end_row);
1196         // ### Find the proxy column range also
1197         if (proxy_end_row >= 0) {
1198             // the row was accepted, but some columns might still be filtered out
1199             int source_left_column = source_top_left.column();
1200             while (source_left_column < source_bottom_right.column()
1201                    && m->proxy_columns.at(source_left_column) == -1)
1202                 ++source_left_column;
1203             const QModelIndex proxy_top_left = create_index(
1204                 proxy_start_row, m->proxy_columns.at(source_left_column), it);
1205             int source_right_column = source_bottom_right.column();
1206             while (source_right_column > source_top_left.column()
1207                    && m->proxy_columns.at(source_right_column) == -1)
1208                 --source_right_column;
1209             const QModelIndex proxy_bottom_right = create_index(
1210                 proxy_end_row, m->proxy_columns.at(source_right_column), it);
1211             emit q->dataChanged(proxy_top_left, proxy_bottom_right);
1212         }
1213     }
1214
1215     if (!source_rows_insert.isEmpty()) {
1216         sort_source_rows(source_rows_insert, source_parent);
1217         insert_source_items(m->proxy_rows, m->source_rows,
1218                             source_rows_insert, source_parent, Qt::Vertical);
1219     }
1220 }
1221
1222 void QSortFilterProxyModelPrivate::_q_sourceHeaderDataChanged(Qt::Orientation orientation,
1223                                                            int start, int end)
1224 {
1225     Q_Q(QSortFilterProxyModel);
1226     Mapping *m = create_mapping(QModelIndex()).value();
1227     int proxy_start = (orientation == Qt::Vertical
1228                        ? m->proxy_rows.at(start)
1229                        : m->proxy_columns.at(start));
1230     int proxy_end = (orientation == Qt::Vertical
1231                      ? m->proxy_rows.at(end)
1232                      : m->proxy_columns.at(end));
1233     emit q->headerDataChanged(orientation, proxy_start, proxy_end);
1234 }
1235
1236 void QSortFilterProxyModelPrivate::_q_sourceAboutToBeReset()
1237 {
1238     Q_Q(QSortFilterProxyModel);
1239     q->beginResetModel();
1240 }
1241
1242 void QSortFilterProxyModelPrivate::_q_sourceReset()
1243 {
1244     Q_Q(QSortFilterProxyModel);
1245     invalidatePersistentIndexes();
1246     _q_clearMapping();
1247     // All internal structures are deleted in clear()
1248     q->endResetModel();
1249     update_source_sort_column();
1250     if (dynamic_sortfilter)
1251         sort();
1252 }
1253
1254 void QSortFilterProxyModelPrivate::_q_sourceLayoutAboutToBeChanged()
1255 {
1256     Q_Q(QSortFilterProxyModel);
1257     saved_persistent_indexes.clear();
1258     emit q->layoutAboutToBeChanged();
1259     if (persistent.indexes.isEmpty())
1260         return;
1261
1262     saved_persistent_indexes = store_persistent_indexes();
1263 }
1264
1265 void QSortFilterProxyModelPrivate::_q_sourceLayoutChanged()
1266 {
1267     Q_Q(QSortFilterProxyModel);
1268
1269     qDeleteAll(source_index_mapping);
1270     source_index_mapping.clear();
1271
1272     update_persistent_indexes(saved_persistent_indexes);
1273     saved_persistent_indexes.clear();
1274
1275     if (dynamic_sortfilter && update_source_sort_column()) {
1276         //update_source_sort_column might have created wrong mapping so we have to clear it again
1277         qDeleteAll(source_index_mapping);
1278         source_index_mapping.clear();
1279     }
1280
1281     emit q->layoutChanged();
1282 }
1283
1284 void QSortFilterProxyModelPrivate::_q_sourceRowsAboutToBeInserted(
1285     const QModelIndex &source_parent, int start, int end)
1286 {
1287     Q_UNUSED(start);
1288     Q_UNUSED(end);
1289     //Force the creation of a mapping now, even if its empty.
1290     //We need it because the proxy can be acessed at the moment it emits rowsAboutToBeInserted in insert_source_items
1291     if (can_create_mapping(source_parent))
1292         create_mapping(source_parent);
1293 }
1294
1295 void QSortFilterProxyModelPrivate::_q_sourceRowsInserted(
1296     const QModelIndex &source_parent, int start, int end)
1297 {
1298     source_items_inserted(source_parent, start, end, Qt::Vertical);
1299     if (update_source_sort_column() && dynamic_sortfilter) //previous call to update_source_sort_column may fail if the model has no column.
1300         sort();                      // now it should succeed so we need to make sure to sort again
1301 }
1302
1303 void QSortFilterProxyModelPrivate::_q_sourceRowsAboutToBeRemoved(
1304     const QModelIndex &source_parent, int start, int end)
1305 {
1306     itemsBeingRemoved = QRowsRemoval(source_parent, start, end);
1307     source_items_about_to_be_removed(source_parent, start, end,
1308                                      Qt::Vertical);
1309 }
1310
1311 void QSortFilterProxyModelPrivate::_q_sourceRowsRemoved(
1312     const QModelIndex &source_parent, int start, int end)
1313 {
1314     itemsBeingRemoved = QRowsRemoval();
1315     source_items_removed(source_parent, start, end, Qt::Vertical);
1316 }
1317
1318 void QSortFilterProxyModelPrivate::_q_sourceColumnsAboutToBeInserted(
1319     const QModelIndex &source_parent, int start, int end)
1320 {
1321     Q_UNUSED(start);
1322     Q_UNUSED(end);
1323     //Force the creation of a mapping now, even if its empty.
1324     //We need it because the proxy can be acessed at the moment it emits columnsAboutToBeInserted in insert_source_items
1325     if (can_create_mapping(source_parent))
1326         create_mapping(source_parent);
1327 }
1328
1329 void QSortFilterProxyModelPrivate::_q_sourceColumnsInserted(
1330     const QModelIndex &source_parent, int start, int end)
1331 {
1332     Q_Q(const QSortFilterProxyModel);
1333     source_items_inserted(source_parent, start, end, Qt::Horizontal);
1334
1335     if (source_parent.isValid())
1336         return; //we sort according to the root column only
1337     if (source_sort_column == -1) {
1338         //we update the source_sort_column depending on the proxy_sort_column
1339         if (update_source_sort_column() && dynamic_sortfilter)
1340             sort();
1341     } else {
1342         if (start <= source_sort_column)
1343             source_sort_column += end - start + 1;
1344
1345         proxy_sort_column = q->mapFromSource(model->index(0,source_sort_column, source_parent)).column();
1346     }
1347 }
1348
1349 void QSortFilterProxyModelPrivate::_q_sourceColumnsAboutToBeRemoved(
1350     const QModelIndex &source_parent, int start, int end)
1351 {
1352     source_items_about_to_be_removed(source_parent, start, end,
1353                                      Qt::Horizontal);
1354 }
1355
1356 void QSortFilterProxyModelPrivate::_q_sourceColumnsRemoved(
1357     const QModelIndex &source_parent, int start, int end)
1358 {
1359     Q_Q(const QSortFilterProxyModel);
1360     source_items_removed(source_parent, start, end, Qt::Horizontal);
1361
1362     if (source_parent.isValid())
1363         return; //we sort according to the root column only
1364     if (start <= source_sort_column) {
1365         if (end < source_sort_column)
1366             source_sort_column -= end - start + 1;
1367         else
1368             source_sort_column = -1;
1369     }
1370
1371     proxy_sort_column = q->mapFromSource(model->index(0,source_sort_column, source_parent)).column();
1372 }
1373
1374 /*!
1375     \since 4.1
1376     \class QSortFilterProxyModel
1377     \brief The QSortFilterProxyModel class provides support for sorting and
1378     filtering data passed between another model and a view.
1379
1380     \ingroup model-view
1381
1382     QSortFilterProxyModel can be used for sorting items, filtering out items,
1383     or both. The model transforms the structure of a source model by mapping
1384     the model indexes it supplies to new indexes, corresponding to different
1385     locations, for views to use. This approach allows a given source model to
1386     be restructured as far as views are concerned without requiring any
1387     transformations on the underlying data, and without duplicating the data in
1388     memory.
1389
1390     Let's assume that we want to sort and filter the items provided by a custom
1391     model. The code to set up the model and the view, \e without sorting and
1392     filtering, would look like this:
1393
1394     \snippet doc/src/snippets/qsortfilterproxymodel-details/main.cpp 1
1395
1396     To add sorting and filtering support to \c MyItemModel, we need to create
1397     a QSortFilterProxyModel, call setSourceModel() with the \c MyItemModel as
1398     argument, and install the QSortFilterProxyModel on the view:
1399
1400     \snippet doc/src/snippets/qsortfilterproxymodel-details/main.cpp 0
1401     \snippet doc/src/snippets/qsortfilterproxymodel-details/main.cpp 2
1402
1403     At this point, neither sorting nor filtering is enabled; the original data
1404     is displayed in the view. Any changes made through the
1405     QSortFilterProxyModel are applied to the original model.
1406
1407     The QSortFilterProxyModel acts as a wrapper for the original model. If you
1408     need to convert source \l{QModelIndex}es to sorted/filtered model indexes
1409     or vice versa, use mapToSource(), mapFromSource(), mapSelectionToSource(),
1410     and mapSelectionFromSource().
1411
1412     \note By default, the model does not dynamically re-sort and re-filter data
1413     whenever the original model changes. This behavior can be changed by
1414     setting the \l{QSortFilterProxyModel::dynamicSortFilter}{dynamicSortFilter}
1415     property.
1416
1417     The \l{itemviews/basicsortfiltermodel}{Basic Sort/Filter Model} and
1418     \l{itemviews/customsortfiltermodel}{Custom Sort/Filter Model} examples
1419     illustrate how to use QSortFilterProxyModel to perform basic sorting and
1420     filtering and how to subclass it to implement custom behavior.
1421
1422     \section1 Sorting
1423
1424     QTableView and QTreeView have a
1425     \l{QTreeView::sortingEnabled}{sortingEnabled} property that controls
1426     whether the user can sort the view by clicking the view's horizontal
1427     header. For example:
1428
1429     \snippet doc/src/snippets/qsortfilterproxymodel-details/main.cpp 3
1430
1431     When this feature is on (the default is off), clicking on a header section
1432     sorts the items according to that column. By clicking repeatedly, the user
1433     can alternate between ascending and descending order.
1434
1435     \image qsortfilterproxymodel-sorting.png A sorted QTreeView
1436
1437     Behind the scene, the view calls the sort() virtual function on the model
1438     to reorder the data in the model. To make your data sortable, you can
1439     either implement sort() in your model, or use a QSortFilterProxyModel to
1440     wrap your model -- QSortFilterProxyModel provides a generic sort()
1441     reimplementation that operates on the sortRole() (Qt::DisplayRole by
1442     default) of the items and that understands several data types, including
1443     \c int, QString, and QDateTime. For hierarchical models, sorting is applied
1444     recursively to all child items. String comparisons are case sensitive by
1445     default; this can be changed by setting the \l{QSortFilterProxyModel::}
1446     {sortCaseSensitivity} property.
1447
1448     Custom sorting behavior is achieved by subclassing
1449     QSortFilterProxyModel and reimplementing lessThan(), which is
1450     used to compare items. For example:
1451
1452     \snippet examples/itemviews/customsortfiltermodel/mysortfilterproxymodel.cpp 5
1453
1454     (This code snippet comes from the
1455     \l{itemviews/customsortfiltermodel}{Custom Sort/Filter Model}
1456     example.)
1457
1458     An alternative approach to sorting is to disable sorting on the view and to
1459     impose a certain order to the user. This is done by explicitly calling
1460     sort() with the desired column and order as arguments on the
1461     QSortFilterProxyModel (or on the original model if it implements sort()).
1462     For example:
1463
1464     \snippet doc/src/snippets/qsortfilterproxymodel-details/main.cpp 4
1465
1466     QSortFilterProxyModel can be sorted by column -1, in which case it returns
1467     to the sort order of the underlying source model.
1468
1469     \section1 Filtering
1470
1471     In addition to sorting, QSortFilterProxyModel can be used to hide items
1472     that do not match a certain filter. The filter is specified using a QRegExp
1473     object and is applied to the filterRole() (Qt::DisplayRole by default) of
1474     each item, for a given column. The QRegExp object can be used to match a
1475     regular expression, a wildcard pattern, or a fixed string. For example:
1476
1477     \snippet doc/src/snippets/qsortfilterproxymodel-details/main.cpp 5
1478
1479     For hierarchical models, the filter is applied recursively to all children.
1480     If a parent item doesn't match the filter, none of its children will be
1481     shown.
1482
1483     A common use case is to let the user specify the filter regexp, wildcard
1484     pattern, or fixed string in a QLineEdit and to connect the
1485     \l{QLineEdit::textChanged()}{textChanged()} signal to setFilterRegExp(),
1486     setFilterWildcard(), or setFilterFixedString() to reapply the filter.
1487
1488     Custom filtering behavior can be achieved by reimplementing the
1489     filterAcceptsRow() and filterAcceptsColumn() functions. For
1490     example (from the \l{itemviews/customsortfiltermodel}
1491     {Custom Sort/Filter Model} example), the following implementation ignores
1492     the \l{QSortFilterProxyModel::filterKeyColumn}{filterKeyColumn} property
1493     and performs filtering on columns 0, 1, and 2:
1494
1495     \snippet examples/itemviews/customsortfiltermodel/mysortfilterproxymodel.cpp 3
1496
1497     (This code snippet comes from the
1498     \l{itemviews/customsortfiltermodel}{Custom Sort/Filter Model}
1499     example.)
1500
1501     If you are working with large amounts of filtering and have to invoke
1502     invalidateFilter() repeatedly, using reset() may be more efficient,
1503     depending on the implementation of your model. However, reset() returns the
1504     proxy model to its original state, losing selection information, and will
1505     cause the proxy model to be repopulated.
1506
1507     \section1 Subclassing
1508
1509     Since QAbstractProxyModel and its subclasses are derived from
1510     QAbstractItemModel, much of the same advice about subclassing normal models
1511     also applies to proxy models. In addition, it is worth noting that many of
1512     the default implementations of functions in this class are written so that
1513     they call the equivalent functions in the relevant source model. This
1514     simple proxying mechanism may need to be overridden for source models with
1515     more complex behavior; for example, if the source model provides a custom
1516     hasChildren() implementation, you should also provide one in the proxy
1517     model.
1518
1519     \note Some general guidelines for subclassing models are available in the
1520     \l{Model Subclassing Reference}.
1521
1522     \sa QAbstractProxyModel, QAbstractItemModel, {Model/View Programming},
1523     {Basic Sort/Filter Model Example}, {Custom Sort/Filter Model Example}, QIdentityProxyModel
1524 */
1525
1526 /*!
1527     Constructs a sorting filter model with the given \a parent.
1528 */
1529
1530 QSortFilterProxyModel::QSortFilterProxyModel(QObject *parent)
1531     : QAbstractProxyModel(*new QSortFilterProxyModelPrivate, parent)
1532 {
1533     Q_D(QSortFilterProxyModel);
1534     d->proxy_sort_column = d->source_sort_column = -1;
1535     d->sort_order = Qt::AscendingOrder;
1536     d->sort_casesensitivity = Qt::CaseSensitive;
1537     d->sort_role = Qt::DisplayRole;
1538     d->sort_localeaware = false;
1539     d->filter_column = 0;
1540     d->filter_role = Qt::DisplayRole;
1541     d->dynamic_sortfilter = false;
1542     connect(this, SIGNAL(modelReset()), this, SLOT(_q_clearMapping()));
1543 }
1544
1545 /*!
1546     Destroys this sorting filter model.
1547 */
1548 QSortFilterProxyModel::~QSortFilterProxyModel()
1549 {
1550     Q_D(QSortFilterProxyModel);
1551     qDeleteAll(d->source_index_mapping);
1552     d->source_index_mapping.clear();
1553 }
1554
1555 /*!
1556   \reimp
1557 */
1558 void QSortFilterProxyModel::setSourceModel(QAbstractItemModel *sourceModel)
1559 {
1560     Q_D(QSortFilterProxyModel);
1561
1562     beginResetModel();
1563
1564     disconnect(d->model, SIGNAL(dataChanged(QModelIndex,QModelIndex)),
1565                this, SLOT(_q_sourceDataChanged(QModelIndex,QModelIndex)));
1566
1567     disconnect(d->model, SIGNAL(headerDataChanged(Qt::Orientation,int,int)),
1568                this, SLOT(_q_sourceHeaderDataChanged(Qt::Orientation,int,int)));
1569
1570     disconnect(d->model, SIGNAL(rowsAboutToBeInserted(QModelIndex,int,int)),
1571                this, SLOT(_q_sourceRowsAboutToBeInserted(QModelIndex,int,int)));
1572
1573     disconnect(d->model, SIGNAL(rowsInserted(QModelIndex,int,int)),
1574                this, SLOT(_q_sourceRowsInserted(QModelIndex,int,int)));
1575
1576     disconnect(d->model, SIGNAL(columnsAboutToBeInserted(QModelIndex,int,int)),
1577                this, SLOT(_q_sourceColumnsAboutToBeInserted(QModelIndex,int,int)));
1578
1579     disconnect(d->model, SIGNAL(columnsInserted(QModelIndex,int,int)),
1580                this, SLOT(_q_sourceColumnsInserted(QModelIndex,int,int)));
1581
1582     disconnect(d->model, SIGNAL(rowsAboutToBeRemoved(QModelIndex,int,int)),
1583                this, SLOT(_q_sourceRowsAboutToBeRemoved(QModelIndex,int,int)));
1584
1585     disconnect(d->model, SIGNAL(rowsRemoved(QModelIndex,int,int)),
1586                this, SLOT(_q_sourceRowsRemoved(QModelIndex,int,int)));
1587
1588     disconnect(d->model, SIGNAL(columnsAboutToBeRemoved(QModelIndex,int,int)),
1589                this, SLOT(_q_sourceColumnsAboutToBeRemoved(QModelIndex,int,int)));
1590
1591     disconnect(d->model, SIGNAL(columnsRemoved(QModelIndex,int,int)),
1592                this, SLOT(_q_sourceColumnsRemoved(QModelIndex,int,int)));
1593
1594     disconnect(d->model, SIGNAL(layoutAboutToBeChanged()),
1595                this, SLOT(_q_sourceLayoutAboutToBeChanged()));
1596
1597     disconnect(d->model, SIGNAL(layoutChanged()),
1598                this, SLOT(_q_sourceLayoutChanged()));
1599
1600     disconnect(d->model, SIGNAL(modelAboutToBeReset()), this, SLOT(_q_sourceAboutToBeReset()));
1601     disconnect(d->model, SIGNAL(modelReset()), this, SLOT(_q_sourceReset()));
1602
1603     QAbstractProxyModel::setSourceModel(sourceModel);
1604
1605     connect(d->model, SIGNAL(dataChanged(QModelIndex,QModelIndex)),
1606             this, SLOT(_q_sourceDataChanged(QModelIndex,QModelIndex)));
1607
1608     connect(d->model, SIGNAL(headerDataChanged(Qt::Orientation,int,int)),
1609             this, SLOT(_q_sourceHeaderDataChanged(Qt::Orientation,int,int)));
1610
1611     connect(d->model, SIGNAL(rowsAboutToBeInserted(QModelIndex,int,int)),
1612             this, SLOT(_q_sourceRowsAboutToBeInserted(QModelIndex,int,int)));
1613
1614     connect(d->model, SIGNAL(rowsInserted(QModelIndex,int,int)),
1615             this, SLOT(_q_sourceRowsInserted(QModelIndex,int,int)));
1616
1617     connect(d->model, SIGNAL(columnsAboutToBeInserted(QModelIndex,int,int)),
1618             this, SLOT(_q_sourceColumnsAboutToBeInserted(QModelIndex,int,int)));
1619
1620     connect(d->model, SIGNAL(columnsInserted(QModelIndex,int,int)),
1621             this, SLOT(_q_sourceColumnsInserted(QModelIndex,int,int)));
1622
1623     connect(d->model, SIGNAL(rowsAboutToBeRemoved(QModelIndex,int,int)),
1624             this, SLOT(_q_sourceRowsAboutToBeRemoved(QModelIndex,int,int)));
1625
1626     connect(d->model, SIGNAL(rowsRemoved(QModelIndex,int,int)),
1627             this, SLOT(_q_sourceRowsRemoved(QModelIndex,int,int)));
1628
1629     connect(d->model, SIGNAL(columnsAboutToBeRemoved(QModelIndex,int,int)),
1630             this, SLOT(_q_sourceColumnsAboutToBeRemoved(QModelIndex,int,int)));
1631
1632     connect(d->model, SIGNAL(columnsRemoved(QModelIndex,int,int)),
1633             this, SLOT(_q_sourceColumnsRemoved(QModelIndex,int,int)));
1634
1635     connect(d->model, SIGNAL(layoutAboutToBeChanged()),
1636             this, SLOT(_q_sourceLayoutAboutToBeChanged()));
1637
1638     connect(d->model, SIGNAL(layoutChanged()),
1639             this, SLOT(_q_sourceLayoutChanged()));
1640
1641     connect(d->model, SIGNAL(modelAboutToBeReset()), this, SLOT(_q_sourceAboutToBeReset()));
1642     connect(d->model, SIGNAL(modelReset()), this, SLOT(_q_sourceReset()));
1643
1644     d->_q_clearMapping();
1645     endResetModel();
1646     if (d->update_source_sort_column() && d->dynamic_sortfilter)
1647         d->sort();
1648 }
1649
1650 /*!
1651     \reimp
1652 */
1653 QModelIndex QSortFilterProxyModel::index(int row, int column, const QModelIndex &parent) const
1654 {
1655     Q_D(const QSortFilterProxyModel);
1656     if (row < 0 || column < 0)
1657         return QModelIndex();
1658
1659     QModelIndex source_parent = mapToSource(parent); // parent is already mapped at this point
1660     IndexMap::const_iterator it = d->create_mapping(source_parent); // but make sure that the children are mapped
1661     if (it.value()->source_rows.count() <= row || it.value()->source_columns.count() <= column)
1662         return QModelIndex();
1663
1664     return d->create_index(row, column, it);
1665 }
1666
1667 /*!
1668   \reimp
1669 */
1670 QModelIndex QSortFilterProxyModel::parent(const QModelIndex &child) const
1671 {
1672     Q_D(const QSortFilterProxyModel);
1673     if (!d->indexValid(child))
1674         return QModelIndex();
1675     IndexMap::const_iterator it = d->index_to_iterator(child);
1676     Q_ASSERT(it != d->source_index_mapping.constEnd());
1677     QModelIndex source_parent = it.key();
1678     QModelIndex proxy_parent = mapFromSource(source_parent);
1679     return proxy_parent;
1680 }
1681
1682 /*!
1683   \reimp
1684 */
1685 int QSortFilterProxyModel::rowCount(const QModelIndex &parent) const
1686 {
1687     Q_D(const QSortFilterProxyModel);
1688     QModelIndex source_parent = mapToSource(parent);
1689     if (parent.isValid() && !source_parent.isValid())
1690         return 0;
1691     IndexMap::const_iterator it = d->create_mapping(source_parent);
1692     return it.value()->source_rows.count();
1693 }
1694
1695 /*!
1696   \reimp
1697 */
1698 int QSortFilterProxyModel::columnCount(const QModelIndex &parent) const
1699 {
1700     Q_D(const QSortFilterProxyModel);
1701     QModelIndex source_parent = mapToSource(parent);
1702     if (parent.isValid() && !source_parent.isValid())
1703         return 0;
1704     IndexMap::const_iterator it = d->create_mapping(source_parent);
1705     return it.value()->source_columns.count();
1706 }
1707
1708 /*!
1709   \reimp
1710 */
1711 bool QSortFilterProxyModel::hasChildren(const QModelIndex &parent) const
1712 {
1713     Q_D(const QSortFilterProxyModel);
1714     QModelIndex source_parent = mapToSource(parent);
1715     if (parent.isValid() && !source_parent.isValid())
1716         return false;
1717     if (!d->model->hasChildren(source_parent))
1718         return false;
1719
1720     if (d->model->canFetchMore(source_parent))
1721         return true; //we assume we might have children that can be fetched
1722
1723     QSortFilterProxyModelPrivate::Mapping *m = d->create_mapping(source_parent).value();
1724     return m->source_rows.count() != 0 && m->source_columns.count() != 0;
1725 }
1726
1727 /*!
1728   \reimp
1729 */
1730 QVariant QSortFilterProxyModel::data(const QModelIndex &index, int role) const
1731 {
1732     Q_D(const QSortFilterProxyModel);
1733     QModelIndex source_index = mapToSource(index);
1734     if (index.isValid() && !source_index.isValid())
1735         return QVariant();
1736     return d->model->data(source_index, role);
1737 }
1738
1739 /*!
1740   \reimp
1741 */
1742 bool QSortFilterProxyModel::setData(const QModelIndex &index, const QVariant &value, int role)
1743 {
1744     Q_D(QSortFilterProxyModel);
1745     QModelIndex source_index = mapToSource(index);
1746     if (index.isValid() && !source_index.isValid())
1747         return false;
1748     return d->model->setData(source_index, value, role);
1749 }
1750
1751 /*!
1752   \reimp
1753 */
1754 QVariant QSortFilterProxyModel::headerData(int section, Qt::Orientation orientation, int role) const
1755 {
1756     Q_D(const QSortFilterProxyModel);
1757     IndexMap::const_iterator it = d->create_mapping(QModelIndex());
1758     if (it.value()->source_rows.count() * it.value()->source_columns.count() > 0)
1759         return QAbstractProxyModel::headerData(section, orientation, role);
1760     int source_section;
1761     if (orientation == Qt::Vertical) {
1762         if (section < 0 || section >= it.value()->source_rows.count())
1763             return QVariant();
1764         source_section = it.value()->source_rows.at(section);
1765     } else {
1766         if (section < 0 || section >= it.value()->source_columns.count())
1767             return QVariant();
1768         source_section = it.value()->source_columns.at(section);
1769     }
1770     return d->model->headerData(source_section, orientation, role);
1771 }
1772
1773 /*!
1774   \reimp
1775 */
1776 bool QSortFilterProxyModel::setHeaderData(int section, Qt::Orientation orientation,
1777                                           const QVariant &value, int role)
1778 {
1779     Q_D(QSortFilterProxyModel);
1780     IndexMap::const_iterator it = d->create_mapping(QModelIndex());
1781     if (it.value()->source_rows.count() * it.value()->source_columns.count() > 0)
1782         return QAbstractProxyModel::setHeaderData(section, orientation, value, role);
1783     int source_section;
1784     if (orientation == Qt::Vertical) {
1785         if (section < 0 || section >= it.value()->source_rows.count())
1786             return false;
1787         source_section = it.value()->source_rows.at(section);
1788     } else {
1789         if (section < 0 || section >= it.value()->source_columns.count())
1790             return false;
1791         source_section = it.value()->source_columns.at(section);
1792     }
1793     return d->model->setHeaderData(source_section, orientation, value, role);
1794 }
1795
1796 /*!
1797   \reimp
1798 */
1799 QMimeData *QSortFilterProxyModel::mimeData(const QModelIndexList &indexes) const
1800 {
1801     Q_D(const QSortFilterProxyModel);
1802     QModelIndexList source_indexes;
1803     for (int i = 0; i < indexes.count(); ++i)
1804         source_indexes << mapToSource(indexes.at(i));
1805     return d->model->mimeData(source_indexes);
1806 }
1807
1808 /*!
1809   \reimp
1810 */
1811 QStringList QSortFilterProxyModel::mimeTypes() const
1812 {
1813     Q_D(const QSortFilterProxyModel);
1814     return d->model->mimeTypes();
1815 }
1816
1817 /*!
1818   \reimp
1819 */
1820 Qt::DropActions QSortFilterProxyModel::supportedDropActions() const
1821 {
1822     Q_D(const QSortFilterProxyModel);
1823     return d->model->supportedDropActions();
1824 }
1825
1826 /*!
1827   \reimp
1828 */
1829 bool QSortFilterProxyModel::dropMimeData(const QMimeData *data, Qt::DropAction action,
1830                                          int row, int column, const QModelIndex &parent)
1831 {
1832     Q_D(QSortFilterProxyModel);
1833     if ((row == -1) && (column == -1))
1834         return d->model->dropMimeData(data, action, -1, -1, mapToSource(parent));
1835     int source_destination_row = -1;
1836     int source_destination_column = -1;
1837     QModelIndex source_parent;
1838     if (row == rowCount(parent)) {
1839         source_parent = mapToSource(parent);
1840         source_destination_row = d->model->rowCount(source_parent);
1841     } else {
1842         QModelIndex proxy_index = index(row, column, parent);
1843         QModelIndex source_index = mapToSource(proxy_index);
1844         source_destination_row = source_index.row();
1845         source_destination_column = source_index.column();
1846         source_parent = source_index.parent();
1847     }
1848     return d->model->dropMimeData(data, action, source_destination_row,
1849                                   source_destination_column, source_parent);
1850 }
1851
1852 /*!
1853   \reimp
1854 */
1855 bool QSortFilterProxyModel::insertRows(int row, int count, const QModelIndex &parent)
1856 {
1857     Q_D(QSortFilterProxyModel);
1858     if (row < 0 || count <= 0)
1859         return false;
1860     QModelIndex source_parent = mapToSource(parent);
1861     if (parent.isValid() && !source_parent.isValid())
1862         return false;
1863     QSortFilterProxyModelPrivate::Mapping *m = d->create_mapping(source_parent).value();
1864     if (row > m->source_rows.count())
1865         return false;
1866     int source_row = (row >= m->source_rows.count()
1867                       ? m->source_rows.count()
1868                       : m->source_rows.at(row));
1869     return d->model->insertRows(source_row, count, source_parent);
1870 }
1871
1872 /*!
1873   \reimp
1874 */
1875 bool QSortFilterProxyModel::insertColumns(int column, int count, const QModelIndex &parent)
1876 {
1877     Q_D(QSortFilterProxyModel);
1878     if (column < 0|| count <= 0)
1879         return false;
1880     QModelIndex source_parent = mapToSource(parent);
1881     if (parent.isValid() && !source_parent.isValid())
1882         return false;
1883     QSortFilterProxyModelPrivate::Mapping *m = d->create_mapping(source_parent).value();
1884     if (column > m->source_columns.count())
1885         return false;
1886     int source_column = (column >= m->source_columns.count()
1887                          ? m->source_columns.count()
1888                          : m->source_columns.at(column));
1889     return d->model->insertColumns(source_column, count, source_parent);
1890 }
1891
1892 /*!
1893   \reimp
1894 */
1895 bool QSortFilterProxyModel::removeRows(int row, int count, const QModelIndex &parent)
1896 {
1897     Q_D(QSortFilterProxyModel);
1898     if (row < 0 || count <= 0)
1899         return false;
1900     QModelIndex source_parent = mapToSource(parent);
1901     if (parent.isValid() && !source_parent.isValid())
1902         return false;
1903     QSortFilterProxyModelPrivate::Mapping *m = d->create_mapping(source_parent).value();
1904     if (row + count > m->source_rows.count())
1905         return false;
1906     if ((count == 1)
1907         || ((d->source_sort_column < 0) && (m->proxy_rows.count() == m->source_rows.count()))) {
1908         int source_row = m->source_rows.at(row);
1909         return d->model->removeRows(source_row, count, source_parent);
1910     }
1911     // remove corresponding source intervals
1912     // ### if this proves to be slow, we can switch to single-row removal
1913     QVector<int> rows;
1914     for (int i = row; i < row + count; ++i)
1915         rows.append(m->source_rows.at(i));
1916     qSort(rows.begin(), rows.end());
1917
1918     int pos = rows.count() - 1;
1919     bool ok = true;
1920     while (pos >= 0) {
1921         const int source_end = rows.at(pos--);
1922         int source_start = source_end;
1923         while ((pos >= 0) && (rows.at(pos) == (source_start - 1))) {
1924             --source_start;
1925             --pos;
1926         }
1927         ok = ok && d->model->removeRows(source_start, source_end - source_start + 1,
1928                                         source_parent);
1929     }
1930     return ok;
1931 }
1932
1933 /*!
1934   \reimp
1935 */
1936 bool QSortFilterProxyModel::removeColumns(int column, int count, const QModelIndex &parent)
1937 {
1938     Q_D(QSortFilterProxyModel);
1939     if (column < 0 || count <= 0)
1940         return false;
1941     QModelIndex source_parent = mapToSource(parent);
1942     if (parent.isValid() && !source_parent.isValid())
1943         return false;
1944     QSortFilterProxyModelPrivate::Mapping *m = d->create_mapping(source_parent).value();
1945     if (column + count > m->source_columns.count())
1946         return false;
1947     if ((count == 1) || (m->proxy_columns.count() == m->source_columns.count())) {
1948         int source_column = m->source_columns.at(column);
1949         return d->model->removeColumns(source_column, count, source_parent);
1950     }
1951     // remove corresponding source intervals
1952     QVector<int> columns;
1953     for (int i = column; i < column + count; ++i)
1954         columns.append(m->source_columns.at(i));
1955
1956     int pos = columns.count() - 1;
1957     bool ok = true;
1958     while (pos >= 0) {
1959         const int source_end = columns.at(pos--);
1960         int source_start = source_end;
1961         while ((pos >= 0) && (columns.at(pos) == (source_start - 1))) {
1962             --source_start;
1963             --pos;
1964         }
1965         ok = ok && d->model->removeColumns(source_start, source_end - source_start + 1,
1966                                            source_parent);
1967     }
1968     return ok;
1969 }
1970
1971 /*!
1972   \reimp
1973 */
1974 void QSortFilterProxyModel::fetchMore(const QModelIndex &parent)
1975 {
1976     Q_D(QSortFilterProxyModel);
1977     QModelIndex source_parent;
1978     if (d->indexValid(parent))
1979         source_parent = mapToSource(parent);
1980     d->model->fetchMore(source_parent);
1981 }
1982
1983 /*!
1984   \reimp
1985 */
1986 bool QSortFilterProxyModel::canFetchMore(const QModelIndex &parent) const
1987 {
1988     Q_D(const QSortFilterProxyModel);
1989     QModelIndex source_parent;
1990     if (d->indexValid(parent))
1991         source_parent = mapToSource(parent);
1992     return d->model->canFetchMore(source_parent);
1993 }
1994
1995 /*!
1996   \reimp
1997 */
1998 Qt::ItemFlags QSortFilterProxyModel::flags(const QModelIndex &index) const
1999 {
2000     Q_D(const QSortFilterProxyModel);
2001     QModelIndex source_index;
2002     if (d->indexValid(index))
2003         source_index = mapToSource(index);
2004     return d->model->flags(source_index);
2005 }
2006
2007 /*!
2008   \reimp
2009 */
2010 QModelIndex QSortFilterProxyModel::buddy(const QModelIndex &index) const
2011 {
2012     Q_D(const QSortFilterProxyModel);
2013     if (!d->indexValid(index))
2014         return QModelIndex();
2015     QModelIndex source_index = mapToSource(index);
2016     QModelIndex source_buddy = d->model->buddy(source_index);
2017     if (source_index == source_buddy)
2018         return index;
2019     return mapFromSource(source_buddy);
2020 }
2021
2022 /*!
2023   \reimp
2024 */
2025 QModelIndexList QSortFilterProxyModel::match(const QModelIndex &start, int role,
2026                                              const QVariant &value, int hits,
2027                                              Qt::MatchFlags flags) const
2028 {
2029     return QAbstractProxyModel::match(start, role, value, hits, flags);
2030 }
2031
2032 /*!
2033   \reimp
2034 */
2035 QSize QSortFilterProxyModel::span(const QModelIndex &index) const
2036 {
2037     Q_D(const QSortFilterProxyModel);
2038     QModelIndex source_index = mapToSource(index);
2039     if (index.isValid() && !source_index.isValid())
2040         return QSize();
2041     return d->model->span(source_index);
2042 }
2043
2044 /*!
2045   \reimp
2046 */
2047 void QSortFilterProxyModel::sort(int column, Qt::SortOrder order)
2048 {
2049     Q_D(QSortFilterProxyModel);
2050     if (d->dynamic_sortfilter && d->proxy_sort_column == column && d->sort_order == order)
2051         return;
2052     d->sort_order = order;
2053     d->proxy_sort_column = column;
2054     d->update_source_sort_column();
2055     d->sort();
2056 }
2057
2058 /*!
2059     \since 4.5
2060     \brief the column currently used for sorting
2061
2062     This returns the most recently used sort column.
2063 */
2064 int QSortFilterProxyModel::sortColumn() const
2065 {
2066     Q_D(const QSortFilterProxyModel);
2067     return d->proxy_sort_column;
2068 }
2069
2070 /*!
2071     \since 4.5
2072     \brief the order currently used for sorting
2073
2074     This returns the most recently used sort order.
2075 */
2076 Qt::SortOrder QSortFilterProxyModel::sortOrder() const
2077 {
2078     Q_D(const QSortFilterProxyModel);
2079     return d->sort_order;
2080 }
2081
2082 /*!
2083     \property QSortFilterProxyModel::filterRegExp
2084     \brief the QRegExp used to filter the contents of the source model
2085
2086     Setting this property overwrites the current
2087     \l{QSortFilterProxyModel::filterCaseSensitivity}{filterCaseSensitivity}.
2088     By default, the QRegExp is an empty string matching all contents.
2089
2090     If no QRegExp or an empty string is set, everything in the source model
2091     will be accepted.
2092
2093     \sa filterCaseSensitivity, setFilterWildcard(), setFilterFixedString()
2094 */
2095 QRegExp QSortFilterProxyModel::filterRegExp() const
2096 {
2097     Q_D(const QSortFilterProxyModel);
2098     return d->filter_regexp;
2099 }
2100
2101 void QSortFilterProxyModel::setFilterRegExp(const QRegExp &regExp)
2102 {
2103     Q_D(QSortFilterProxyModel);
2104     d->filter_regexp = regExp;
2105     d->filter_changed();
2106 }
2107
2108 /*!
2109     \property QSortFilterProxyModel::filterKeyColumn
2110     \brief the column where the key used to filter the contents of the
2111     source model is read from.
2112
2113     The default value is 0. If the value is -1, the keys will be read
2114     from all columns.
2115 */
2116 int QSortFilterProxyModel::filterKeyColumn() const
2117 {
2118     Q_D(const QSortFilterProxyModel);
2119     return d->filter_column;
2120 }
2121
2122 void QSortFilterProxyModel::setFilterKeyColumn(int column)
2123 {
2124     Q_D(QSortFilterProxyModel);
2125     d->filter_column = column;
2126     d->filter_changed();
2127 }
2128
2129 /*!
2130     \property QSortFilterProxyModel::filterCaseSensitivity
2131
2132     \brief the case sensitivity of the QRegExp pattern used to filter the
2133     contents of the source model
2134
2135     By default, the filter is case sensitive.
2136
2137     \sa filterRegExp, sortCaseSensitivity
2138 */
2139 Qt::CaseSensitivity QSortFilterProxyModel::filterCaseSensitivity() const
2140 {
2141     Q_D(const QSortFilterProxyModel);
2142     return d->filter_regexp.caseSensitivity();
2143 }
2144
2145 void QSortFilterProxyModel::setFilterCaseSensitivity(Qt::CaseSensitivity cs)
2146 {
2147     Q_D(QSortFilterProxyModel);
2148     if (cs == d->filter_regexp.caseSensitivity())
2149         return;
2150     d->filter_regexp.setCaseSensitivity(cs);
2151     d->filter_changed();
2152 }
2153
2154 /*!
2155     \since 4.2
2156     \property QSortFilterProxyModel::sortCaseSensitivity
2157     \brief the case sensitivity setting used for comparing strings when sorting
2158
2159     By default, sorting is case sensitive.
2160
2161     \sa filterCaseSensitivity, lessThan()
2162 */
2163 Qt::CaseSensitivity QSortFilterProxyModel::sortCaseSensitivity() const
2164 {
2165     Q_D(const QSortFilterProxyModel);
2166     return d->sort_casesensitivity;
2167 }
2168
2169 void QSortFilterProxyModel::setSortCaseSensitivity(Qt::CaseSensitivity cs)
2170 {
2171     Q_D(QSortFilterProxyModel);
2172     if (d->sort_casesensitivity == cs)
2173         return;
2174
2175     d->sort_casesensitivity = cs;
2176     d->sort();
2177 }
2178
2179 /*!
2180     \since 4.3
2181     \property QSortFilterProxyModel::isSortLocaleAware
2182     \brief the local aware setting used for comparing strings when sorting
2183
2184     By default, sorting is not local aware.
2185
2186     \sa sortCaseSensitivity, lessThan()
2187 */
2188 bool QSortFilterProxyModel::isSortLocaleAware() const
2189 {
2190     Q_D(const QSortFilterProxyModel);
2191     return d->sort_localeaware;
2192 }
2193
2194 void QSortFilterProxyModel::setSortLocaleAware(bool on)
2195 {
2196     Q_D(QSortFilterProxyModel);
2197     if (d->sort_localeaware == on)
2198         return;
2199
2200     d->sort_localeaware = on;
2201     d->sort();
2202 }
2203
2204 /*!
2205     \overload
2206
2207     Sets the regular expression used to filter the contents
2208     of the source model to \a pattern.
2209
2210     \sa setFilterCaseSensitivity(), setFilterWildcard(), setFilterFixedString(), filterRegExp()
2211 */
2212 void QSortFilterProxyModel::setFilterRegExp(const QString &pattern)
2213 {
2214     Q_D(QSortFilterProxyModel);
2215     d->filter_regexp.setPatternSyntax(QRegExp::RegExp);
2216     d->filter_regexp.setPattern(pattern);
2217     d->filter_changed();
2218 }
2219
2220 /*!
2221     Sets the wildcard expression used to filter the contents
2222     of the source model to the given \a pattern.
2223
2224     \sa setFilterCaseSensitivity(), setFilterRegExp(), setFilterFixedString(), filterRegExp()
2225 */
2226 void QSortFilterProxyModel::setFilterWildcard(const QString &pattern)
2227 {
2228     Q_D(QSortFilterProxyModel);
2229     d->filter_regexp.setPatternSyntax(QRegExp::Wildcard);
2230     d->filter_regexp.setPattern(pattern);
2231     d->filter_changed();
2232 }
2233
2234 /*!
2235     Sets the fixed string used to filter the contents
2236     of the source model to the given \a pattern.
2237
2238     \sa setFilterCaseSensitivity(), setFilterRegExp(), setFilterWildcard(), filterRegExp()
2239 */
2240 void QSortFilterProxyModel::setFilterFixedString(const QString &pattern)
2241 {
2242     Q_D(QSortFilterProxyModel);
2243     d->filter_regexp.setPatternSyntax(QRegExp::FixedString);
2244     d->filter_regexp.setPattern(pattern);
2245     d->filter_changed();
2246 }
2247
2248 /*!
2249     \since 4.2
2250     \property QSortFilterProxyModel::dynamicSortFilter
2251     \brief whether the proxy model is dynamically sorted and filtered
2252     whenever the contents of the source model change
2253
2254     Note that you should not update the source model through the proxy
2255     model when dynamicSortFilter is true. For instance, if you set the
2256     proxy model on a QComboBox, then using functions that update the
2257     model, e.g., \l{QComboBox::}{addItem()}, will not work as
2258     expected. An alternative is to set dynamicSortFilter to false and
2259     call \l{QSortFilterProxyModel::}{sort()} after adding items to the
2260     QComboBox.
2261
2262     The default value is false.
2263 */
2264 bool QSortFilterProxyModel::dynamicSortFilter() const
2265 {
2266     Q_D(const QSortFilterProxyModel);
2267     return d->dynamic_sortfilter;
2268 }
2269
2270 void QSortFilterProxyModel::setDynamicSortFilter(bool enable)
2271 {
2272     Q_D(QSortFilterProxyModel);
2273     d->dynamic_sortfilter = enable;
2274     if (enable)
2275         d->sort();
2276 }
2277
2278 /*!
2279     \since 4.2
2280     \property QSortFilterProxyModel::sortRole
2281     \brief the item role that is used to query the source model's data when sorting items
2282
2283     The default value is Qt::DisplayRole.
2284
2285     \sa lessThan()
2286 */
2287 int QSortFilterProxyModel::sortRole() const
2288 {
2289     Q_D(const QSortFilterProxyModel);
2290     return d->sort_role;
2291 }
2292
2293 void QSortFilterProxyModel::setSortRole(int role)
2294 {
2295     Q_D(QSortFilterProxyModel);
2296     if (d->sort_role == role)
2297         return;
2298     d->sort_role = role;
2299     d->sort();
2300 }
2301
2302 /*!
2303     \since 4.2
2304     \property QSortFilterProxyModel::filterRole
2305     \brief the item role that is used to query the source model's data when filtering items
2306
2307     The default value is Qt::DisplayRole.
2308
2309     \sa filterAcceptsRow()
2310 */
2311 int QSortFilterProxyModel::filterRole() const
2312 {
2313     Q_D(const QSortFilterProxyModel);
2314     return d->filter_role;
2315 }
2316
2317 void QSortFilterProxyModel::setFilterRole(int role)
2318 {
2319     Q_D(QSortFilterProxyModel);
2320     if (d->filter_role == role)
2321         return;
2322     d->filter_role = role;
2323     d->filter_changed();
2324 }
2325
2326 /*!
2327     \obsolete
2328
2329     This function is obsolete. Use invalidate() instead.
2330 */
2331 void QSortFilterProxyModel::clear()
2332 {
2333     Q_D(QSortFilterProxyModel);
2334     emit layoutAboutToBeChanged();
2335     d->_q_clearMapping();
2336     emit layoutChanged();
2337 }
2338
2339 /*!
2340    \since 4.3
2341
2342     Invalidates the current sorting and filtering.
2343
2344     \sa invalidateFilter()
2345 */
2346 void QSortFilterProxyModel::invalidate()
2347 {
2348     Q_D(QSortFilterProxyModel);
2349     emit layoutAboutToBeChanged();
2350     d->_q_clearMapping();
2351     emit layoutChanged();
2352 }
2353
2354 /*!
2355    \obsolete
2356
2357     This function is obsolete. Use invalidateFilter() instead.
2358 */
2359 void QSortFilterProxyModel::filterChanged()
2360 {
2361     Q_D(QSortFilterProxyModel);
2362     d->filter_changed();
2363 }
2364
2365 /*!
2366    \since 4.3
2367
2368    Invalidates the current filtering.
2369
2370    This function should be called if you are implementing custom filtering
2371    (e.g. filterAcceptsRow()), and your filter parameters have changed.
2372
2373    \sa invalidate()
2374 */
2375 void QSortFilterProxyModel::invalidateFilter()
2376 {
2377     Q_D(QSortFilterProxyModel);
2378     d->filter_changed();
2379 }
2380
2381 /*!
2382     Returns true if the value of the item referred to by the given
2383     index \a left is less than the value of the item referred to by
2384     the given index \a right, otherwise returns false.
2385
2386     This function is used as the < operator when sorting, and handles
2387     the following QVariant types:
2388
2389     \list
2390     \o QVariant::Int
2391     \o QVariant::UInt
2392     \o QVariant::LongLong
2393     \o QVariant::ULongLong
2394     \o QVariant::Double
2395     \o QVariant::Char
2396     \o QVariant::Date
2397     \o QVariant::Time
2398     \o QVariant::DateTime
2399     \o QVariant::String
2400     \endlist
2401
2402     Any other type will be converted to a QString using
2403     QVariant::toString().
2404
2405     Comparison of \l{QString}s is case sensitive by default; this can
2406     be changed using the \l {QSortFilterProxyModel::sortCaseSensitivity}
2407     {sortCaseSensitivity} property.
2408
2409     By default, the Qt::DisplayRole associated with the
2410     \l{QModelIndex}es is used for comparisons. This can be changed by
2411     setting the \l {QSortFilterProxyModel::sortRole} {sortRole} property.
2412
2413     \note The indices passed in correspond to the source model.
2414
2415     \sa sortRole, sortCaseSensitivity, dynamicSortFilter
2416 */
2417 bool QSortFilterProxyModel::lessThan(const QModelIndex &left, const QModelIndex &right) const
2418 {
2419     Q_D(const QSortFilterProxyModel);
2420     QVariant l = (left.model() ? left.model()->data(left, d->sort_role) : QVariant());
2421     QVariant r = (right.model() ? right.model()->data(right, d->sort_role) : QVariant());
2422     switch (l.userType()) {
2423     case QVariant::Invalid:
2424         return (r.type() != QVariant::Invalid);
2425     case QVariant::Int:
2426         return l.toInt() < r.toInt();
2427     case QVariant::UInt:
2428         return l.toUInt() < r.toUInt();
2429     case QVariant::LongLong:
2430         return l.toLongLong() < r.toLongLong();
2431     case QVariant::ULongLong:
2432         return l.toULongLong() < r.toULongLong();
2433     case QMetaType::Float:
2434         return l.toFloat() < r.toFloat();
2435     case QVariant::Double:
2436         return l.toDouble() < r.toDouble();
2437     case QVariant::Char:
2438         return l.toChar() < r.toChar();
2439     case QVariant::Date:
2440         return l.toDate() < r.toDate();
2441     case QVariant::Time:
2442         return l.toTime() < r.toTime();
2443     case QVariant::DateTime:
2444         return l.toDateTime() < r.toDateTime();
2445     case QVariant::String:
2446     default:
2447         if (d->sort_localeaware)
2448             return l.toString().localeAwareCompare(r.toString()) < 0;
2449         else
2450             return l.toString().compare(r.toString(), d->sort_casesensitivity) < 0;
2451     }
2452     return false;
2453 }
2454
2455 /*!
2456     Returns true if the item in the row indicated by the given \a source_row
2457     and \a source_parent should be included in the model; otherwise returns
2458     false.
2459
2460     The default implementation returns true if the value held by the relevant item
2461     matches the filter string, wildcard string or regular expression.
2462
2463     \note By default, the Qt::DisplayRole is used to determine if the row
2464     should be accepted or not. This can be changed by setting the
2465     \l{QSortFilterProxyModel::filterRole}{filterRole} property.
2466
2467     \sa filterAcceptsColumn(), setFilterFixedString(), setFilterRegExp(), setFilterWildcard()
2468 */
2469 bool QSortFilterProxyModel::filterAcceptsRow(int source_row, const QModelIndex &source_parent) const
2470 {
2471     Q_D(const QSortFilterProxyModel);
2472     if (d->filter_regexp.isEmpty())
2473         return true;
2474     if (d->filter_column == -1) {
2475         int column_count = d->model->columnCount(source_parent);
2476         for (int column = 0; column < column_count; ++column) {
2477             QModelIndex source_index = d->model->index(source_row, column, source_parent);
2478             QString key = d->model->data(source_index, d->filter_role).toString();
2479             if (key.contains(d->filter_regexp))
2480                 return true;
2481         }
2482         return false;
2483     }
2484     QModelIndex source_index = d->model->index(source_row, d->filter_column, source_parent);
2485     if (!source_index.isValid()) // the column may not exist
2486         return true;
2487     QString key = d->model->data(source_index, d->filter_role).toString();
2488     return key.contains(d->filter_regexp);
2489 }
2490
2491 /*!
2492     Returns true if the item in the column indicated by the given \a source_column
2493     and \a source_parent should be included in the model; otherwise returns false.
2494
2495     The default implementation returns true if the value held by the relevant item
2496     matches the filter string, wildcard string or regular expression.
2497
2498     \note By default, the Qt::DisplayRole is used to determine if the row
2499     should be accepted or not. This can be changed by setting the \l
2500     filterRole property.
2501
2502     \sa filterAcceptsRow(), setFilterFixedString(), setFilterRegExp(), setFilterWildcard()
2503 */
2504 bool QSortFilterProxyModel::filterAcceptsColumn(int source_column, const QModelIndex &source_parent) const
2505 {
2506     Q_UNUSED(source_column);
2507     Q_UNUSED(source_parent);
2508     return true;
2509 }
2510
2511 /*!
2512    Returns the source model index corresponding to the given \a
2513    proxyIndex from the sorting filter model.
2514
2515    \sa mapFromSource()
2516 */
2517 QModelIndex QSortFilterProxyModel::mapToSource(const QModelIndex &proxyIndex) const
2518 {
2519     Q_D(const QSortFilterProxyModel);
2520     return d->proxy_to_source(proxyIndex);
2521 }
2522
2523 /*!
2524     Returns the model index in the QSortFilterProxyModel given the \a
2525     sourceIndex from the source model.
2526
2527     \sa mapToSource()
2528 */
2529 QModelIndex QSortFilterProxyModel::mapFromSource(const QModelIndex &sourceIndex) const
2530 {
2531     Q_D(const QSortFilterProxyModel);
2532     return d->source_to_proxy(sourceIndex);
2533 }
2534
2535 /*!
2536   \reimp
2537 */
2538 QItemSelection QSortFilterProxyModel::mapSelectionToSource(const QItemSelection &proxySelection) const
2539 {
2540     return QAbstractProxyModel::mapSelectionToSource(proxySelection);
2541 }
2542
2543 /*!
2544   \reimp
2545 */
2546 QItemSelection QSortFilterProxyModel::mapSelectionFromSource(const QItemSelection &sourceSelection) const
2547 {
2548     return QAbstractProxyModel::mapSelectionFromSource(sourceSelection);
2549 }
2550
2551 /*!
2552   \fn QObject *QSortFilterProxyModel::parent() const
2553   \internal
2554 */
2555
2556 QT_END_NAMESPACE
2557
2558 #include "moc_qsortfilterproxymodel.cpp"
2559
2560 #endif // QT_NO_SORTFILTERPROXYMODEL