Recursively cross a tree in Javascript

Question

This is a very simple task for Java, but the asynchronous nature of javascript makes this task (for me) practically impossible, at least with my knowledge now. (I am not trying to use bash javascript.!).

It is very simple. The top level tree has a null parent in my mysql database. Easy to find children. 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 checks to see if the tree has any rows available. If he adds it all to the set. If it does not continue until it finds a row.

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

That's what i am 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 just need to infer all the children available in this root tree.

Please let me know if this makes no sense. I will try to reorganize. I hope I have some point. I would not want to use something like Fibers to do this, but I have no options. Thanks.

Answer 1

Currently, using dig() incompatible:

 // asynchronous with callback dig(52, treeArray, function (t) { res.json(t); }); // then synchronous with `return`? treeArray.concat(dig(rows[i].tree_id, treeArray)); 

In addition, concat in the last line actually does little, since it does not change the array to which it called. You probably wouldn’t want this, since dig was passing around treeArray , and not defining a new treeSet , as in getBranches . So, if that were the case, then every time I would add a treeArray to the end.

You can still use concat with multiple treeSet s, but you need to keep its return value:

 treeSet = treeSet.concat(subSet); 

And you will have to replace the for loop with an asynchronous iterator, since the loop will not wait for asynchronous operations before continuing. There are several options for this in the async library if you want to try it.

So with a few treeSet s, concat and async.forEachSeries you can 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); }); 

Answer 2

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

I changed your dig function to use async 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 strings are arrays. forEach scan each line and execute hasLine, each iteration will call the callback function when it ends, and AllDone will be called when all callback functions are called. the hard part here is recursion, each recursive call will have a forEach loop, and it will only call the AllDone method after all callbacks completed.

however, forEach runs in parallel, so the order is not preserved

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

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