package com.estate.expert.admin.utils.tree.helper;

import com.estate.expert.admin.utils.tree.TreeNode;
import lombok.extern.slf4j.Slf4j;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;

/**
 * 树的构建器
 *
 * 主要用于从一棵树生成另外一个相同结构的树
 *
 */
@Slf4j
public class TreeHelper {

    /**
     * 构建新树
     *
     * 采用深度优先遍历
     * 自上而下遍历
     * 适合层级树，可以较快的裁剪掉不需要的路径
     */
    public static <T, K> TreeNode<K> convertTree(TreeNode<T> node, NodeConvertor<T, K> convertor, NodeFilter<T> filter) {
        if(!filter.shouldAdd(node))
            return null;

        TreeNode<K> newNode = cloneNode(node);
        newNode.setData(convertor.convert(node, newNode));

        for (TreeNode<T> child : node.getChildren().values()) {
            var newChild = convertTree(child, convertor, filter);
            if(newChild != null)
                newNode.addChild(newChild);
        }
        return newNode;
    }

    /**
     * 单纯转换树，不进行裁剪
     */
    public static <T, K> TreeNode<K> convertTree(TreeNode<T> node, NodeConvertor<T, K> convertor) {
        return convertTree(node ,convertor, (n) -> true);
    }

    /**
     * 裁剪树
     */
    public static <T> TreeNode<T> pruneTree(TreeNode<T> node, NodeFilter<T> filter) {
        return convertTree(node , (n, newNode)->{
            return n.getData();
        }, filter);
    }

    /**
     * 按层级裁剪树
     */
    public static <T> TreeNode<T> pruneTreeByLevels(TreeNode<T> node, List<Integer> levels) {
        // 创建一个新的空节点作为新树的根节点
        TreeNode<T> newRoot = cloneNode(node);
        newRoot.setData(node.getData());

        // 创建一个栈，用于存放当前正在处理的节点路径
        Deque<TreeNode<T>> path = new ArrayDeque<>();
        path.push(newRoot);

        // 使用深度优先搜索遍历原始树
        dfsPrune(node, 0, levels, path);

        return newRoot;
    }

    /**
     * 将路径转换为id
     * @param path 路径
     * @return id
     */
    private static int pathToId(String path){
        var parts = path.split("/");
        int id = 0;
        for(var part : parts){
            if(part.isEmpty())
                continue;
            id = id * 1000 + Integer.parseInt(part);
        }
        return id;
    }

    /**
     * 深度优先搜索裁剪树
     * @param node 节点
     * @param level 层级
     * @param levels 层级列表
     * @param path 路径
     */
    private static <T> void dfsPrune(TreeNode<T> node, int level, List<Integer> levels, Deque<TreeNode<T>> path) {
        if (levels.contains(level)) {
            // 如果当前层级在指定的层级列表中，就复制当前节点到新树中
            TreeNode<T> newNode = cloneNode(node);

            // 由于存在跨层合并的情况，所以需要重新计算id，避免id冲突
            var fullId = pathToId(node.getPath());
            newNode.setId(fullId);
            newNode.setData(node.getData());
            path.peek().addChild(newNode);
            path.push(newNode);
        }

        // 遍历子节点
        for (TreeNode<T> child : node.getChildren().values()) {
            dfsPrune(child, level + 1, levels, path);
        }

        if (levels.contains(level)) {
            // 如果当前层级在指定的层级列表中，就从路径中移除当前节点
            path.pop();
        }
    }

    /**
     * 自下而上遍历树
     * 用于计算结果求解，需要先求解子节点的结果
     */
    public static <T> void travel(TreeNode<T> node, NodeVisitor<T> visitor) {
        if(node == null)
            return;
        for (TreeNode<T> child : node.getChildren().values()) {
            travel(child, visitor);
        }
        visitor.visit(node);
    }

    /**
     * 广度优先遍历树
     * @param node 节点
     * @param visitor 访问器
     */
    public static <T> void bfsTravel(TreeNode<T> node, NodeVisitor<T> visitor){
        var queue = new java.util.LinkedList<TreeNode<T>>();
        queue.add(node);

        while (!queue.isEmpty()){
            var n = queue.poll();
            visitor.visit(n);
            queue.addAll(n.getChildren().values());
        }
    }

    /**
     * 打印树
     * @param node 节点
     */
    public static <T> void printTree(TreeNode<T> node){
        if(node == null)
            return;
        bfsTravel(node, (n) -> {
            log.info("{}", n);
        });
    }

    /**
     * 克隆节点
     * @param node 节点
     * @return 克隆节点
     */
    private static <T, K> TreeNode<K> cloneNode(TreeNode<T> node) {
        TreeNode<K> newNode = new TreeNode<>();
        newNode.setId(node.getId());
        newNode.setPath(node.getPath());
        newNode.setName(node.getName());
        return newNode;
    }

}