Results 1 to 14 of 14

Thread: On the mistreatment of the noble root

  1. #1
    Join Date
    Jun 2014
    Posts
    98
    Thanks
    43
    Thanked 4 Times in 4 Posts
    Platforms
    Windows

    Thumbs up 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.

  2. #2
    Join Date
    Dec 2009
    Location
    New Orleans, Louisiana
    Posts
    791
    Thanks
    13
    Thanked 153 Times in 150 Posts
    Qt products
    Qt5
    Platforms
    MacOS X

    Default Re: On the mistreatment of the noble root

    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".

  3. The following user says thank you to jefftee for this useful post:

    neuronet (4th January 2015)

  4. #3
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: On the mistreatment of the noble root

    Quote Originally Posted by neuronet View Post
    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?
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  5. The following user says thank you to wysota for this useful post:

    neuronet (4th January 2015)

  6. #4
    Join Date
    Jun 2014
    Posts
    98
    Thanks
    43
    Thanked 4 Times in 4 Posts
    Platforms
    Windows

    Default Re: On the mistreatment of the noble root

    Quote Originally Posted by wysota View Post
    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).
    Last edited by neuronet; 4th January 2015 at 14:36.

  7. #5
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: On the mistreatment of the noble root

    Quote Originally Posted by neuronet View Post
    Ithough simpletreemodel example stores header data in the rootItem
    That's internal representation. QModelIndex is part of API.

    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).

    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.

    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.

    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.

    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.

    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  8. The following user says thank you to wysota for this useful post:

    neuronet (4th January 2015)

  9. #6
    Join Date
    Jun 2014
    Posts
    98
    Thanks
    43
    Thanked 4 Times in 4 Posts
    Platforms
    Windows

    Default Re: On the mistreatment of the noble root

    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:
    Qt Code:
    1. rootItem = TreeItem([], parent = None)
    2. child0 = TreeItem([data], parent = rootItem)
    To copy to clipboard, switch view to plain text mode 
    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:

    modelview-models.png
    Last edited by neuronet; 4th January 2015 at 15:37.

  10. #7
    Join Date
    Jan 2006
    Location
    Graz, Austria
    Posts
    8,416
    Thanks
    37
    Thanked 1,544 Times in 1,494 Posts
    Qt products
    Qt3 Qt4 Qt5
    Platforms
    Unix/X11 Windows

    Default Re: On the mistreatment of the noble root

    Quote Originally Posted by neuronet View Post
    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 View Post
    For instance, in building the data structure, we would do something like:
    Qt Code:
    1. rootItem = TreeItem([], parent = None)
    2. child0 = TreeItem([data], parent = rootItem)
    To copy to clipboard, switch view to plain text mode 
    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,
    _

  11. #8
    Join Date
    Jun 2014
    Posts
    98
    Thanks
    43
    Thanked 4 Times in 4 Posts
    Platforms
    Windows

    Default Re: On the mistreatment of the noble root

    ON the root item, anda_skoa wrote:
    Quote Originally Posted by anda_skoa View Post
    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:
    Qt Code:
    1. if parentItem == self.rootItem:
    2. return QtCore.QModelIndex()
    To copy to clipboard, switch view to plain text mode 
    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:
    Qt Code:
    1. item0 = TreeItem(data0, parent = None) #instead of parent = rootItem
    2. .
    3. .
    4. .
    5. itemN = treeItem(dataN, parent = None)
    To copy to clipboard, switch view to plain text mode 

    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?
    Last edited by neuronet; 4th January 2015 at 16:41.

  12. #9
    Join Date
    Jan 2006
    Location
    Graz, Austria
    Posts
    8,416
    Thanks
    37
    Thanked 1,544 Times in 1,494 Posts
    Qt products
    Qt3 Qt4 Qt5
    Platforms
    Unix/X11 Windows

    Default Re: On the mistreatment of the noble root

    Quote Originally Posted by neuronet View Post
    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 View Post
    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,
    _

  13. The following user says thank you to anda_skoa for this useful post:

    neuronet (4th January 2015)

  14. #10
    Join Date
    Jun 2014
    Posts
    98
    Thanks
    43
    Thanked 4 Times in 4 Posts
    Platforms
    Windows

    Exclamation Re: On the mistreatment of the noble root

    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)
    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)
    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:
    Qt Code:
    1. void QTreeView::setRootIndex(const QModelIndex &index)
    2. {
    3. Q_D(QTreeView);
    4. d->header->setRootIndex(index);
    5. QAbstractItemView::setRootIndex(index);
    6. }
    To copy to clipboard, switch view to plain text mode 

    And in qabstractitemview.cpp we have:
    Qt Code:
    1. /*!
    2. Sets the root item to the item at the given index.
    3. */
    4. void QAbstractItemView::setRootIndex(const QModelIndex &index)
    5. {
    6. if (index.isValid() && index.model() != d->model) {
    7. qWarning("QAbstractItemView::setRootIndex failed : index must be from the currently set model");
    8. return;
    9. }
    10. d->root = index;
    11. d->doDelayedItemsLayout();
    12. }
    To copy to clipboard, switch view to plain text mode 

    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:
    Qt Code:
    1. /*!
    2. Returns the model index of the model's root item. The root item is
    3. the parent item to the view's toplevel items. The root can be invalid.
    4. \sa setRootIndex()
    5. */
    6. QModelIndex QAbstractItemView::rootIndex() const
    7. {
    8. return QModelIndex(d_func()->root);
    9. }
    To copy to clipboard, switch view to plain text mode 

    Indeed, when I run view.rootIndex() on the view in the simpletreemodel example, I get the "invalid" index back.
    Last edited by neuronet; 4th January 2015 at 20:06. Reason: updated contents

  15. #11
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: On the mistreatment of the noble root

    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  16. The following user says thank you to wysota for this useful post:

    neuronet (4th January 2015)

  17. #12
    Join Date
    Jun 2014
    Posts
    98
    Thanks
    43
    Thanked 4 Times in 4 Posts
    Platforms
    Windows

    Default Re: On the mistreatment of the noble root

    Quote Originally Posted by wysota View Post
    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!

  18. #13
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: On the mistreatment of the noble root

    Quote Originally Posted by neuronet View Post
    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.

    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.
    Your biological and technological distinctiveness will be added to our own. Resistance is futile.

    Please ask Qt related questions on the forum and not using private messages or visitor messages.


  19. The following user says thank you to wysota for this useful post:

    neuronet (4th January 2015)

  20. #14
    Join Date
    Jan 2008
    Location
    Alameda, CA, USA
    Posts
    5,230
    Thanks
    302
    Thanked 864 Times in 851 Posts
    Qt products
    Qt5
    Platforms
    Windows

    Default Re: On the mistreatment of the noble root

    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.

  21. The following user says thank you to d_stranz for this useful post:

    neuronet (5th January 2015)

Similar Threads

  1. QFileSystemModel root
    By Alundra in forum Qt Programming
    Replies: 3
    Last Post: 9th June 2014, 15:06
  2. QDir::root ()
    By RenanBS in forum Qt Programming
    Replies: 10
    Last Post: 6th June 2014, 19:00
  3. debugging as root
    By weaver4 in forum Qt Programming
    Replies: 0
    Last Post: 13th February 2012, 22:10
  4. how to run QT application with root permission
    By noa l in forum Qt Programming
    Replies: 4
    Last Post: 15th December 2010, 14:32
  5. root-priviliges in application
    By bkv in forum KDE Forum
    Replies: 2
    Last Post: 29th October 2006, 19:58

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.