Skip to content

Instantly share code, notes, and snippets.

@franky47
Created November 29, 2021 15:24
Show Gist options
  • Save franky47/f24b5b72b3064572785513b0b59aa758 to your computer and use it in GitHub Desktop.
Save franky47/f24b5b72b3064572785513b0b59aa758 to your computer and use it in GitHub Desktop.
Recursion-free, depth-first object traversal à la `reduce`.
/**
* Traverse a JSON object depth-first, in a `reduce` manner.
*
* License: MIT © 2021 François Best (https://francoisbest.com)
*
* @param input The root node to traverse
* @param callback A function to call on each visited node
* @param initialState Think of this as the last argument of `reduce`
*/
export function reduceTree<State>(
input: Json,
callback: (state: State, item: Item) => State,
initialState: State
) {
type StackItem = Item & {
state: State
}
const stack: StackItem[] = [
{
path: [],
type: typeOf(input),
node: input,
state: initialState
}
]
while (stack.length > 0) {
const { state, ...item } = stack.shift()!
const newState = callback(state, item)
if (!isCollection(item.node)) {
continue
}
const children: StackItem[] = Object.entries(item.node).map(
([key, child]) => ({
key,
node: child,
type: typeOf(child),
path: [...item.path, key],
state: newState
})
)
stack.unshift(...children)
}
}
// Types & Helpers --
type Literal = string | number | boolean | null
type Dict = { [key: string]: Json }
type Json = Literal | Array<Json> | Dict
type JsonType = 'string' | 'number' | 'boolean' | 'null' | 'array' | 'object'
function isObject(item: Json): item is Dict {
return (
typeof item === 'object' &&
Object.prototype.toString.call(item) === '[object Object]'
)
}
function isCollection(item: Json): item is Array<Json> | Dict {
return Array.isArray(item) || isObject(item)
}
interface Item {
key?: string
path: string[]
node: Json
type: JsonType
}
function typeOf(item: Json): JsonType {
if (Array.isArray(item)) {
return 'array'
}
if (isObject(item)) {
return 'object'
}
if (item === null) {
return 'null'
}
return typeof item as JsonType
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment