I created following functions to loop over all indexes in a table or a tree and find the one that contains required string:
#include <QModelIndex>
#include <QAbstractItemModel>
#include <QAbstractItemView>
QModelIndex findIndexByString(const QAbstractItemModel* model, const QString& text, const QModelIndex& parent = QModelIndex());
QModelIndex findIndexByString(const QModelIndex& index, const QString& text) {
// First check this particular index
if(index.data().toString() == text)
return index;
// Check if it has children and loop
const QAbstractItemModel* model = index.model();
if(model==nullptr)
return QModelIndex();
if (!model->hasChildren(index))
return QModelIndex();
// STACK OVERFLOW HERE (model and index keep repeating)
return findIndexByString(model, text, index);
}
QModelIndex findIndexByString(const QAbstractItemModel* model, const QString& text, const QModelIndex& parent) {
int rows = model->rowCount(parent);
int cols = model->columnCount(parent);
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j) {
QModelIndex index_child = findIndexByString(model->index(i, j, parent), text);
if(index_child.isValid())
return index_child;
}
return QModelIndex();
}
QModelIndex findIndexByString(const QAbstractItemView* view, const QString& text) {
//const QModelIndex root = view->rootIndex();
const QAbstractItemModel* model = view->model();
return findIndexByString(model, text);
}
This code is self contained and doesn't have any dependencies outside Qt library.
I encountered stack overflow error when looping over some model in foreign code.
I am trying to create generic correct algorithm to do this. Is the algorithm above correct?
The code looks fine. It's a classic depth-first search. It runs out of stack because your model is not a tree, but a cyclic graph and/or it has infinite depth.
We can reformulate the search with an explicit stack and add tests that ensure a reasonable behavior in face of ill-formed model.
If your model has infinite depth or cycles by design, the code below will act appropriately and won't run out of stack.
// https://github.com/KubaO/stackoverflown/tree/master/questions/model-find-diagnostic-44416637
#include <QtGui>
First, we'll need a set of indexes, since QSet will only work with persistent indexes that we don't use:
class IndexSet : public QMap<QModelIndex, bool> {
public:
void insert(const QModelIndex & key) { QMap::insert(key, true); }
};
The state of the finder, that we'll keep on an explicit stack:
struct FindState {
QModelIndex index;
int rows;
int cols;
int i = 0;
int j = 0;
FindState() = default;
FindState(const QAbstractItemModel* model, const QModelIndex & index) :
index(index),
rows(model->rowCount(index)),
cols(model->columnCount(index)) {}
bool isInitial() const { return i == 0 && j == 0; }
bool equalTo(const QVariant & value) const {
return index.isValid() && index.data() == value;
}
bool operator==(const FindState & o) const {
return index == o.index;
}
};
QDebug operator<<(QDebug dbg, const FindState & s) {
return dbg << "{" << s.index << "," << s.i << "," << s.j << "}";
}
Then, a find utility that verifies that things are sane and that the model doesn't misbehave:
QModelIndex findIndexByValue(const QAbstractItemModel* model, const QVariant& needle,
const QModelIndex& parent = {}) {
int iterations = {};
int maxDepth = {};
const auto depthLimit = 100;
IndexSet indexes;
QStack<FindState> states;
states.push({model, parent});
for (; !states.isEmpty(); iterations++) {
auto valid = true;
auto & top = states.top();
if (top.isInitial()) {
if (states.size() > 1) {
if (!top.index.isValid()) {
qWarning() << "the index isn't valid, stack:" << states;
valid = false;
}
if (!model->hasIndex(top.index.row(), top.index.column(), top.index.parent())) {
qWarning() << "the index doesn't exist, stack:" << states;
valid = false;
}
}
if (indexes.contains(top.index)) {
qWarning() << "skipping already seen index" << top.index;
valid = false;
}
if (valid) {
indexes.insert(top.index);
if (top.equalTo(needle))
break;
}
}
if (valid && model->hasChildren(top.index) && top.i < top.rows && top.j < top.cols) {
FindState state(model, model->index(top.i, top.j, top.index));
top.i ++;
if (top.i == top.rows) {
top.i = 0;
top.j ++;
}
if (states.contains(state))
qWarning() << "skipping duplicate index" << state.index;
else if (states.size() == depthLimit)
qWarning() << "stack is full, skipping index" << state.index;
else {
states.push(state);
maxDepth = std::max(maxDepth, states.size());
}
} else
states.pop();
}
qDebug() << "max depth" << maxDepth << "iterations" << iterations;
return states.isEmpty() ? QModelIndex() : states.top().index;
}
QModelIndex findIndexByString(const QAbstractItemModel* model, const QString& needle, const QModelIndex& parent = {}) {
return findIndexByValue(model, QVariant::fromValue(needle), parent);
}
For comparison, we can include the original implementations from the question:
QModelIndex findIndexByString2(const QAbstractItemModel* model, const QString& text, const QModelIndex& parent = QModelIndex());
QModelIndex findIndexByString2(const QModelIndex& index, const QString& text) {
if (index.data().toString() == text)
return index;
auto model = index.model();
if (!model || !model->hasChildren(index))
return {};
return findIndexByString2(model, text, index);
}
QModelIndex findIndexByString2(const QAbstractItemModel* model, const QString& text, const QModelIndex& parent) {
int rows = model->rowCount(parent);
int cols = model->columnCount(parent);
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j) {
auto child = findIndexByString2(model->index(i, j, parent), text);
if (child.isValid())
return child;
}
return {};
}
Finally, we need a rudimentary test harness. A path into the model is represented by a vector of positions within an item. Each position has a string representation.
struct Pos {
int row, col;
QString toString() const { return QStringLiteral("(%1,%2)").arg(row).arg(col); }
};
Q_DECLARE_TYPEINFO(Pos, Q_PRIMITIVE_TYPE);
using Path = QVector<Pos>;
The builder adds items to the model to ensure that a given path is valid. Each item's value is a string representing its path as a concatenation of positions that make up the path (row,col)(row,col).... As the builder builds up the model, it also retains the paths of all the items it created.
struct Builder {
QStandardItemModel * model;
QStringList paths;
Path add(Path path, const Pos & pos) {
auto item = model->invisibleRootItem();
path.push_back(pos);
QString pathString;
for (auto p : path) {
pathString += p.toString();
auto child = item->child(p.row, p.col);
if (!child) {
item->setChild(p.row, p.col, child = new QStandardItem(pathString));
paths << pathString;
}
item = child;
}
return path;
}
explicit Builder(QStandardItemModel * model) : model(model) {}
};
Finally, we can create a model, and ensure that both methods of finding items provide the same results:
int main() {
QStandardItemModel model;
Builder b(&model);
Path path, ____;
path = b.add({}, {1, 0}); // *(1,0)
____ = b.add(path, {1, 1}); // (1,0)-(1,1)
____ = b.add(path, {0, 0}); // (1,0)-(0,0)
path = b.add({}, {1, 1}); // *(1,1)
path = b.add(path, {3, 3}); // *(1,1)-(3,3)
____ = b.add(path, {0, 0}); // (1,1)-(3,3)-(0,0)
path.pop_back(); // -(1,1)
path = b.add(path, {2, 2}); // *(1,1)-(2,2)
____ = b.add(path, {0, 1}); // (1,1)-(2,2)-(0,1)
path = b.add({}, {2, 1}); // *(2,1)
IndexSet indexes;
for (auto path : b.paths) {
auto index = findIndexByString(b.model, path);
auto index2 = findIndexByString2(b.model, path);
Q_ASSERT(index.isValid());
Q_ASSERT(!indexes.contains(index));
Q_ASSERT(index2 == index);
indexes.insert(index);
}
}
This concludes the example.