Line data Source code
1 : import type { TreeNode } from '@/types/treeExplorerTypes'
2 :
3 8014 : export function buildTree<T>(
4 : items: T[],
5 : key: (item: T) => string[]
6 : ): TreeNode<T> {
7 8014 : const root: TreeNode<T> = {
8 : key: 'root',
9 : label: 'root',
10 : children: []
11 : }
12 :
13 8014 : const map: Record<string, TreeNode<T>> = {
14 : root: root
15 : }
16 :
17 8014 : for (const item of items) {
18 4635307 : const keys = key(item)
19 4635307 : let parent = root
20 4635307 : for (let i = 0; i < keys.length; i++) {
21 16134651 : const k = keys[i]
22 : // 'a/b/c/' represents an empty folder 'c' in folder 'b' in folder 'a'
23 : // 'a/b/c/' is split into ['a', 'b', 'c', '']
24 16134651 : if (k === '' && i === keys.length - 1) break
25 :
26 16134321 : const id = parent.key + '/' + k
27 16134497 : if (!Object.hasOwn(map, id)) {
28 5770070 : const node: TreeNode<T> = {
29 : key: id,
30 : label: k,
31 : leaf: false,
32 : children: []
33 : }
34 5770070 : map[id] = node
35 5770070 : parent.children?.push(node)
36 : }
37 16134321 : parent = map[id]
38 : }
39 4635307 : parent.leaf = keys[keys.length - 1] !== ''
40 4635307 : parent.data = item
41 : }
42 8014 : return root
43 : }
44 :
45 : /**
46 : * If a tree root has exactly one non-leaf child folder, promote that
47 : * folder's children up to the root level, removing the redundant layer.
48 : */
49 507 : export function unwrapTreeRoot<T>(tree: TreeNode<T>): TreeNode<T> {
50 507 : if (
51 : tree.children?.length === 1 &&
52 : !tree.children[0].leaf &&
53 : (tree.children[0].children?.length ?? 0) > 0
54 : ) {
55 259 : return { ...tree, children: tree.children[0].children }
56 : }
57 248 : return tree
58 : }
59 :
60 19799 : export function flattenTree<T>(tree: TreeNode<T>): T[] {
61 19799 : const result: T[] = []
62 19799 : const stack: TreeNode<T>[] = [tree]
63 19799 : while (stack.length) {
64 59074 : const node = stack.pop()!
65 59074 : if (node.leaf && node.data) result.push(node.data)
66 59074 : stack.push(...(node.children ?? []))
67 : }
68 19799 : return result
69 : }
70 :
71 : /**
72 : * Sort the children of the node recursively.
73 : * @param node - The node to sort.
74 : * @param options - The options for sorting.
75 : * @param options.groupLeaf - Whether to group leaf nodes together.
76 : * @returns The sorted node.
77 : */
78 1084 : export function sortedTree<T>(
79 : node: TreeNode<T>,
80 : {
81 : groupLeaf = false
82 : }: {
83 : groupLeaf?: boolean
84 : } = {}
85 : ): TreeNode<T> {
86 1084 : const newNode: TreeNode<T> = {
87 : ...node
88 : }
89 :
90 1084 : if (node.children) {
91 1084 : if (groupLeaf) {
92 : // Split children into folders and files
93 1084 : const folders = node.children.filter((child) => !child.leaf)
94 1084 : const files = node.children.filter((child) => child.leaf)
95 :
96 : // Sort folders and files separately by label
97 1084 : const sortedFolders = folders.sort((a, b) =>
98 : a.label.localeCompare(b.label)
99 : )
100 1084 : const sortedFiles = files.sort((a, b) => a.label.localeCompare(b.label))
101 :
102 : // Recursively sort folder children
103 1084 : newNode.children = [
104 : ...sortedFolders.map((folder) =>
105 : sortedTree(folder, { groupLeaf: true })
106 : ),
107 : ...sortedFiles
108 : ]
109 : } else {
110 : const sortedChildren = [...node.children].sort((a, b) =>
111 : a.label.localeCompare(b.label)
112 : )
113 0 : newNode.children = sortedChildren.map((child) =>
114 : sortedTree(child, { groupLeaf: false })
115 : )
116 : }
117 : }
118 :
119 1084 : return newNode
120 : }
121 :
122 2356 : export const findNodeByKey = <T extends TreeNode>(
123 : root: T,
124 : key: string
125 : ): T | null => {
126 8435 : if (root.key === key) {
127 1757 : return root
128 : }
129 8432 : if (!root.children) {
130 0 : return null
131 : }
132 8430 : for (const child of root.children) {
133 4157 : const result = findNodeByKey(child, key)
134 4157 : if (result) {
135 1765 : return result
136 : }
137 : }
138 4913 : return null
139 : }
140 :
141 : /**
142 : * Deep clone a tree node and its children.
143 : * @param node - The node to clone.
144 : * @returns A deep clone of the node.
145 : */
146 12 : function cloneTree<T extends TreeNode>(node: T): T {
147 12 : const clone = { ...node }
148 :
149 : // Clone children recursively
150 12 : if (node.children && node.children.length > 0) {
151 4 : clone.children = node.children.map((child) => cloneTree(child))
152 : }
153 :
154 12 : return clone
155 : }
156 :
157 : /**
158 : * Merge a subtree into the tree.
159 : * @param root - The root of the tree.
160 : * @param subtree - The subtree to merge.
161 : * @returns A new tree with the subtree merged.
162 : */
163 2356 : export const combineTrees = <T extends TreeNode>(root: T, subtree: T): T => {
164 4 : const newRoot = cloneTree(root)
165 :
166 : const parentKey = subtree.key.slice(0, subtree.key.lastIndexOf('/'))
167 4 : const parent = findNodeByKey(newRoot, parentKey)
168 :
169 4 : if (parent) {
170 4 : parent.children ??= []
171 4 : parent.children.push(cloneTree(subtree))
172 : }
173 :
174 4 : return newRoot
175 : }
|