how to implement a QAbstractItemModel for an already existing tree-like data structure without copy?

Question

After reading the docs and examples of QAbstractItemModel and QModelIndex, I am still confused on how to properly implement the model for a QTreeView.

Since I want to provide a model for an existing hierarchical data structure, I'm avoiding using QTreeWidget or QStandardItemModel and the related issues with data duplication and synchronization. However, I failed to implement a working item model (too many issues, it is not useful to post my code).

After reading this answer it seems clear that QModelIndex does not contain hierarchical information, but simply relies on the model to tell the parent of a given index. Consequently it does not seem possible to provide an abstract tree model for an existing data structure without defining at least another helper class for storing such relation. But still, I cannot implement properly the model.

Suppose the data structure is this simple one:

struct Property {
    QString name;
    QString value;
};
struct Node {
    QString name;
    QVector<Property> properties;
};
struct Track {
    int length;
    QString channel;
};
struct Model {
    QVector<Node> nodes;
    QVector<Track> tracks;
};

where Model is the toplevel one, and it resembles a tree. The tree displayed in the QTreeView could look like this:

Model
  ├─Nodes
  │  ├─Node "node1"
  │  │  └─Properties
  │  │     ├─Property property1 = value1
  │  │     └─Property property2 = value2
  │  └─Node "node2"
  │     └─Properties
  │        └─Property property1 = someValue
  └─Tracks
      ├─Track 1, ...
      ├─Track 2, ...
      └─Track 3, ...

How the QAbstractItemModel subclass should be implemented to access the existing data without copy?

Answer 1

You are incorrect, you can totally expose any tree structure as QAbstractItemModel without any additional structuring information. You do however have to bend the rules and abuse things a little. You can in fact have a perfectly usable model with an implementation of parent() that returns a default constructed invalid index, while it is an abstract method and it has to be implemented, it doesn't really need to do actually do anything meaningul.

As you already mentioned - the index does give you an opaque pointer to store a data reference. And since tree models have a fixed column count of 1, this leaves the column in the index free to use as some typeid or index. Now you have a way of knowing what each of those opaque pointers actually points to, so you can select the proper code path to retrieve row count and data. Those are the ones that you really do need to implement. Most likely index() too if you want to use some stock model view, but if you explicitly request children indices in a parent delegate, you can even get away with a dud implementation for index() as well.

Now, if your tree nodes do not keep references to their parents, obviously you will not be able to go down the tree directly. What you can do tho is, whatever your current index is, do not have it just free floating, but keep a stack of all the parent indices up from the root node. And now you can go down, by simply keeping breadcrumbs as you went up. You may not even need an explicit stack, in most cases you will be able to get the relevant information to construct the parent index from the parent delegate.

Answer 2

Here's my solution to the problem.

First of all, my initial guess that QModelIndex is incapable of storing the parent-child relationship is correct. In fact the method QModelIndex::parent simply calls QAbstractItemModel::parent, and the task of implementing the parent method is left to the model class. When the underlying model is a proper tree, pointer to tree nodes can be stored in the QModelIndex class, but in my case we are dealing with a "virtual" tree and this relationship is not available. Thus we are forced to introduce some kind of extra storage to be able to tell where we are in the tree. If QModelIndex natively supported having a pointer to the parent index, this problem would have been solved much more easily. But since QModelIndex is a value class, we cannot have a pointer to parent, but rather we have to store all the parent indices inside the QModelIndex class, and maybe the Qt developers had some good way to not do so. So I stored a QVector<QModelIndex> in the internal-pointer field of QModelIndex. There are some things to take care of, like avoiding allocating more than necessary of such indices, and also to remember freeing the memory when those are no more needed (we can't use QObject hierarchy here). There may be additional problems to take care of when the model is read-write, but in this case I'm dealing with a read-only model.

My implementation follows. Methods rowCount and data define this specific virtual tree. The other methods can be abstracted away in a class that can be re-used.

class MyModel : public QAbstractItemModel
{
    Q_OBJECT

private:
    struct IndexData
    {
        QVector<QModelIndex> parents;
    };

public:
    explicit MyModel(QObject *parent = nullptr);
    ~MyModel();

    QVariant data(const QModelIndex &index, int role) const override;
    QModelIndex index(int row, int column, const QModelIndex &parent = QModelIndex()) const override;
    QModelIndex parent(const QModelIndex &index) const override;
protected:
    IndexData * indexData(const QModelIndex &index) const;
    QList<int> indexPath(const QModelIndex &index) const;
    QString indexString(const QModelIndex &index) const;
    QString indexString(int row, int column, const QModelIndex &parent) const;
public:
    int indexDepth(const QModelIndex &index) const;
    int rowCount(const QModelIndex &parent = QModelIndex()) const override;
    int columnCount(const QModelIndex &parent = QModelIndex()) const override;
    Qt::ItemFlags flags(const QModelIndex &index) const override;

private:
    QMap<QString, IndexData*> indexData_;
    Model model;
};

implementation:

MyModel::MyModel(QObject *parent)
    : QAbstractItemModel(parent)
{
    model.nodes.resize(2);
    model.nodes[0].name = "node1";
    model.nodes[0].properties.resize(2);
    model.nodes[0].properties[0].name = "property1";
    model.nodes[0].properties[0].value = "value1";
    model.nodes[0].properties[1].name = "property2";
    model.nodes[0].properties[1].value = "value2";
    model.nodes[1].name = "node2";
    model.nodes[1].properties.resize(1);
    model.nodes[1].properties[0].name = "property1";
    model.nodes[1].properties[0].value = "someValue";
    model.tracks.resize(3);
    model.tracks[0].length = 2;
    model.tracks[0].channel = "A";
    model.tracks[1].length = 4;
    model.tracks[1].channel = "B";
    model.tracks[2].length = 3;
    model.tracks[2].channel = "C";
}

MyModel::~MyModel()
{
    for(auto v : indexData_) delete v;
}

QVariant MyModel::data(const QModelIndex &index, int role) const
{
    if(!index.isValid() || role != Qt::DisplayRole) return {};

    int d = indexDepth(index);
    auto path = indexPath(index);

    if(d == 1) return "Model";
    if(d == 2 && path[0] == 0 && path[1] == 0) return "Nodes";
    if(d == 2 && path[0] == 0 && path[1] == 1) return "Tracks";
    if(d == 3 && path[0] == 0 && path[1] == 0) return QString("Node \"%1\"").arg(model.nodes[path[2]].name);
    if(d == 4 && path[0] == 0 && path[1] == 0) return "Properties";
    if(d == 5 && path[0] == 0 && path[1] == 0 && path[3] == 0) return QString("Property %1 = %2").arg(model.nodes[path[2]].properties[path[4]].name, model.nodes[path[2]].properties[path[4]].value);
    if(d == 3 && path[0] == 0 && path[1] == 1) return QString("Track %1...").arg(index.row() + 1);
    return {};
}

QModelIndex MyModel::index(int row, int column, const QModelIndex &parent) const
{
    QString dataKey = indexString(row, column, parent);
    auto it = indexData_.find(dataKey);
    IndexData *data;
    if(it == indexData_.end())
    {
        data = new IndexData;
        const_cast<MyModel*>(this)->indexData_.insert(dataKey, data);
        if(parent.isValid())
        {
            data->parents.append(parent);
            data->parents.append(indexData(parent)->parents);
        }
    }
    else
    {
        data = it.value();
    }
    return createIndex(row, column, data);
}

QModelIndex MyModel::parent(const QModelIndex &index) const
{
    if(!index.isValid()) return {};
    auto data = indexData(index);
    if(data->parents.empty()) return {};
    return data->parents.at(0);
}

MyModel::IndexData * MyModel::indexData(const QModelIndex &index) const
{
    if(!index.internalPointer()) return nullptr;
    return reinterpret_cast<IndexData*>(index.internalPointer());
}

QList<int> MyModel::indexPath(const QModelIndex &index) const
{
    QList<int> path;
    auto data = indexData(index);
    for(int i = data->parents.size() - 1; i >= 0; i--)
        path.push_back(data->parents[i].row());
    path.push_back(index.row());
    return path;
}

QString MyModel::indexString(const QModelIndex &index) const
{
    return indexString(index.row(), index.column(), index.parent());
}

QString MyModel::indexString(int row, int column, const QModelIndex &parent) const
{
    QString pre = parent.isValid() ? indexString(parent) + "." : "";
    return pre + QString("[%1,%2]").arg(row).arg(column);
}

int MyModel::indexDepth(const QModelIndex &index) const
{
    if(!index.isValid()) return 0;
    return 1 + indexDepth(index.parent());
}

int MyModel::rowCount(const QModelIndex &parent) const
{
    if(!parent.isValid()) return 1; // root item

    int d = indexDepth(parent);
    auto path = indexPath(parent);

    //if(d == 0) return 1; // root item
    if(d == 1) return 2;
    if(d == 2 && path[0] == 0 && path[1] == 0) return model.nodes.size();
    if(d == 2 && path[0] == 0 && path[1] == 1) return model.tracks.size();
    if(d == 3 && path[0] == 0 && path[1] == 0) return 1;
    if(d == 4 && path[0] == 0 && path[1] == 0 && path[3] == 0) return model.nodes[path[2]].properties.size();
    return 0;
}

int MyModel::columnCount(const QModelIndex &parent) const
{
    return 1;
}

Qt::ItemFlags MyModel::flags(const QModelIndex &index) const
{
    if(index.isValid()) return Qt::ItemIsEnabled | Qt::ItemIsSelectable;
    return {};
}