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

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: []
        }
      ]
    }
  ]
}

Answer 2

要实现从扁平的 ItemDataType 数组到嵌套式数据结构的转换，你可以使用递归算法来遍历和处理这些关系。在这个例子中，主要的关系是继承（inheritance），但你可以根据需要扩展到其他关系类型。

下面是一个基本的实现方法，不依赖于现有的库，而是手动编写递归函数来处理继承链：

function getInheritanceChain(dataList: ItemDataType[], id: ItemDataTypeId): ReturnType | null {
  // 查找当前ID的项
  const currentItem = dataList.find(item => item.id === id);
  if (!currentItem) return null;

  // 递归构建继承链
  function buildChain(item: ItemDataType): ReturnType {
    const chainItem: ReturnType = {
      name: item.name,
      type: item.type,
      comesFrom: []
    };

    // 处理继承关系
    item.relations.forEach(relation => {
      if (relation.name === 'inheritance') {
        const parentItem = dataList.find(parent => parent.id === relation.relationToId);
        if (parentItem) {
          chainItem.comesFrom.push(buildChain(parentItem));
        }
      }
    });

    return chainItem;
  }

  return buildChain(currentItem);
}

// 返回值类型定义
interface ReturnType {
  name: string;
  type: 'Class' | 'AbstractClass' | 'Interface';
  comesFrom: ReturnType[];
}

// 示例数据
const dataList = [
  // ...（如你所示的数据）
];

// 使用示例
console.log(getInheritanceChain(dataList, 3));

在这个实现中，getInheritanceChain 函数首先查找具有给定ID的项。然后，它调用 buildChain 函数来递归地构建继承链。buildChain 函数会检查当前项的继承关系，并对每个继承关系递归调用自身以构建嵌套的 comesFrom 数组。

这种方法不需要额外的库，并且可以根据需要轻松地扩展到处理其他类型的关系。此外，通过递归方式，你可以灵活地处理任何深度的继承链。