Other ideas (and it's an infinite discussion) would be: if one analyzes how users would use the tree, you could probably envision other optimizations: If many elements are to be selected, a user would select in the vast majority of cases a range, then maybe few others non contigous items. Now in that case, one could maintain a range selection data structure, then any other data structure for the rest of the selected item if any(could probably still be a terribly linear array list as we could reasonably assume that there would be much more elements in the range selection than anything else). Of course there would be limitations & examples that contradicts this : if another sort is selected then we can end up again in many elements distributed differently in the tree and makes the optimization void.
Other examples that could contradict this assumption would be if the user loads a selection from a serialized object from disk (i.e. selection was the result of a non user direct interaction and so on) Also, it might be worth mentioning that once you know the items you have drawn, you could keep track of them and therefore not needing a lookup table because the number of displayable items would be << to the total number of items in tree (if its not the case then it means there are few elements and we don't need to discuss that case anyway). -Fabien > > The way I see it, if the selection list is managed as an array > > of item ptrs (instead of as a per-item bit flag), then when > > Fl_Tree runs its draw() loop, wouldn't it have to do a lookup > > on this array each time it has to check if an item is selected > > (in order to draw it properly)? > The indirection lookup in the selection data structure could actually eat a > lot of cpu if you use a non suitable abstract data type : > Without going back to universisty (!), just think of the proper data > representation and you win: a list (linked or array) is bad for seeking > element (the complexity is average n/2 for n elements) > a much better approach for still getting great performances is to use either > a binary search (log(n) complexity) or even better in our case a hashtable > (almost constant complexity) > > Now the funny thing about that discussion is that in the old days I published > some experimentation made on fltk in my branch and had implemented widget > lookup table which was just a hastable ... from scratch (no STL needed). > It seemed that many users got & refered to this implementation I made but > nobody used it in the core team. > I even published performances results in these days. > Ah the old days where I had (lot of ) spare time :) > > Peace. _______________________________________________ fltk-bugs mailing list fltk-bugs@easysw.com http://lists.easysw.com/mailman/listinfo/fltk-bugs
