/****************************************************************************

**

** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtGui module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include "qsortfilterproxymodel.h"

#ifndef QT_NO_SORTFILTERPROXYMODEL

#include "qitemselectionmodel.h"

#include <qsize.h>

#include <qdebug.h>

#include <qdatetime.h>

#include <qpair.h>

#include <qstringlist.h>

#include <private/qabstractitemmodel_p.h>

#include <private/qabstractproxymodel_p.h>

QT_BEGIN_NAMESPACE

typedef QList<QPair<QModelIndex, QPersistentModelIndex> > QModelIndexPairList;

static inline QSet<int> qVectorToSet(const QVector<int> &vector)

{

    QSet<int> set;

    set.reserve(vector.size());

    for(int i=0; i < vector.size(); ++i)

        set << vector.at(i);

    return set;

}

class QSortFilterProxyModelLessThan

{

public:

    inline QSortFilterProxyModelLessThan(int column, const QModelIndex &parent,

                                       const QAbstractItemModel *source,

                                       const QSortFilterProxyModel *proxy)

        : sort_column(column), source_parent(parent), source_model(source), proxy_model(proxy) {}

    inline bool operator()(int r1, int r2) const

    {

        QModelIndex i1 = source_model->index(r1, sort_column, source_parent);

        QModelIndex i2 = source_model->index(r2, sort_column, source_parent);

        return proxy_model->lessThan(i1, i2);

    }

private:

    int sort_column;

    QModelIndex source_parent;

    const QAbstractItemModel *source_model;

    const QSortFilterProxyModel *proxy_model;

};

class QSortFilterProxyModelGreaterThan

{

public:

    inline QSortFilterProxyModelGreaterThan(int column, const QModelIndex &parent,

                                          const QAbstractItemModel *source,

                                          const QSortFilterProxyModel *proxy)

        : sort_column(column), source_parent(parent),

          source_model(source), proxy_model(proxy) {}

    inline bool operator()(int r1, int r2) const

    {

        QModelIndex i1 = source_model->index(r1, sort_column, source_parent);

        QModelIndex i2 = source_model->index(r2, sort_column, source_parent);

        return proxy_model->lessThan(i2, i1);

    }

private:

    int sort_column;

    QModelIndex source_parent;

    const QAbstractItemModel *source_model;

    const QSortFilterProxyModel *proxy_model;

};

class QSortFilterProxyModelPrivate : public QAbstractProxyModelPrivate

{

    Q_DECLARE_PUBLIC(QSortFilterProxyModel)

public:

    struct Mapping {

        QVector<int> source_rows;

        QVector<int> source_columns;

        QVector<int> proxy_rows;

        QVector<int> proxy_columns;

        QVector<QModelIndex> mapped_children;

        QMap<QModelIndex, Mapping *>::const_iterator map_iter;

    };

    mutable QMap<QModelIndex, Mapping*> source_index_mapping;

    int source_sort_column;

    int proxy_sort_column;

    Qt::SortOrder sort_order;

    Qt::CaseSensitivity sort_casesensitivity;

    int sort_role;

    bool sort_localeaware;

    int filter_column;

    QRegExp filter_regexp;

    int filter_role;

    bool dynamic_sortfilter;

    QModelIndexPairList saved_persistent_indexes;

    QMap<QModelIndex, Mapping *>::const_iterator create_mapping(

        const QModelIndex &source_parent) const;

    QModelIndex proxy_to_source(const QModelIndex &proxyIndex) const;

    QModelIndex source_to_proxy(const QModelIndex &sourceIndex) const;

    bool can_create_mapping(const QModelIndex &source_parent) const;

    void remove_from_mapping(const QModelIndex &source_parent);

    inline QMap<QModelIndex, Mapping *>::const_iterator index_to_iterator(

        const QModelIndex &proxy_index) const

    {

        Q_ASSERT(proxy_index.isValid());

        Q_ASSERT(proxy_index.model() == q_func());

        const void *p = proxy_index.internalPointer();

        Q_ASSERT(p);

        QMap<QModelIndex, Mapping *>::const_iterator it =

            static_cast<const Mapping*>(p)->map_iter;

        Q_ASSERT(it != source_index_mapping.constEnd());

        Q_ASSERT(it.value());

        return it;

    }

    inline QModelIndex create_index(int row, int column,

                                    QMap<QModelIndex, Mapping*>::const_iterator it) const

    {

        return q_func()->createIndex(row, column, *it);

    }

    void _q_sourceDataChanged(const QModelIndex &source_top_left,

                           const QModelIndex &source_bottom_right);

    void _q_sourceHeaderDataChanged(Qt::Orientation orientation, int start, int end);

    void _q_sourceAboutToBeReset();

    void _q_sourceReset();

    void _q_sourceLayoutAboutToBeChanged();

    void _q_sourceLayoutChanged();

    void _q_sourceRowsAboutToBeInserted(const QModelIndex &source_parent,

                                        int start, int end);

    void _q_sourceRowsInserted(const QModelIndex &source_parent,

                               int start, int end);

    void _q_sourceRowsAboutToBeRemoved(const QModelIndex &source_parent,

                                       int start, int end);

    void _q_sourceRowsRemoved(const QModelIndex &source_parent,

                              int start, int end);

    void _q_sourceColumnsAboutToBeInserted(const QModelIndex &source_parent,

                                           int start, int end);

    void _q_sourceColumnsInserted(const QModelIndex &source_parent,

                                  int start, int end);

    void _q_sourceColumnsAboutToBeRemoved(const QModelIndex &source_parent,

                                          int start, int end);

    void _q_sourceColumnsRemoved(const QModelIndex &source_parent,

                                 int start, int end);

    void clear_mapping();

    void sort();

    bool update_source_sort_column();

    void sort_source_rows(QVector<int> &source_rows,

                          const QModelIndex &source_parent) const;

    QVector<QPair<int, QVector<int > > > proxy_intervals_for_source_items_to_add(

        const QVector<int> &proxy_to_source, const QVector<int> &source_items,

        const QModelIndex &source_parent, Qt::Orientation orient) const;

    QVector<QPair<int, int > > proxy_intervals_for_source_items(

        const QVector<int> &source_to_proxy, const QVector<int> &source_items) const;

    void insert_source_items(

        QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,

        const QVector<int> &source_items, const QModelIndex &source_parent,

        Qt::Orientation orient, bool emit_signal = true);

    void remove_source_items(

        QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,

        const QVector<int> &source_items, const QModelIndex &source_parent,

        Qt::Orientation orient, bool emit_signal = true);

    void remove_proxy_interval(

        QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,

        int proxy_start, int proxy_end, const QModelIndex &proxy_parent,

        Qt::Orientation orient, bool emit_signal = true);

    void build_source_to_proxy_mapping(

        const QVector<int> &proxy_to_source, QVector<int> &source_to_proxy) const;

    void source_items_inserted(const QModelIndex &source_parent,

                               int start, int end, Qt::Orientation orient);

    void source_items_about_to_be_removed(const QModelIndex &source_parent,

                                          int start, int end, Qt::Orientation orient);

    void source_items_removed(const QModelIndex &source_parent,

                              int start, int end, Qt::Orientation orient);

    void proxy_item_range(

        const QVector<int> &source_to_proxy, const QVector<int> &source_items,

        int &proxy_low, int &proxy_high) const;

    QModelIndexPairList store_persistent_indexes();

    void update_persistent_indexes(const QModelIndexPairList &source_indexes);

    void filter_changed(const QModelIndex &source_parent = QModelIndex());

    QSet<int> handle_filter_changed(

        QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,

        const QModelIndex &source_parent, Qt::Orientation orient);

    void updateChildrenMapping(const QModelIndex &source_parent, Mapping *parent_mapping,

                               Qt::Orientation orient, int start, int end, int delta_item_count, bool remove);

    virtual void _q_sourceModelDestroyed();

};

typedef QMap<QModelIndex, QSortFilterProxyModelPrivate::Mapping *> IndexMap;

void QSortFilterProxyModelPrivate::_q_sourceModelDestroyed()

{

    QAbstractProxyModelPrivate::_q_sourceModelDestroyed();

    clear_mapping();

}

void QSortFilterProxyModelPrivate::remove_from_mapping(const QModelIndex &source_parent)

{

    if (Mapping *m = source_index_mapping.take(source_parent)) {

        for (int i = 0; i < m->mapped_children.size(); ++i)

            remove_from_mapping(m->mapped_children.at(i));

        delete m;

    }

}

void QSortFilterProxyModelPrivate::clear_mapping()

{

    // store the persistent indexes

    QModelIndexPairList source_indexes = store_persistent_indexes();

    qDeleteAll(source_index_mapping);

    source_index_mapping.clear();

    // update the persistent indexes

    update_persistent_indexes(source_indexes);

}

IndexMap::const_iterator QSortFilterProxyModelPrivate::create_mapping(

    const QModelIndex &source_parent) const

{

    Q_Q(const QSortFilterProxyModel);

    IndexMap::const_iterator it = source_index_mapping.constFind(source_parent);

    if (it != source_index_mapping.constEnd()) // was mapped already

        return it;

    Mapping *m = new Mapping;

    int source_rows = model->rowCount(source_parent);

    for (int i = 0; i < source_rows; ++i) {

        if (q->filterAcceptsRow(i, source_parent))

            m->source_rows.append(i);

    }

    int source_cols = model->columnCount(source_parent);

    for (int i = 0; i < source_cols; ++i) {

        if (q->filterAcceptsColumn(i, source_parent))

            m->source_columns.append(i);

    }

    sort_source_rows(m->source_rows, source_parent);

    m->proxy_rows.resize(source_rows);

    build_source_to_proxy_mapping(m->source_rows, m->proxy_rows);

    m->proxy_columns.resize(source_cols);

    build_source_to_proxy_mapping(m->source_columns, m->proxy_columns);

    it = IndexMap::const_iterator(source_index_mapping.insert(source_parent, m));

    m->map_iter = it;

    if (source_parent.isValid()) {

        QModelIndex source_grand_parent = source_parent.parent();

        IndexMap::const_iterator it2 = create_mapping(source_grand_parent);

        Q_ASSERT(it2 != source_index_mapping.constEnd());

        it2.value()->mapped_children.append(source_parent);

    }

    Q_ASSERT(it != source_index_mapping.constEnd());

    Q_ASSERT(it.value());

    return it;

}

QModelIndex QSortFilterProxyModelPrivate::proxy_to_source(const QModelIndex &proxy_index) const

{

    if (!proxy_index.isValid())

        return QModelIndex(); // for now; we may want to be able to set a root index later

    if (proxy_index.model() != q_func()) {

        qWarning() << "QSortFilterProxyModel: index from wrong model passed to mapToSource";

        return QModelIndex();

    }

    IndexMap::const_iterator it = index_to_iterator(proxy_index);

    Mapping *m = it.value();

    if ((proxy_index.row() >= m->source_rows.size()) || (proxy_index.column() >= m->source_columns.size()))

        return QModelIndex();

    int source_row = m->source_rows.at(proxy_index.row());

    int source_col = m->source_columns.at(proxy_index.column());

    return model->index(source_row, source_col, it.key());

}

QModelIndex QSortFilterProxyModelPrivate::source_to_proxy(const QModelIndex &source_index) const

{

    if (!source_index.isValid())

        return QModelIndex(); // for now; we may want to be able to set a root index later

    if (source_index.model() != model) {

        qWarning() << "QSortFilterProxyModel: index from wrong model passed to mapFromSource";

        return QModelIndex();

    }

    QModelIndex source_parent = source_index.parent();

    IndexMap::const_iterator it = create_mapping(source_parent);

    Mapping *m = it.value();

    if ((source_index.row() >= m->proxy_rows.size()) || (source_index.column() >= m->proxy_columns.size()))

        return QModelIndex();

    int proxy_row = m->proxy_rows.at(source_index.row());

    int proxy_column = m->proxy_columns.at(source_index.column());

    if (proxy_row == -1 || proxy_column == -1)

        return QModelIndex();

    return create_index(proxy_row, proxy_column, it);

}

bool QSortFilterProxyModelPrivate::can_create_mapping(const QModelIndex &source_parent) const

{

    if (source_parent.isValid()) {

        QModelIndex source_grand_parent = source_parent.parent();

        IndexMap::const_iterator it = source_index_mapping.constFind(source_grand_parent);

        if (it == source_index_mapping.constEnd()) {

            // Don't care, since we don't have mapping for the grand parent

            return false;

        }

        Mapping *gm = it.value();

        if (gm->proxy_rows.at(source_parent.row()) == -1 ||

            gm->proxy_columns.at(source_parent.column()) == -1) {

            // Don't care, since parent is filtered

            return false;

        }

    }

    return true;

}

/*!

  \internal

  Sorts the existing mappings.

*/

void QSortFilterProxyModelPrivate::sort()

{

    Q_Q(QSortFilterProxyModel);

    emit q->layoutAboutToBeChanged();

    QModelIndexPairList source_indexes = store_persistent_indexes();

    IndexMap::const_iterator it = source_index_mapping.constBegin();

    for (; it != source_index_mapping.constEnd(); ++it) {

        QModelIndex source_parent = it.key();

        Mapping *m = it.value();

        sort_source_rows(m->source_rows, source_parent);

        build_source_to_proxy_mapping(m->source_rows, m->proxy_rows);

    }

    update_persistent_indexes(source_indexes);

    emit q->layoutChanged();

}

/*!

  \internal

    update the source_sort_column according to the proxy_sort_column

    return true if the column was changed

*/

bool QSortFilterProxyModelPrivate::update_source_sort_column()

{

    Q_Q(QSortFilterProxyModel);

    QModelIndex proxy_index = q->index(0, proxy_sort_column, QModelIndex());

    int old_source_sort_colum = source_sort_column;

    source_sort_column = q->mapToSource(proxy_index).column();

    return old_source_sort_colum != source_sort_column;

}

/*!

  \internal

  Sorts the given \a source_rows according to current sort column and order.

*/

void QSortFilterProxyModelPrivate::sort_source_rows(

    QVector<int> &source_rows, const QModelIndex &source_parent) const

{

    Q_Q(const QSortFilterProxyModel);

    if (source_sort_column >= 0) {

        if (sort_order == Qt::AscendingOrder) {

            QSortFilterProxyModelLessThan lt(source_sort_column, source_parent, model, q);

            qStableSort(source_rows.begin(), source_rows.end(), lt);

        } else {

            QSortFilterProxyModelGreaterThan gt(source_sort_column, source_parent, model, q);

            qStableSort(source_rows.begin(), source_rows.end(), gt);

        }

    } else { // restore the source model order

        qStableSort(source_rows.begin(), source_rows.end());

    }

}

/*!

  \internal

  Given source-to-proxy mapping \a source_to_proxy and the set of

  source items \a source_items (which are part of that mapping),

  determines the corresponding proxy item intervals that should

  be removed from the proxy model.

  The result is a vector of pairs, where each pair represents a

  (start, end) tuple, sorted in ascending order.

*/

QVector<QPair<int, int > > QSortFilterProxyModelPrivate::proxy_intervals_for_source_items(

    const QVector<int> &source_to_proxy, const QVector<int> &source_items) const

{

    QVector<QPair<int, int> > proxy_intervals;

    if (source_items.isEmpty())

        return proxy_intervals;

    int source_items_index = 0;

    while (source_items_index < source_items.size()) {

        int first_proxy_item = source_to_proxy.at(source_items.at(source_items_index));

        Q_ASSERT(first_proxy_item != -1);

        int last_proxy_item = first_proxy_item;

        ++source_items_index;

        // Find end of interval

        while ((source_items_index < source_items.size())

               && (source_to_proxy.at(source_items.at(source_items_index)) == last_proxy_item + 1)) {

            ++last_proxy_item;

            ++source_items_index;

        }

        // Add interval to result

        proxy_intervals.append(QPair<int, int>(first_proxy_item, last_proxy_item));

    }

    qStableSort(proxy_intervals.begin(), proxy_intervals.end());

    return proxy_intervals;

}

/*!

  \internal

  Given source-to-proxy mapping \a src_to_proxy and proxy-to-source mapping

  \a proxy_to_source, removes \a source_items from this proxy model.

  The corresponding proxy items are removed in intervals, so that the proper

  rows/columnsRemoved(start, end) signals will be generated.

*/

void QSortFilterProxyModelPrivate::remove_source_items(

    QVector<int> &source_to_proxy, QVector<int> &proxy_to_source,

    const QVector<int> &source_items, const QModelIndex &source_parent,

    Qt::Orientation orient, bool emit_signal)

{

    Q_Q(QSortFilterProxyModel);

    QModelIndex proxy_parent = q->mapFromSource(source_parent);

    if (!proxy_parent.isValid() && source_parent.isValid())

        return; // nothing to do (already removed)

    QVector<QPair<int, int> > proxy_intervals;

    proxy_intervals = proxy_intervals_for_source_items(source_to_proxy, source_items);

    for (int i = proxy_intervals.size()-1; i >= 0; --i) {

        QPair<int, int> interval = proxy_intervals.at(i);

        int proxy_start = interval.first;

        int proxy_end = interval.second;

        remove_proxy_interval(source_to_proxy, proxy_to_source, proxy_start, proxy_end,

                              proxy_parent, orient, emit_signal);

    }

}

/*!

  \internal

  Given source-to-proxy mapping \a source_to_proxy and proxy-to-source mapping

  \a proxy_to_source, removes items from \a proxy_start to \a proxy_end

  (inclusive) from this proxy model.

*/

void QSortFilterProxyModelPrivate::remove_proxy_interval(

    QVector<int> &source_to_proxy, QVector<int> &proxy_to_source, int proxy_start, int proxy_end,

    const QModelIndex &proxy_parent, Qt::Orientation orient, bool emit_signal)

{

    Q_Q(QSortFilterProxyModel);

    if (emit_signal) {

        if (orient == Qt::Vertical)

            q->beginRemoveRows(proxy_parent, proxy_start, proxy_end);

        else

            q->beginRemoveColumns(proxy_parent, proxy_start, proxy_end);

    }

    // Remove items from proxy-to-source mapping

    proxy_to_source.remove(proxy_start, proxy_end - proxy_start + 1);

    build_source_to_proxy_mapping(proxy_to_source, source_to_proxy);

    if (emit_signal) {