type AnyFunction = (...args: any[]) => any;

interface TreeHelperConfig {
  id: string;
  children: string;
  pid: string;
}

// 默认配置
const DEFAULT_CONFIG: TreeHelperConfig = {
  id: 'id',
  children: 'children',
  pid: 'pid',
};

// 获取配置。  Object.assign 从一个或多个源对象复制到目标对象
const getConfig = (config: Partial<TreeHelperConfig>): TreeHelperConfig =>
  Object.assign({}, DEFAULT_CONFIG, config);

/**
 * @description 将list转化为tree
 * @param list 普通数组
 * @param config 配置项
 * @returns 树形结构的数组
 */
function listToTree<T = any>(list: any[], config: Partial<TreeHelperConfig> = {}): T[] {
  const conf = getConfig(config);
  const nodeMap = new Map();
  const result: T[] = [];
  const { id, children, pid } = conf;

  for (const node of list) {
    node[children] = node[children] || [];
    nodeMap.set(node[id], node);
  }
  for (const node of list) {
    const parent = nodeMap.get(node[pid]);
    (parent ? parent[children] : result).push(node);
  }
  return result;
}

function treeToList<T = any>(tree: any, config: Partial<TreeHelperConfig> = {}): T {
  config = getConfig(config);
  const { children } = config;
  const result: any = [...tree];
  for (let i = 0; i < result.length; i++) {
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    if (!result[i][children!]) continue;
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    result.splice(i + 1, 0, ...result[i][children!]);
  }
  return result;
}

function findNode<T = any>(
  tree: any,
  func: AnyFunction,
  config: Partial<TreeHelperConfig> = {},
): T | null {
  config = getConfig(config);
  const { children } = config;
  const list = [...tree];
  for (const node of list) {
    if (func(node)) return node;
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    node[children!] && list.push(...node[children!]);
  }
  return null;
}

function findNodeAll<T = any>(
  tree: any,
  func: AnyFunction,
  config: Partial<TreeHelperConfig> = {},
): T[] {
  config = getConfig(config);
  const { children } = config;
  const list = [...tree];
  const result: T[] = [];
  for (const node of list) {
    func(node) && result.push(node);
    // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
    node[children!] && list.push(...node[children!]);
  }
  return result;
}

function findPath<T = any>(
  tree: any,
  func: AnyFunction,
  config: Partial<TreeHelperConfig> = {},
): T | T[] | null {
  config = getConfig(config);
  const path: T[] = [];
  const list = [...tree];
  const visitedSet = new Set();
  const { children } = config;
  while (list.length) {
    const node = list[0];
    if (visitedSet.has(node)) {
      path.pop();
      list.shift();
    } else {
      visitedSet.add(node);
      // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
      node[children!] && list.unshift(...node[children!]);
      path.push(node);
      if (func(node)) {
        return path;
      }
    }
  }
  return null;
}

function findPathAll(tree: any, func: AnyFunction, config: Partial<TreeHelperConfig> = {}) {
  config = getConfig(config);
  const path: any[] = [];
  const list = [...tree];
  const result: any[] = [];
  const visitedSet = new Set(),
    { children } = config;
  while (list.length) {
    const node = list[0];
    if (visitedSet.has(node)) {
      path.pop();
      list.shift();
    } else {
      visitedSet.add(node);
      // eslint-disable-next-line @typescript-eslint/no-non-null-assertion
      node[children!] && list.unshift(...node[children!]);
      path.push(node);
      func(node) && result.push([...path]);
    }
  }
  return result;
}

function forEach<T = any>(
  tree: T[],
  func: (n: T) => any,
  config: Partial<TreeHelperConfig> = {},
): void {
  config = getConfig(config);
  const list: any[] = [...tree];
  const { children } = config;
  for (let i = 0; i < list.length; i++) {
    //func 返回true就终止遍历，避免大量节点场景下无意义循环，引起浏览器卡顿
    if (func(list[i])) {
      return;
    }
    children && list[i][children] && list.splice(i + 1, 0, ...list[i][children]);
  }
}

/**
 * 递归遍历树结构
 * @param treeDatas 树
 * @param callBack 回调
 * @param parentNode 父节点
 */
function eachTree(
  treeDatas: any[],
  callBack: AnyFunction,
  parentNode = {},
  config: Partial<TreeHelperConfig> = {},
) {
  config = getConfig(config);
  const { children } = config;
  treeDatas.forEach((element) => {
    const newNode = callBack(element, parentNode) || element;
    if (children && element[children]) {
      eachTree(element[children], callBack, newNode);
    }
  });
}

/**
 * @description 遍历树形结构，并返回所有节点中指定的值。
 * @param tree 树形结构数组
 * @param getValue 获取节点值的函数
 * @param childProps 作为子节点数组的可选属性名称。
 * @returns 所有节点中指定的值的数组
 */
function traverseTreeValues<T, V>(
  tree: T[],
  getValue: (node: T) => V,
  options: Partial<TreeHelperConfig> = {},
): V[] {
  const config = getConfig(options);
  const result: V[] = [];
  const { children: childProp } = config;

  const dfs = (treeNode: T) => {
    const value = getValue(treeNode);
    result.push(value);
    const children = treeNode?.[childProp];
    if (!children) {
      return;
    }
    if (children.length) {
      for (const child of children) {
        dfs(child);
      }
    }
  };

  for (const treeNode of tree) {
    dfs(treeNode);
  }
  return result.filter(Boolean);
}

/**
 * 根据条件过滤给定树结构的节点，并以原有顺序返回所有匹配节点的数组。
 * @param treeNodes 要过滤的树结构的根节点数组。
 * @param predicate 用于匹配每个节点的条件。
 * @param childProps 作为子节点数组的可选属性名称。
 * @returns 包含所有匹配节点的数组。
 */
function filterTree<T>(
  tree: T[],
  predicate: (node: T) => boolean,
  options: Partial<TreeHelperConfig> = {},
): T[] {
  const { children: childProps } = getConfig(options);
  const _filterTree = (nodes: T[]): T[] => {
    return nodes.filter((node) => {
      if (predicate(node)) {
        if (node[childProps]) {
          node[childProps] = _filterTree(node[childProps]);
        }
        return true;
      }
      return false;
    });
  };

  return _filterTree(tree);
}

/**
 * 根据条件重新映射给定树结构的节
 * @param tree 要过滤的树结构的根节点数组。
 * @param mapper 用于map每个节点的条件。
 * @param childProps 作为子节点数组的可选属性名称。
 */
function mapTree<T>(
  tree: T[],
  mapper: (node: T) => T,
  options: Partial<TreeHelperConfig> = {},
): T[] {
  const { children: childProps } = getConfig(options);
  return tree.map((node) => {
    const mapperNode = mapper(node);
    if (mapperNode[childProps]) {
      mapperNode[childProps] = mapTree(mapperNode[childProps], mapper, options);
    }
    return mapperNode;
  });
}

export {
  eachTree,
  filterTree,
  findNode,
  findNodeAll,
  findPath,
  findPathAll,
  forEach,
  listToTree,
  mapTree,
  traverseTreeValues,
  treeToList,
};