package com.kcim.common.util;

/**
 * @program: CostAccount
 * @description:
 * @author: Wang.YS
 * @create: 2024-08-13 18:28
 **/


import org.springframework.util.CollectionUtils;
import org.springframework.util.StringUtils;

import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

/**
 * 获取树深度
 * 注：若最深一层只有null元素，该层不计入深度
 */
public class TreeDepthUtil {
    private static final Byte FLAG = 1;

    /**
     * dfs的递归实现获取树深度
     *
     * @param root       根节点
     * @param childField 子节点列表字段名称
     * @param <T>        节点类型
     * @return 树深度
     */
    public static <T> int getTreeDepthByDfsWithRecursion(T root, String childField) {
        if (root == null || !StringUtils.hasText(childField)) {
            return 0;
        }
        List<Integer> depth = new ArrayList<>(1);
        depth.add(0);
        // 这里只是需要一个标志，表示当前路径上的点，所以用byte减少内存占用
        Stack<Byte> stack = new Stack<>();
        doGetTreeDepthByDfs(root, childField, stack, depth);
        return depth.get(0);
    }

    private static <T> void doGetTreeDepthByDfs(T parent, String childField, Stack<Byte> stack, List<Integer> depth) {
        stack.push(FLAG);
        depth.set(0, Math.max(depth.get(0), stack.size()));
        Collection<T> childs = (Collection<T>) getFieldValue(parent, childField);
        if (CollectionUtils.isEmpty(childs)) {
            stack.pop();
            return;
        }
        for (T child : childs) {
            if (child == null) {
                continue;
            }
            doGetTreeDepthByDfs(child, childField, stack, depth);
        }
        stack.pop();
    }

    /**
     * dfs的非递归（循环）实现获取树深度
     *
     * @param root       根节点
     * @param childField 子节点列表字段名称
     * @param <T>        节点类型
     * @return 树深度
     */
    public static <T> int getTreeDepthByDfsWithLoop(T root, String childField) {
        if (root == null || !StringUtils.hasText(childField)) {
            return 0;
        }
        Stack<Iterator> stack = new Stack<>();
        List<T> list = new ArrayList<>();
        list.add(root);
        Iterator<T> iterator = list.iterator();
        Iterator<T> emptyIterator = (Iterator<T>) Collections.emptyList().iterator();
        int depth = 0;
        while (true) {
            while (!iterator.hasNext() && !stack.isEmpty()) {
                iterator = stack.pop();
            }
            if (!iterator.hasNext() && stack.isEmpty()) {
                break;
            }
            stack.push(iterator);
            depth = Math.max(depth, stack.size());
            T next = iterator.next();
            Collection<T> childs = (Collection<T>) getFieldValue(next, childField);
            if (childs != null) {
                childs = childs.stream().filter(o -> o != null).collect(Collectors.toList());
            }
            iterator = childs == null ? emptyIterator : childs.iterator();
        }
        return depth;
    }

    /**
     * bfs的递归实现获取树深度
     *
     * @param root       根节点
     * @param childField 子节点列表字段名称
     * @param <T>        节点类型
     * @return 树深度
     */
    public static <T> int getTreeDepthByBfsWithRecursion(T root, String childField) {
        if (root == null || !StringUtils.hasText(childField)) {
            return 0;
        }
        List<T> parents = new ArrayList<>();
        parents.add(root);
        List<Integer> depth = new ArrayList<>(1);
        depth.add(0);
        doGetTreeDepthByBfs(parents, childField, depth);
        return depth.get(0);
    }

    private static <T> void doGetTreeDepthByBfs(Collection<T> parents, String childField, List<Integer> depth) {
        if (parents.isEmpty()) {
            return;
        }
        depth.set(0, depth.get(0) + 1);
        readChilds(parents, childField);
        doGetTreeDepthByBfs(parents, childField, depth);
    }

    /**
     * bfs的非递归（循环）实现获取树深度
     *
     * @param root       根节点
     * @param childField 子节点列表字段名称
     * @param <T>        节点类型
     * @return 树深度
     */
    public static <T> int getTreeDepthByBfsWithLoop(T root, String childField) {
        if (root == null || !StringUtils.hasText(childField)) {
            return 0;
        }
        List<T> parents = new ArrayList<>();
        parents.add(root);
        int depth = 0;
        while (!parents.isEmpty()) {
            depth++;
            readChilds(parents, childField);
        }
        return depth;
    }


    private static <T> void readChilds(Collection<T> parents, String childField) {
        List<T> allChilds = new ArrayList<>();
        for (T parent : parents) {
            Collection<T> childs = (Collection<T>) getFieldValue(parent, childField);
            if (childs == null) {
                continue;
            }
            allChilds.addAll(childs.stream().filter(o -> o != null).collect(Collectors.toList()));
        }
        parents.clear();
        parents.addAll(allChilds);
    }

    /**
     * 获取字段值
     *
     * @param element   待获取值的对象
     * @param fieldName 字段名称
     * @param <T>       对象类型
     * @return 字段值
     */
    private static <T> Object getFieldValue(T element, String fieldName) {
        try {
            Field field = element.getClass().getDeclaredField(fieldName);
            field.setAccessible(true);
            return field.get(element);
        } catch (IllegalAccessException exception) {
            throw new RuntimeException("no permission to read field [" + fieldName + "]!");
        } catch (NoSuchFieldException e) {
            throw new RuntimeException("field [" + fieldName + "] not exists!");
        }
    }
}
