Avoid redundant calls to QSortFilterProxyModel::filterAcceptsRow() if the filter has become strictly narrower

Question

Is there any way invalidate the filter in a QSortFilterProxyModel, but to indicate that the filter has been narrowed down so filterAcceptsRow() should be called only on the currently visible rows?

Currently Qt doesn't do that. When I call QSortFilterProxyModel::invalidateFilter(), and my filter is changed from "abcd" to "abcde", an entirely new mapping is created, and filterAcceptsRow() is called on all source rows, even though it's obvious that source rows that were hidden so far will remain hidden.

This is the code from Qt's sources in QSortFilterProxyModelPrivate::create_mapping() which calls my overridden filterAcceptsRow(), and it creates an entirely new Mapping and iterates over all the source rows:

Mapping *m = new Mapping;

int source_rows = model->rowCount(source_parent);
m->source_rows.reserve(source_rows);
for (int i = 0; i < source_rows; ++i) {
    if (q->filterAcceptsRow(i, source_parent))
        m->source_rows.append(i);
}

What I want is to iterate only the visible rows in mapping and call filterAcceptsRow() only on them. If a row is already hidden filterAcceptsRow() should not be called on it, because we already know that it would return false for it (the filter has become more stringent, it hasn't been loosened).

Since I have overriden filterAcceptsRow(), Qt can't know the nature of the filter, but when I call QSortFilterProxyModel::invalidateFilter(), I have the information about whether the filter has become strictly narrower, so I could pass that information to Qt if it has a way of accepting it.

On the other hand, if I've changed the filter from abcd to abce, then the filter should be called on all source rows, since it has become strictly narrower.

Answer 1

I wrote a QIdentityProxyModel subclass that stores a list of chained QSortFilterProxyModel. It provides an interface similar to QSortFilterProxyModel and accepts a narrowedDown boolean parameter that indicates if the filter is being narrowed down. So that:

• When the filter is being narrowed down, a new QSortFilterProxyModel is appended to the chain, and the QIdentityProxyModel switches to proxy the new filter at the end of the chain.
• Otherwise, It deletes all the filters in the chain, constructs a new chain with one filter that corresponds to the current filtering criteria. After that, the QIdentityProxyModel switches to proxy the new filter in the chain.

Here is a program that compares the class to using a normal QSortFilterProxyModel subclass:

#include <QtWidgets>

class FilterProxyModel : public QSortFilterProxyModel{
public:
    explicit FilterProxyModel(QObject* parent= nullptr):QSortFilterProxyModel(parent){}
    ~FilterProxyModel(){}

    //you can override filterAcceptsRow here if you want
};

//the class stores a list of chained FilterProxyModel and proxies the filter model

class NarrowableFilterProxyModel : public QIdentityProxyModel{
    Q_OBJECT
    //filtering properties of QSortFilterProxyModel
    Q_PROPERTY(QRegExp filterRegExp READ filterRegExp WRITE setFilterRegExp)
    Q_PROPERTY(int filterKeyColumn READ filterKeyColumn WRITE setFilterKeyColumn)
    Q_PROPERTY(Qt::CaseSensitivity filterCaseSensitivity READ filterCaseSensitivity WRITE setFilterCaseSensitivity)
    Q_PROPERTY(int filterRole READ filterRole WRITE setFilterRole)
public:
    explicit NarrowableFilterProxyModel(QObject* parent= nullptr):QIdentityProxyModel(parent), m_filterKeyColumn(0),
        m_filterCaseSensitivity(Qt::CaseSensitive), m_filterRole(Qt::DisplayRole), m_source(nullptr){
    }

    void setSourceModel(QAbstractItemModel* sourceModel){
        m_source= sourceModel;
        QIdentityProxyModel::setSourceModel(sourceModel);
        for(FilterProxyModel* proxyNode : m_filterProxyChain) delete proxyNode;
        m_filterProxyChain.clear();
        applyCurrentFilter();
    }

    QRegExp filterRegExp()const{return m_filterRegExp;}
    int filterKeyColumn()const{return m_filterKeyColumn;}
    Qt::CaseSensitivity filterCaseSensitivity()const{return m_filterCaseSensitivity;}
    int filterRole()const{return m_filterRole;}

    void setFilterKeyColumn(int filterKeyColumn, bool narrowedDown= false){
        m_filterKeyColumn= filterKeyColumn;
        applyCurrentFilter(narrowedDown);
    }
    void setFilterCaseSensitivity(Qt::CaseSensitivity filterCaseSensitivity, bool narrowedDown= false){
        m_filterCaseSensitivity= filterCaseSensitivity;
        applyCurrentFilter(narrowedDown);
    }
    void setFilterRole(int filterRole, bool narrowedDown= false){
        m_filterRole= filterRole;
        applyCurrentFilter(narrowedDown);
    }
    void setFilterRegExp(const QRegExp& filterRegExp, bool narrowedDown= false){
        m_filterRegExp= filterRegExp;
        applyCurrentFilter(narrowedDown);
    }
    void setFilterRegExp(const QString& filterRegExp, bool narrowedDown= false){
        m_filterRegExp.setPatternSyntax(QRegExp::RegExp);
        m_filterRegExp.setPattern(filterRegExp);
        applyCurrentFilter(narrowedDown);
    }
    void setFilterWildcard(const QString &pattern, bool narrowedDown= false){
        m_filterRegExp.setPatternSyntax(QRegExp::Wildcard);
        m_filterRegExp.setPattern(pattern);
        applyCurrentFilter(narrowedDown);
    }
    void setFilterFixedString(const QString &pattern, bool narrowedDown= false){
        m_filterRegExp.setPatternSyntax(QRegExp::FixedString);
        m_filterRegExp.setPattern(pattern);
        applyCurrentFilter(narrowedDown);
    }

private:
    void applyCurrentFilter(bool narrowDown= false){
        if(!m_source) return;
        if(narrowDown){ //if the filter is being narrowed down
            //instantiate a new filter proxy model and add it to the end of the chain
            QAbstractItemModel* proxyNodeSource= m_filterProxyChain.empty()?
                        m_source : m_filterProxyChain.last();
            FilterProxyModel* proxyNode= newProxyNode();
            proxyNode->setSourceModel(proxyNodeSource);
            QIdentityProxyModel::setSourceModel(proxyNode);
            m_filterProxyChain.append(proxyNode);
        } else { //otherwise
            //delete all filters from the current chain
            //and construct a new chain with the new filter in it
            FilterProxyModel* proxyNode= newProxyNode();
            proxyNode->setSourceModel(m_source);
            QIdentityProxyModel::setSourceModel(proxyNode);
            for(FilterProxyModel* node : m_filterProxyChain) delete node;
            m_filterProxyChain.clear();
            m_filterProxyChain.append(proxyNode);
        }
    }
    FilterProxyModel* newProxyNode(){
        //return a new child FilterModel with the current properties
        FilterProxyModel* proxyNode= new FilterProxyModel(this);
        proxyNode->setFilterRegExp(filterRegExp());
        proxyNode->setFilterKeyColumn(filterKeyColumn());
        proxyNode->setFilterCaseSensitivity(filterCaseSensitivity());
        proxyNode->setFilterRole(filterRole());
        return proxyNode;
    }
    //filtering parameters for QSortFilterProxyModel
    QRegExp m_filterRegExp;
    int m_filterKeyColumn;
    Qt::CaseSensitivity m_filterCaseSensitivity;
    int m_filterRole;

    QAbstractItemModel* m_source;
    QList<FilterProxyModel*> m_filterProxyChain;
};

//Demo program that uses the class

//used to fill the table with dummy data
std::string nextString(std::string str){
    int length= str.length();
    for(int i=length-1; i>=0; i--){
        if(str[i] < 'z'){
            str[i]++; return str;
        } else str[i]= 'a';
    }
    return std::string();
}

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    //set up GUI
    QWidget w;
    QGridLayout layout(&w);
    QLineEdit lineEditFilter;
    lineEditFilter.setPlaceholderText("filter");
    QLabel titleTable1("NarrowableFilterProxyModel:");
    QTableView tableView1;
    QLabel labelTable1;
    QLabel titleTable2("FilterProxyModel:");
    QTableView tableView2;
    QLabel labelTable2;
    layout.addWidget(&lineEditFilter,0,0,1,2);
    layout.addWidget(&titleTable1,1,0);
    layout.addWidget(&tableView1,2,0);
    layout.addWidget(&labelTable1,3,0);
    layout.addWidget(&titleTable2,1,1);
    layout.addWidget(&tableView2,2,1);
    layout.addWidget(&labelTable2,3,1);

    //set up models
    QStandardItemModel sourceModel;
    NarrowableFilterProxyModel filterModel1;;
    tableView1.setModel(&filterModel1);

    FilterProxyModel filterModel2;
    tableView2.setModel(&filterModel2);

    QObject::connect(&lineEditFilter, &QLineEdit::textChanged, [&](QString newFilter){
        QTime stopWatch;
        newFilter.prepend("^"); //match from the beginning of the name
        bool narrowedDown= newFilter.startsWith(filterModel1.filterRegExp().pattern());
        stopWatch.start();
        filterModel1.setFilterRegExp(newFilter, narrowedDown);
        labelTable1.setText(QString("took: %1 msecs").arg(stopWatch.elapsed()));
        stopWatch.start();
        filterModel2.setFilterRegExp(newFilter);
        labelTable2.setText(QString("took: %1 msecs").arg(stopWatch.elapsed()));
    });

    //fill model with strings from "aaa" to "zzz" (17576 rows)
    std::string str("aaa");
    while(!str.empty()){
        QList<QStandardItem*> row;
        row.append(new QStandardItem(QString::fromStdString(str)));
        sourceModel.appendRow(row);
        str= nextString(str);
    }
    filterModel1.setSourceModel(&sourceModel);
    filterModel2.setSourceModel(&sourceModel);

    w.show();
    return a.exec();
}

#include "main.moc"

Notes:

• The class provides some kind of optimization only when the filter is being narrowed down, since the newly constructed filter at the end of the chain does not need to search through all source model's rows.
• The class depends on the user to tell if the filter is being narrowed down. That is when the user passes true for the argument narrowedDown, the filter is assumed to be a special case of the current filter (even if it is not really so). Otherwise, it behaves exactly the same as the normal QSortFilterProxyModel and possibly with some additional overhead (resulted from cleaning up the old filter chain).
• The class can be further optimized when the filter is not being narrowed down, so that it looks in the current filter chain for a filter that is similar to the current filter and switch to it immediately (instead of deleting the whole chain and starting a new one). This can be particularly useful when the user is deleting some characters at the end filter QLineEdit (ie. when the filter changes back from "abcd" to "abc", since you should already have a filter in the chain with "abc"). But currently, this is not implemented as I want the answer to be as minimal and clear as possible.

Answer 2

Because the filters can also be generic (for custom filter sorting you are encouraged to override filterAcceptsRow()) the ProxyModel cannot know whether it will become narrower or not.

if you would need to provide it to the proxy as a parameter it would break encapsulation because the filter-logic should only be contained inside the filter model.

You cannot override invalidateFilter though because it is not declared virtual. What you can do is having a structure in your derived proxy where you store the values you lastly filtered in there and only check them in , when the filter just got narrower. Both of this you can do in filterAcceptsRow().

invalidateFilter() still will call rowCount() though. So this function needs to have a low call time in your model for this to be effective.

Here is some pseudocode how filterAcceptsRow() could look like:

index // some index to refer to the element;

if(!selectionNarrowed()) //need search all elements
{
    m_filteredElements.clear(); //remove all previously filtered
    if(filterApplies(getFromSource(index))) //get element from sourceModel
    {
        m_filteredElements.add(index); //if applies add to "cache"
        return true;
    }
    return false;
}

//selection has only narrowed down    
if(!filterApplies(m_filteredElements(index)) //is in "cache"?
{
    m_filteredElements.remove(index); //if not anymore: remove from cache
    return false;
}
return true;

There are some things to be aware of though. Be careful if you want to store the QModelIndex..You can have a look at QPersistentModelIndex.

You also need to be aware about changes in the underlying model and connect the appropriate slots and invalidate your "cache" in those cases.

While an alternative could be "filter stacking". I see this may get confusing when you really need to invalidate all filters.