Glorious, just glorious.  When a new tool comes into existence and everyone applauds your efforts and say with glee how much this widget doohickey will improve the lives of millions.  Or at least the minions.  Whatever.  Until ten minutes later when people start actually using it, suddenly all you hear is complaining.

“My selection keeps getting cleared.”  “I have to keep scrolling back to where I was.”  “I think I’m blind, can I see the nurse?”

Waauuuh?  Ten minutes ago everything was roses, and now they want the moon on a stick!

The problem is, widget libraries suck.   All of them, to my knowledge, make lives miserable for programmers by default.  When we have a list of things in a window, we have two choices of working with it:

1. Rebuild the whole window every time, having done a lot of work to completely determine what should be in it.
2. Incrementally change only the things that need changing, and hope to hell that nothing ever goes out of sync, and all the things in the window are right (ie. you are receiving and handling correctly every message that affects the contents at all times).

Cleverer programmers than I have tried #2 and failed miserably, creating tools that crash at random times and are utterly unpredictable.  I refuse to go down that path, for my own sanity, even if it is “higher performance”.  It’s rare that such concerns are overriding tools designs these days for interactive listboxes, unless your list has millions of entries.  Not likely.

So, that leaves rebuilding the contents of your window.  This is completely clean and simple, right?

1. Freeze the control (so the user doesn’t see it update)
2. Clear the control
3. Gather your junk
4. Fill the control with junk
5. Thaw the control (so the user can see it gloriously accurate)

…except there’s a problem.  A bunch of them, actually.  You’ve thrown away ALL the state that has collected in the control when it’s cleared.  Things like:

• Current selection
• Current focused item
• Expansion choices (for tree controls)
• Current scrolled position
• etc…

The next obvious way to make this process work better is messy.  Insert step (1A) Capture ALL that state  mentioned above, using many passes over the data, and possibly not able to get the state exactly right depending on the widget library, (4A) Do numerous searches over the new control to propagate the stored state so it is regenerated and looks like the user’s old control.  Besides the fact that this is incredibly tedious and error-prone, it’s very slow and a lot of temporary data.  This alone would be tedious enough to teach you not to use lists or trees in your apps.

No fear, there’s a solution.  What should you do? A simple hybrid approach works wonders:

1. Freeze the control
2. Gather your junk (do not clear it)
3. Walk the control’s items and search your junk to see if you should remove any items.  Copy these to a separate data structure before removing them, so you aren’t changing the control as you iterate (unless your widget is cool with that).
4. Remove entries that should be removed from control.
5. Walk your junk and search the control’s items to see if each element is already present.  If not, insert your junk.
6. Thaw the control

The difference?  No state is destroyed except that which must be destroyed, you have minimal modification to the control itself which should perform pretty well (if that matters), and you are pretty well guaranteed that the contents of the control matches the full set of data that you wanted it to represent.

It seems like a lot of extra work, but totally worth it and incredibly simple to write.  Yes, some controls will be especially badly behaved and search very slowly, in which case you might need to pull all the items out into a STL map or something, but that’s only going to matter with very dense lists.

That begs the question, how should a widget library work?  Well, ideally it would do all this work for me.  I’d like to present it with a complete list  of stuff I want to put in the control and have it work out what to insert and what to remove.   The alternative is to use virtual data and basically provide accessors directly to your own data structure, but the boilerplate required for this is prohibitive and I honestly don’t want to spend more effort getting things to look right, especially if I might change my representation later…

Anyway, I thought I’d share something that was on my mind.  I’ve been working on an editor for a few weeks and after having implemented the above algorithms for all controls,  it feels much more polished and usable.

spread the word:

You must be logged in to post a comment.