Designing tree-like models

We found that developers are often confused about implementing tree-like models using Qt classes. Now we can show some tricks and considerations about the way of designing them.

First for some refreshment, let’s remind what you have for addressing the elements in the model. This is QModelIndex, which have pointer to model that created the index object, row and column and plus a some pointer or id (qint64) which can be used for addressing.

1.

Let’s start from simplest case – no parents-children, so just a some two-dimension table. It is clear that you just use the row and column and no worry about pointer or id in index objects, so it can be just a zero – unused. Implementation of index()/parent() is extremely simple, parent is always QModelIndex() (empty onject), index is just created as createIndex(row,col,0). But it is important that rowCount(parent) returns 0 for valid parents, otherwise you are making infinitely deep model:

QModelIndex index(int r,int c, const QModelIndex &) const 
    { return createIndex(r,c,0); }
QModelIndex parent(const QModelIndex &) const 
    { return QModelIndex(); }
int rowCount(const QModelIndex & p) 
    { return p.isValid() ? 0 : m_rowsNum; }

I guess everything is simple and self-explanatory. If the model represent some array of elements, then no real need to use internalId/internalPointer as you already have row and column for sufficient addressing.

Another benefit that you have no need to instantiate elements (no pointer), but you can addressing them with model index and create those object later – like only when user is really scrolled to them and data() is accessed, just lazy initialization, well, you can create object even later than the data() is accessed.

2.

Let’s now move to little complication. We have two-level model – every root element can have a children, but these children do not have any nested, so just two levels.
We have more information to build sufficient addressing. That is very common type of constructed models.

Let’s first consider how calls index() and parent() are used. Two simple cases:
first – when you click on “+” of folded root element to expand nested children, the tree-view requests rowCount() of the root element, and then to get info to draw them it needs to build address from row,column and parent – these 3 items are enough for addressing;
second case – when you have some index, but do not know where it is in hierarchy, you can just call parent(), to identify the place of the element. Tree-view may use the second case when for example you click onto some element – view need to get the info about the parent by having just index object, or you for example you call view->expand(index); – view need to find which item and in which branch should be expanded.

You may see a conclusion from usages above that your model should implement methods index() and parent() to have complexity of O(const) because otherwise tree-views will be slowing down fast as more elements appears in model and when more deep level.

Returning to our example of two-level model, you can reveal that we can just use internalId as indication of row of parent item. Example:

QModelIndex index(int r,int c, const QModelIndex & p) const 
    { return createIndex(r,c, p.isValid() ? p.row() : -1); }
QModelIndex parent(const QModelIndex & i) const 
    { return i.internalId() >=0 ? createIndex(i.internalId(),0) 
                                : QModelIndex(); }
int rowCount(const QModelIndex & p) 
    { return !p.isValid() ? m_rowsOf.size() :
                 !p.parent().isValid() ? m_rowsOf[p.row()] : 0; }

Again we are not using pointers to elements themselves, but you can do this – then take in account that every element preferably should have pointer to parent and pointers to children – only then you can implement index()/parent() with O(const). Otherwise if you spend computation time to get parent or children pointers you will see lagging in views and related.

3.

When you have tree-like models that have defined number of levels, you may need to use pointers, or still use previous approach, but modified in the way that you split qint64 internalId to shorter size numbers. Example: 3-level model, then you split qint64 to two qint32 numbers which identify parent and grand-parent.

This approach can very efficient in such example. Imagine that you have C-structres which are just mapped from file into memory.

struct Root {
    char[100] name;
    char[100] value;
    struct Sub {
        char[100] code;
        struct File {
            char[100] name;
            int mode;
            int attr;
        } 
        files[100];
    } subs[3000];
}
roots[100000];

To use pointers for addressing you have to create at least 100000*3000*100 objects which have pointers to parent and children elements just for referencing the elements of array – some bridge between model and to the array = memory consumption, cpu spent to initializations, etc.

Instead you can use approach of using internalId which is split into two numbers, and then no need to create any additional object, addressing is just automatic, O(const), so yes, even with Qt you can just map bytes from file into memory – such arrays of structures and model is just ready to be shown in view without cpu spent on preparations.

Of course when more then three levels but defined number, you will have less bits for every number, so you may want to switch to pointers at some case.

4.

When you have tree-like models that have undefined number of levels, for example tree of folders/files, you probably have no choice than use only pointers.