On the mistreatment of the noble root

As I work through tree models I am struck by the ubiquity of the "invalid" model index (QModelIndex()). Not only is it used as the index of the root, it is also expected you return QModelIndex() as the parent of the root (documentation)

It seems there should be two things here, and this convention of using QModelIndex() for what seem to be different things is confusing. It seems the root should be a special valid index (one that doesn't correspond to data displayed in the tree), and we should have another value for truly invalid indexes (e.g., that correspond to things that do not exist, or are out of bounds of the model, things like that).

The root index seems special, real, and functional (i.e., the root index is the parent of all top-level items in the model, and is the starting point for the traversal of the entire tree structure). Hence, calling its index "invalid" seems almost misleading. Further, not only does the parent of the root not have this special status, it does not even exist at a conceptual level in the model. Even so, we use the exact same index as we do for the root.

The noble root of our trees seems to be getting short shrift. :(

Think of it this way... In the tree model, every index has a parent, except the top level indexes you create. i.e. their parent is "invalid".

Quote:

---

Originally Posted by neuronet

Hence, calling its index "invalid" seems almost misleading.

---

Not really. The index doesn't point to any valid data thus it is invalid :) I have never thought of it as "confusing". In what situations do you get confused by such approach?

Quote:

---

Originally Posted by wysota

Not really. The index doesn't point to any valid data thus it is invalid :) I have never thought of it as "confusing". In what situations do you get confused by such approach?

---

I guess it makes sense to say that the root item has no valid data in the traditional sense, in that it has no internalPointer() to a data item (though simpletreemodel example stores header data in the rootItem, so again we have a case where it does something useful). But it is an actual parent (indeed, it is unique in that it is everyone's parent), and serves a useful purpose in the overall model. It also seems to be the first node the view starts with when it traverses the tree checking for dimensions (the first calls to rowCount are made with the root index as parameter).

So in those senses it is not only valid, but useful and functional and not the same as other invalid indexes like the (nonexistent) parent of root. It would be much more intuitive to have a separate index and set of methods for the root versus (what we now call) the other invalid indexes. I suppose I could subclass QAbstractItemModel and build in this functionality myself? So we'd have isRoot() and other methods to treat the root with the respect she deserves.

Put it this way, the root is unique among other invalid indexes, and it would make things easier for the beginner (ahem!) if Qt treated it as such. As it stands now, it seems we have to decide on a case-by-case basis whether to think of an invalid index as the root, or something else (e.g., parent of root).

Quote:

---

Originally Posted by neuronet

Ithough simpletreemodel example stores header data in the rootItem

---

That's internal representation. QModelIndex is part of API.

Quote:

---

But it is an actual parent (indeed, it is unique in that it is everyone's parent),

---

In my opinion top-level items do not have a parent thus their parent is an invalid index (== no parent).

Quote:

---

the first calls to rowCount are made with the root index as parameter

---

Semantics of this call: "tell me how many top-level items (items without a parent) there are" -- there is no ambiguity in that.

Quote:

---

So in those senses it is not only valid

---

No, I don't agree. An index by definition points to data. A "root index" does not point to data.

Quote:

---

It would be much more intuitive to have a separate index and set of methods for the root

---

That would bloat the API and require one to implement twice as many methods when implementing a model.

Quote:

---

I suppose I could subclass QAbstractItemModel and build in this functionality myself?

---

Sure but you would also have to subclass QAbstractItemView (and implement your own subclasses of that too) and QAbstractItemDelegate and in practice you would implement your own model-view architecture. You could as well start from scratch and implement something totally different.

Quote:

---

Put it this way, the root is unique among other invalid indexes

---

IMO there are no "kinds" of invalid indexes. A valid index is one that points to data in the model, an invalid index is one that does not point to data in the model. There is no third kind.

OK so I think we have the crux: on one hand, there is the root item. It is real, and is a real parent. It doesn't store data that is displayed in the tree, but is everyone's parent. For instance, in building the data structure, we would do something like:

Code:

---

rootItem = TreeItem([], parent = None)
child0 = TreeItem([data], parent = rootItem)

---

That is, you build an actual root item. And that root item is set as the parent of every top-level item in the tree.

Then, at the level of indexes, the root is assigned a special value because we need it to be of type QModelIndex, but it doesn't (as a rule) store data that is displayed in the tree view. So we give it the empty index value (QModelIndex()). This index's internal pointer points to nothing, and its row/column coordinates are invalid (-1, -1) (indeed, this is likely the origin of the term 'isValid' for the method).

But ultimately I am just making a semantic point, and realize I need to conform to the standards of Qt as it is written. For reasons you point out, it would be a pain in the rump to give my rootItem a special index, perhaps a more advanced project to take on later? :)

But it was confusing to this noob that the precious root, at the level of the index, is called 'invalid'. Because at the item level, it is valid, and at a conceptual level, it serves a purpose....it roots the tree! Following canonical image taken from http://qt-project.org/doc/qt-4.8/mod...gramming.html:

Attachment 10863

Quote:

---

Originally Posted by neuronet

OK so I think we have the crux: on one hand, there is the root item. It is real, and is a real parent.

---

It doesn't exist and it is not a parent.

In programming terminology, however, we usually think of a tree as starting at a single/origin node.
If that is not the case, i.e. there are multiple top level nodes, each potentially having a subtree, it can be benefitial to think of them as a first level of chilren under some conceptual root.

For example, a file system tree on Unix systems starts with a single root node, but on Windows there are several (the drives).

Quote:

---

Originally Posted by neuronet

For instance, in building the data structure, we would do something like:

Code:

---

rootItem = TreeItem([], parent = None)
child0 = TreeItem([data], parent = rootItem)

---

That is, you build an actual root item. And that root item is set as the parent of every top-level item in the tree.

---

That would be an implementation detail of your model.

Cheers,
_

ON the root item, anda_skoa wrote:

Quote:

---

Originally Posted by anda_skoa

It doesn't exist and it is not a parent.

---

Well, there is literally a rootItem defined and it is explicitly set to be the parent of the top-level TreeItems in the data structure. This is indeed an 'implementation detail' of the model, but that doesn't make it unreal, no? It corresponds to the root index. By that I just mean that when this rootItem is the parent item, then QModelIndex() is returned in the parent() method in TreeModel. That is, within parent(), we have:

Code:

---

if parentItem == self.rootItem:
            return QtCore.QModelIndex()

---

But I think I am starting to understand. Perhaps I shouldn't read so much into that one example. We could have just as easily have built it differently, and not had such a root item. In which case, none of the concerns/questions I have would arise. That is, we could have just started in with multiple top-level nodes:

Code:

---

item0 = TreeItem(data0, parent = None) #instead of parent = rootItem
.
.
.
itemN = treeItem(dataN, parent = None)

---

And then, within the model, for these top-level items parent() would return QModelIndex().

So my argument in the thread, as a general claim, is false, and the way things work in simpletreemodel and editabletreemodel examples that come with Qt don't represent how it has to be. Indeed, they may even be slightly confusing, given their use of an actual TreeItem named rootItem.

Am I starting to get closer to understanding?

Quote:

---

Originally Posted by neuronet

Well, there is literally a rootItem defined and it is explicitly set to be the parent of the top-level TreeItems in the data structure. This is indeed an 'implementation detail' of the model, but that doesn't make it unreal, no?

---

Sure.
I was talking about the general case, not a specific implementation.
Any specific model implementation could have an internal tree node associated with the conceptual root index, but that would still be specific to that exact model implementation.

Quote:

---

Originally Posted by neuronet

So my argument in the thread, as a general claim, is false, and the way things work in simpletreemodel and editabletreemodel examples that come with Qt don't represent how it has to be. Indeed, they may even be slightly confusing, given their use of an actual TreeItem named rootItem.

Am I starting to get closer to understanding?

---

Exactly.

Cheers,
_

OK I think I'm getting closer to understanding: thanks.

Note just in case anyone comes here wondering what the heck I'm going on about, below I paste the main discussion of "root items" I found in the docs accompanying simpletreemodel and editabletreemodel. In particular, note the claim therein "The root item corresponds to the null model index, QModelIndex()" which is what had me going down the wrong path:

Root item (the TreeItem in the data structure)

Quote:

---

The root item in the tree structure has no parent item and it is never referenced outside the model. Although the root item (with no parent item) is automatically assigned a row number of 0, this information is never used by the model.

Note that, since the root item in the model will not have a parent, TreeItem.parent() will return 0 [in Python, None] in that case. We need to ensure that the model handles this case correctly when we implement the TreeModel.parent() function.[T]op-level items...can be obtained from the root item by calling its child() function, and each of these items return the root node from their parent() functions

---

Root item's "index" (handling of rootItem in TreeModel)

Quote:

---

We place an item at the root of the tree of items. This root item corresponds to the null model index, QModelIndex(), that is used to represent the parent of a top-level item when handling model indexes. Although the root item does not have a visible representation in any of the standard views, we use its internal list of QVariant objects to store a list of strings that will be passed to views for use as horizontal header titles.

It is up to the TreeModel constructor to create a root item for the model. This item only contains vertical header data for convenience. We also use it to reference the internal data structure that contains the model data, and it is used to represent an imaginary parent of top-level items in the model.

The TreeModel destructor ensures that the root item and all of its descendants are deleted when the model is destroyed. It only has to delete the root item; all child items will be recursively deleted by the TreeItem destructor.

Items without parents, including the root item, are handled by returning a null model index. We only need to ensure that we never return a model index corresponding to the root item. To be consistent with the way that the index() function is implemented, we return an invalid model index for the parent of any top-level items in the model [including rootItem].

---

The seeming contradiction between the claims 1) "We...need to ensure that we never return a model index corresponding to the root item" and 2) "The root item corresponds to the null model index, QModelIndex()" was just one of the things that had (has) me confused.

---

Added after 17 minutes:

I just noticed that QTreeView has a function setRootIndex(). It is defined, in qtreeview.cpp with:

Code:

---

void QTreeView::setRootIndex(const QModelIndex &index)
{
Q_D(QTreeView);
d->header->setRootIndex(index);
QAbstractItemView::setRootIndex(index);
}

---

And in qabstractitemview.cpp we have:

Code:

---

/*!
Sets the root item to the item at the given index.
*/
void QAbstractItemView::setRootIndex(const QModelIndex &index)
{
Q_D(QAbstractItemView);
if (index.isValid() && index.model() != d->model) {
qWarning("QAbstractItemView::setRootIndex failed : index must be from the currently set model");
return;
}
d->root = index;
d->doDelayedItemsLayout();
}

---

This strongly suggests it is mistaken to say that the root index doesn't exist, full stop. Perhaps the thing to say is that it defaults to QModelIndex()? It actually seems there is some functionality built in that I was looking for, albeit in the view not part of QAbstractItemModel.

Note QTreeView also seems to inherit the rootIndex method:

Code:

---

/*!
Returns the model index of the model's root item. The root item is
the parent item to the view's toplevel items. The root can be invalid.
\sa setRootIndex()
*/
QModelIndex QAbstractItemView::rootIndex() const
{
return QModelIndex(d_func()->root);
}

---

Indeed, when I run view.rootIndex() on the view in the simpletreemodel example, I get the "invalid" index back.

A root index of a view is something different than "root index" we were talking about earlier. The former is an index children (subtree) of which are visible in the view. The view doesn't have to display the whole model, it displays items below the root index (without quotes). A "root index" of a model (with quotes) "corresponds" to a common "pseudo-parent" of top-level items in the model.

Quote:

---

Originally Posted by wysota

A root index of a view is something different than "root index" we were talking about earlier. The former is an index children (subtree) of which are visible in the view. The view doesn't have to display the whole model, it displays items below the root index (without quotes). A "root index" of a model (with quotes) "corresponds" to a common "pseudo-parent" of top-level items in the model.

---

So just to put it a different way: setting a root item other than QModelIndex() in the view would basically be a way to say to the view "Make the corresponding item, and everything above it, invisible?" Yet, from the model's point of view, this doesn't matter, and the stuff people wrote above to help me understand still holds true of the model. That is, changing the root index in the view doesn't affect the model (and its indexes) at all, only the view of that model. Indeed, we could have multiple views with different root indexes set, and this should not change the model.

That makes sense.

Thanks a lot for all this help I am learning so much from you guys!

Quote:

---

Originally Posted by neuronet

So just to put it a different way: setting a root item other than QModelIndex() in the view would basically be a way to say to the view "Make the corresponding item, and everything above it, invisible?"

---

Invisible is not the right word.

Quote:

---

That is, changing the root index in the view doesn't affect the model (and its indexes) at all, only the view of that model. Indeed, we could have multiple views with different root indexes set, and this should not change the model.

---

Correct. Consider a file system model where you traverse the model in the view (e.g. changing the current directory) by changing the root index of the view. Try implementing it using QFileSystemModel, QTableView and doubleClicked() signal.

I think you could say that in graph theory terminology, QAbstractItemModel in its most general form represents a disconnected, acyclic graph. It is disconnected in that the model allows multiple top-level parents; it is acyclic because no item can have more than one parent. (A loop can only exist if an item can have more than one parent). You can argue about whether the graph is "directed" or not, since you can traverse the model both upwards and downwards from an index in the middle somewhere.

I think it is the "disconnected" part of this which is hanging you up. anda_skoa's analogy of the Windows file system is a good example to illustrate this. Each logical drive represents the top of a tree; in the old File Manager, there was no way to pop up to "above" one logical drive and down into another logical drive - "C:\ " was as far up as you could go. Likewise any other logical drive. So, the top of each logical drive has an invalid parent. When File Manager was supplanted by Windows Explorer, "My Computer" (and now just "Computer") became a logical root to tie all the drives together, but you still can't navigate up "C" and back down "D" by going through "Computer" - it's still an invalid root even though it is given a visible representation in Explorer.

Note that QAbstractItemModel itself has no concept of a root index. This concept is introduced only for QAbstractItemView, where it is an optional convenience that can be used for displaying tree-shaped models.