PHP usort для строковой иерархии - PullRequest
Новая
       13

PHP usort для строковой иерархии

0 голосов
/ 25 января 2019

У меня есть массив со строковой иерархией, такой как: 

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 для строковых иерархий?

Ответы [ 2 ]

0 голосов
/ 25 января 2019

В основном вам нужно рекурсивно обрабатывать данные, чтобы разобрать в них древовидную структуру и упорядочить их.Эта функция сделает это.Он ищет дочерние элементы текущего родителя (выбирая их через 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_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

Демо на 3v4l.org

0 голосов
/ 25 января 2019 
<?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;
}

  • В вышеприведенной функции мы создаем 2 вида массивов, а именно $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_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);
    }
}

  • Здесь мы перебираем всех родителей верхнего уровня, сохраняя их в массиве result с помощью no. раз они встречались в исходном массиве.

  • Как только мы это сделаем, мы бы теперь проследили за его дочерними элементами и включили все его дочерние элементы в массив результатов.

Часть 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. Вполне возможно, что у этого ребенка могут быть и собственные дети. Таким образом, мы рекурсивно собираем их все, используя поиск в глубину . Таким образом, мы всегда заботимся о том, чтобы родитель был раньше ребенка.

  • В последнем разделе мы просто выводим результат.

...