Geek Answers Handbook

Finding a node in a tree using recursive javascript promises

I was stuck in a program based on Javascript promises and could not figure out how to get it to return the correct value in the promises format.

Given the tree API returning the children of the node as PROMISE. For instance:

tree.getChildren('/2/4')
.then(function (nodes) {    
    console.log(nodes); // logs 7,8,9 as children of node 4
}

using the method, the tree.getChildrenmethod searchNodemust recursively try to search searchValuein the tree and return its path if it is found, nullotherwise.

The method below is simply trying to find the node in the tree path, but it just returns undefined, which, in my opinion, is due to the asynchronous nature of the method. How to rewrite the code in honor of promises and get the desired behavior?

function searchNode(searchValue, path){
    tree.getChildren(path).then(function(children){
        if(children.length>0){
            for(var i = 0; i<children.length; i++){
                if(children[i] == searchValue){
                    return path;
                } else {
                    childPath = searchNode(searchValue, path+"/"+children[i]);
                    if(childPath != null)
                        return childPath;
                }
            }
        }
        else{
            return null;
        }
    })
}
0
2

, searchNode Promise.

:

  • tree.getChildren

  • () searchNode , :

     childPath = searchNode(searchValue, path+"/"+children[i]);
 if (childPath != null) { // ...etc.

    . , then, .

, , , , promises. .

null , , , promises, .

, promises, , , , ( ), , ... . , , .

:

function searchNode(searchValue, path){
    return tree.getChildren(path).then(function(children){
        // First look for the value among the immediate children
        for(let i = 0; i<children.length; i++){
            if(children[i] == searchValue){
                return path;
            }
        }
    // Then look deeper
    return (function loop(i) {
        if (i >= children.length) {
            return Promise.reject("not found"); 
        } else { 
            // after asynchronous result comes in, either
            // continue the loop, or resolve with path
            return searchNode(searchValue, path+"/"+children[i])
                .catch(loop.bind(null, i+1));
        }
    })(0);
}


"use strict";
// Simple implementation of tree
const tree = {
    root: {
        '2': {
            '4': {
                '1': {}
            },
            '7': {}
        },
        '0': {}
    },
    getChildren: function(path) {
        return new Promise(function (resolve) {
            const node = path.split('/').reduce(function (parent, node) {
                return node === '' || !parent ? parent : parent[node];
            }, tree.root);
            resolve(Object.keys(node));
        });
    }
};

function searchNode(searchValue, path){
    return tree.getChildren(path).then(function(children){
        // First look for the value in the immediate children
        for(let i = 0; i<children.length; i++){
            if(children[i] == searchValue){
                return path;
            }
        }
        // Then look deeper
        return (function loop(i) {
            if (i >= children.length) {
                return Promise.reject("not found"); 
            } else { 
                // after asynchronous result comes in, either
                // continue the loop, or resolve with path
                return searchNode(searchValue, path+"/"+children[i])
                    .catch(loop.bind(null, i+1));
            }
        })(0);
    })
}

// Demo
searchNode('1', '').then(function (path) {
    console.log(path);
}, function (reason) {
    console.log(reason);
});
Hide result

. node, , sibling node. , tree.getChildren , :

, node 1000 , node. , . , - , , " " () , , . , , .

, searchNode then , , .

- Promise.not Promise.some -, Promise.race Promise.all. Q & A, " ES6 ?" :

// Invert the outcome of a promise
Promise.not = promise => promise.then(x => {throw x}, e => e);
// Resolve when the first promise resolves
Promise.some = iterable => Promise.not(Promise.all(iterable.map(Promise.not)));

, bluebird Promise.any.

, , . , . , , .

Promise.some :

function searchNode(searchValue, path){
    let resolved = false;

    return (function searchNodeSub(path) {
        return tree.getChildren(path).then(function(children){
            // If we already found the value via another parallel search, quit
            return resolved ? true
                // Otherwise look for the value among the immediate children
                : children.some(child => child == searchValue) ? path
                // If not found there, look deeper -- in parallel
                : Promise.some(children.map(child => searchNodeSub(path+"/"+child)));
        })
    })(path).then( path => (resolved = true, path) ); // register that we have a result
}

children.some Promise.some.

"use strict";
// Simple implementation of tree
const tree = {
    root: {
        '2': {
            '4': {
                '1': {}
            },
            '7': {}
        },
        '0': {}
    },
    getChildren: function(path) {
        return new Promise(function (resolve) {
            let node = path.split('/').reduce(function (parent, node) {
                return node === '' || !parent ? parent : parent[node];
            }, tree.root);
            resolve(Object.keys(node));
        });
    }
};

// Invert the outcome of a promise
Promise.not = promise => promise.then(x => {throw x}, e => e);
// Resolve when the first promise resolves
Promise.some = iterable => Promise.not(Promise.all(iterable.map(Promise.not)));

function searchNode(searchValue, path){
    let resolved = false;
    
    return (function searchNodeSub(path) {
        return tree.getChildren(path).then(function(children){
            // If we already found the value via another parallel search, quit
            return resolved ? true
                // Otherwise look for the value among the immediate children
                : children.some(child => child == searchValue) ? path
                // If not found there, look deeper -- in parallel
                : Promise.some(children.map(child => searchNodeSub(path+"/"+child)));
        })
    })(path).then( path => (resolved = true, path) ); // register that we have a result
}

// Demo
searchNode('1', '').then(function (path) {
    console.log(path);
}, function (reason) {
    console.log('Not found');
});
Hide result
+3

.getChildren() searchNode, childPath:

function searchNode(searchValue, path){
  return tree.getChildren(path).then(function(children){ //return the promise so we can later wait for it to resolve
    if(children.length>0){
        for(var i = 0; i<children.length; i++){
            if(children[i] == searchValue){
                return path;
            } else {
                return searchNode(searchValue, path+"/"+children[i])
                  .then(function(childPath){ //wait for searchNode to complete
                    if (childPath != null) {
                      return childPath;
                    }
                  });
            }
        }
    }
    else{
        return null;
    }
  })
}
0

More articles:


All Articles