У меня есть массив объектов, которые определяют, какие из них следует показывать первыми. Примером этого массива может быть:
[
{
"id": "b94ae1a5-c6b2-4e45-87cd-a4036fdb7870",
"prerequisites_ids": [
"2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1"
]
},
{
"id": "ef7d2415-808f-4efc-939e-2692f38a5ee7",
"prerequisites_ids": [
"74e41a2c-e74e-4016-bb2c-f2e84c04fe92"
]
},
{
"id": "74e41a2c-e74e-4016-bb2c-f2e84c04fe92",
"prerequisites_ids": []
},
{
"id": "2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1",
"prerequisites_ids": [
"ef7d2415-808f-4efc-939e-2692f38a5ee7"
]
}
]
Как я могу отсортировать его, чтобы получить это?
[
{
"id": "74e41a2c-e74e-4016-bb2c-f2e84c04fe92",
"prerequisites_ids": []
},
{
"id": "ef7d2415-808f-4efc-939e-2692f38a5ee7",
"prerequisites_ids": [
"74e41a2c-e74e-4016-bb2c-f2e84c04fe92"
]
},
{
"id": "2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1",
"prerequisites_ids": [
"ef7d2415-808f-4efc-939e-2692f38a5ee7"
]
},
{
"id": "b94ae1a5-c6b2-4e45-87cd-a4036fdb7870",
"prerequisites_ids": [
"2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1"
]
}
]
Я попытался создать пользовательскую функцию:
export function comparePrerequisites(a, b) {
if (!a.prerequisites_ids) {
return -1
}
if (a.prerequisites_ids.includes(b.id)) {
return 1;
}
}
data.sort(comparePrerequisites)
но, похоже, не работает. Заранее спасибо!
Если предпосылки являются первичным ключом сортировки, то что является вторичным? (Например, в каком порядке вы хотите, чтобы a
и b
были в том случае, если у них обоих одинаковые предпосылки или нет?)
А как же циклы? Два объекта, которые говорят, что они взаимно зависят друг от друга?
У нас есть требования для топологический сортировка. Это не работа для метода sort
. Вместо этого вы можете использовать рекурсию (обход DFS) для детализации до зависимости, которая уже собрана, или до листа (без зависимостей).
Вот реализация:
function topologicalSort(tasks) {
const visited = new Set;
const taskMap = new Map(tasks.map(task => [task.id, task]));
function dfs(tasks) {
for (let task of tasks) {
if (!visited.has(task.id)) {
dfs(task.prerequisites_ids.map(id => taskMap.get(id)));
}
visited.add(task);
}
}
dfs(tasks);
return [...visited];
}
// Demo on your example:
let tasks = [{"id": "b94ae1a5-c6b2-4e45-87cd-a4036fdb7870","prerequisites_ids": ["2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1"]},{"id": "ef7d2415-808f-4efc-939e-2692f38a5ee7","prerequisites_ids": ["74e41a2c-e74e-4016-bb2c-f2e84c04fe92"]},{"id": "74e41a2c-e74e-4016-bb2c-f2e84c04fe92","prerequisites_ids": []},{"id": "2a4fdd9c-45d0-49d9-a0eb-ba5a0464f2b1","prerequisites_ids": ["ef7d2415-808f-4efc-939e-2692f38a5ee7"]}];
console.info(topologicalSort(tasks));
Массив, пустой или нет, всегда равен правдивый. Вам нужно будет проверить его свойство
.length
.