src/corelib/itemmodels/qsortfilterproxymodel.cpp

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