Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
_es6-BFS-DFS.js - Using ES6 for breadth-frist-search and depth-first-search.
// getChildren(win) - returns array of windows that are child to `win`
// isTrue(win) - just a random callback
function recurseDFS(win) {
// depth first
let coll = [];
coll.push(isTrue(win));
let children = getChildren(win);
for (let child of children) {
coll.push(...recurseDFS(child));
}
return coll;
}
function recurseBFS(win) {
// breadth first
let coll = [];
let todo = [win];
while (todo.length) {
let cur = todo.shift();
coll.push(isTrue(cur));
todo.push(...getChildren(cur));
}
return coll;
}
/////// actually usable stuff, will stop recursion, and get actual data from the callback
// doCallback - function. arguments: win, depth. return: object;{data:any, done:bool} - set `done` to true if you want to stop recursion, if `data` is not set, then nothing is pushed to `coll` for that recurse. so if you want to not stop recursion and not collect for the current recurse, it is fine ok to not return anything from the callback.
function recurseDFS(win, doCallback, progstopref, progdepth=0) {
// progstopref - used programatically, devuser should never pass it
// progdepth - use programatically, devuser should never pass it
let stop = progstopref || {yes:false};
let depth = progdepth;
let coll = [];
if (stop.yes) return coll;
let rez = doCallback(win, depth);
if (rez && rez.data) coll.push(rez.data);
if (rez && rez.done) {
stop.yes = true;
} else {
let children = getChildren(win);
for (let child of children) {
coll.push(...recurseDFS(child, stop, depth+1));
}
}
return coll;
}
function recurseBFS(win, doCallback) {
let coll = [];
let todo = [];
let depth = -1;
let next_depth = [win]; // holds the current `win`'s at current `depth`
breakpoint: {
while (next_depth.length) {
depth++;
todo.push(...next_depth);
next_depth.length = 0; // next_depth.splice(0, next_depth.length); // empty `next_depth`
while (todo.length) {
let cur = todo.shift();
let rez = doCallback(win, depth);
if (rez && rez.data) coll.push(rez.data);
if (rez && rez.done) break breakpoint;
next_depth.push(...getChildren(cur));
}
}
}
return coll;
}
Owner

Noitidart commented Dec 6, 2016 edited

README

Rev3

  • Finished recurseBFS
  • Fixed typo in recurseDFS

Rev4

  • Untested, but added bottom half section, which is hooked up so can actually pass a callback, and collect real data, and stop recursion
  • getChildren is still an imaginary function

Rev5

  • Touched up in bottom half
  • Noted that its possible to not return anything from callback, made recurseDFS handle getting undefined from a callback as a return value
  • Style touch up in recurseBFS
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment