how to sort entries similar to a linked list?

Question

I have the following data structure and i'd like to sort this based on the before and after values.

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

Is there neat way to do this with PHP?

function usort() - http://php.net/manual/en/function.usort.php — splash58, Jun 24 '16 at 09:45
@splash58 Precisely no! http://stackoverflow.com/q/38008964/476 — deceze, Jun 24 '16 at 09:47
Can you more precisely describe how you would like it sorted? Is it something with: 'after : 9' means after all entries with ID lower then 9, and 'before : 10' means that all values higher then 10 should come after this one? — Frank Houweling, Jun 24 '16 at 10:03
Thanks. I'd expect The keys to be in the order 0, 4, 1, 2, 3. I realise both 1 and 4 specify "after: 14", which takes precedence is not important for this scenario. — rbaker86, Jun 24 '16 at 10:54
@deceze this is Unclear, right? Do you understand the expected sorting rules? — mickmackusa, Sep 16 '22 at 23:06

score 0 · Answer 1 · edited May 23 '17 at 10:29

I don't think there's a straightforward "one-liner" type solution to this.

I'm not clear whether parentId has any significance on the sorting, but if not this feels quite similar to this question about sorting an array of Javascript includes by dependency I answered earlier this week.

The only real difference is that before you can sort by dependency you'll need to convert those "before" entries into "after" entries on the corresponding row.

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

score 0 · Answer 2 · answered Jun 24 '16 at 16:45

I think you could use the uasort() function for your needs. To define your comparison function, I would suggest to transform all the after conditions to the beforeconditions:

$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);

Now you could use the $condition in your comparison function:

$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

how to sort entries similar to a linked list?

2 Answers2