package org.jeecg.modules.dnc.utils;
|
|
import it.unimi.dsi.fastutil.longs.Long2IntMap;
|
import it.unimi.dsi.fastutil.longs.Long2IntOpenHashMap;
|
import it.unimi.dsi.fastutil.longs.Long2ObjectMap;
|
import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
|
import org.jeecg.modules.dnc.entity.ProductMix;
|
|
import java.util.*;
|
import java.util.concurrent.ConcurrentHashMap;
|
import java.util.concurrent.ConcurrentLinkedQueue;
|
import java.util.stream.Collectors;
|
|
public class TreeBuilder {
|
//========================= 数据预处理 =========================//
|
public CleanResult preprocessData(List<ProductMix> rawList) {
|
// 阶段1：构建线程安全的节点映射
|
ConcurrentHashMap<Long, ProductMix> tempMap = (ConcurrentHashMap<Long, ProductMix>) rawList.parallelStream()
|
.collect(Collectors.toConcurrentMap(
|
ProductMix::getId,
|
item -> item,
|
(existing, replacement) -> existing
|
));
|
|
// 转换为FastUtil结构以优化内存
|
Long2ObjectOpenHashMap<ProductMix> nodeMap = new Long2ObjectOpenHashMap<>(tempMap.size());
|
nodeMap.putAll(tempMap);
|
|
// 阶段2：过滤有效节点
|
List<ProductMix> validNodes = rawList.parallelStream()
|
.filter(item -> {
|
if (item.getParentId() == 0) return true; // 根节点直接通过
|
if (!nodeMap.containsKey(item.getParentId())) {
|
System.err.println("无效父节点引用: ID=" + item.getId() + " 父ID=" + item.getParentId());
|
return false;
|
}
|
return true;
|
})
|
.collect(Collectors.toList());
|
|
return new CleanResult(nodeMap, validNodes);
|
}
|
|
//========================= 拓扑排序 =========================//
|
public List<ProductMix> topologicalSort(List<ProductMix> nodes,
|
Long2ObjectMap<ProductMix> nodeMap) {
|
// 防御空数据
|
if (nodes.isEmpty()) return Collections.emptyList();
|
|
// 1. 构建邻接表（父节点 -> 子节点列表）
|
Long2ObjectMap<List<Long>> adjacencyList = new Long2ObjectOpenHashMap<>(nodes.size());
|
nodes.forEach(node -> {
|
Long parentId = node.getParentId();
|
adjacencyList.computeIfAbsent(parentId, k -> new ArrayList<>())
|
.add(node.getId());
|
});
|
|
// 2. 初始化入度计数器
|
Long2IntMap inDegree = new Long2IntOpenHashMap();
|
nodes.forEach(node -> inDegree.put(node.getId().longValue(), 0));
|
|
// 3. 计算入度
|
nodes.forEach(node -> {
|
if (node.getParentId() != 0 && nodeMap.containsKey(node.getParentId())) {
|
inDegree.put(node.getId().longValue(), inDegree.get(node.getId()) + 1);
|
}
|
});
|
|
// 4. 初始化队列
|
Queue<Long> queue = new ConcurrentLinkedQueue<>(
|
nodes.stream()
|
.filter(node -> inDegree.get(node.getId()) == 0)
|
.map(ProductMix::getId)
|
.collect(Collectors.toList())
|
);
|
|
// 5. 拓扑排序核心逻辑
|
List<ProductMix> sorted = new ArrayList<>(nodes.size());
|
while (!queue.isEmpty()) {
|
Long currentId = queue.poll();
|
ProductMix current = nodeMap.get(currentId);
|
sorted.add(current);
|
|
List<Long> children = adjacencyList.getOrDefault(currentId, Collections.emptyList());
|
children.forEach(childId -> {
|
int degree = inDegree.get(childId) - 1;
|
inDegree.put(childId, Integer.valueOf(degree));
|
if (degree == 0) {
|
queue.offer(childId);
|
}
|
});
|
}
|
|
// // 6. 循环检测
|
// if (sorted.size() != nodes.size()) {
|
// handleSortingFailure(nodes, sorted, nodeMap);
|
// return Collections.emptyList();
|
// }
|
return sorted;
|
}
|
|
//========================= 树结构组装 =========================//
|
public List<ProductMix> assembleTree(List<ProductMix> sortedNodes,
|
Long2ObjectMap<ProductMix> nodeMap) {
|
// 1. 创建节点副本
|
Map<Long, ProductMix> treeMap = new ConcurrentHashMap<>(sortedNodes.size());
|
sortedNodes.forEach(node -> {
|
ProductMix newNode = new ProductMix(
|
node.getId(),
|
node.getParentId(),
|
node.getName(),
|
node.getCode(),
|
node.getType(),
|
node.getCreateTime()
|
);
|
treeMap.put(newNode.getId(), newNode);
|
});
|
|
// 2. 建立父子关系
|
sortedNodes.forEach(node -> {
|
if (node.getParentId() != 0) {
|
ProductMix parent = treeMap.get(node.getParentId());
|
if (parent != null) {
|
parent.getChildren().add(treeMap.get(node.getId()));
|
}
|
}
|
});
|
|
// 3. 返回根节点
|
return treeMap.values().stream()
|
.filter(node -> node.getParentId() == 0)
|
.collect(Collectors.toList());
|
}
|
|
//========================= 辅助方法 =========================//
|
private void handleSortingFailure(List<ProductMix> originalNodes,
|
List<ProductMix> sortedNodes,
|
Long2ObjectMap<ProductMix> nodeMap) {
|
// 查找未处理的节点ID
|
Set<Long> processedIds = sortedNodes.stream()
|
.map(ProductMix::getId)
|
.collect(Collectors.toSet());
|
|
List<ProductMix> unprocessed = originalNodes.stream()
|
.filter(node -> !processedIds.contains(node.getId()))
|
.collect(Collectors.toList());
|
|
System.err.println("拓扑排序失败，未处理节点数: " + unprocessed.size());
|
detectCycles(unprocessed, nodeMap);
|
}
|
|
private void detectCycles(List<ProductMix> nodes,
|
Long2ObjectMap<ProductMix> nodeMap) {
|
Set<Long> visited = new HashSet<>();
|
nodes.forEach(node -> {
|
Long currentId = node.getId();
|
Set<Long> path = new LinkedHashSet<>();
|
|
while (currentId != 0) {
|
if (!path.add(currentId)) {
|
System.err.println("循环路径: " + path);
|
return;
|
}
|
ProductMix current = nodeMap.get(currentId);
|
if (current == null) break;
|
currentId = current.getParentId();
|
}
|
visited.addAll(path);
|
});
|
}
|
|
//========================= 数据结构 =========================//
|
public static class CleanResult {
|
private final Long2ObjectMap<ProductMix> nodeMap;
|
private final List<ProductMix> validNodes;
|
|
public CleanResult(Long2ObjectMap<ProductMix> nodeMap,
|
List<ProductMix> validNodes) {
|
this.nodeMap = nodeMap;
|
this.validNodes = validNodes;
|
}
|
|
public Long2ObjectMap<ProductMix> getNodeMap() { return nodeMap; }
|
public List<ProductMix> getValidNodes() { return validNodes; }
|
}
|
}
|
