Hierarchical models in Qt

I continue the theme of creating models using Qt MV. Last time there was a critical article on how to do it. Go to the positive part.

To create flat models of lists and tables, you can use QAbstractListModel and QAbstractTableModel blanks. Bringing them to readiness is not a big deal, so there is no need to consider them in detail.

Creating hierarchical models is a more difficult task. About her and will be discussed in this article.
')
In general, Qt allows you to create not only tree models, but also models of more complex configurations and dimensions. For example, a table in which each element is grouped for a subtable. Despite this, in most cases, when people talk about hierarchical models, they mean trees. It is the process of creating trees that I want to highlight.

Figure: Table in the table

Another introductory note concerns the essence of the model, which I will create as an example. I wanted to choose something specific and universal, so I decided to create a model for the example that maps the file system. It does not suffer from completeness and completeness, so hardly anyone wants to use it seriously (especially since there is already a QFileSystemModel ), but for example it is quite suitable. In the next article, if there is one, around this model I am going to build several proxies.

Design

First of all, it is necessary to determine the internal data structure . Here I would highlight 2 main areas:

• Models with well-defined structure or small nesting.
  An example would be the property editor in Qt Designer. In this case, all the information about the position of a particular model element can be stored in the index itself ( QModelIndex ) using internalId . In the case of a property editor, you can save the property group identifier in internalId .
  Another example is a notebook model. Obviously, the entry “ Lol4t0 ” belongs to the Lo subgroup, which, in turn, belongs to the group L. And back - the Lo group includes those and only those records that begin with the prefix " Lo ". This is what I call a well-defined structure.
  
  
• Models without a well-defined structure. The file system model refers to just that. Knowing only the name of the Documents folder, generally speaking, it is impossible to determine which folder it is in and which folders it contains.

Additional data on the organization of data can be used in the design, so the creation of models of the first type usually does not cause problems. The article deals with models of the second type.

All kinds of data that you have to deal with when developing tree models are actually similar. Therefore, it is not difficult to isolate some general recommendations regarding the internal organization of the data:

• You must store node data
• There must be a one-to-one relationship between the QModelIndex and the element of the internal data structure.
• Each node must contain references to the parent node and child nodes.

In the case of the file system model, I will use QFileInfo to store information about each node. In addition, you will need to store information about the child nodes and the parent node. Additionally, you will need information about whether a search for child nodes was performed or not.

Business data ( QFileInfo ) had to wrap service information. In most cases, without this it is impossible to do. If the domain data already supports the hierarchy, you can use it, but I have never met the case where the source data would contain all the necessary information.

We get the following internal data structure:

 struct FilesystemModel::NodeInfo { QFileInfo fileInfo; //    QVector<NodeInfo> children; //    NodeInfo* parent; //     bool mapped; //     . }; 

When creating a tree, I will construct a list of nodes corresponding to the root objects of file systems, and I will load their children as necessary:

 typedef QVector<NodeInfo> NodeInfoList; NodeInfoList _nodes; //      

There will be several columns in the tree:

 enum Columns { RamificationColumn, // ,    ,  . //     QTreeView NameColumn = RamificationColumn, //     ModificationDateColumn, //      SizeColumn, //     ColumnCount //   }; 

Minimal implementation

Once you have decided on the structure of the data storage, you can begin to implement the model.
If you need to implement a hierarchical model, then nothing remains but to inherit from QAbstractItemModel . In order to implement the simplest model, you need to write an implementation of all five functions:

 virtual QModelIndex index(int row, int column, const QModelIndex &parent) const; virtual QModelIndex parent(const QModelIndex &child) const; virtual int rowCount(const QModelIndex &parent = QModelIndex()) const; virtual int columnCount(const QModelIndex &parent = QModelIndex()) const; virtual QVariant data(const QModelIndex &index, int role = Qt::DisplayRole) const; 

However, the implementation of the first two usually accounts for 80% of the problems associated with the creation of hierarchical models. The point is that they are called very often, so the use of algorithms in them is more complicated than O (1), generally speaking, it is not desirable.

I suggest storing a pointer to NodeInfo in the internalPointer index. In most cases, this is exactly what they do. In the implementation of index in no case can not return non-existent indexes. You do not need to rely on the fact that no one will request such an index. To check the existence of an index there is a very convenient function hasIndex .

 QModelIndex FilesystemModel::index(int row, int column, const QModelIndex &parent) const { if (!hasIndex(row, column, parent)) { return QModelIndex(); } if (!parent.isValid()) { //     return createIndex(row, column, const_cast<NodeInfo*>(&_nodes[row])); } NodeInfo* parentInfo = static_cast<NodeInfo*>(parent.internalPointer()); return createIndex(row, column, &parentInfo->children[row]); } 

With parent things are a little more complicated. Despite the fact that at a given index you can always find the NodeInfo parent element, to create an index of the parent element it is also necessary to know its position among the "brothers".

There are two options - either to store information about its position with each node, or to determine this position again each time. The trouble with the first is that when adding and removing nodes, all the underlying nodes will have to be updated. What I really did not want. Therefore, I chose the second option, despite its computational complexity. In a real model, I would adhere to this choice until I could prove that it was a bottleneck.

 QModelIndex FilesystemModel::parent(const QModelIndex &child) const { if (!child.isValid()) { return QModelIndex(); } NodeInfo* childInfo = static_cast<NodeInfo*>(child.internalPointer()); NodeInfo* parentInfo = childInfo->parent; if (parentInfo != 0) { // parent      return createIndex(findRow(parentInfo), RamificationColumn, parentInfo); } else { return QModelIndex(); } } int FilesystemModel::findRow(const NodeInfo *nodeInfo) const { const NodeInfoList& parentInfoChildren = nodeInfo->parent != 0 ? nodeInfo->parent->children: _nodes; NodeInfoList::const_iterator position = qFind(parentInfoChildren, *nodeInfo); return std::distance(parentInfoChildren.begin(), position); } 

The implementation of rowCount and columnCount trivial: in the first case, we can always determine the number of child nodes from NodeInfo::children::size , and the number of columns is fixed.

 int FilesystemModel::rowCount(const QModelIndex &parent) const { if (!parent.isValid()) { return _nodes.size(); } const NodeInfo* parentInfo = static_cast<const NodeInfo*>(parent.internalPointer()); return parentInfo->children.size(); } int FilesystemModel::columnCount(const QModelIndex &) const { return ColumnCount; } 

The implementation of data also not difficult, all the necessary information is obtained from QFileInfo . At a minimum, you need to implement support for Qt::DisplayRole roles to display text in view and Qt::EditRole , if editing is provided. Data received from the model with the role of Qt::EditRole will be loaded into the editor. Moreover, the data that the model returns when queried with Qt::DisplayRole and Qt::EditRole may differ. For example, we will display files without extensions, and edit - with the extension.

Now you can display the model using QTreeView and see the result.

However, what is it! Root elements cannot be expanded.
Indeed, the data for them has not yet been downloaded.

Dynamic data loading

To implement automatic loading of data as needed, Qt implements the following API:

 bool canFetchMore(const QModelIndex &parent) const; void fetchMore(const QModelIndex &parent); 

The first function should return true , when data for a given parent element can be loaded, and the second one can actually load data.
NodeInfo::mapped comes in handy NodeInfo::mapped . Data can be loaded when mapped == false .

 bool FilesystemModel::canFetchMore(const QModelIndex &parent) const { if (!parent.isValid()) { return false; } const NodeInfo* parentInfo = static_cast<const NodeInfo*>(parent.internalPointer()); return !parentInfo->mapped; } 

For loading we will use the functions provided by QDir . In this case, do not forget to use beginInsertRows and endInsertRows when changing the number of rows. Unfortunately, QTreeView loads only when trying to expand a node, and does not try to load new data when scrolling through the list. Therefore, nothing remains as to download the entire list of child nodes in its entirety. You can correct this behavior, perhaps, by creating your own display component.

 void FilesystemModel::fetchMore(const QModelIndex &parent) { NodeInfo* parentInfo = static_cast<NodeInfo*>(parent.internalPointer()); const QFileInfo& fileInfo = parentInfo->fileInfo; QDir dir = QDir(fileInfo.absoluteFilePath()); QFileInfoList children = dir.entryInfoList(QStringList(), QDir::AllEntries | QDir::NoDotAndDotDot, QDir::Name); beginInsertRows(parent, 0, children.size() - 1); parentInfo->children.reserve(children.size()); for (const QFileInfo& entry: children) { NodeInfo nodeInfo(entry, parentInfo); nodeInfo.mapped = !entry.isDir(); parentInfo->children.push_back(std::move(nodeInfo)); } parentInfo->mapped = true; endInsertRows(); } 

We do the download, run the program, but the result is not. Root nodes are still impossible to deploy. The thing is, QTreeView uses the hasChildren function to check if a node has children, and assumes that only those nodes that have children can be expanded. hasChildren , by default, returns true only when the number of rows and the number of columns for the parent node is greater than 0.

In this case, this behavior does not fit. Override the hasChildren function so that it returns true for the specified node, when it definitely has or can have (when mapped ==false ) child nodes.

You can accurately determine if the directory is empty, but it is quite an expensive operation, whether to use it is up to you.

 bool FilesystemModel::hasChildren(const QModelIndex &parent) const { if (parent.isValid()) { const NodeInfo* parentInfo = static_cast<const NodeInfo*>(parent.internalPointer()); Q_ASSERT(parentInfo != 0); if (!parentInfo->mapped) { return true;//QDir(parentInfo->fileInfo.absoluteFilePath()).count() > 0; --   ,     } } return QAbstractItemModel::hasChildren(parent); } 

Now the model works, you can view the folders.

I think this can be finished, for completeness, one could add the function of renaming files and folders, creating directories and tracking file system changes. But this is clearly beyond the allowed article on Habr. I posted a slightly more advanced example on GitHub .