как сортировать записи похожие на связанный список?

Question

У меня есть следующая структура данных, и я хотел бы отсортировать ее на основе значений 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?

Answer 1

Я не думаю, что есть прямое решение типа «однострочный».

Неясно, имеет ли значение значение parentId при сортировке, но если это не похоже на this question about sorting an array of Javascript includes by dependency, я ответил ранее на этой неделе.

Единственная реальная разница заключается в том, что прежде чем вы сможете сортировать по зависимости, вам нужно будет преобразовать эти записи «до» в записи «после» в соответствующей строке.

$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 
*/ 

Answer 2

Я думаю, вы могли бы использовать функцию 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