как отсортировать записи, похожие на связанный список?
У меня есть следующая структура данных, и я хотел бы отсортировать это на основе before а также after ценности.
array (size=5)
0 =>
array (size=3)
'id' => int 14
'parentId' => int 0
'before' => int 15
1 =>
array (size=3)
'id' => int 15
'parentId' => int 0
'after' => int 14
2 =>
array (size=3)
'id' => int 9
'parentId' => int 0
'after' => int 15
3 =>
array (size=3)
'id' => int 8
'parentId' => int 0
'after' => int 9
4 =>
array (size=3)
'id' => int 1
'parentId' => int 0
'after' => int 14
Есть ли способ сделать это с помощью PHP?
Решение
Я не думаю, что есть прямое решение типа «одна строка» для этого.
Мне не понятно parentId имеет какое-либо значение для сортировки, но если нет, то это похоже на этот вопрос о сортировке массива Javascript включает в себя зависимость Я ответил ранее на этой неделе.
Единственное реальное отличие состоит в том, что перед тем, как вы сможете отсортировать по зависимости, вам необходимо преобразовать эти записи «до» в записи «после» в соответствующей строке.
$data = [
["id" => 14, "parentId" => 0, "before" => 15],
["id" => 15, "parentId" => 0, "after" => 14],
["id" => 9, "parentId" => 0, "after" => 15],
["id" => 8, "parentId" => 0, "after" => 9],
["id" => 1, "parentId" => 0, "after" => 14]
];
// Use the ID of each element as the array index.
$data = array_combine(array_column($data, "id"), $data);
// Convert each "after" entry into an array.
$data = array_map(function($element) {
$element["after"] = isset($element["after"]) ? [$element["after"]] : [];
return $element;
}, $data);
// Convert each "before" entry into an "after" entry.
foreach ($data as $id => $element) {
if (isset($element["before"])) {
$data[$element["before"]]["after"][] = $id;
unset($data[$id]["before"]);
}
}
// Remove empty "after" entries.
$data = array_map(function($element) {
if (!count($element["after"])) {
unset($element["after"]);
}
return $element;
}, $data);
$sorted = [];
while ($count = count($data)) {
// Remove any met dependencies.
foreach ($data as $id => $element) {
if (isset($element["after"])) {
foreach ($element["after"] as $after_id => $after_element) {
if (isset($sorted[$after_element])) {
unset($data[$id]["after"][$after_id]);
}
}
if (!count($data[$id]["after"])) {
unset($data[$id]["after"]);
}
}
}
// Add elements with no more dependencies to the output array.
foreach ($data as $id => $element) {
if (!isset($element["after"])) {
$sorted[$id] = $element;
unset($data[$id]);
}
}
if (count($data) == $count) {
die("Unresolvable dependency");
}
}
var_dump($sorted);
/*
array (size=5)
14 =>
array (size=2)
'id' => int 14
'parentId' => int 0
15 =>
array (size=2)
'id' => int 15
'parentId' => int 0
1 =>
array (size=2)
'id' => int 1
'parentId' => int 0
9 =>
array (size=2)
'id' => int 9
'parentId' => int 0
8 =>
array (size=2)
'id' => int 8
'parentId' => int 0
*/
Другие решения
Я думаю, что вы могли бы использовать uasort() функция для ваших нужд.
Чтобы определить вашу функцию сравнения, я бы предложил преобразовать все after условия для beforeусловия:
$array = [
[
'id' => 14,
'parentId' => 0,
'before' => 15
],
[
'id' => 15,
'parentId' => 0,
'after' => 14
],
[
'id' => 9,
'parentId' => 0,
'after' => 15
],
[
'id' => 8,
'parentId' => 0,
'after' => 9
],
[
'id' => 1,
'parentId' => 0,
'after' => 14
]
];
//transform all after conditions to before conditions
function defineBeforeCondition($array)
{
$befores = array_column($array, 'before', 'id');
$afters = array_column($array, 'after', 'id');
return array_merge(array_chunk($befores, 1, true), array_map('array_flip', array_chunk($afters, 1, true)));
}
$condition = defineBeforeCondition($array);
Теперь вы можете использовать $condition в вашей функции сравнения:
$compare = function ($array1, $array2) use ($condition)
{
//iterate through before conditions
foreach ($condition as $before) {
//if there is a match
if (isset($before[$array1['id']]) && $before[$array1['id']] === $array2['id']) {
//if the value of the first element is greater than the value of the second element,
//but the first element should precede the second, return -1
if ($array1['id'] > $array2['id']) {
return -1;
}
//otherwise make a normal comparison
//note the spaceship operator for PHP >= 7.0
return $array1['id'] <=> $array2['id'];
}
}
//no data, move down the first element
return 1;
};
uasort($array, $compare);
var_dump($array);
array (size=5)
0 =>
array (size=3)
'id' => int 14
'parentId' => int 0
'before' => int 15
4 =>
array (size=3)
'id' => int 1
'parentId' => int 0
'after' => int 14
1 =>
array (size=3)
'id' => int 15
'parentId' => int 0
'after' => int 14
2 =>
array (size=3)
'id' => int 9
'parentId' => int 0
'after' => int 15
3 =>
array (size=3)
'id' => int 8
'parentId' => int 0
'after' => int 9