javascript - How to get altered tree from Immutable tree, maximising reuse of nodes - Stack Overflow

admin管理员组

文章数量:1320587

I have a tree structure data like this:

[{
    id: 54,
    name:123,
    children: [{
        id: 54,
        name:123,
        children: [{
            id: 154,
            name:1234,
            children []...
        }]
    }]
}, {
 ...
}]

I am using Angular 2. As far as I know, change detection kicks in whenever input changes and your change detection strategy is onPush.

To optimise the tree structure updates (e.g. toggling a node at a nested level or changing any attributes of such a node), I used Immutable.

How can Immutable help me to optimise my updates? I read that Immutable reuses references from old data to construct new objects whenever data changes.

How do I use Immutable data structures efficiently to update nodes at a nested level?

Assumptions

1. I don't have a keyPath for any of the nodes.
2. Each node has a unique id property value which can be used to query tree data (but how?)

Problems

1. How can I update a node somewhere at a nested level? What could be the most efficient way of reaching out to that node?
2. How do I update multiple nodes? I heard of the withMutations API, but is there any other efficient way?

My approach

1. Deep-copy everything and then modify the newly constructed object:

   var newState = deepClone(oldState) // deep copy everything and construct a new object 
   newState.nodes.forEach(node => {
       if(node.id == 54) {
           node.id = 789;
       }
   })
   

2. What I am trying to implement:

   var newState = Immutable.fromJS(oldState) // create an immutable object 
   newState = newState.find(node => {
       node.set("id", 123);
   }); // any changes to object will return new object
   

With the second solution I hope to achieve re-use of nodes, as pictured below:

I have a tree structure data like this:

[{
    id: 54,
    name:123,
    children: [{
        id: 54,
        name:123,
        children: [{
            id: 154,
            name:1234,
            children []...
        }]
    }]
}, {
 ...
}]

I am using Angular 2. As far as I know, change detection kicks in whenever input changes and your change detection strategy is onPush.

To optimise the tree structure updates (e.g. toggling a node at a nested level or changing any attributes of such a node), I used Immutable.

How can Immutable help me to optimise my updates? I read that Immutable reuses references from old data to construct new objects whenever data changes.

How do I use Immutable data structures efficiently to update nodes at a nested level?

Assumptions

1. I don't have a keyPath for any of the nodes.
2. Each node has a unique id property value which can be used to query tree data (but how?)

Problems

1. How can I update a node somewhere at a nested level? What could be the most efficient way of reaching out to that node?
2. How do I update multiple nodes? I heard of the withMutations API, but is there any other efficient way?

My approach

1. Deep-copy everything and then modify the newly constructed object:

   var newState = deepClone(oldState) // deep copy everything and construct a new object 
   newState.nodes.forEach(node => {
       if(node.id == 54) {
           node.id = 789;
       }
   })
   

2. What I am trying to implement:

   var newState = Immutable.fromJS(oldState) // create an immutable object 
   newState = newState.find(node => {
       node.set("id", 123);
   }); // any changes to object will return new object
   

With the second solution I hope to achieve re-use of nodes, as pictured below:

• javascript
• immutability
• immutable.js
• immutable-collections

Share Improve this question Follow edited Dec 26, 2016 at 13:46 trincot 351k3636 gold badges272272 silver badges325325 bronze badges asked Dec 23, 2016 at 9:22 Display NameDisplay Name 33755 silver badges1515 bronze badges 18

• 3 "Immutable update" is an oxymoron. You have a value, and you want another similar value, so you create the differences and share the similarities – Caleth Commented Dec 23, 2016 at 9:28
• 1 @Caleth agreed. But need your help in efficiently finding a way to reach node in a tree and update it – Display Name Commented Dec 23, 2016 at 9:31
• 1 You create a new tree. Rather than copying unchanged values, you reference them, and this is safe because nothing changes – Caleth Commented Dec 23, 2016 at 9:34
• 1 So is your data structure intended to be updated (mutable) or intended to be copied in its entirety with the change applied to the copy you make (immutable)? The latter is of course less efficient. – trincot Commented Dec 23, 2016 at 9:58
• 1 "If I make a tree data immutable and update only a part of it": this is impossible. An immutable tree cannot have any part of it updated, by the definition of "immutable". You are just looking for updating a tree. – trincot Commented Dec 23, 2016 at 10:15

 |  Show 13 more ments

1 Answer 1

Sorted by: Reset to default 10 +50

Realise that when you use Immutable for your tree structure, you cannot expect to replace a node without also changing the internal references to that node, which means that such a change will need to bubble up to the root of the tree, also changing the root.

More detailed: as soon as you use a method to change a certain property value, you will get a new object returned for that particular node. Then to re-inject that new node in your tree, i.e. in the parent's children list, you will use a method that will create a new children list (since the children property is immutable as well). Now the problem is to attach that children list to the parent, which will result in a new parent node, ...etc. You'll end up recreating all the ancestor nodes of the node you want to change, giving you a new tree instance, which will have some reuse of nodes that were not in the root-to-node path.

To re-use your image, you'll get something like this:

The Immutable API can do this for you with the updateIn method (or setIn if your update concerns only one property of the targeted node). You will need to pass it the key path to identify the (nested) node you want to modify.

So, if for instance you know the id of the node to be changed, you could use a little helper function to find the key path to that particular node.

function findKeyPathOf(tree, childrenKey, predicate) {
    var path;
    if (Immutable.List.isList(tree)) {
        tree.some(function (child, i) {
            path = findKeyPathOf(child, childrenKey, predicate);
            if (path) return path.unshift(i); // always returns truthy
        });
        return path;
    } 
    if (predicate(tree)) return [];
    path = findKeyPathOf(tree.get(childrenKey), childrenKey, predicate);
    if (path) return [childrenKey].concat(path);
}

You need to pass it the tree, the name of the property that has the children (so children in your case), and the function that will identify the node you are looking for. Let's say you want the path to the node with id 4, then you would call it like this:

var keyPath = findKeyPathOf(tree, 'children', node => node.get('id') == 4);

That key path could look something like this -- an alteration of an index in the array, and the children property providing the deeper array:

[0, 'children', 0, 'children', 1]

Then to modify the node at that path, you would do something like this:

var newTree = tree.updateIn(keyPath, node => node.set('name', 'Hello'));

Here is a demo with some sample data:

// Function to get the path to a certain node in the tree
function findKeyPathOf(tree, childrenKey, predicate) {
    var path;
    if (Immutable.List.isList(tree))
        childrenKey = tree.findKey(child =>
            path = findKeyPathOf(child, childrenKey, predicate));
    else if (predicate(tree)) 
        return [];
    else
        path = findKeyPathOf(tree.get(childrenKey), childrenKey, predicate);
    return path && [childrenKey].concat(path);
}

// Function to pare two trees
function differences(tree1, tree2, childrenKey) {
    if (Immutable.List.isList(tree1)) {
        return tree1.reduce(function (diffs, child, i) {
            return diffs.concat(differences(child, tree2.get(i), childrenKey));
        }, []);
    }
    return (tree1 !== tree2 ? [tree1] : []) 
        .concat(differences(tree1.get(childrenKey), tree2.get(childrenKey),
                            childrenKey));
}

// Sample data
var tree = [{
    id: 1,
    name: 'Mike',
    children: [{
        id: 2,
        name: 'Helen',
        children: [{
            id: 3,
            name: 'John',
            children: []
        },{
            id: 4,
            name: 'Sarah',
            children: [{
                id: 5,
                name: 'Joy',
                children: []
            }]
        }]
    }]
}, {
    id: 6,
    name: 'Jack',
    children: [{
        id: 7,
        name: 'Irene',
        children: []
    },{
        id: 8,
        name: 'Peter',
        children: []
    }]
}];

// Create immutable tree from above plain object:
var tree = Immutable.fromJS(tree);

// Use the function to find the node with id == 4:
var keyPath = findKeyPathOf(tree, 'children', node => node.get('id') == 4);

// Found it?
if (keyPath) {
    // Set 'name' to 'Hello' in that node:
    var newTree = tree.updateIn(keyPath, node => node.set('name', 'Hello'));
    // Print the new tree:
    console.log(newTree.toJS());
    // Compare all nodes to see which ones were altered:
    var altered = differences(tree, newTree, 'children').map(x => x.get('id'));
    console.log('IDs of nodes that were replaced: ', altered);
} else {
    console.log('Not found!');
}

.as-console-wrapper { max-height: 100% !important; top: 0; }

<script src="https://cdnjs.cloudflare./ajax/libs/immutable/3.8.1/immutable.min.js"></script>

本文标签： javascriptHow to get altered tree from Immutable treemaximising reuse of nodesStack Overflow