Server IP : 85.214.239.14 / Your IP : 3.15.225.164 Web Server : Apache/2.4.62 (Debian) System : Linux h2886529.stratoserver.net 4.9.0 #1 SMP Tue Jan 9 19:45:01 MSK 2024 x86_64 User : www-data ( 33) PHP Version : 7.4.18 Disable Function : pcntl_alarm,pcntl_fork,pcntl_waitpid,pcntl_wait,pcntl_wifexited,pcntl_wifstopped,pcntl_wifsignaled,pcntl_wifcontinued,pcntl_wexitstatus,pcntl_wtermsig,pcntl_wstopsig,pcntl_signal,pcntl_signal_get_handler,pcntl_signal_dispatch,pcntl_get_last_error,pcntl_strerror,pcntl_sigprocmask,pcntl_sigwaitinfo,pcntl_sigtimedwait,pcntl_exec,pcntl_getpriority,pcntl_setpriority,pcntl_async_signals,pcntl_unshare, MySQL : OFF | cURL : OFF | WGET : ON | Perl : ON | Python : ON | Sudo : ON | Pkexec : OFF Directory : /lib/node_modules/npm/node_modules/treeverse/lib/ |
Upload File : |
// Perform a depth-first walk of a tree, ONLY doing the descent (visit) // // This uses a stack rather than recursion, so that it can handle deeply // nested trees without call stack overflows. (My kingdom for proper TCO!) // // This is only used for cases where leave() is not specified. // // a // +-- b // | +-- 1 // | +-- 2 // +-- c // +-- 3 // +-- 4 // // Expect: // visit a // visit b // visit 1 // visit 2 // visit c // visit 3 // visit 4 // // stack.push(tree) // while stack not empty // pop T from stack // VISIT(T) // get children C of T // push each C onto stack const depth = ({ visit, filter, getChildren, tree, }) => { const stack = [] const seen = new Map() const next = () => { while (stack.length) { const node = stack.pop() const res = visitNode(node) if (isPromise(res)) { return res.then(() => next()) } } return seen.get(tree) } const visitNode = (visitTree) => { if (seen.has(visitTree)) { return seen.get(visitTree) } seen.set(visitTree, null) const res = visit ? visit(visitTree) : visitTree if (isPromise(res)) { const fullResult = res.then(resThen => { seen.set(visitTree, resThen) return kidNodes(visitTree) }) seen.set(visitTree, fullResult) return fullResult } else { seen.set(visitTree, res) return kidNodes(visitTree) } } const kidNodes = (kidTree) => { const kids = getChildren(kidTree, seen.get(kidTree)) return isPromise(kids) ? kids.then(processKids) : processKids(kids) } const processKids = (kids) => { kids = (kids || []).filter(filter) stack.push(...kids) } stack.push(tree) return next() } const isPromise = p => p && typeof p.then === 'function' module.exports = depth