Создать древовидную структуру без какого-либо родителя в качестве входных данных из списка объектов с одним уровнем

Question

У меня есть список объектов, которые содержат уровень. Порядок объектов ссылается на родительские объекты. Проблема в том, что у меня нет parentId в моих входных данных.

Входные данные:

const listData = [
    { level: 1, name: "a" }, 
    { level: 2, name: "b", someOther: "asd" },
    { level: 2, name: "c" },
    { level: 3, name: "d" },
    { level: 4, name: "e" },
    { level: 2, name: "f" }
]

Интерфейс вывода должен выглядеть следующим образом:

interface Item {
    name: String;
    listData?: Item[]
    ... otherKeys
}

Я пытался добавить родительскую ссылку к каждому объекту и getParentByLevelsBackwards (элемент, уровни), который на самом деле не сработал.

Я добавил полный тестовый код здесь. Может быть, у кого-то есть хорошая рекомендация по решению такой проблемы или даже лучше рабочая реализация для этой проблемы?

// listData has n objects with n levels from 1 to x
// listData elements can have other attributes that should be persisted
// sublevel level should always +1
const assert = require("assert");

const listData = [{
        level: 1,
        name: "a"
    }, //first is always level 1
    {
        level: 2,
        name: "b",
        someOther: "asd"
    },
    {
        level: 2,
        name: "c"
    },
    {
        level: 3,
        name: "d"
    },
    {
        level: 4,
        name: "e"
    },
    // { level: 5, name: "e" }, // would give bonus points
    {
        level: 2,
        name: "f"
    }
];

const resultToBe = [{
    level: 1,
    name: "a",
    listData: [{
            level: 2,
            name: "b",
            someOther: "asd"
        },
        {
            level: 2,
            name: "c",
            listData: [{
                level: 3,
                name: "d",
                listData: [{
                    level: 4,
                    name: "e"
                }]
            }]
        },
        {
            level: 2,
            name: "f"
        }
    ]
}];

const createResult = listData => {
    return [];
};

const test = () => {
    const result = createResult(listData);
    console.log("Input is:", JSON.stringify(listData, null, 4));
    console.log("Result is:", JSON.stringify(result, null, 4));
    assert.deepStrictEqual(result, resultToBe, "Objects missmatch");
};

test();

Answer 1

Вы можете использовать массив для уровней в качестве вспомогательного массива для последних вставленных уровней.

const
    listData = [{ level: 1, name: "a" }, { level: 2, name: "b", someOther: "asd" }, { level: 2, name: "c" }, { level: 3, name: "d" }, { level: 4, name: "e" }, { level: 2, name: "f" }],
    result = [],
    levels = [result];

listData.forEach(o => {
    o.children = [];
    levels[o.level] = o.children;
    levels[o.level - 1].push(o);
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

То же самое без пустых дочерних массивов.

const
    listData = [{ level: 1, name: "a" }, { level: 2, name: "b", someOther: "asd" }, { level: 2, name: "c" }, { level: 3, name: "d" }, { level: 4, name: "e" }, { level: 2, name: "f" }],
    result = [],
    levels = [result];

listData.forEach(o => {
    if (!levels[o.level - 1]) {
        var temp = levels[o.level - 2],
            last = temp[temp.length - 1];
        levels[o.level - 1] = [];
        last.children = levels[o.level - 1];
    }
    levels[o.level - 1].push(o);
});

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }