Merging two trees using treemodel.js
Example: http://jsfiddle.net/yeehawjared/bawv0790/
I am creating an application where a web page opens by loading JSON from a large data tree structure. TreeModel.js parses this nicely, and all is well.
As time passes, the browser receives updates in the form of smaller data trees. I'm trying to get my head around the pool additionalData
in masterTree
. I can't think of a way to move both at the same time and perform a node-by-node comparison. If I could, it would be easy to combine properties node.model.x
and add children if they don't exist.
In the code below, I'm looking at additional data, but I don't know how to efficiently combine new nodes with masterTree
. Can someone please help my methodology with psuedo code or point me in the right direction? What's the best way to keep mine up to date masterTree
?
Many thanks.
var tree = new TreeModel();
var masterTree = tree.parse(data1);
var additionalData = tree.parse(data2);
additionalData.walk(function (node) {
// compare additionalData to the masterTree
if (node.model.id == masterTree.model.id) {
console.debug('match, combine the attributes')
} else {
// add the additional node to the materTree
}
});
source to share
Take a look at this fiddle for an example in action: http://jsfiddle.net/bawv0790/1/
An important function mergeNodes
. It is a recursive function that takes 2 nodes, n1 and n2. It first updates the size of n1 to match n2 and adds n2 children to n1 if they are missing or merges them if they are present.
function mergeNodes(n1, n2) {
var n1HasN2Child, i, n2Child;
// Update the sizes
updateSize(n1, n2);
// Check which n2 children are present in n1
n1HasN2Child = n2.children.map(hasChild(n1));
// Iterate over n2 children
for (i = 0; i < n1HasN2Child.length; i++) {
n2Child = n2.children[i];
if (n1HasN2Child[i]) {
// n1 already has this n2 child, so lets merge them
n1Child = n1.first({strategy: 'breadth'}, idEq(n2Child));
mergeNodes(n1Child, n2Child);
} else {
// n1 does not have this n2 child, so add it
n1.addChild(n2Child);
}
}
}
Checking which children of n2 are in n1 can be greatly improved if the children were sorted.
source to share