javascript - 按嵌套的相关数组元素对数组进行分组

Question

我有一个数组存储任务信息。每个任务还​​有一个它所依赖的 taskId 数组。

输入

let inputArr = [
    {
        id: 1,
        dependOnTasks: [2, 3]
    },
    {
        id: 2,
        dependOnTasks: [3]
    },
    {
        id: 3,
        dependOnTasks: []
    },
    {
        id: 4,
        dependOnTasks: [5]
    },
    {
        id: 5,
        dependOnTasks: []
    },
    {
        id: 6,
        dependOnTasks: [5]
    }
]

预期的输出是将所有相关任务分组到一个数组中以显示到 UI 中。

输出

[
    [
        {
            id: 1,
            dependOnTasks: [2, 3]
        },
        {
            id: 2,
            dependOnTasks: [3]
        },
        {
            id: 3,
            dependOnTasks: []
        }
    ],
    [
        {
            id: 4,
            dependOnTasks: [5]
        },
        {
            id: 5,
            dependOnTasks: []
        },
        {
            id: 6,
            dependOnTasks: [5]
        }
    ]
]

我已经编写了一个函数来执行此操作，但似乎我对它进行硬编码的想法是错误的。希望有人可以帮助我使用纯 JavaScript/TypeScript 或 Underscore 以正确的方式存档它，因为我们已经在项目中使用过。

---

注意:TaskId 将是随机字符串，如“5878465507b36e1f9c4c46fe”

Answer 1

// will contain the groups (results).
var result = [];

// will serve as a holder of the already treated indexes of inputArr.
var indexCache = [];

// insert obj into a group, insert its dependencies and the object that depend on it as well.
function insertWithDependencies(obj, group){
    // insert this obj into this group
    group.push(obj);

    // First: look for the objects it depends on
    obj.dependOnTasks.forEach(function(id){
        for(var i = 0; i < inputArr.length; i++){
            // if the object in this index is already treated, then ignore it
            if(indexCache.indexOf(i) != -1) continue;
            // if this object is a dependency of obj then insert it with its own dependencies.
            if(inputArr[i].id == id){
                var o = inputArr[i];
                indexCache.push(i); // cache this i as well
                insertWithDependencies(o, group);
            }
        }
    });

    // Then: look for the objects that depends on it
    for(var i = 0; i < inputArr.length; i++){
        // if the object in this index is already treated, then ignore it
        if(indexCache.indexOf(i) != -1) continue;
        // if this object depends on obj then insert it with ...
        if(inputArr[i].dependOnTasks.indexOf(obj.id) != -1){
            var o = inputArr[i];
            indexCache.push(i); // cache i 
            insertWithDependencies(o, group);
        }
    }
};

// while there is element in the inputArr that haven't been treated yet
while(inputArr.length != indexCache.length){
    // the group that will hold the depending tasks all together
    var group = [];

    // look for the first untreated object in inputArr
    var i;
    for(i = 0; i < inputArr.length; i++)
        if(indexCache.indexOf(i) == -1)
            break;
    var obj = inputArr[i];

    // cache its index
    indexCache.push(i)

    // insert it along its dependencies
    insertWithDependencies(obj, group);

    // push the group into the result array
    result.push(group);
}

另一种方式:

这里有一个优化的方法，但是 inputArr 里面的数据之后会丢失。它不会使用 indexCache 来查看索引是否已被处理，而是会使 inputArr 中的所有已处理项目都为 null。因此，如果您不关心或以后不会使用 inputArr，请改用它:

var result = [];
function insertWithDependencies(obj, group){
    group.push(obj);
    obj.dependOnTasks.forEach(function(id){
        for(var i = 0; i < inputArr.length; i++){
            if(!inputArr[i]) continue;
            if(inputArr[i].id == id){
                var o = inputArr[i];
                inputArr[i] = null;
                insertWithDependencies(o, group);
            }
        }
    });
    for(var i = 0; i < inputArr.length; i++){
        if(!inputArr[i]) continue;
        if(inputArr[i].dependOnTasks.indexOf(obj.id) != -1){
            var o = inputArr[i];
            inputArr[i] = null;
            insertWithDependencies(o, group);
        }
    }
};

function findNotNull(){
    for(var i = 0; i < inputArr.length; i++)
        if(inputArr[i]) return i;
    return -1;
}

var index;
while((index = findNotNull()) != -1){
    var group = [];

    var obj = inputArr[index];
    inputArr[index] = null;
    insertWithDependencies(obj, group);

    result.push(group);
}

console.log(result);