CODEWITHSUNDEEP
javascriptpromise
fearless_fool
fearless_fool

Reputation: 35219

walking a tree with Promises

I have a tree structure that I want to walk using Promises, and I haven't figured out the right code pattern for it.

Assume that we're given node names, and the act of converting a node name to a node is an asynchronous process (e.g. involves a web access). Also assume that each node contains a (possibly empty) list of children names:

function getNodeAsync(node_name) {
    // returns a Promise that produces a node
}

function childrenNamesOf(node) {
    // returns a list of child node names
}

What I want to end up with a method with this signature:

function walkTree(root_name, visit_fn) {
   // call visit_fn(root_node), then call walkTree() on each of the
   // childrenNamesOf(root_node), returning a Promise that is fulfilled
   // after the root_node and all of its children have been visited.
}

that returns a Promise that's fulfilled after the root node and all of its children have been visited, so it might be called as follows:

walkTree("grandpa", function(node) { console.log("visiting " + node.name); })
  .then(function(nodes) { console.log("found " + nodes.length + " nodes.")});

update

I've create a gist that shows my first attempt. My (slightly buggy) implementation for walkTree() is:

function walkTree(node_name, visit_fn) {
    return getNodeAsync(node_name)
        .then(function(node) {
            visit_fn(node);
            var child_names = childrenNamesOf(node);
            var promises = child_names.map(function(child_name) {
                walkTree(child_name, visit_fn);
            });
            return Promise.all(promises);
        });
};

This visits the nodes in the correct order, but the outermost Promise resolves before all the sub-nodes have been visited. See the gist for full details.

And as @MinusFour points out, using this technique to flatten the list of nodes is rather pointless. In fact, I really just want the final promise to fire when all the nodes have been visited, so a more realistic use case is:

walkTree("grandpa", function(node) { console.log("visiting " + node.name); })
  .then(function() { console.log("finished walking the tree")});

Upvotes: 3

Views: 461

Answers (2)

fearless_fool
fearless_fool

Reputation: 35219

Despite what I said in the O.P, I don't really care about the return values of the final promise, but I do want to wait until all the nodes have been traversed.

The problem with the original attempt was simply a missing return statement in the map() function. (Despite appearances, this is essentially structurally identical to @MinusFour's answer.) Corrected form below:

function walkTree(node_name, visit_fn) {
    return getNodeAsync(node_name)
        .then(function(node) {
            visit_fn(node);
            var child_names = childrenNamesOf(node);
            var promises = child_names.map(function(child_name) {
                return walkTree(child_name, visit_fn);
            });
            return Promise.all(promises);
        });
};

Here are two use cases for walkTree(). The first simply prints the nodes in order then announces when the tree walk is finished:

walkTree("grandpa", function(node) { console.log("visiting " + node.name); })
  .then(function() { console.log("finished walking the tree")});

The second creates a flat list of nodes, made available when the tree walk completes:

var nodes = [];
walkTree("grandpa", function(node) { nodes.push(node) })
  .then(function() { console.log('found', nodes.length, 'nodes);
                     console.log('nodes = ', nodes); });

Upvotes: 0

MinusFour
MinusFour

Reputation: 14423

Well it isn't much of a problem to handle a function call for each node, but gathering the node values is kind of a problem. Kind of hard to walk that tree, your best bet would be to map it to a tree with no eventual values. You could use something like:

function buildTree(root_name) {
    var prom = getNodeAsync(root_name);
    return Promise.all([prom, prom.then(function(n){
        return Promise.all(childrenNamesOf(n).map(child => buildTree(child)))
    })]);
}

From there on you do:

var flatTree = buildTree(root_name).then(flatArray);
flatTree.then(nodes => nodes.forEach(visit_fn));
flatTree.then(nodes => whateverYouWantToDoWithNodes);

To flatten the array you could use:

function flatArray(nodes){
    if(Array.isArray(nodes) && nodes.length){
        return nodes.reduce(function(n, a){
                return flatArray(n).concat(flatArray(a));
        });
    } else {
        return Array.isArray(nodes) ? nodes : [nodes];
    }
}

To be honest, it's pointless to have the tree walker if you want a list of nodes you are better up flattening it up and then iterating the elements, but you can walk the array tree if you want.

Upvotes: 1

Related Questions