结构树计算

lyh

2025-03-06 62211b786eaaf8304ef30d8dad7917118f293528

结构树计算

 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
                ));

        // è½¬æ¢ä¸º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(), 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; }
    }
}