PHP 对字符串层次结构进行排序

Question

我有一个字符串层次结构的数组，如下所示：

table, parent_table
test, NULL
test, NULL
test2, test
test4, NULL
test5, test3
test6, test5
test3, test

我想用这样的函数进行排序：

usort($array, function($a,$b) {
    return ($a['table'] === $b['parent_table']) ? -1 : 1;
});

理想的结果是

table, parent_table
test, NULL
test, NULL
test2, test
test3, test
test5, test3
test6, test5
test4, NULL

这会将父表排序在子表之上。我一直在努力为这个问题找到一个好的解决方案。字符串层次结构是否有 usort？

Answer 1

<?php

$data = [
    [
        'table' => 'test',
        'parent_table' => NULL,
    ],
    [
        'table' => 'test',
        'parent_table' => NULL,
    ],
    [
        'table' => 'test2',
        'parent_table' => 'test',
    ],
    [
        'table' => 'test4',
        'parent_table' => NULL,
    ],
    [
        'table' => 'test5',
        'parent_table' => 'test3',
    ],
    [
        'table' => 'test6',
        'parent_table' => 'test5',
    ],
    [
        'table' => 'test3',
        'parent_table' => 'test',
    ],
];


function reorderHierarchy($data){

    $hierarchy = [];
    $top_level_parents = [];

    foreach($data as $each_data){
        $hierarchy[$each_data['table']] = array();
        if(is_null($each_data['parent_table'])){
            if(!isset($top_level_parents[$each_data['table']])){
                $top_level_parents[$each_data['table']] = 0;
            }
            $top_level_parents[$each_data['table']]++;
        }
    }

    foreach($data as $each_data){
        if(!is_null($each_data['parent_table'])){
            $hierarchy[$each_data['parent_table']][] = $each_data['table'];
        }
    }

    $result = [];
    traverseHierarchy($hierarchy,$top_level_parents,$result);
    return $result;
}

function traverseHierarchy($hierarchy,$top_level_parents,&$result){
    foreach($top_level_parents as $each_parent => $occurrences){
        while($occurrences-- > 0){
            $result[] = [
                'table' => $each_parent,
                'parent_table' => NULL
            ];
        }       

        traverseChildren($hierarchy,$each_parent,$result);
    }
}

function traverseChildren($hierarchy,$parent,&$result){
    foreach($hierarchy[$parent] as $each_child){
        $result[] = [
            'table' => $each_child,
            'parent_table' => $parent
        ];

        traverseChildren($hierarchy,$each_child,$result);
    }
}


foreach(reorderHierarchy($data) as $each_data){
    echo $each_data['table']," , ",(is_null($each_data['parent_table']) ? "NULL" : $each_data['parent_table']),"<br/>";
}

输出：

test , NULL
test , NULL
test2 , test
test3 , test
test5 , test3
test6 , test5
test4 , NULL

演示： https://3v4l.org/AmJpY

解释：

第 1 部分：

function reorderHierarchy($data){

    $hierarchy = [];
    $top_level_parents = [];

    foreach($data as $each_data){
        $hierarchy[$each_data['table']] = array();
        if(is_null($each_data['parent_table'])){
            if(!isset($top_level_parents[$each_data['table']])){
                $top_level_parents[$each_data['table']] = 0;
            }
            $top_level_parents[$each_data['table']]++;
        }
    }

    foreach($data as $each_data){
        if(!is_null($each_data['parent_table'])){
            $hierarchy[$each_data['parent_table']][] = $each_data['table'];
        }
    }

    $result = [];
    traverseHierarchy($hierarchy,$top_level_parents,$result);
    return $result;
}

在上面的函数中，我们创建了两种数组，即$hierarchy和$top_level_parents。 $hierarchy 是一个数组，其中每个键都包含 children 键。 $top_level_parents 是一个数组，它收集所有没有任何 parent 的 table，键是 table 名称，值是它的出现。
然后我们调用另一个函数traverseHierarchy遍历所有这些顶层parent并得到它们的children。这样，我们将始终在 children 之前访问 parents，因为我们首先迭代 parents（即使是 children 也是有效的 children 95=]s 其他 tables).
为了更好地解释，两个数组如下所示：

$层次结构：

Array
(
    [test] => Array
        (
            [0] => test2
            [1] => test3
        )

    [test2] => Array
        (
        )

    [test4] => Array
        (
        )

    [test5] => Array
        (
            [0] => test6
        )

    [test6] => Array
        (
        )

    [test3] => Array
        (
            [0] => test5
        )
)

$top_level_parents:

Array
(
    [test] => 2
    [test4] => 1
)

第 2 部分：

function traverseHierarchy($hierarchy,$top_level_parents,&$result){
    foreach($top_level_parents as $each_parent => $occurrences){
        while($occurrences-- > 0){
            $result[] = [
                'table' => $each_parent,
                'parent_table' => NULL
            ];
        }       

        traverseChildren($hierarchy,$each_parent,$result);
    }
}

在这里，我们遍历所有顶级 parents，将它们存储在 result 数组中，编号为。它们出现在原始数组中的次数。
一旦完成，我们现在将遍历它的 children 并将它的所有 children 也包含在结果数组中。

第 3 部分：

function traverseChildren($hierarchy,$parent,&$result){
    foreach($hierarchy[$parent] as $each_child){
        $result[] = [
            'table' => $each_child,
            'parent_table' => $parent
        ];

        traverseChildren($hierarchy,$each_child,$result);
    }
}

在这里，我们遍历所有children并将它们包含在result中。这个 child 很有可能也有自己的 children。因此，我们将使用 depth first search 递归地收集它们。这样我们总是确保 parent 出现在 child 之前。
在最后一节中，我们只是打印结果。

Answer 2

从根本上说，您需要递归地处理数据以将树结构从中解析出来并按顺序排列。这个函数会做到这一点。它寻找当前 parent 的 children（通过 array_filter 选择它们），然后遍历当前 children，合并它们的所有 child ren 进入输出数组。因为需要跳过匹配parents，所以在将它添加到输出之前，我们必须检查一个child是否与之前的不相同：

function hsort($array, $parent) {
    $output = array();
    $children = array_filter($array, function ($v) use ($parent) { return $v['parent_table'] === $parent; });
    sort($children);
    $lastchild = NULL;
    foreach ($children as $child) {
        if ($child != $lastchild && !is_null($lastchild)) {
            $output[] = $lastchild;
            $output = array_merge($output, hsort($array, $lastchild['table']));
        }
        elseif ($lastchild != NULL) {
            $output[] = $lastchild;
        }
        $lastchild = $child;
    }
    if (!is_null($lastchild)) {
        $output[] = $lastchild;
        $output = array_merge($output, hsort($array, $lastchild['table']));
    }
    return $output;
}

echo "table   | parent_table\n";
foreach (hsort($array, NULL) as $v) {
    printf("%-8s| %s\n", $v['table'], $v['parent_table'] ?? 'NULL');
}

输出

table | parent_table 
test  | NULL
test  | NULL
test2 | test 
test3 | test 
test5 | test3 
test6 | test5 
test4 | NULL

Demo on 3v4l.org

PHP 对字符串层次结构进行排序

PHP usort for string hierarchy

php

sorting

usort