트리 구조 데이터의 JavaScript 처리

줄거리
전단 항목 중 일부 경우 트리 구조 데이터를 처리해야 한다.(1년 전) 나는 그것에 관한 글을 한 편 썼지만, 지금은 더 좋은 해결 방안이 생겼다.

사색
이전에, 나는 Proxy를 사용하여 트리 구조 데이터의 차이를 없애고 그것을 처리했다.그리고 나는 이것이 완전히 불필요하다는 것을 깨달았다. antdTree component를 사용한 후deepdash 사실상 첫 번째 단계는 전혀 필요없었다.

The following code is implemented by TypeScript, it is better to know TypeScript type manipulation

사실상 트리 구조 데이터는 매우 간단한 인터페이스 (interface)로 추상화할 수 있다

interface Node {
  id: string
  children: Node[]
}

다만 업무 중에는 몇 개의 필드가 있는데, 이 두 필드의 명칭은 다르다.
예를 들어, 시스템 메뉴 및 시스템 권한

interface SysMenu {
  id: number // menu id
  name: string // the name to be displayed
  sub: SysMenu[] // sub-level menu
}

interface SysPermission {
  uid: string // System unique uuid
  label: string // The name of the menu to be displayed
  children: SysPermission[] // sub permissions
}

보시다시피, 그것들은 모두 id 필드와 children 필드가 있지만, 명칭만 다르다.그런 다음 패키지가 변경되지 않은 부분을 그대로 유지하고 변경된 부분을 외부에서 가져오는 패키지의 원칙에 따라 두 필드가 외부에서 지정됩니다.

조작하다
그렇다면 트리 구조에서 어떤 조작을 사용할 수 있습니까?

reduce 합병

each 스트리밍

map 매핑

filter 필터

treeToList 나열할 트리

listToTree 트리에 목록

그러나 내가 현재 사용하고 있는 유일한 것은 each/map/filter/treeToList이기 때문에 나는 먼저 다음과 같은 내용을 실현할 것이다.

일반 트리 구조에 필요한 매개변수 유형 정의하기
트리 구조에 id/children가 포함되어야 하는 경우 트리 구조 작업에 대한 일반 매개변수를 정의할 수 있습니다.

export interface TreeOption<T extends object> {
  /**
   * A uniquely identified field
   */
  id: keyof T
  /**
   * Field for child nodes
   */
  children: keyof T
}

위의 인터페이스는 트리 노드 정보를 쉽게 읽을 수 있도록 id/children 필드 이름을 설명해야 합니다.

Thanks to TypeScript, without it it would be impossible to define types and check for subtle errors in the code. Java, for example, has difficulty defining reflection-related types, and usually has to use String.

수형도
다음 treeMap 구현은 사실상 귀속 함수입니다.

import { TreeOption } from '. /treeOption'

/**
 * Tree structure mapping
 * Using depth-first algorithm
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeMap<
  T extends object,
  C extends TreeOption<T>,
  F extends (
    t: Omit<T, C['children']> & Record<C['children'], ReturnType<F>[]>,
    path: T[C['id']][],
  ) => object
>(nodeList: T[], fn: F, options: C): ReturnType<F>[] {
  function inner(nodeList: T[], parentPath: T[C['id']][]): any {
    return nodeList.map((node) => {
      const path = [. .parentPath, node[options.id]]
      const children = (node[options.children] as any) as T[]
      if (!children) {
        return fn(node as any, path)
      }
      return fn(
        {
          ... . node,
          [options.children]: inner(children, path),
        },
        path,
      )
    })
  }

  return inner(nodeList, [])
}

그런데 조심하는 분들은 여기 두 가지 이상한 조작이 있다는 걸 아실 거예요.

먼저 모든 하위 노드를 처리한 다음에 처리된 하위 노드를 반사 함수에 전달하는 것이지 반대로 전달하는 것이 아니다.-이는 JSX 프런트엔드 프레임워크 react와 실제로 호환되기 위한 것입니다.

노드의 path를 계산하여 매핑 함수에 넣는다. -이것은 현재 노드와 차원 구조의 모든 부 노드를 이해하기 위해 필요할 때(예를 들어 목록으로 변환) 이 관건적인 정보를 얻을 수 있도록 한다.

트리 필터
다음 함수는 treeMap 기반(#grin)

import { TreeOption } from '. /treeOption'
import { treeMap } from '. /treeMap'

/**
 * Filter a list of tree nodes
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeFilter<T extends object, C extends TreeOption<T>>(
  nodeList: T[],
  fn: (t: T, path: T[C['id']][]) => boolean,
  options: C,
): T[] {
  return treeMap(
    nodeList,
    (node: any, path) => {
      const children = (node[options.children] as any) as T[] | undefined
      // if it's the wrong node just blow it up
      if (!fn(node as T, path)) {
        return null
      }
      //return if it is a leaf node
      if (!children) {
        return node
      }
      //count all children nodes that are not null
      const sub = children.filter((node) => node ! == null)
      //If all children are null, blow them up
      if (sub.length === 0) {
        return null
      }
      return {
        ... . node,
        children: sub,
      }
    },
    options,
  ).filter((node) => node ! == null)
}

상기 필터의 흐름도
! treeFilter flowchart.drawio

originalDrawio

수풀
마찬가지로 TreeMap을 기반으로 한 것은 사실상 좀 평범하다.

import { TreeOption } from '. /treeOption'
import { treeMap } from '. /treeMap'

/**
 * Tree structure mapping
 * Use depth-first algorithm
 * @param nodeList
 * @param fn
 * @param options
 */
export function treeEach<T extends object, C extends TreeOption<T>>(
  nodeList: T[],
  fn: (t: T, path: T[C['id']][]) => void,
  options: C,
) {
  treeMap(
    nodeList,
    (node, path) => {
      fn(node as T, path)
      return node
    },
    options,
  )
}

수목학자
동상 1

import { TreeOption } from '. /treeOption'
import { treeEach } from '. /treeEach'

/**
 * Flatten a list of tree nodes
 * @param nodeList
 * @param options
 */
export function treeToList<
  T extends object,
  C extends TreeOption<T> & { path: string },
  R extends T & { [K in C['path']]: NonNullable<T[C['id']]>[] }
>(nodeList: T[], options: C): R[] {
  const res: R[] = []
  treeEach(
    nodeList,
    (node, path) => {
      res.push({ . . node, [options.path]: path } as R)
    },
    options,
  )
  return res
}

FAQ
그래서 진흙 속에 존재할 수 있는 질문이 있습니다. 저는 여기서 대답할 것입니다. 다른 질문이 있으면 아래에서 직접 논평할 수 있습니다.
물음: 왜 사용하지 않습니까?A:lodash에 의존하고 API가 좀 복잡하기 때문입니다.질문: 왜 깊이 우선 알고리즘을 사용합니까?

답:react 등 웹 프레임워크와 호환되어야 하기 때문에 모든 JSX 하위 노드는 부모 노드에 계산하여 전달해야 한다.

문: 왜 순환이 아닌 순환을 사용합니까?

답: 이건 순전히 개인적인 취향이에요.순환은 더 좋은 성능을 제공하지만 대부분의 경우 성능이 중요하지 않기 때문에 나는 더욱 직관적인 귀속을 사용한다.

: TypeScript를 사용하는 이유는 무엇입니까?

답: TypeScript의 유형 시스템은 코드 사용자에게 더욱 친밀하고 유지보수하기 쉽기 때문에-그러나 TypeScript의 유형 시스템은 너무 복잡하기 때문에 초보자에게 그다지 우호적이지 않다. 참고deepdash

Finally, I have created a module @liuli-util/tree that already contains the above functionality.