Faulty Tree Models

asked 2012-11-05 13:33:28 +0800

avidD gravatar image avidD
166 2

I am again fighting with the tree model. Maybe someone can help me. Here's the situation:

We have a tree that display a directed acyclic graph. That is, the tree contains all paths within that graph, meaning that the same object can occur in multiple positions. Users can freely edit this graph by inserting, moving, deleting, and linking nodes as long as they don't introduce cycles (which would lead to infinite paths).
The tree supports multiple selection. That is, I can mark, say, the children 2, 3, 5 of a node n and move those three edges (other occurrences of the nodes stay untouched) to a new parent n'. I signal the moving of edges by issueing delete events of the two intervals [2,3] and [5] for parent n and a corresponding insert event for n'. I first execute the operation on the database and, if successful, on the object model and then issue the events to update the view. I believe this makes sense, so the view stays consistent with the underlying data and does actually display the data and not what the data is desired to look like in the future (after a possible failing command).

1) Now one instance of the problem is this:
n' can be a descendant of n. ZK expects me to define the parents involved in events using a path, say n has the path [5,5,5]. Now also assume n' is child 6 of n having path [5,5,5,6].
The database has already been changed because I do not want to update the GUI only to see that the operation is (application-wise) illegal and must be rolled back in the GUI. Same for the model which is changed after updating the database. Consequently, when ZK tries to insert the three new children of [5,5,5,6] I have to adjust the tree model so that it actually returns the new parent [5,5,5,3] to move to, because the indexes in the model have changed through the operation. So the tree model knows the intervals that were deleted and adjusts getChildCount(node) and getChild(..) accordingly.
--> the model must know the "delete-intervals" and adjust getChildCount and getChild

2) Also, it may be possible that the target of the move operation lies before any of the nodes [5,5,5] on the path where the nodes must be deleted. In this case, I must adjust indexes by adding the intervals yielding, e.g., a new path [8, 5,5] if the three nodes were moved to the beginning of the list of children of the root.
--> the model must know the "insert-intervals" and adjust getChildCount and getChild

Adding these workarounds has cost a lot of nerves but it seems to work in isolated sessions. But the requirements are a bit harder. It is possible for multiple users to modify the same tree view of a DAG. However, we do not want modifications to become visible at once. So we put them in queues, one for each copy of the tree in a concurrent session. When such a concurrent sessions "goes into edit mode", the queue must be emptied by updating all views of nodes that were modified in concurrent sessions. In this case, no modifications are done on the database, only the session-scope model and the GUI for that session need be updated. Very easy I would think, just reload the lists of children, compute a delta (intervals that were inserted / removed) and issue events to ZK. Please note, that any number of nodes may have changed since the last session-update.
In this case, I just set multiple intervals in my tree model so it knows which indexes need offsets.

3) Now the current instance of the problem:
In one session I moved the children [0,1] of node [5] behind that node as new children 6 and 7 of the root [] that has had only the six children [0..5] up to now. So, I tell my tree model that (root, [6,7]) have been added while (child-5-of-root, [0,1]) was deleted where 'root' and 'child-5-of-root' are the domain objects displayed in the tree. But this leads to the problem that my model now adjusts the indexes of the new children 6 and 7 to 5 because it knows that the interval [6,7] has been added. This adjustment is done because any number of modifications may have been done since the current user last updated the tree and ZK may very well use a child of the root on the path to some other node in response to some other modification. This problem does not occur in the single-session case because there every update can involve only a limited number of nodes as it is directly executed in the GUI after successful modification of the domain model.

So I am issueing this event:

        TreeDataEvent.INTERVAL_ADDED,         // event type
        [],                               // path to parent
        6,                              // from
        7);                            // to

and the model only returns child 5 twice when ZK tries to draw 6 and 7.

So I can now adjust my model again. I don't know yet how to do this but it is surely possible.

I would say the interface has one serious flaw:
* the parent argument of fireEvent assumes that the model has not yet changed, so that all nodes are in the model where they were before and the path can be traversed as is without any adjustments
* the modified interval is expected to reflect the new state. So ZK assumes it can use the given indexes to access the new nodes for drawing.

I am starting to get really annoyed by the tree model which gave me a really hard time more than once already.
The int-array path has probably been introduced to gain some minor performance benefit. However, it is not a good style to represent objects that indeed exist and could be used (e.g., the Treeitems) as int-arrays everywhere. This is called premature optimization and is known to be "the root of all evil". Now again, I have to build workarounds to deal with these "§$"% paths. Everything could have been really easy would the event-interface be object-oriented. Actually, I doubt that the performance benefit of using int-arrays is so large. I expect the penalties for some hashmap look-ups of the Treeitems to be neglectable compared to the time required for rendering. And the usability of the interface has dropped significantly (at least in my opinion).

I see myself adding workarounds anytime I want to modify trees. Are my requirements too hard? Or am I wrong and missing some simple solution? Has anyone run into a similar problem yet?


delete flag offensive retag edit

1 Reply

Sort by » oldest newest

answered 2012-11-13 08:29:32 +0800

avidD gravatar image avidD
166 2

I am now issueing each single event after every (atomic) modification to the domain model. While this works, it seems unnatural and produces a tight coupling between the application layer, that should be entirely independent of the presentation layer and the GUI code in the sense that the GUI library dictates that I must issue "sub-atomic" events that signal inconsistent states of the view model. For instance, if I move N from M to K at position p, I must signal the following events after each partial modification
* N has been removed from the children of M
* N has been added as child p of K
At least IMO this domain-wise atomic operation (move) should be possible to execute as a whole before the two events are posted to the GUI. Otherwise, the GUI library constrains the design of the applicaiton layer too much.


link publish delete flag offensive edit
Your reply
Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

[hide preview]

Question tools




Asked: 2012-11-05 13:33:28 +0800

Seen: 94 times

Last updated: Nov 13 '12

Support Options
  • Email Support
  • Training
  • Consulting
  • Outsourcing
Learn More