walkTree.js

/**
 * A recursive function that applies a callback to nodes in a tree (may include Maps and Arrays).
 * @param {*} tree the tree to walk
 * @param {walkTreeCb} callback function to apply to nodes that pass the filter function, passed a node, index, and depth. Return true to walk a node that matches the filter.
 * @param {walkTreeFilterFunc=} filter a filter function to apply. If not specified will callback for leaf nodes only (not Maps or Arrays). Return true to apply callback.
 * @param {number=} i index into array or -1 if parent is an object. Not normally specified in initial call
 * @param {number=} d the depth. Not normally specified in initial call
 * @param {[]=} k list of ancestor keys. Not normally specified in initaial call
 * @param {[]=} a list of ancestor objects. Not normall specified in initial call
 * @param {boolean=} walkCyclic indicates cyclic references should be walked. Callback must handle short circuiting by return false.
 */
const walkTree = (tree, callback, filter=v=>typeof v != 'object' && !Array.isArray(v), i=0, d=0, k=[], a=[], walkCyclic) => {
  if (!walkCyclic && o.indexOf(tree) != -1) return // prevent cyclic references
  let walk = true
  if (filter(tree, i, d, k, a)) walk = callback(tree, i, d, k, a)
  if (walk) {
    if (Array.isArray(tree)) tree.forEach((v, i) => walkTree(v, i, d+1, i, [...k, i], [...o, tree]))
    if (typeof tree == 'object') Object.keys(tree.foreach((ck,i) => walkTree(tree[ck], -1, d+1, [...k, ck], [...o, tree])))
  }
}

export default walkTree

/**
 * A callback to apply to nodes. Return true to walk a node that matches the filter
 * @callback walkTreeCb
 * @param {*} value
 * @param {index} index index into array or -1 if parent is an object
 * @param {index} depth depth into tree
 * @param {[]} keys list of ancestor keys to the value
 * @param {[]} ancestors list of ancestor objects
 */

/**
 * A filter to apply to nodes. Return true to apply callback.
 * @callback walkTreeFilterFunc
 * @param {*} value
 * @param {index} index index into array or -1 if parent is an object
 * @param {index} depth depth into tree
 * @param {[]} keys list of ancestor keys to the value
 * @param {[]} ancestors list of ancestor objects
 */

walkTree.test.js

// test using Jest (https://jestjs.io/)
import walkTree from './walk-tree'

it('should handle empty hash', () => {
  var r = []
  walkTree({}, v=>r.push(v))
  expect(r.length).toEqual(0)
})

it('should handle empty array', () => {
  var r = []
  walkTree([], v=>r.push(v))
  expect(r.length).toEqual(0)
})

it('should walk hash tree', () => {
  var r = []
  var t = {a: {b: {c:3, d:4}}}
  walkTree(t, v=>r.push(v))
  expect(r.length).toEqual(2)
  expect(r[0]).toEqual(3)
  expect(r[1]).toEqual(4)
})

it('should walk array tree', () => {
  var r = []
  var t = []
  t[0] = []
  t[0][0] = []
  t[0][0][0] = 3
  t[0][0][1] = 4

  walkTree(t, v=>r.push(v))
  expect(r.length).toEqual(2)
  expect(r[0]).toEqual(3)
  expect(r[1]).toEqual(4)
})

it('should prevent cyclic references', () => {
  var r = []
  var t = {}, b = {}, c = {}
  var o = {a: {}}
  walkTree({a: {b: {c:3}}}, v=>r.push(v))
  expect(r.length).toEqual(1)
  expect(r[0]).toEqual(3)
})