/**
 * 使用高性能算法，将array结构数据变为tree结构数据。*注意，会修改原始数据*
 * @example
 * //生成测试数据
 * function addChildren(count,parent){
 *  const data = [];
 *  const pid = parent?parent.id:null;
 *  const parentName = parent?parent.name+'-':'';
 *  _.each(_.range(0,count),i=>{
 *    const sortNo = _.randi(0,count);
 *    data.push({id:_.alphaId(),pid,name:parentName+i,sortNo})
 *  });
 *  return data;
 * }
 *
 * function genTree(depth,parents,data){
 *  _.each(parents,r=>{
 *    const children = addChildren(_.randi(1,4),r);
 *    if(depth-1>0){
 *      genTree(depth-1,children,data);
 *    }
 *    _.append(data,...children);
 *  });
 * }
 *
 * const roots = addChildren(2);
 * const data = [];
 * genTree(2,roots,data);
 * _.insert(data,0,...roots);
 *
 * const tree = _.arrayToTree(data,'id','pid',{attrMap:{text:'name'}});
 * _.walkTree(tree,(parentNode,node,chain)=>console.log('node',node.text,'sortNo',node.sortNo,'chain',_.map(chain,n=>n.name)));
 *
 *
 * @param array 原始数据集。如果非Array类型，返回空数组
 * @param idKey id标识
 * @param pidKey 父id标识
 * @param options 自定义选项
 * @param options.rootParentValue 根节点的parentValue，用于识别根节点。默认null
 * @param options.childrenKey 包含子节点容器的key。默认'children'
 * @param options.attrMap 转换tree节点时的属性映射，如\{text:'name'\}表示把array中一条记录的name属性映射为tree节点的text属性
 * @param options.sortKey 如果指定排序字段，则会在转换tree时自动排序。字段值可以是数字或字符等可直接进行比较的类型。性能高于转换后再排序
 * @returns 返回转换好的顶级节点数组或空数组
 * @since 1.0.0
 */
declare function arrayToTree<V extends Record<string | number | symbol, any>>(array: V[], idKey?: string, pidKey?: string, options?: {
    rootParentValue?: any;
    attrMap?: Record<string, any>;
    childrenKey?: string;
    sortKey?: string;
}): V[];

declare function closest<V extends Record<string | number | symbol, any>, U extends Record<string | number | symbol, any>>(node: V, predicate: (node: V, times: number, cancel: () => void) => boolean, parentKey: string, composed?: boolean): U | null;
declare function closest<U extends Record<string | number | symbol, any>>(node: Record<string | number | symbol, any>, predicate: (node: Record<string | number | symbol, any>, times: number, cancel: () => void) => boolean, parentKey: string, composed?: boolean): U | null;

/**
 * 非函数迭代类型
 */
type NonFuncItee = string | Record<any, any> | Array<any>;

/**
 * 类似<code>findTreeNodes</code>，但会返回包含所有父节点的节点副本数组，已做去重处理。
 * 结果集可用于重新构建tree
 * @example
 * //生成测试数据
 * function addChildren(count,parent){
 *  const data = [];
 *  const pid = parent?parent.id:null;
 *  const parentName = parent?parent.name+'-':'';
 *  _.each(_.range(0,count),i=>{
 *    const sortNo = _.randi(1,4);
 *    data.push({id:_.alphaId(),pid,name:parentName+i,sortNo})
 *  });
 *  return data;
 * }
 *
 * function genTree(depth,parents,data){
 *  _.each(parents,r=>{
 *    const children = addChildren(_.randi(1,4),r);
 *    if(depth-1>0){
 *      genTree(depth-1,children,data);
 *    }
 *    _.append(data,...children);
 *  });
 * }
 *
 * const roots = addChildren(2);
 * const data = [];
 * genTree(2,roots,data);
 * _.insert(data,0,...roots);
 * const tree = _.arrayToTree(data,'id','pid',{sortKey:'sortNo'});
 *
 * _.each(_.filterTree(tree,node=>node.sortNo>1),node=>console.log(_.omit(node,'children','id','pid')))
 *
 *
 * @param treeNodes 一组节点或一个节点
 * @param predicate (node,parentNode,chain,level) 断言
 * <br>当断言是函数时回调参数见定义
 * <br>其他类型请参考 {@link utils!iteratee}
 * @param options 自定义选项
 * @param options.childrenKey 包含子节点容器的key。默认'children'
 * @returns 找到的符合条件的所有节点副本或空数组
 * @since 1.0.0
 */
declare function filterTree<V extends Record<string | number | symbol, any>>(treeNodes: V | V[], predicate: (node: V, parentNode: V, chain: V[], level: number) => boolean | NonFuncItee, options?: {
    childrenKey?: string;
}): V[];

/**
 * 查找给定节点及所有子孙节点中符合断言的第一个节点并返回
 * @example
 * //生成测试数据
 * function addChildren(count,parent){
 *  const data = [];
 *  const pid = parent?parent.id:null;
 *  const parentName = parent?parent.name+'-':'';
 *  _.each(_.range(0,count),i=>{
 *    const sortNo = _.randi(0,count);
 *    data.push({id:_.alphaId(),pid,name:parentName+i,sortNo})
 *  });
 *  return data;
 * }
 *
 * function genTree(depth,parents,data){
 *  _.each(parents,r=>{
 *    const children = addChildren(_.randi(2,5),r);
 *    if(depth-1>0){
 *      genTree(depth-1,children,data);
 *    }
 *    _.append(data,...children);
 *  });
 * }
 *
 * const roots = addChildren(2);
 * const data = [];
 * genTree(4,roots,data);
 * _.insert(data,0,...roots);
 * const tree = _.arrayToTree(data,'id','pid',{sortKey:'sortNo'});
 *
 * console.log(_.omit(_.findTreeNode(tree,node=>node.sortNo>2),'children','id','pid'))
 *
 *
 * @param treeNodes 一组节点或一个节点
 * @param predicate (node,parentNode,chain,level,index) 断言
 * <br>当断言是函数时回调参数见定义
 * <br>其他类型请参考 {@link utils!iteratee}
 * @param options 自定义选项
 * @param options.childrenKey 包含子节点容器的key。默认'children'
 * @returns 第一个匹配断言的节点或undefined
 * @since 1.0.0
 */
declare function findTreeNode<U extends Record<string | number | symbol, any>>(treeNodes: Record<string | number | symbol, any> | Record<string | number | symbol, any>[], predicate: (node: Record<string | number | symbol, any>, parentNode: Record<string | number | symbol, any>, chain: Record<string | number | symbol, any>[], level: number, index: number) => boolean | NonFuncItee, options?: {
    childrenKey?: string;
}): U | undefined;
declare function findTreeNode<V extends Record<string | number | symbol, any>, U extends Record<string | number | symbol, any>>(treeNodes: V | V[], predicate: (node: V, parentNode: V, chain: V[], level: number, index: number) => boolean | NonFuncItee, options?: {
    childrenKey?: string;
}): U | undefined;

/**
 * 查找给定节点及所有子孙节点中符合断言的所有节点并返回
 * @example
 * //生成测试数据
 * function addChildren(count,parent){
 *  const data = [];
 *  const pid = parent?parent.id:null;
 *  const parentName = parent?parent.name+'-':'';
 *  _.each(_.range(0,count),i=>{
 *    const sortNo = _.randi(0,count);
 *    data.push({id:_.alphaId(),pid,name:parentName+i,sortNo})
 *  });
 *  return data;
 * }
 *
 * function genTree(depth,parents,data){
 *  _.each(parents,r=>{
 *    const children = addChildren(_.randi(2,5),r);
 *    if(depth-1>0){
 *      genTree(depth-1,children,data);
 *    }
 *    _.append(data,...children);
 *  });
 * }
 *
 * const roots = addChildren(2);
 * const data = [];
 * genTree(3,roots,data);
 * _.insert(data,0,...roots);
 * const tree = _.arrayToTree(data,'id','pid',{sortKey:'sortNo'});
 *
 * _.each(_.findTreeNodes(tree,node=>node.sortNo>2),node=>console.log(_.omit(node,'children','id','pid')))
 *
 *
 * @param treeNodes 一组节点或一个节点
 * @param predicate (node,parentNode,chain,level,index) 断言
 * <br>当断言是函数时回调参数见定义
 * <br>其他类型请参考 {@link utils!iteratee}
 * @param options 自定义选项
 * @param options.childrenKey 包含子节点容器的key。默认'children'
 * @returns 找到的符合条件的所有节点或空数组
 * @since 1.0.0
 */
declare function findTreeNodes<U extends Record<string | number | symbol, any>>(treeNodes: Record<string | number | symbol, any> | Record<string | number | symbol, any>[], predicate: (node: Record<string | number | symbol, any>, parentNode: Record<string | number | symbol, any>, chain: Record<string | number | symbol, any>[], level: number, index: number) => boolean | NonFuncItee, options?: {
    childrenKey?: string;
}): U[];
declare function findTreeNodes<V extends Record<string | number | symbol, any>, U extends Record<string | number | symbol, any>>(treeNodes: V | V[], predicate: (node: V, parentNode: V, chain: V[], level: number, index: number) => boolean | NonFuncItee, options?: {
    childrenKey?: string;
}): U[];

/**
 * 对给定节点及所有子孙节点(同级)排序
 * @example
 * //生成测试数据
 * function addChildren(count,parent){
 *  const data = [];
 *  const pid = parent?parent.id:null;
 *  const parentName = parent?parent.name+'-':'';
 *  _.each(_.range(0,count),i=>{
 *    const sortNo = _.randi(0,9);
 *    data.push({id:_.alphaId(),pid,name:parentName+i,sortNo})
 *  });
 *  return data;
 * }
 *
 * function genTree(depth,parents,data){
 *  _.each(parents,r=>{
 *    const children = addChildren(_.randi(1,4),r);
 *    if(depth-1>0){
 *      genTree(depth-1,children,data);
 *    }
 *    _.append(data,...children);
 *  });
 * }
 *
 * const roots = addChildren(1);
 * const data = [];
 * genTree(2,roots,data);
 * _.insert(data,0,...roots);
 * let tree = _.arrayToTree(data,'id','pid');
 *
 * console.log('Before sort---------------');
 * _.walkTree(_.cloneDeep(tree),(parentNode,node,chain)=>console.log('node',node.name,'sortNo',node.sortNo))
 * _.sortTree(tree,(a,b)=>a.sortNo - b.sortNo);
 * console.log('After sort---------------');
 * _.walkTree(tree,(parentNode,node,chain)=>console.log('node',node.name,'sortNo',node.sortNo))
 *
 * @param treeNodes 一组节点或一个节点
 * @param comparator (a,b) 排序函数
 * @param options 自定义选项
 * @param options.childrenKey 包含子节点容器的key。默认'children'
 *
 * @since 1.0.0
 */
declare function sortTree<V extends Record<string | number | symbol, any>>(treeNodes: V | V[], comparator: (a: V, b: V) => number, options?: {
    childrenKey?: string;
}): void;

/**
 * 以给定节点为根遍历所有子孙节点。深度优先
 * @example
 * //生成测试数据
 * function addChildren(count,parent){
 *  const data = [];
 *  const pid = parent?parent.id:null;
 *  const parentName = parent?parent.name+'-':'';
 *  _.each(_.range(0,count),i=>{
 *    const sortNo = _.randi(0,count);
 *    data.push({id:_.alphaId(),pid,name:parentName+i,sortNo})
 *  });
 *  return data;
 * }
 *
 * function genTree(depth,parents,data){
 *  _.each(parents,r=>{
 *    const children = addChildren(_.randi(1,4),r);
 *    if(depth-1>0){
 *      genTree(depth-1,children,data);
 *    }
 *    _.append(data,...children);
 *  });
 * }
 *
 * const roots = addChildren(2);
 * const data = [];
 * genTree(2,roots,data);
 * _.insert(data,0,...roots);
 * const tree = _.arrayToTree(data,'id','pid',{sortKey:'sortNo'});
 *
 * _.walkTree(tree,(node,parentNode,chain)=>console.log('node',node.name,'sortNo',node.sortNo,'chain',_.map(chain,n=>n.name)))
 *
 * @param treeNodes 一组节点或一个节点
 * @param callback (node,parentNode,chain,level,index)回调函数，如果返回false则中断遍历，如果返回-1则停止分支遍历
 * @param options 自定义选项
 * @param options.childrenKey 包含子节点容器的key。默认'children'
 * @since 1.0.0
 */
declare function walkTree<V extends Record<string | number | symbol, any>>(treeNodes: V | V[], callback: (node: V, parentNode: V, chain: V[], level: number, index: number) => boolean | number | void, options?: Record<string, any>): void;

export { arrayToTree, closest, filterTree, findTreeNode, findTreeNodes, sortTree, walkTree };