Tags

Here is a interesting problem that I came across at my work today. We have two tree structures and want to move folders from one tree to another. The movements can happen in either direction. After all the movements are done, the trees get updated in the db.

I can record each drop (of a drag-and-drop operation). Then loop through all these recorded drops and make the necessary updates. This works fine except that it is not optimal (In the particular context where I faced this issue, there were other complications as well. I have skipped those for simplicity).

Let us look at the trees.

Two Trees

Two Trees

LR is the Root of the left tree and RR is the Root of the right tree.
When a folder is dragged and dropped, the folder along with its children are moved (entire sub tree).

Let a move be defined as a triplet (node, oldParent, newParent) where
node is the node that is being dropped.
oldParent is the parent from which ‘node’ was dragged.
newParent is the parent under which the ‘node’ is dropped.

This notation stays the same whether the movement is within or across trees as long as all IDs are unique across all trees (in my case they were all GUIDs)

Consider the move
(L3, LR, R3)
This means the subtree under L3 (inclusive) moves under R3 on the right hand side tree.

Consider these moves
(L311, L31,R2) – move 1
(L3, LR, R3) – move 2
(L311, R2, L31) – move 3
In effect, move 1 and move 3 cancel each other.

Consider these moves
(L3, LR, R2) – move 1
(L3, R2, L2) – move 2
In effect, these two moves can be combined into one single move as (L3, LR, L2)

A little thought suggests that there are two kinds of move reductions.
(1) total reduction (cancellation) and (2) partial reduction

The conditions for these are quite simple.
For a given ‘node’
if oldParent -> newParent of a move is swapped in the other move, it is a total reduction.
if oldParent of one move == newParent of other move then it is a partial reduction.

It is not required that the reductions be done after all the movements are complete. ie., when a node is dropped, I can check if the node was previously dropped ( by storing all the drops in a map). If it was already there, then make the above checks and see if one of the reductions is feasible.

A pseudo code will look like this
nodeexists = dropMap.get(node);
if (nodeexists)
if nodeexists.oldParent == node.newParent &&
nodeexists.newParent == node.oldParent
dropMap.remove(node)
else nodeexists.oldParent == node.newParent ||
nodeexists.newParent == node.oldParent
//modify the nodeexists old & new parent.

It was quite interesting to discover that by modeling the moves appropriately, simple set of rules could handle the redundant moves.

Advertisements