/**
 *  获取树状结构，如果已经是树状结构，直接返回
 *  @param dataSource
 *  @returns {*[]|*}
 */
export function getTreeData(dataSource: any) {
    if (!dataSource) return []

    if (!Array.isArray(dataSource)) dataSource = [dataSource]

    // 含有children属性，已经是树状结构
    if (dataSource.find((item: any) => !!item.children)) return dataSource

    return convertToTree(dataSource)
}

/**
 *  转换为树状结构
 *  @param rows
 *  @param keyField
 *  @param parentKeyField
 *  @returns {*[]|*}
 */
export function convertToTree(rows: any, keyField = 'id', parentKeyField = 'parentId') {
    if (!rows) return []

    // 拷贝，多次执行修改原始的rows会出问题，指定id，parentId
    rows = rows.map((item: any) => ({ id: item[keyField], parentId: item[parentKeyField], ...item }));

    // 获取所有的顶级节点
    let nodes = rows.filter((item: any) => !rows.find((r: any) => r.id === item.parentId))

    // 存放要处理的节点
    let toDo = [...nodes]

    while (toDo.length) {
        // 处理一个，头部弹出一个
        let node = toDo.shift()
        // 获取子节点
        rows.forEach((child: any) => {
            if (child.parentId === node.id) {
                if (node.children) {
                    node.children.push(child)
                } else {
                    node.children = [child]
                }
                // child加入toDo，继续处理
                toDo.push(child)
            }
        });
    }
    return nodes
}

/**
 *  获取所有的父节点
 *  @param treeData 树状结构数据
 *  @param fieldValue 用于查找的值
 *  @param field 用户查找的键，默认id
 *  @returns {*|[]*}
 */
export function findParentNodes(treeData: any, fieldValue: any, field = 'id') {
    treeData = Array.isArray(treeData) ? treeData : [treeData]

    // 深度遍历查找
    function dfs(data: any, fieldValue: any, parents: any) {
        for (let i = 0; i < data.length; i++) {
            const item = data[i]
            // 找到id则返回父级id
            if (item[field] === fieldValue) return parents
            // children不存在或为空则不递归
            if (!item.children || !item.children.length) return
            // 往下查找时将当前id入栈
            parents.push(item)

            if (dfs(item.children, fieldValue, parents).length) return parents
            // 深度遍历查找未找到当前id，出栈
            parents.pop()
        }
        // 未找到时返回空数组
        return []
    }
    return dfs(treeData, fieldValue, [])
}

/**
 *  查找keys中对应树的叶子节点，如果keys为null或undefined，查找树中所有叶子节点
 *  @param treeData
 *  @param keys
 *  @param keyField
 */
export function findLeafNodes(treeData: any, keys: any, keyField = 'id') {
    if (!treeData) return []

    if (!Array.isArray(treeData)) treeData = [treeData]

    const keysIncludes = (node: any) => {
        if (!keys || !Array.isArray(keys)) return false  // 查找所有叶子节点
        return keys.includes(node[keyField])
    }

    let result: any = []
    const loop = (nodes: any) => nodes.forEach((node: any) => {
        if (node.children && node.children.length) return loop(node.children)

        if (keysIncludes(node)) result.push(node)
    })

    loop(treeData)

    return result
}

/**
 *  删除节点
 *  @param treeData
 *  @param key
 *  @param keyField
 */
export function removeNode(treeData: any, key: any, keyField = 'id') {
    if (!treeData) return null

    if (!Array.isArray(treeData)) treeData = [treeData]

    const loop = (data: any) => {
        for (let i = 0; i < data.length; i++) {
            const item = data[i]
            if (item[keyField] === key) {
                data.splice(i, 1)
                break
            } else if (item.children && item.children.length) {
                loop(item.children)
            }
        }
    };
    loop(treeData)
}

/**
 *  过滤树
 *  @param treeData
 *  @param filter 过滤函数
 *  @returns {*[]|*}
 */
export function filterTree(treeData: any, filter = (node: any) => true) {
    if (!treeData) return []

    if (!Array.isArray(treeData)) treeData = [treeData]

    const getNodes = (result: any, node: any) => {
        if (filter(node)) {
            result.push(node)
            return result
        } 
        if (Array.isArray(node.children)) {
            const children = node.children.reduce(getNodes, [])
            if (children.length) result.push({ ...node, children })
        }
        return result
    }
    return treeData.reduce(getNodes, [])
}

/**
 * 将树平展
 */
export function treeToArr(data: any, res: any = [], status?: boolean) {
  data.forEach((item: any) => {
    if (status) {
      res.push(item)
    } else {
      if (!item.children) {
        res.push(item)
      }
    }
    if (item.children && item.children.length !== 0) {
      treeToArr(item.children, res)
    } 
  })

  return res
}