Tree Util

interface TreeConfig {
  id: string
  pid: string
}

interface TreeHelperConfig {
  id: string
  children: string
  pid: string
}
const DEFAULT_CONFIG: TreeHelperConfig = {
  id: 'id',
  children: 'children',
  pid: 'pid',
}

const getConfig = (config: Partial<TreeHelperConfig>) =>
  Object.assign({}, DEFAULT_CONFIG, config)

// tree from list
export const listToTree = <T = any>(
  list: any[],
  config: Partial<TreeHelperConfig> = {},
): T[] => {
  const conf = getConfig(config) as TreeHelperConfig
  const nodeMap = new Map()
  const result: T[] = []
  const { id, children, pid } = conf

  for (const node of list) {
    node[children] = node[children] || []
    nodeMap.set(node[id], node)
  }
  for (const node of list) {
    const parent = nodeMap.get(node[pid])
    ;(parent ? parent.children : result).push(node)
  }
  return result
}

export const treeToList = <T = any>(
  tree: any,
  config: Partial<TreeHelperConfig> = {}
): T => {
  config = getConfig(config)
  const { children } = config
  const result: any = [...tree]
  for (let i = 0; i < result.length; i++) {
    if (!result[i][children!]) continue
    result.splice(i + 1, 0, ...result[i][children!])
  }
  return result
}

export const filter = <T = any>(
  tree: T[],
  func: (n: T) => boolean,
  config: Partial<TreeHelperConfig> = {},
): T[] => {
  config = getConfig(config)
  const children = config.children as string
  function listFilter(list: T[]) {
    return list
      .map((node: any) => ({ ...node }))
      .filter((node) => {
        node[children] = node[children] && listFilter(node[children])
        return func(node) || (node[children] && node[children].length)
      })
  }
  return listFilter(tree)
}


export const filterAll = <T = any>(
  tree: T[],
  func: (n: T, m: T) => T,
  config: Partial<TreeHelperConfig> = {},
): T[] => {
    const getNodes = (result, object) => {

      func(result, object)

      if (Array.isArray(object.children)) {
        const children = object.children.reduce(getNodes, [])
        if (children.length) {
          result.push({ ...object, children })
        }
      }

      return result
    }
    return tree.reduce(getNodes, [])

}

export const findPath = <T = any>(
  tree: any,
  func: Fn,
  config: Partial<TreeHelperConfig> = {},
): T | T[] | null => {
  config = getConfig(config)
  const path: T[] = []
  const list = [...tree]
  const visitedSet = new Set()
  const { children } = config
  while (list.length) {
    const node = list[0]
    if (visitedSet.has(node)) {
      path.pop()
      list.shift()
    } else {
      visitedSet.add(node)
      node[children!] && list.unshift(...node[children!])
      path.push(node)
      if (func(node)) {
        return path
      }
    }
  }
  return null
}
export const findPathAll = (
  tree: any,
  func: Fn,
  config: Partial<TreeHelperConfig> = {},
) => {
  config = getConfig(config)
  const path: any[] = []
  const list = [...tree]
  const result: any[] = []
  const visitedSet = new Set(),
    { children } = config
  while (list.length) {
    const node = list[0]
    if (visitedSet.has(node)) {
      path.pop()
      list.shift()
    } else {
      visitedSet.add(node)
      node[children!] && list.unshift(...node[children!])
      path.push(node)
      func(node) && result.push([...path])
    }
  }
  return result
}

export const findNode = <T = any>(
  tree: any,
  func: Fn,
  config: Partial<TreeHelperConfig> = {},
): T | null => {
  config = getConfig(config)
  const { children } = config
  const list = [...tree]
  for (const node of list) {
    if (func(node)) return node
    node[children!] && list.push(...node[children!])
  }
  return null
}

export const findNodeAll = <T = any>(
  tree: any,
  func: Fn,
  config: Partial<TreeHelperConfig> = {},
): T[] => {
  config = getConfig(config)
  const { children } = config
  const list = [...tree]
  const result: T[] = []
  for (const node of list) {
    func(node) && result.push(node)
    node[children!] && list.push(...node[children!])
  }
  return result
}

const list = [
    {
      id: '1',
      path: 'a',
      title: 'a',
      pid: '0'
    },
    {
      id: '2',
      path: 'b',
      title: 'b',
      meta: {
        title: 'apple'
      }
      pid: '0'
    },
    {
      id: '1-1',
      path: 'a/a',
      title: 'ab',
      pid: '1'
    },
    {
      id: '2-1',
      path: 'b/a',
      title: 'apple',
      pid: '2'
    },
    {
      id: '3',
      path: 'b/a/a',
      title: 'cider',
      pid: '2-1'
    },
    {
      id: '4',
      path: 'b/a/a',
      title: 'coke',
      pid: '3'
    },
]

const tree = listToTree(list)
console.log("list 2 tree", tree, tree.length)

// console.log("tree 2 list", treeToList<TreeConfig[]>(tree), treeToList<TreeConfig[]>(tree).length)

// console.log("filter", filter<TreeConfig>(tree, (node: TreeConfig) => {
//           return node.title.includes('app')
//         }))


// console.log("filter", filter<TreeConfig>(tree, (node: TreeConfig) => {
//           return node.title.includes('a')
//         }))
console.log("filterAll", filterAll<TreeConfig>(tree, (a: TreeConfig, b: TreeConfig) => {
  if (b.meta) {
    if (b.meta.title.includes('a')) {
      a.push(b)
      return a
    }
  }
}))
        

Playground Link