wxPython: VirtualTreeListCtrl with millions of items

views:

answers:

wxPython: VirtualTreeListCtrl with millions of items

I would like to add 1,000,000+ entries to the root node of a TreeListCtrl. Therefore I would like to make it "virtual", i.e. work just like a virtual ListCtrl so that it's still fast and I can easily scroll around due to the currently-displayed items being loaded on-demand. But I can't use a virtual ListCtrl because I also want to be able to expand any of the 1,000,000 items to display its children (the items will always have less than 50 children). Can this be done efficiently with a TreeListCtrl? Or with a different class? From my own experiments with treemixin.VirtualTree and wx.gizmos.TreeListCtrl, overloading the OnGetItemText method does not work the same way as it does with a plain virtual ListCtrl. It doesn't get called on-demand as the user is scrolling around, meaning all 1,000,000 items have to be added to the TreeListCtrl in advance.

One thing you might do is leave the sub-nodes empty, and catch the expand-node event. Then you check to see if the node's sub-nodes are populated. If they aren't, you add them before expanding the node. If they are populated, you simply ignore the event.

Ryan Ginstrom 2010-06-19 08:13:27

This would help if there weren't many sub-nodes per node. But my root node has 1 million children attached (i.e., there are 1 million nodes in the second layer of the tree), and then each of those 1 million has up to 50 children. Taking the time to add 1 million sub-nodes to a node is too slow.

Darryl 2010-06-21 00:28:39

Forgive any confusion, but I was under the impression that you could use the virtual tree control to draw the million sub-nodes, but not their children. So my suggestion was to use the virtual tree control for the children of the root, and then intercept the expand-node events on those million children to add the sub-nodes.

Ryan Ginstrom 2010-06-21 03:05:48

You're right that the treemixin doesn't make the TreeListCtrl really virtual. I thought about that when I was developing treemixin, but the one thing I didn't know how to solve was how to know which lines to draw to the left of items when the user is looking at items deep down the tree, e.g. 10000 to 10030. If you know of a solution for that I'll gladly adapt treemixin.

Frank

Author treemixin

Frank Niessink 2010-06-19 08:15:57

Thanks for creating treemixin! But I don't understand what you mean about drawing. Is it purely a graphical issue, or is it a problem with missing information in the underlying data structure? You would just need to know how many layers deep a node is, right?

Darryl 2010-06-21 00:24:21

No, just create a complex tree in a random tool and look at the vertical lines to the left of a random item. See http://www.sapdesignguild.org/community/IMAGES/explorer_tree.gif and imagine you only have to draw "membership" to "protected".The lines to the left depend on the structure of the tree above and below those items.

Frank Niessink 2010-07-03 15:53:06

I think what I'll do is use a virtual ListCtrl along with a skip-list for the data model. Initially, the data model will contain the 1 million top-layer nodes. When a node is expanded, I can insert its children into the skip-list in log time (much better than the linear time for an array). I will indent the names of the children in the ListCtrl so that you can visually tell who their parent is. I think the log search time for the skip-list (as opposed to instant random-access time for an array) will be fast enough to handle the user's scrolling. If someone has a better suggestion, please let me know. I will provide an update in the future as to whether my idea worked or not.

Darryl 2010-06-21 18:09:19

ansaurus

tags:

views:

answers:

wxPython: VirtualTreeListCtrl with millions of items

related questions