-
Notifications
You must be signed in to change notification settings - Fork 5
/
TreeUtils.java
210 lines (197 loc) · 8.96 KB
/
TreeUtils.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
package com.example.demo.util;
import com.example.demo.bean.TestTreeObj;
import org.apache.commons.collections4.CollectionUtils;
import java.util.*;
import java.util.function.BiConsumer;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.function.Predicate;
;
/**
* 树和平铺相关工具类
*
* @author 876651109@qq.com
* @date 2021/3/1 8:21 下午
*/
public class TreeUtils {
public static void main(String[] args) {
List<TestTreeObj> list = new ArrayList<TestTreeObj>() {{
add(TestTreeObj.builder().id(1).build());
add(TestTreeObj.builder().id(11).pid(1).build());
add(TestTreeObj.builder().id(12).pid(1).build());
add(TestTreeObj.builder().id(111).pid(11).build());
add(TestTreeObj.builder().id(112).pid(11).build());
add(TestTreeObj.builder().id(121).pid(12).build());
add(TestTreeObj.builder().id(122).pid(12).build());
add(TestTreeObj.builder().id(2).build());
add(TestTreeObj.builder().id(21).pid(2).build());
add(TestTreeObj.builder().id(22).pid(2).build());
add(TestTreeObj.builder().id(211).pid(21).build());
add(TestTreeObj.builder().id(212).pid(21).build());
add(TestTreeObj.builder().id(221).pid(22).build());
add(TestTreeObj.builder().id(222).pid(22).build());
}};
List<TestTreeObj> treeResult = listToTree(list, TestTreeObj::setTestTreeObj, TestTreeObj::getId, TestTreeObj::getPid, (l) -> l.getPid() == 0);
List<TestTreeObj> testTreeObjs = new ArrayList<TestTreeObj>() {{
add(TestTreeObj.builder().id(1).testTreeObj(new ArrayList<TestTreeObj>() {{
add(TestTreeObj.builder().id(11).testTreeObj(new ArrayList<TestTreeObj>() {{
add(TestTreeObj.builder().id(111).build());
add(TestTreeObj.builder().id(112).build());
}}).build());
}}).build());
}};
List<TestTreeObj> result = new ArrayList<>();
treeToListDeep(testTreeObjs, result, TestTreeObj::getTestTreeObj, (l) -> l.getTestTreeObj() == null);
List<TestTreeObj> result2 = new ArrayList<>();
treeToListDeep(testTreeObjs, result2, TestTreeObj::getTestTreeObj, (l) -> l.getPid() == 0);
System.out.println(result2);
System.out.println("loopTree示例过滤出以1结尾的id");
List<TestTreeObj> filterResult = new ArrayList<>();
loopTree(testTreeObjs, TestTreeObj::getTestTreeObj, s -> {
if (String.valueOf(s.getId()).endsWith("1")) {
filterResult.add(s);
}
});
System.out.println(filterResult.size());
}
/**
* 树转平铺
* treeToListDeep(testTreeObjs, result, TestTreeObj::getTestTreeObj, (l) -> l.getTestTreeObj() == null);
*
* @param source 源数据
* @param target 目标容器
* @param childListFn 递归调用方法
* @param addTargetCondition 添加到容器的判断方法
* @author 876651109@qq.com
* @date 2021/3/1 8:19 下午
*/
public static <F> void treeToListDeep(List<F> source, List<F> target, Function<F, List<F>> childListFn, Predicate<F> addTargetCondition) {
loopTree(source, childListFn, (l) -> {
if (addTargetCondition.test(l)) {
target.add(l);
}
});
}
public static <F> void treeToListDeep(List<F> source, Function<F, List<F>> childListFn, Predicate<F> addTargetCondition) {
treeToListDeep(source, new ArrayList<>(), childListFn, addTargetCondition);
}
/**
* List<TestTreeObj> treeResult = listToTree(list, TestTreeObj::setTestTreeObj, TestTreeObj::getId, TestTreeObj::getPid, (l) -> l.getPid() == 0);
*
* @param source 源数据
* @param setChildListFn 设置递归的方法
* @param idFn 获取id的方法
* @param pidFn 获取父id的方法
* @param getRootCondition 获取根节点的方法
* @return {@link List<F>}
* @author 876651109@qq.com
* @date 2021/3/1 8:18 下午
*/
public static <F, T> List<F> listToTree(List<F> source, BiConsumer<F, List<F>> setChildListFn, Function<F, T> idFn, Function<F, T> pidFn, Predicate<F> getRootCondition) {
return listToTree(source, setChildListFn, idFn, pidFn, getRootCondition, null);
}
/**
* 复杂形式，进行listen回调,用流式写法可以与外界交互
* (idx,obj)->{System.out.println(123);},idx是从0开始的层级
*
* @param listen 回调函数
* @author seal 876651109@qq.com
* @date 2021/6/3 7:46 下午
*/
public static <F, T> List<F> listToTree(List<F> source, BiConsumer<F, List<F>> setChildListFn, Function<F, T> idFn, Function<F, T> pidFn, Predicate<F> getRootCondition, BiConsumer<Integer, F> listen) {
List<F> tree = new ArrayList<>();
Map<T, List<F>> map = new HashMap<>(source.size());
for (F f : source) {
if (getRootCondition.test(f)) {
tree.add(f);
} else {
List<F> tempList = map.getOrDefault(pidFn.apply(f), new ArrayList<>());
tempList.add(f);
map.put(pidFn.apply(f), tempList);
}
}
tree.forEach(l -> assembleTree(l, map, setChildListFn, idFn, listen, 0));
return tree;
}
/**
* 组装树
*/
private static <F, T> void assembleTree(F current, Map<T, List<F>> map, BiConsumer<F, List<F>> setChildListFn, Function<F, T> idFn, BiConsumer<Integer, F> listen, int idx) {
List<F> fs = map.get(idFn.apply(current));
setChildListFn.accept(current, fs);
if (CollectionUtils.isNotEmpty(fs)) {
fs.forEach(l -> assembleTree(l, map, setChildListFn, idFn, listen, idx + 1));
}
if (listen != null) {
listen.accept(idx, current);
}
}
/**
* 树的简易递归,listen会回调当前对象
*
* @param source 源数据
* @param childListFn get方法
* @param listen 回调函数
* @author seal 876651109@qq.com
* @date 2021/6/5 16:47
*/
public static <F> void loopTree(List<F> source, Function<F, List<F>> childListFn, Consumer<F> listen) {
loopTree(source, childListFn, listen, null);
}
public static <F> void loopTree(List<F> source, Function<F, List<F>> childListFn, Consumer<F> preListen, Consumer<F> postFun) {
if (CollectionUtils.isEmpty(source)) {
return;
}
source.forEach(l -> {
Optional.ofNullable(preListen).ifPresent(s -> s.accept(l));
loopTree(childListFn.apply(l), childListFn, preListen, postFun);
Optional.ofNullable(postFun).ifPresent(s -> s.accept(l));
});
}
/**
* 与listToTree功能一致，但是前方法循环两次，该方法利用递归只循环一次，用空间换时间的方式
*
* @return
*/
public static <T, K> List<T> buildTree(List<T> dataList, int index, Map<K, T> dataMap,
Function<T, K> idFn,
Function<T, K> pIdFn,
Function<T, List<T>> getChildFn,
BiConsumer<T, List<T>> setChildFn,
Predicate<K> predicate) {
List<T> resultList = new ArrayList<>(dataList.size());
while (index < dataList.size()) {
T item = dataList.get(index);
dataMap.put(idFn.apply(item), item);
K pId = pIdFn.apply(item);
if (predicate.test(pId)) {
resultList.add(item);
} else {
T parent = dataMap.get(pId);
//为null表示还没被循环到父级,则递归，再次循环剩下的部分
if (Objects.isNull(parent)) {
index += 1;
List<T> list = buildTree(dataList, index, dataMap, idFn, pIdFn, getChildFn, setChildFn, predicate);
parent = dataMap.get(pId);
// 如果为null 表示列表没有父级，自动升级为顶节点
if (Objects.isNull(parent)) {
resultList.add(item);
} else {
List<T> childList = Optional.ofNullable(getChildFn.apply(parent)).orElse(new ArrayList<>());
childList.add(item);
setChildFn.accept(parent, childList);
}
if (list.size() != 0) {
resultList.addAll(list);
}
} else {
List<T> childList = Optional.ofNullable(getChildFn.apply(parent)).orElse(new ArrayList<>());
childList.add(item);
setChildFn.accept(parent, childList);
}
}
index += 1;
}
return resultList;
}
}