CODEWITHSUNDEEP
javascriptnode.jsasynchronous
Drew H
Drew H

Reputation: 4739

Recursively traverse tree in Javascript

This is super simple task to do in Java but the asynchronous nature of javascript makes this task(for me) almost impossible, at least with my knowledge now.(I'm not trying to bash javascript. Love the language!).

It's very basic. A top level tree has a parent of null in my mysql database. It's easy finding children. The children have lines available to them. The depth of the tree is variable.

    private static Set<Tree> getBranches( Tree trunk ) {

    Set<Tree> treeSet = new HashSet<Tree>();

    if ( trunk != null ) {

        if ( trunk.hasLines() ) { //queries if tree has lines.  returns true or false
            treeSet.add( trunk );
        }

        for ( Tree tree : trunk.treeList ) {
            treeSet.addAll( getBranches( tree ) );
        }
    }

    return treeSet;
}

Basically the method tests if the tree has lines available. If it does it adds all of those to a set. If not it continues until it finds lines.

The asynchronous nature of the mysql node library turns this task into hell.

Here is what I have now

   function hasLines(tree_id, callback) {
        var ret;
        pool.query('SELECT * from pkg_line_tree where tree_id = ?', [tree_id], function (err, rows) {

            if (rows.length > 0) {
                ret = true;
            } else {
                ret = false;
            }
            callback(ret);
        });
    }


     function dig(tree_id, treeArray, callback) {

        pool.query('SELECT * from tree where parent_id = ?', [tree_id], function (err, rows) {

           if (rows) {

              for (var i in rows) {
                 hasLines(rows[i].tree_id, function (t) {

                    if (t) {
                       treeArray.push(rows[i].tree_id);
                    } else {
                       treeArray.concat(dig(rows[i].tree_id, treeArray));
                    }
                 });
              }

              if (callback) {
                 callback(treeArray);
              }

           }
        });

        return treeArray;
     }


     var treeArray = [];
     dig(52, treeArray, function (t) {
        res.json(t);
     });

I really just need to output all the children available in this root tree.

Please let me know if this doesn't make sense. I'll try to refactor. I'm hoping I got some kind of point across. I'd hate to use something like Fibers to get this done but I'm out of options. Thanks.

Upvotes: 4

Views: 3148

Answers (2)

Jonathan Lonowski
Jonathan Lonowski

Reputation: 123473

Your use of dig() isn't currently consistent:

// asynchronous with callback
dig(52, treeArray, function (t) {
   res.json(t);
});

// then synchronous with `return`?
treeArray.concat(dig(rows[i].tree_id, treeArray));

Also, the concat in the last line isn't actually doing much, since it doesn't alter the array it's called on. You probably wouldn't actually want it to as dig passes around the treeArray rather than defining a new treeSet like in getBranches. So, if it did, it would append treeArray onto the end of itself each time.

You could still use concat with multiple treeSets, but you'd have to store its return value:

treeSet = treeSet.concat(subSet);

And, you'll have to replace the for loop this with an asynchronous iterator as the loop won't wait for asynchronous operations before continuing. The async library has a few options for this, if you're up for trying it.

So, with multiple treeSets, concat, and async.forEachSeries, you could try:

function dig(tree_id, callback) {
  var treeSet = [];

  hasLines(tree_id, function (yep) {
    if (yep) {
      treeSet.push(tree_id);
    }

    pool.query('SELECT * from tree where parent_id = ?', [tree_id], function (err, rows) {

      function each(row, next) {
        dig(row.tree_id, function (subSet) {
          treeSet = treeSet.concat(subSet);
          next(null);
        });
      }

      function done() {
        callback(treeSet);
      }

      async.forEachSeries(rows, each, done);
    });
  });
}

dig(52, function (treeSet) {
  res.json(treeSet);
});

Upvotes: 2

yngccc
yngccc

Reputation: 5684

you have to use async https://github.com/caolan/async

I have modified your dig function to use async's forEach method

function dig(tree_id, treeArray, AllDone) {
       pool.query('SELECT * from tree where parent_id = ?', [tree_id], function (err, rows) {
          if (rows) {
            async.forEach(
                rows,
                function(row, callback) {
                    hasLine(row.tree_id, function(t){
                        if (t) {
                            treeArray.push(row.tree_id);
                            callback();
                        }
                        else {
                            dig(row.tree_id, treeArray, callback);
                        }
                    });
                },
                function(err) {
                    if (err) AllDone(err, treeArray);
                    else AllDone(null, treeArray);
                });
            }
          else 
            AllDone(null, treeArray)
        });
}

treeArray = [];
dig(52, treeArray, function(err, t) {  
    res.json(t);  
});

assuming rows is an array.. forEach go through each row and perform hasLine, each iteration will call the callback function when it finish, and AllDone will be called when all callback functions are called. the tricky part here is the recursion, each recursive call will have a forEach loop, and it will call the AllDone method only when all callbacks are finish.

however forEach execute in parallel, so order is not perserved

I think this should work, if you don't care about order.

Edit : you can use forEachSeries to solve the order problem.

Upvotes: 2

Related Questions