PHP usort用于字符串层次结构

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

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？

<?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是一个数组，其中每个键都有它的子键。$top_level_parents是一个收集所有没有任何父级的表的数组，其中键是表名，值是它的出现次数。
然后，我们调用另一个函数traverseHierarchy来遍历所有这些顶级父母，并获取他们的孩子。通过这种方式，我们总是在孩子之前访问父母，因为我们首先迭代父母(甚至对其他表的孩子有效)。
为了更好地解释，两个数组看起来如下：

$层次结构：

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

$top_level_pparents:

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

这里，我们对所有顶级父级进行迭代，将它们存储在result数组中，并记录它们在原始数组中发生的次数。
一旦完成，我们现在将遍历它的子级，并将它的所有子级也包括在结果数组中。

第3部分：

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

在这里，我们对所有子项进行迭代，并将它们包含在result中。这个孩子很有可能也有自己的孩子。因此，我们将使用深度优先搜索递归地收集它们。通过这种方式，我们始终确保父母在孩子之前。
在最后一节中，我们只打印结果。

从根本上讲，您需要递归地处理数据，以按顺序解析树结构。此函数将执行此操作。它查找当前父级的子级(通过array_filter选择它们)，然后遍历当前子级，将它们的所有子级合并到输出数组中。由于需要跳过匹配的父级，我们必须在将其添加到输出之前检查子级是否与前一个不同：

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_tablen";
foreach (hsort($array, NULL) as $v) {
printf("%-8s| %sn", $v['table'], $v['parent_table'] ?? 'NULL');
}

输出

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

3v4l.org 上的演示

相关内容

最新更新

热门标签：