From 62211b786eaaf8304ef30d8dad7917118f293528 Mon Sep 17 00:00:00 2001
From: lyh <925863403@qq.com>
Date: 星期四, 06 三月 2025 16:41:57 +0800
Subject: [PATCH] 结构树计算
---
lxzn-module-dnc/src/main/java/org/jeecg/modules/dnc/utils/TreeBuilder.java | 181 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 181 insertions(+), 0 deletions(-)
diff --git a/lxzn-module-dnc/src/main/java/org/jeecg/modules/dnc/utils/TreeBuilder.java b/lxzn-module-dnc/src/main/java/org/jeecg/modules/dnc/utils/TreeBuilder.java
new file mode 100644
index 0000000..fed3ea5
--- /dev/null
+++ b/lxzn-module-dnc/src/main/java/org/jeecg/modules/dnc/utils/TreeBuilder.java
@@ -0,0 +1,181 @@
+package org.jeecg.modules.dnc.utils;
+
+import it.unimi.dsi.fastutil.longs.*;
+import org.jeecg.modules.dnc.entity.ProductMix;
+
+import java.util.*;
+import java.util.concurrent.*;
+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
+ ));
+
+ // 杞崲涓篎astUtil缁撴瀯浠ヤ紭鍖栧唴瀛�
+ 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() + " 鐖禝D=" + 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(), 0));
+
+ // 3. 璁＄畻鍏ュ害
+ nodes.forEach(node -> {
+ if (node.getParentId() != 0 && nodeMap.containsKey(node.getParentId())) {
+ inDegree.put(node.getId(), 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()
+ );
+ 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; }
+ }
+}
\ No newline at end of file
--
Gitblit v1.9.3