Optimizing filterAcceptsRow() to filter a tree

[vfernandez]

I have a custom QSortFilterProxyModel that's being used with a custom model and a QTreeView. Through a QLineEdit and the corresponding signal/slot connection, it allows the user to search for something in the tree of the model and also to hide/show comments which are also nodes in the tree. This is the code:


ParsedTreeFilterProxyModel::ParsedTreeFilterProxyM odel(QObject *parent)
: QSortFilterProxyModel(parent)
{
m_commentsVisible = true;
}


bool ParsedTreeFilterProxyModel::commentsVisible()
{
return m_commentsVisible;
}


void ParsedTreeFilterProxyModel::setCommentsVisible(boo l visible)
{
m_commentsVisible = visible;
filterChanged();
}


bool ParsedTreeFilterProxyModel::filterAcceptsRow(int sourceRow, const QModelIndex &sourceParent) const
{
QString name = sourceModel()->data( sourceModel()->index(sourceRow, 0, sourceParent) ).toString();
QString value = sourceModel()->data( sourceModel()->index(sourceRow, 1, sourceParent) ).toString();
QString type = sourceModel()->data( sourceModel()->index(sourceRow, 0, sourceParent), Qt::UserRole ).toString();
bool isComment = (type == "ConfigNode");
return ( (!isComment || m_commentsVisible) && (name.contains(filterRegExp()) || value.contains(filterRegExp())) );
}

Nothing special but as you may guess, when I search for something it only displays the nodes from the top level. When a node is inside some subtree, the parent tree nodes aren't displayed (as the documentation states). Now I want to make it work as it should: display a tree node if there's some child somewhere in its subtree that matches the filter.

The question is: when filterAcceptsRow() is processing one of those parent tree nodes, do I have to search for nodes that match the filter through the whole subtree (which is obviously very inefficient and time-consuming) or is there a better, more efficient, way to do it? I could think of moving through the tree and when a node matches the filter marking all the parent nodes as "visible" or something like that but AFAIK it's not possible with filterAcceptsRow(). Is it?

P.S.: I'm using Qt 4.2.

[wysota]

I think you have to scan all the children... What you can do is implement a kind of cache - with each item associate the last searched expression and the return value for that expression, then there won't be any big overhead on the search as each item would be actually searched once and then the cached value will be returned. Pseudocode follows...


bool itemMatchesExpression(const QModelIndex &ind, const QRegExp &exp){
if(exp==cache(index).expression) return cache(index).value);
cache(index).expression = exp;
bool v = false;
foreach(QModelIndex i, ind.children()){
v = itemMatchesExpression(i, exp);
if(v) break;
}
cache(index).value = v;
return cache(index).value;
}

bool Model::filterAcceptsRow(int sourceRow, const QModelIndex &sourceParent) const{
return itemMatchesExpression(index(0, sourceRow, sourceParent), expression);
}