Scenarios
There are some situations in front-end projects where you need to handle tree-structured data. (A year) ago I wrote an article about it, but now, I have a better solution.
Thinking
Previously I used Proxy to smooth out the differences in tree-structured data and then process it. Then I realized that this is totally redundant, and after using antd's Tree component, deepdash, indeed the first step is totally unnecessary.
The following code is implemented by TypeScript, it is better to know TypeScript type manipulation
In fact, the tree structure data can be abstracted to a very simple interface (interface)
interface Node {
id: string
children: Node[]
}
It's just that there are some more fields in the business, and the two fields have different names.
For example, system menu and system permissions
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
}
As you can see, they both have id
and children
fields, just with different names. Then, according to the encapsulation principle of encapsulating the parts that remain the same and leaving the parts that change to external input, these two fields are then specified externally.
Operations
So, what operations are available in the tree structure?
-
reduce
merge -
each
traverses -
map
mapping -
filter
filtering -
treeToList
tree to list -
listToTree
list to tree
However, the only thing I'm currently using is each/map/filter/treeToList
, so I'll implement the following first.
Define the mandatory parameter types required for a generic tree structure
If the tree structure must contain id/children
, then this can be used to define generic parameters for tree structure operations.
export interface TreeOption<T extends object> {
/**
* A uniquely identified field
*/
id: keyof T
/**
* Field for child nodes
*/
children: keyof T
}
The above is an interface that must declare what the field name of id/children
is, to make it easier for the internal implementation to read tree node information.
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
The following implementation of treeMap is actually a recursive function.
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, [])
}
But those who are careful may have noticed that two strange operations are done here
- all child nodes are processed first, and then the processed child nodes are passed into the map function instead of the other way around. -- this is actually to be compatible with the JSX front-end framework react.
- compute the
path
of the node and throw it into the map function. -- This is to make it easy to know all the parents of the current node and the hierarchy, so that you can get this key information when you need it (e.g. to convert to a list).
treeFilter
Well, the following functions will be based on the treeMap implementation (#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)
}
Flowchart of the above filter
treeEach
Again, based on treeMap, this is actually a bit lackluster.
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,
)
}
treeToList
Same as above.
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
So, here are some questions that may exist in the mud, I'll answer them here, if you have other questions, you can comment directly below.
- Q: Why not use deepdash?
- A: Because it relies on lodash and the API provided is a bit complicated.
- Q: Why use the depth-first algorithm?
- A: Because of the need to be compatible with web frameworks such as react, where all JSX children need to be computed and passed to the parent node.
- Q: Why do you use recursion instead of loops?
- A: This is purely a personal preference. Loops provide better performance, but in most cases, performance is not important, so I use the more intuitive recursion.
- Q: Why use the TypeScript implementation?
- A: Because TypeScript's type system is more user-friendly and more maintainable for code users. -- but because TypeScript's type system is too complex, so it is not very friendly to newcomers, see TypeScript Type Programming
Finally, I have created a module @liuli-util/tree that already contains the above functionality.
Top comments (0)