Как сгенерировать массив бинарной структуры используя Nested Set?

Question

[nepster-web]

Использую Nested Set для построения структур пользователей и наткнулся на следующий вопрос:

К примеру у нас есть вот такой код для генерации списка:

foreach ($struct as $n => $user)
    {
        if ($user['level'] == $level) {
            echo Html::endTag('li') . "\n";
        } elseif ($user['level'] > $level) {
            echo Html::beginTag('ul') . "\n";
        } else {
            echo Html::endTag('li') . "\n";
    
            for ($i = $level - $user['level']; $i; $i--) {
                echo Html::endTag('ul') . "\n";
                echo Html::endTag('li') . "\n";
            }
        }
    
        echo Html::beginTag('li');
        echo $user['user_id'];
        $level = $user['level'];
    }
    
    for ($i = $level; $i; $i--) {
        echo Html::endTag('li') . "\n";
        echo Html::endTag('ul') . "\n";
    }

На выходе:

500
    501
    533
        516
504
    505
        506

Массив $struct:

Array
(
    [0] => Array
        (
            [user_id] => 500
            [previous_id] => 234
            [side] => R
            [lft] => 2
            [rgt] => 9
            [level] => 2
        )

    [1] => Array
        (
            [user_id] => 501
            [previous_id] => 500
            [side] => R
            [lft] => 3
            [rgt] => 4
            [level] => 3
        )

    [2] => Array
        (
            [user_id] => 533
            [previous_id] => 500
            [side] => L
            [lft] => 5
            [rgt] => 8
            [level] => 3
        )

    [3] => Array
        (
            [user_id] => 516
            [previous_id] => 533
            [side] => L
            [lft] => 6
            [rgt] => 7
            [level] => 4
        )

    [4] => Array
        (
            [user_id] => 504
            [previous_id] => 234
            [side] => L
            [lft] => 10
            [rgt] => 15
            [level] => 2
        )

    [5] => Array
        (
            [user_id] => 505
            [previous_id] => 504
            [side] => L
            [lft] => 11
            [rgt] => 14
            [level] => 3
        )

    [6] => Array
        (
            [user_id] => 506
            [previous_id] => 505
            [side] => L
            [lft] => 12
            [rgt] => 13
            [level] => 4
        )

)

Мне нужно отрендерить бинарную структуру


Проблема состоит в том, что не могу сгенерировать подходящий массив.

Подскажите пожалуйста как это этого массива, можно сгенерировать что-то такое:

Array
(
    [0] => Array
        (
            [0] => Array
                (
                    [user_id] => 500
                    [previous_id] => 234
                    [side] => L
                )

            [1] => Array
                (
                    [user_id] => 504
                    [previous_id] => 234
                    [side] => R
                )

        )

    [1] => Array
        (
            [0] => Array
                (
                    [user_id] => 501
                    [previous_id] => 500
                    [side] => L
                )

            [1] => Array
                (
                    [user_id] => 533
                    [previous_id] => 500
                    [side] => R
                )

            [2] => Array
                (
                    [user_id] => 505
                    [previous_id] => 504
                    [side] => L
                )

            [3] => Array
                (
                )

        )

    [3] => Array
        (
            [0] => Array
                (
                )

            [1] => Array
                (
                )

            [2] => Array
                (
                    [user_id] => 516
                    [previous_id] => 533
                    [side] => L
                )

            [3] => Array
                (
                )

            [4] => Array
                (
                    [user_id] => 506
                    [previous_id] => 505
                    [side] => L
                )

            [5] => Array
                (
                )

            [6] => Array
                (
                )

            [7] => Array
                (
                )

        )

)

Answer 1

[_ _]

У вас будет структура вроде той, что ниже, у которой subitems это массив элементов этой же структуры. В data храните полезную нагрузку для узла (в вашем случае user_id, L, R):

array(
'id' => ...,
'data' => array(...),
'subitems' => array(...)
)

Заводите индексный массив ссылок $node_index = array(); и массив результатов $result = array();
Сортируете исходный массив по возрастанию level, после чего делаете что-то вроде:

foreach($node in $source_array) {
   if(!($parent_node = $node_index[$node['previous_id']])) {
       $result[$node['previous_id']] = array(
           'id' => $node['previous_id'],
           'data' => array(...),
           'subitems' => array()
       );
       $node_index = &$result[$node['previous_id']];
       $parent_node = $node_index[$node['previous_id']];
   }
   $parent_node['subitems'][$node['id']] = $node;
   $node_index[$node['id']] = &$parent_node['subitems'][$node['id']];
}

Не могу утверждать, что код 100% рабочий, написал по памяти. Суть его в том, что $node_index является хэшем id ноды => ссылка на нее. Без этого массива пришлось бы мудрить рекурсию для того, чтобы распихать элементы по иерархии.

В результате у вас получится иерархический массив, обойдя который рекурсивно вы сможете его визуализировать.

А если совсем по-хорошему, то лучше какое-нибудь готовое дерево использовать. Это так, dirty hack, не более.

Comments

[nepster-web]

Я ж использую nested set, только для рендеринга нужна такая вот штука. На самом деле, там будет рендериться только 3 уровня. Так как больше не лезет на страницу. Большое спасибо за код, попробую и отпишусь.