The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

treeview & data

I am working on an application that uses the treeview widget. Each child in the treeview is tied to some real data that can be displayed and modified. To give you a visual, think of it like a primitive email client where the treeview root is the name of the user, and all the children of the root are emails the user received (let's just assume a single level for now). Doubleclicking on a leaf brings up the email text.

I am trying to use the MVC pattern to keep data processing away from the GUI, however, I am having problems in this particular case.

Firstly, picture this. I have a controller class (C++) that creates and owns all the GUI objects (views) and the engine. In effect, the controller is the top-level object. It listens (observer) to the GUI objects for any events (user input and otherwise) and makes engine API calls to process these events. It also directly accesses the GUI elements to update their data.

For example, if the user selects a leaf in the treeview, and hits "del" on the keyboard, the treeview sends a message to its observer (controller), which tells the controller to delete the data, and delete the leaf from the treeview. No calls to the engine in this case.

Now onto my problem. I seemingly had two options in terms of keeping track of the data (the emails):

1) Attach them directly to the treeview leaves.
2) Keep the data in a list (in the engine) and somehow find a way to link it to the treeview.

I ended up picking #1 simply because #2 was too cumbersome. The treeview architecture isn't the easiest thing to implement with linear data structures like lists and such.

In order to stick with the MVC pattern, the treeview does not do any data handling itself. It notifies the controller which makes engine API calls to add/delete data to the treeview or modify what's attached.

I've never worked with the treeview control before, and even though the path that I took looks OK, I still don't like the fact that the treeview holds the data. I somehow feel like the engine should be in charge of the data, but I couldn't make that work easily.

If you've used the treeview widget extensively, could you comment on what I've done and how I might be able to improve it? I'd be greatful for your ideas and comments.

Thank you!
newbie coder
Monday, August 01, 2005
 
 
It would really help to know WHICH treeview you're talking about, and which OS you're on, and which language/environment you're working in, etc.
Chris Tavares Send private email
Monday, August 01, 2005
 
 
I don't understand your setup.  The treeview should be just a facade for the actual tree of data, which should be in the "model" part of the MVC pattern.  That seems to be your "engine."

So when you hit delete on a leaf, it should notify the controller, which should have the model delete the appropriate data item, and should then have the treeview update itself from the model's updated data.  The treeview update code should either update itself entirely each time (probably not the best, but easy to program), or should be able to figure out what's changed, based on the passed-in data model, and should add/update/delete the appropriate GUI items.
Kyralessa Send private email
Monday, August 01, 2005
 
 
After writing that, I see that you're trying to keep data out of the treeview.  But you say that in case of a delete, there are no calls to the engine, and I don't get what you mean by that.  You say the controller is deleting the data, but where is the data it's deleting?
Kyralessa Send private email
Monday, August 01, 2005
 
 
> It would really help to know WHICH treeview you're talking
> about, and which OS you're on, and which
> language/environment you're working in, etc.

- Win2K/XP
- Visual C++ 6.0
- CTreeCtrl

> So when you hit delete on a leaf, it should notify the
> controller, which should have the model delete the
> appropriate data item, and should then have the treeview
> update itself from the model's updated data.

I could have done that, but that means the treeview is a "view" to the data that resides elsewhere. For a few leaves, it might be OK to update the entire tree, but what if there are hundreds of leaves? Updating the entire tree a little too much.

> The treeview update code should either update itself
> entirely each time (probably not the best, but easy to
> program), or should be able to figure out what's
> changed, based on the passed-in data model, and should
> add/update/delete the appropriate GUI items.

This is where I got stuck. The tree is not linear, but most data storage methods are (queues, stacks, lists, etc). Therefore, what would be a good way to map data to a treeview without having to recreate the entire tree from scratch when something changes (esp deleted)?
newbie coder
Monday, August 01, 2005
 
 
Caveat: I don't know much about the CTreeCtrl.  But it surely must have a way to identify a particular treenode.  And there must be a way to identify your data objects, whether by memory location or key or the object itself.

So I'm thinking that as you initially fill the treeview, you also populate a hashtable.  The hashtable's key is the data object or data object key; the object to which that key points is the treenode where it's represented (or its handle or whatever).

So after you update a data item, you find its treenode using the hashtable.  For updates, you update that node; for inserts, you get the appropriate parent, then add the inserted node to it; and so forth.

This way you don't have to walk the nodes to find the one you're looking for, and you don't have to embed any sort of ID in the node itself.
Kyralessa Send private email
Monday, August 01, 2005
 
 
> The treeview architecture isn't the easiest thing to implement with linear data structures like lists and such.

Each tree node includes a list of 0 or more child nodes.

> If you've used the treeview widget extensively, could you comment on what I've done and how I might be able to improve it?

I find it hard to imagine that all the data is only in the tree nodes ... because where did all this data come from? Isn't it stored on disk somewhere?

Instead, I imagine:

* Emails are stored in a database
* A list of emails is extracted from the database; this list is used to create tree nodes
* Each tree node includes the data from a subset of the fields in the email which it represents.

The data associated with each typical Windows tree node is as follows:

* A single string, a text label
* Either an object type, or perhaps an object state, which is represented by the choice of icon that you associate with the node
* An identify ... this is the pointer-to-void thing ... it may contain a pointer to *all* the data associated with the object (e.g. the text of the email) ... OR (and this is what I'd probably recommend) it contains only the ID or GUID or index value or whatever it is, that allows you to identify the object (the email) within the persistent database within which all emails are stored

The view would then invoke add/delete/edit commands implemented by the controller, and pass-in as a parameter to these commands the *identity* of the email being operated on ... the controller will then implement this action by changing data in the model (in the database).
Christopher Wells Send private email
Monday, August 01, 2005
 
 
> This way you don't have to walk the nodes to find the one you're looking for, and you don't have to embed any sort of ID in the node itself.

I think you *do* need to embed an ID in the node ... because the user may use the GUI to select a node in the tree and then invoke, for example, the 'delete' command on the selected node ... and to implement this functionality the software must be able to identify which is the email that is associated with the currently-selected tree node.

Your implementation would be OK if the GUI were only a passive, read-only view of the data.
Christopher Wells Send private email
Monday, August 01, 2005
 
 
Thank you for the replies. You gave me some leads to follow.

The database/id approach is great. So is the hashtable approach. Either one is better than attaching the data directly to the tree control (via the void pointers) which is what I am doing now.

I think I am going to go with the hashtable as it appears to be a little easier to code.
newbie coder
Monday, August 01, 2005
 
 
Oops!  Good point.
Kyralessa Send private email
Tuesday, August 02, 2005
 
 
Christopher is correct, you need an id or some such thing that links your view and data.


> For a few leaves, it might be OK to update the entire tree, but what if there are hundreds of leaves?

Hint: hint.

(More obvious Hint: IIRC there is a hint parameter, often unused, on the update method of MFC views, which is what you are using, I guess. If you aren't then you can always use a similar mechanism. In short, you don't update the entire view, just update what the data tells the view has changed.)

Wednesday, August 03, 2005
 
 
Deep down inside, I knew tying the data to the tree control wasn't the best idea.  :)
newbie coder
Wednesday, August 03, 2005
 
 
> Deep down inside, I knew tying the data to the tree
> Deep down inside, I knew tying the data to the tree
> control wasn't the best idea.  :)

IMHO the two methods are effectively the same and tying the data to the tree is no better or worse than having the data in a hash table.

With the hash table approach using an id you get a pointer, while using the attached data approach the pointer is tied directly to the leaf of the tree. In both cases you end up with exactly the same pointer.

The only real difference is the two is when attaching the pointer directly to the tree there is a chance the pointer might get destroyed. If this should happen the tree only finds out about the bad pointer when it tries to use it.

Using the hash approach does not isolate you from this condition since the code still needs to cater for the condition where the hash table returns a null pointer.

But I don’t see this as a problem with the approach used, but rather with the design of the software. Both examples describe an exception condition and it should fairly straight forward to design the software to ensure these exceptions never happen, by always keeping the pointers valid.
Jussi Jumppanen
Wednesday, August 03, 2005
 
 
>IMHO the two methods are effectively the same and tying the
>data to the tree is no better or worse than having the data
>in a hash table.

I am trying to implement the MVC while doing all this.

Therefore, the way I understood it, the difference is that if the tree holds the actual data, then either the model will have to know about the tree (view), which is bad, or there won't really be a model since the data is pretty much the model.

By keeping the data in the hash table, I can keep it within the model, and only assign the id's to the tree. That way, the model and the tree are separate, and the controller is the binder between the two as it should be.

Using the hash table introduces another level of complexity, but helps keep the model (and data) away from the views...

Please someone correct me if I am horribly wrong!  :)
newbie
Wednesday, August 03, 2005
 
 
I think it's right to separate data from the view.

Imagine that you implement another feature: e.g. a "Find" dialog, which searches through all emails for some text, and then displays the matching emails in a list ... when you implement this new "Find" dialog, you want the emails which you're searching to be collected somewhere ('somewhere' meaning 'in the data model', e.g. in the database or hashtable) ... if the emails were stored only in the treeview then you'd implement the "find" dialog by iterating through all the data attached to items in the tree (instead of iterating the datanase or hashtable).

You might want to implement the "Find" dialog when the treeview isn't even displayed / doesn't even exist.
Christopher Wells Send private email
Thursday, August 04, 2005
 
 
Jussi

Zeus editor seems to use lots of treeview controls. I wonder what you did there... Would it be ok to divulge the information?
newbie
Thursday, August 04, 2005
 
 
Zeus does indeed have lots of tree view controls.

The tree view in Zeus is nothing more than a home grown c++ class wrapping the Win32 SysTreeView32 control, similar to the CTreeCtrl found in MFC.

These trees are used to display lists of things (i.e. list of files, lists of tags, lists of projects etc) so when it comes to displaying these lists, Zeus uses the approach of attaching the data pointer directly to the leaf.

The leaf does not own the pointer, but it can assume the pointer will always be valid and to insure this is the case, whenever the list changes, the tree displaying the list is reloaded.

Early on in the development this approach did result in the occasional tree view crash, but in a way the crash was a good thing, as it highlighted a problem, not with the tree view, but rather the code that was incorrectly managing the list.

Attaching the data directly to the leaf is definitely not the only way to handle tree views, but for me personally, I find the approach works extremely well.
Jussi Jumppanen
Thursday, August 04, 2005
 
 
> I think it's right to separate data from the view.

FWIW consider the class browser tree view in Zeus. This is nothing but a view of the ctags database information, the structure of which looks similar to this:

    Zeus -> project -> files -> tag item

This reads "Zeus has many projects, a project is a list of files, a file is a list of tags".

To hold this structure in memory Zeus defines an abstract base item and then defines the project, file and tag items as specific classes of this base item.

This enables the ctags information in held in lists of abstract base items as follows:

Zeus has a:
    List<BaseItem *> listProjects;

A Project has a:
    List<BaseItem *> listFiles;

A File has a:
    List<BaseItem *> listTags;

Now to display this information, all the browser tree needs to do is display lists of abstract base items. To build its view it does nothing more than asks the ctags manager for a list of items, loads the list into the tree and attaches the abstract base item to the leaf of the tree.

The tree does not know or care where these base items come from, it just knows of them as abstract base items and it knows they are guaranteed to valid.

In fact at the high level the browser project leaves are in fact items that came from the "listProjects" list while at the lower level, the tag leaves contain items held in the file "listTags" list.
Jussi Jumppanen
Thursday, August 04, 2005
 
 
Jussi


Thank you for your posts. Great insights! I think I followed most of what you said, but here are a few things
that need clarification in my mind:

>Zeus uses the approach of attaching the data pointer
>directly to the leaf.
>The leaf does not own the pointer, but it can assume the
>pointer will always be valid and to insure this is the
>case, whenever the list changes, the tree displaying the >list is reloaded.

So you update the entire tree when even one item in it changes?

> Now to display this information, all the browser tree
> needs to do is display lists of abstract base items. To
> build its view it does nothing more than asks the ctags
> manager for a list of items, loads the list into the
> tree and attaches the abstract base item to the leaf of
> the tree.

So the treeview control "caches" the list of items to be displayed and when something changes, it gets a new set of items, caches them and displays them? Is that how it works?
newbie
Friday, August 05, 2005
 
 
> So you update the entire tree when even one item
> in it changes?

That's pretty what happens.

But the tree control contains extra code to minimize the effects of these reloads in the form of:

1) The painting code is optimized to minimize flicker.

2) All currently open items retain their open state after the reload.

3) The nodes are loaded on demand which basically means any node that is closed only requires a single item to be added to the tree. At a later point when this node is opened by the user, only then do the next level of nodes get loaded into the tree.

For example if you have the class browser view open, click on an item to load it into the editor, change the name of the item and save the change, this will trigger the class browser view reload and the new item name will be displayed.

If you do this quickly enough and often enough you can see the flicker but in general the response is pretty good

> So the treeview control "caches" the list of items to
> be displayed and when something changes, it gets a new
> set of items, caches them and displays them? Is that
> how it works?

Yes and no. I personally would not use the word "cache" as it implies some sort of copy of the data. At least in the case of Zeus the tree is not displaying a copy of the data, but rather the actual data, hence the need for the reload when the data changes.

With a truly "cache" approach you could get away without out needing the reload, as you would only need to add a few lines of missing data to the cache.

For small/medium list sizes my guess is the use of a cache/non cache approach would be undetectable by the end user, so the added code complexity required of a truly cached approach is hardly worth it.

While on the topic of tree view data, on occasions I have though of ways Zeus could have been coded differently. One idea I had was to write a generic tree control, specifically designed to display XML data.

The XML structure is very similar to the tree view structure and since it is should be possible to represent most data in XML format, in theory it would be possible to create a tree view control that could manage any form of data.
Jussi Jumppanen
Sunday, August 07, 2005
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz