'''设计'''

对于数据库层次模型的设计，有很多种设计方案，具体如何设计一是看数据库支持那些特性，二是看业务需求是如何的。抛开业务，就数据库而言，目前的关系型数据库支持以下几种层次模型的存储方案。

邻接表

路径枚举

嵌套集

闭包表

算法

路径唯一型

子节点有且仅拥有唯一的父节点。每个节点有且仅能通过唯一确定的路径访问。

路径混合型

子节点可能拥有两个及以上的父节点。存在一个或多个节点可以被多条路径访问。

算法设计

例如：[B,C],[A,B],[C,D],[B,E],[F,B]

图关系如下：
     A   F
      \ /
       B
      / \
     E   C
          \
           D

初始：[A],[B],[C],[D],[E],[F]
第一步，执行[B,C]解析，从初始数组中(循环)查找B，再(循环)查找C，将C从初始数组中删除，挂载到B下。
[A],[B,[C]],[D],[E],[F]
第二步：执行[A,B]解析，从初始数组中(循环)查找A，再(循环)查找B，将B从初始数组中删除，挂载到A下。
[A,[B,[C]],[D],[E],[F]
第三步：执行[C,D]解析，从初始数组中(循环)查找C，再(循环)查找D，将D从初始数组中删除，挂载到C下。
[A,[B,[C,[D]]]],[E],[F]
第四步：执行[C,D]解析，从初始数组中(循环)查找B，再(循环)查找E，将E从初始数组中删除，挂载到B下。
[A,[B,[[C,[D]],[E]]],[F]
第五步：执行[C,D]解析，从初始数组中(循环)查找F，再(循环)查找B，将B从初始数组中删除，挂载到F下。
[A,[B,[[C,[D]],[E]]],[F,[B,[[C,[D]],[E]]]

注意：
混合型：每次将子节点从初始数组中删除，父结点不删除。
唯一型：每次将子节点从挂载的父节点数组上删除，父结点删除。

算法实现

export class Transfer {
  private readonly _data: Array<any>;

  constructor(data: Array<any>) {
    this._data = data;
  }

  /**
   * @param tierHandler
   * Specify the parent/child data struct.
   * Pay attention the struct should bring into correspondence with each other in general.
   * If not, your must keep least one field in struct is the same as each other.
   * You need to divide data which you give into a parent data and a child data.
   * @param buildLogic
   * Specify logic to build the forest.
   * Sample variable use to compare with the target variable data one by one.
   * Sample is original data. Target is changeable data.
   */
  toForest<T>(
    tierHandler: (data: any | T) => { parent: any; child: any },
    buildLogic: (sample: any) => (target: any) => boolean,
  ) {
    const forest = new Forest<T>();
    for (const row of this._data) {
      let node;
      const { parent: parentData, child: childData } = tierHandler(row);
      node = forest.search(buildLogic(parentData));
      if (!node) {
        forest.push(new Forest(parentData));
      }
      node = forest.search(buildLogic(childData));
      if (!node) {
        forest.push(new Forest(childData));
      }
    }
    for (const row of this._data) {
      const { parent: parentData, child: childData } = tierHandler(row);
      const parent = forest.search(buildLogic(parentData), true);
      const child = forest.search(buildLogic(childData), true);
      // If one of child nodes inherits two parent nodes, it will return all path reach to the node, when recursion if false.
      // Otherwise, it will only return one path to the node. and which path will return is decide by the orders if path description information.
      // By the way, if it return all path of one node, named the structure is a forest is very funny. seriously, named it graph or topology is better.
      // But haha, it forest, it just forest, because i named it.
      forest.delete((el) => el === child.data);
      parent.push(child);
    }
    return forest;
  }

  /**
   * @deprecated
   * notice: Jult see toForest function!
   * @param tierHandler
   * @param buildLogic
   */
  toGraph<T>(
    tierHandler: (data: any | T) => { parent: any; child: any },
    buildLogic: (sample: any) => (target: any) => boolean,
  ) {
    const forest = new Forest<T>();
    for (const row of this._data) {
      let node;
      const { parent: parentData, child: childData } = tierHandler(row);
      node = forest.search(buildLogic(parentData));
      if (!node) {
        forest.push(new Forest(parentData));
      }
      node = forest.search(buildLogic(childData));
      if (!node) {
        forest.push(new Forest(childData));
      }
    }
    const graph = new Forest<T>();
    for (const row of this._data) {
      const { parent: parentData, child: childData } = tierHandler(row);
      let parent = graph.search(buildLogic(parentData), true);
      if (!parent) {
        parent = forest.search(buildLogic(parentData));
        graph.push(parent);
      }
      let child = graph.search(buildLogic(childData));
      if (child) {
        graph.delete((el) => el === child.data);
      } else {
        child = forest.search(buildLogic(childData));
      }
      parent.push(child);
    }
    return graph;
  }

  /**
   * @deprecated
   * notice: this function have a trap!
   * @param tierHandler
   * @param buildLogic
   */
  // toForest<T>(
  //   tierHandler: (data: any | T) => { parent: any; child: any },
  //   buildLogic: (sample: any) => (target: any) => boolean,
  // ) {
  //   const forest = new Forest<T>();
  //   for (const row of this._data) {
  //     const { parent: parentData, child: childData } = tierHandler(row);
  //     let parent = forest.delete(buildLogic(parentData));
  //     if (!parent) {
  //       parent = new Forest<T>(parentData);
  //     }
  //     let child = forest.delete(buildLogic(childData));
  //     if (!child) {
  //       child = new Forest<T>(childData);
  //     }
  //     parent.push(child);
  //     forest.push(parent);
  //   }
  //   return forest;
  // }
}

export class Forest<T> {
  private readonly _data: T | undefined;

  private readonly _nodes: Forest<T>[];

  /**
   *
   * @param data
   * Forest instance will be root node (or meaning root pointer) if data is not specified.
   */
  constructor(data?: any) {
    this._data = data;
    this._nodes = [];
  }

  get data() {
    return this._data;
  }

  get nodes() {
    return this._nodes;
  }

  /**
   * Return the element which searched firstly.
   * @param callback
   * Search condition.
   * @param recursion
   * Whether execute recursion search.
   * @return element searched or undefined.
   */
  search(
    callback: (el: T) => boolean,
    recursion?: boolean,
  ): Forest<T> | undefined {
    if (this.data !== undefined && callback(this.data)) {
      return this;
    }
    for (const node of this._nodes) {
      if (callback(node.data)) {
        return node;
      }
      if (recursion === true) {
        const found = node.search(callback);
        if (found) {
          return found;
        }
      }
    }
    return undefined;
  }

  /**
   * Delete element which searched firstly.
   * @param callback
   * Delete condition.
   * @param recursion
   * Whether execute recursion delete.
   * @return the deleted element or undefined.
   */
  delete(
    callback: (el: T) => boolean,
    recursion?: boolean,
  ): Forest<T> | undefined {
    const clone: Forest<T>[] = Object.assign([], this._nodes);
    for (let i = 0; i < clone.length; i++) {
      const node = clone[i];
      if (callback(node.data)) {
        return this._nodes.splice(i, 1)[0];
      }
      if (recursion === true) {
        const found = node.delete(callback);
        if (found) {
          return found;
        }
      }
    }
    return undefined;
  }

  /**
   * According to the callback function to flat whole forest.
   * @param callback
   * Flat condition.
   */
  flat(callback: (el: T) => any) {
    let result = [];
    if (this.data !== undefined) {
      result.push(callback(this.data));
    }
    for (const node of this._nodes) {
      result = result.concat(node.flat(callback));
    }
    return result;
  }

  /**
   * Append new node to current node
   * @param node
   */
  push(node: Forest<T>) {
    this._nodes.push(node);
  }
}