KprAlamBizPlugin/src/main/java/com/shkpr/service/alambizplugin/components/checker/IsolatedLinesFinder.java

package com.shkpr.service.alambizplugin.components.checker;


import com.global.base.log.LogLevelFlag;
import com.global.base.log.LogPrintMgr;
import com.shkpr.service.alambizplugin.commtools.BeanUtil;
import com.shkpr.service.alambizplugin.components.AsyncResultManager;
import com.shkpr.service.alambizplugin.constants.GisSurveySystemCheckKeys;
import com.shkpr.service.alambizplugin.constants.GisSurveySystemCheckResultHead;
import com.shkpr.service.alambizplugin.constants.LogFlagBusiType;
import com.shkpr.service.alambizplugin.dto.GisSurveyLayerApplyLine;
import com.shkpr.service.alambizplugin.dto.GisSurveySystemCheckElement;
import com.shkpr.service.alambizplugin.dto.GisSurveySystemCheckId;
import com.shkpr.service.alambizplugin.dto.GisSurveySystemCheckResultDetail;
import org.springframework.scheduling.annotation.Async;
import org.springframework.scheduling.annotation.AsyncResult;
import org.springframework.stereotype.Component;
import org.springframework.util.concurrent.ListenableFuture;

import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 孤立线查找
 *
 * @author 欧阳劲驰
 * @since 1.0.0
 */
@Component
public class IsolatedLinesFinder {
    /**
     * log
     */
    private final String mStrClassName;
    private final String mBizType;
    private final AsyncResultManager asyncResultManager;

    public IsolatedLinesFinder(AsyncResultManager asyncResultManager) {
        mStrClassName = "IsolatedLinesFinder";
        mBizType = LogFlagBusiType.BUSI_GIS_SURVEY.toStrValue();
        this.asyncResultManager = asyncResultManager;
    }

    /**
     * 寻找孤立线
     *
     * @param lines 线集合
     * @return 线分组
     */
    @Async
    public ListenableFuture<GisSurveySystemCheckResultDetail> findIsolatedLines(List<GisSurveyLayerApplyLine> lines
            , GisSurveySystemCheckId systemCheckId) throws InterruptedException {
        LogPrintMgr.getInstance().printLogMsg(LogLevelFlag.LOG_INFO, mBizType, mStrClassName, "开始执行寻找孤立线========>");
        long begin = System.currentTimeMillis();

        //创建并查集
        UnionFind unionFind = new UnionFind();
        //分组线
        List<List<GisSurveySystemCheckElement>> groupElements = unionFind.groupLines(lines);

        return new AsyncResult<>(createResult(groupElements, systemCheckId, begin));
    }

    /**
     * 创建结果
     *
     * @param data          数据
     * @param systemCheckId 系统检查id
     * @param begin         开始时间
     * @return 结果
     */
    private GisSurveySystemCheckResultDetail createResult(List<List<GisSurveySystemCheckElement>> data
            , GisSurveySystemCheckId systemCheckId, long begin) {
        long end = System.currentTimeMillis();
        LogPrintMgr.getInstance().printLogMsg(LogLevelFlag.LOG_INFO, mBizType, mStrClassName
                , String.format(
                        "结束执行寻找孤立线,用时(毫秒):%d"
                        , (end - begin)
                )
        );

        //数据大小
        final int size = data.size();
        //结果flag
        final String FLAG = systemCheckId.getFlag();
        //写入json和excel结果
        Path jsonPath = asyncResultManager.writeJson(data, FLAG, GisSurveySystemCheckKeys.ISOLATED_LINES + ".json");
        Path excelPath = asyncResultManager.writeExcel(GisSurveySystemCheckResultHead.ISOLATED_LINES,
                buildExcel(data), FLAG, GisSurveySystemCheckKeys.ISOLATED_LINES + ".xlsx");

        //构建结果
        return new GisSurveySystemCheckResultDetail(true
                , FLAG + "/" + jsonPath.getFileName()
                , FLAG + "/" + excelPath.getFileName()
                , size);
    }

    /**
     * 构建excel数据
     *
     * @param data 数据
     * @return excel数据
     */
    private List<Map<String, Object>> buildExcel(List<List<GisSurveySystemCheckElement>> data) {
        return IntStream.range(0, data.size())
                .boxed()
                .flatMap(i -> data.get(i).stream().map(element -> {
                    Map<String, Object> map = new HashMap<>();
                    map.put(GisSurveySystemCheckResultHead.KEYS.GROUP_NAME, i + 1);
                    map.put(GisSurveySystemCheckResultHead.KEYS.UP_NO, element.getUpNo());
                    map.put(GisSurveySystemCheckResultHead.KEYS.DOWN_NO, element.getDownNo());
                    map.put(GisSurveySystemCheckResultHead.KEYS.CODE, element.getCode());
                    map.put(GisSurveySystemCheckResultHead.KEYS.UP_NODE, element.getUpNode());
                    map.put(GisSurveySystemCheckResultHead.KEYS.DOWN_NODE, element.getDownNode());
                    map.put(GisSurveySystemCheckResultHead.KEYS.NAME, element.getName());
                    return map;
                })).collect(Collectors.toList());
    }

    /**
     * 并查集
     */
    public static class UnionFind {
        //线的子父关系,key:子,value:父(可能为根)
        private final Map<String, String> parent = new HashMap<>();
        //点根线关系,{线的节点编码}->{根线编码}
        private final Map<String, String> pointRoot = new HashMap<>();
        //秩,通常树的根节点为1
        private final Map<String, Integer> rank = new HashMap<>();

        /**
         * 线分组
         *
         * @param lines 线集合
         * @return 分组集合
         */
        public List<List<GisSurveySystemCheckElement>> groupLines(List<GisSurveyLayerApplyLine> lines) throws InterruptedException {
            //处理所有线
            for (GisSurveyLayerApplyLine line : lines) {
                //响应中断
                if (Thread.interrupted()) throw new InterruptedException();
                //初始化节点
                initNode(line.getCode());
                //当前code
                String currentRoot = line.getCode();
                //处理起点,合并当前线与以upNode为终点的根线
                if (pointRoot.containsKey(line.getUpNode())) {
                    String existingRoot = pointRoot.get(line.getUpNode());
                    currentRoot = unionAndGetRoot(currentRoot, existingRoot);
                }
                //处理终点,合并当前线与以downNode为终点的根线
                if (pointRoot.containsKey(line.getDownNode())) {
                    String existingRoot = pointRoot.get(line.getDownNode());
                    currentRoot = unionAndGetRoot(currentRoot, existingRoot);
                }
                //更新当前节点的根线映射
                updateRootMappings(line.getUpNode(), currentRoot);
                updateRootMappings(line.getDownNode(), currentRoot);
            }
            //清理关系表
            pointRoot.clear();
            //构建分组结果
            Map<String, List<GisSurveySystemCheckElement>> groups = new HashMap<>();
            for (GisSurveyLayerApplyLine line : lines) {
                //响应中断
                if (Thread.interrupted()) throw new InterruptedException();
                //当前线code
                String lineCode = line.getCode();
                //根线code
                String rootCode = findRoot(lineCode);
                //当前线存入根线组
                groups.computeIfAbsent(rootCode, k -> new ArrayList<>())
                        //转为返回元素
                        .add(BeanUtil.copy(line, GisSurveySystemCheckElement.class));
            }

            //分组结果值集合
            Collection<List<GisSurveySystemCheckElement>> groupValues = groups.values();
            //排除1组数据
            if (groupValues.size() == 1) groupValues = Collections.emptyList();

            return new ArrayList<>(groupValues);
        }

        /**
         * 更新节点对应的根线映射
         *
         * @param node        节点
         * @param currentRoot 当前节点的根线
         */
        private void updateRootMappings(String node, String currentRoot) throws InterruptedException {
            //获取点根线关系,如存在该关系,则再寻找一次根线,保证多点根一致
            String existingRoot = pointRoot.get(node);
            if (existingRoot != null) currentRoot = unionAndGetRoot(currentRoot, existingRoot);
            //更新点根线关系
            pointRoot.put(node, currentRoot);
        }

        /**
         * 初始化节线
         *
         * @param code 节点code
         */
        public void initNode(String code) {
            parent.computeIfAbsent(code, k -> {
                rank.put(k, 0);
                return k;
            });
        }

        /**
         * 查找根节点
         *
         * @param code 节点code
         * @return 根节点code
         */
        public String findRoot(String code) throws InterruptedException {
            //当前code
            String current = code;
            //最大迭代深度(该算法时间为常数级,如查找深度到64则为程序异常)
            int maxIterationsDepth = 64;
            //迭代记录,防止无限递归
            int iterations = 0;
            while (iterations++ < maxIterationsDepth) {
                //响应中断
                if (Thread.interrupted()) throw new InterruptedException();
                //提取父节点
                String parentNode = parent.get(current);
                // 找到根节点立即返回
                if (parentNode.equals(current)) return current;
                //当前节点指向祖父节点,路径减半(已知子父关系,故跳过)
                String grandparent = parent.get(parentNode);
                parent.put(current, grandparent);
                current = grandparent;
            }
            //递归保险,最终强制验证是否为根节点,否则结束查找
            if (parent.get(current).equals(current)) return current;
            else throw new IllegalStateException("该code无法查询到根节点: " + code);
        }

        /**
         * 合并并返回根线
         *
         * @param current 当前线
         * @param target  目标线
         * @return 根线
         */
        public String unionAndGetRoot(String current, String target) throws InterruptedException {
            //获取两线的根线
            String rootCurrent = findRoot(current);
            String rootTarget = findRoot(target);
            //排除根线相同
            if (rootCurrent.equals(rootTarget)) return rootCurrent;
            //按秩合并,如 当前线根节点秩 大于 目标线根节点秩,则 目标线根线 为 当前线根线 的下游线
            if (rank.get(rootCurrent) > rank.get(rootTarget)) {
                parent.put(rootTarget, rootCurrent);
                return rootCurrent;
            } else {
                //否则 当前线根线 为 目标线根线 的下游线
                parent.put(rootCurrent, rootTarget);
                //如线秩相同,则对根线升秩
                if (rank.get(rootCurrent).equals(rank.get(rootTarget))) {
                    rank.put(rootTarget, rank.get(rootTarget) + 1);
                }
                return rootTarget;
            }
        }
    }
}