从扁平的数据结构数组，转换为嵌套式的数据结构，请问需要什么算法才能实现呢？

Question

请问下，这种算法叫什么呢，如何才能进行实现：

定义的interface如下：

type PropertyDataType = {
  name: string,
  isFrom: ItemDataType,  // 从哪个类/抽象类/接口来的
  value: string | number |  undefined,  // 接口无实现 = undefined
}

type MethodDataType = {
  name: string, 
  isFrom: ItemDataType,
  value: string | undefined  // 接口无实现 = undefined
  isAbstract: boolean  // 是否是抽象方法
}

//#region 类接口之间的关系
type InheritanceRelationType = {
  name: 'inheritance',
  relationToId: ItemDataTypeId
}

type ImplementationRelationType = {
  name: 'implementation',
  relationToId: ItemDataTypeId
}

type AggregationRelationType = {
  name: 'aggregation',
  relationToId: ItemDataTypeId
}

type CompositionRelationType = {
  name: 'composition',
  relationToId: ItemDataTypeId
} 

type RelationType = InheritanceRelationType | ImplementationRelationType | AggregationRelationType | CompositionRelationType
//#endregion

type ItemDataTypeId = string | number

// 类数据类型: 类/抽象类/接口
export type ItemDataType = {
  id: ItemDataTypeId,
  type: 'Class' | 'AbstractClass' | 'Interface', 
  name: string, // 类名称
  properties: PropertyDataType[],  // 属性
  methods: MethodDataType[],
  relations: RelationType[]  // 与其他ItemDataType的关系
}

现在有数据（很多的ItemDataType类型数据组成的数组）：

const dataList = <ItemDataType[]>[
  {
    id: 1,
    type: 'Class',
    name: 'AnimalBase',
    properties: [],
    methods: [],
    relations: []
  },
  {
    id: 2,
    type: 'Class',
    name: 'Animal',
    properties: [],
    methods: [],
    relations: [{name: 'inheritance', relationToId: 1}]
  },
  {
    id: 3,
    type: 'Class',
    name: 'Cat',
    properties: [],
    methods: [],
    relations: [{name: 'inheritance', relationToId: 2}]
  }
]

想要
设定一个方法：
getInheritanceChain(id:number): ReturnType
返回ReturnType数据内容为嵌入式数据，举例：

{
  name: 'Cat',
  comesFrom: [
    {
      relationName: 'inheritance',
      name: 'Animal',
      type: 'Class',
      comesFrom: [
        {
          relationName: 'inheritance',
          name: 'AnimalBase',
          type: 'Class',
          comesFrom: []
        }
      ]
    }
  ]
}

请问这个需要如何进行处理呢？是否有现有的库进行直接处理呢？

Answer 1

const map = new Map(dataList.map(item => [item.id, item]))

interface ComesFrom {
    relationName: string
    name: string
    type: string
    comesFrom?: ComesFrom[]
}
function getRelations(item: ItemDataType): ComesFrom[] {
    return item.relations.map(r => {
        const item = map.get(r.relationToId)
        if (item === undefined) throw new Error('relationToId is invalid')
        return {
            relationName: r.name,
            name: item.name,
            type: item.type,
            comesFrom: getRelations(item)
        }
    })
}

function getInheritanceChain(id: ItemDataTypeId) {
    const item = map.get(id)

    return item
        ? {
                name: item.name,
                comesFrom: getRelations(item)
          }
        : undefined
}

console.log(getInheritanceChain(3))

{
  name: "Cat",
  comesFrom: [
    {
      relationName: "inheritance",
      name: "Animal",
      type: "Class",
      comesFrom: [
        {
          relationName: "inheritance",
          name: "AnimalBase",
          type: "Class",
          comesFrom: []
        }
      ]
    }
  ]
}