Как из дерева сделать ul-li структуру?

Получилось, что я немного меньше стал публиковать записей в блоге, но на это есть довольно веские причины. Помимо работы я постоянно занимаюсь MaxSite CMS.

Столкнулся с одной проблемой, может кто поможет её решить. (Самому уже не хвататет уже ни терпения, ни ума).

Задача связана с выводом рубрик. Есть таблица рубрик, где есть поля:

• category_id (номер рубрики)
• category_id_parent (номер родителя)

Теоретически этого хватает, чтобы организовать древовидную структуру (массив).

Я её реализовал классическим способом: через рекурсию. То есть для поиска «детей» выполняется еще один SQL-запрос. Соответственно при большом количестве рубрик и её «ветвистости» получается довольно много SQL-запросов.

Частично эту проблему можно решить за счет кэширования: получается где-то раза в два меньше.

Погуглив я нашел еще один способ создания деревьев: в нем указывается отступ слева (level). Например так («Код 1»):

001            level = 0
    002        level = 1
    003        level = 1
        004    level = 2
    005        level = 1

Путем различных манипуляций с массивом я смог сделать аналогичную структуру рубрик. При этом понадобился всего один SQL-запрос. Получилась примерно так:

[1] => Array
        (
            [category_id] => 1
            [category_id_parent] => 0
            [category_name] => Новости
            [category_menu_order] => 4
            [parents] => 0
            [childs] =>
            [level] => 0
        )
    [3] => Array
        (
            [category_id] => 3
            [category_id_parent] => 0
            [category_name] => CodeIgniter
            [category_menu_order] => 1
            [parents] => 0
            [childs] => 6 5
            [level] => 0
        )
    [6] => Array
        (
            [category_id] => 6
            [category_id_parent] => 3
            [category_name] => Еще
            [category_menu_order] => 0
            [parents] => 3
            [childs] =>
            [level] => 1
        )
...

Это «одномерная» структура, где сразу указываются и level (отступ), и все «дети» (childs), и родитель (parents). Всей этой информации по идее должно хватить на то, чтобы выстраивать и получать любые рубрики.

Теперь, чтобы выстоить рубрики по уровню, вполне достаточно одного level. И в принципе сделать это с помощью str_pad - две строчки кода (результат будет выглядеть как «код 1»).

Но дальше - ступор... Потратил несколько дней, но так и не смог придумать, каким образом все это конвертировать в ul-li. Сложность в том, что простыми заменами кажется не обойтись из-за вложенности тэгов. Чтобы было совсем понятно, нужно конвертировать «Код 1» (или сам массив) вот в это:

• 001

• 002
• 003

• 004
• 005

HTML-код:

<ul>
    <li>001
        <ul>
            <li>002</li>
            <li>003
                <ul>
                    <li>004</li>
                </ul>
            </li>
            <li>005</li>
        </ul>
    </li>
</ul>

Кто-то знает как решить эту задачку?

[upd] Вот мой вариант решения, основанный только на level. Передполагается, что массив ($r) уже отсортирован в нужной последовательности.

function mso_tree_print($r)
{
    $out = "\n<ul>";
    $open  = "</li>\n<li>";
    $close = "</li>\n</ul>";
    $left  = "\n<ul>\n<li>";
    $old_level = 0;
    $open_li = 0;
    foreach ($r as $key=>$val)
    {
        $level = $val['level'];
        if ($level == $old_level)
        {
            $out .= $open . $val['category_name'];
        }
        elseif ($level > $old_level)
        {
            $open_li = $open_li + $level - $old_level;
            $out .= $left . $val['category_name'];
        }
        else // $level < $old_level
        {
            if (( $open_li) > 0)
                $out .= str_repeat($close, $open_li);
            $out .= $open . $val['category_name'];
            $open_li = 0;
        }
        $old_level = $level;
    }
    $out .= $close;
    $out = str_replace("<ul></li>", "<ul>", $out);
    return $out;
}

Сорри, при переносе удалились комменты, поэтому здесь, те, которые сохранились.

TedBeer :

6 апреля 2008 г. в 18:51 edit

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

$info = Array(
1 => Array
(
'category_id' => 1,
'category_id_parent' => 0,
'category_name' => 'Один'
),
2 => Array
(
'category_id' => 2,
'category_id_parent' => 1,
'category_name' => 'Два'
),
3 => Array
(
'category_id' => 3,
'category_id_parent' => 1,
'category_name' => 'Три'
),
4 => Array
(
'category_id' => 4,
'category_id_parent' => 3,
'category_name' => 'Четыре'
),
5 => Array
(
'category_id' => 5,
'category_id_parent' => 0,
'category_name' => 'Пять'
),
6 => Array
(
'category_id' => 6,
'category_id_parent' => 4,
'category_name' => 'Шесть'
)
);
$top = Array();
foreach($info as &$item){
$parentId = $item['category_id_parent'];
$id = $item['category_id'];
if( $parentId && isset($info[ $parentId])){
if( !isset($info[ $parentId]['children']))
$info[ $parentId]['children'] = Array($id);
else
$info[ $parentId]['children'][] = $id;
} else {
$top[] = $id;
}
}
function glue( $in, &$info){
$out = Array();
foreach( $in as $id){
$out[] = '<li>'. $info[$id]['category_name'];
if( isset( $info[$id]['children'])){
$out[] = '<ul>';
$out[] = glue( $info[$id]['children'], $info);
$out[] = '</ul>';
}
$out[] = '</li>';
}
return implode("\n", $out);
}
echo '<ul>' . glue( $top, $info) . '</ul>';

Galchenkov :

7 апреля 2008 г. в 11:19 edit

'Один', 'level' => 0);
$categories[] = Array('name' => 'Два', 'level' => 1);
$categories[] = Array('name' => 'Три', 'level' => 1);
$categories[] = Array('name' => 'Четыре', 'level' => 2);
$categories[] = Array('name' => 'Пять', 'level' => 3);
$categories[] = Array('name' => 'Шесть', 'level' => 2);
$categories[] = Array('name' => 'Семь', 'level' => 0);
// Инициализируем переменную
$current_level = -1;
foreach ($categories as $category)
{
// Уровень отображаемого категории (узла, если хотите)
$category_level = $category['level'];
if ($current_level <li>'.$category['name'];
}
if ($current_level &gt; $category_level)
{
// Тут важно закрыть все открытые ранее списки (ведь из третьего
// уровня можно сразу попасть в первый)
echo str_repeat('</li></ul>', $current_level - $category_level + 1);
echo '<ul><li>'.$category['name'];
}
if ($current_level == $category_level)
{
echo '</li><li>' . $category['name'];
}
$current_level = $category_level;
}
// Тут тоже закрываем все открытые ранее списки
echo str_repeat('</li></ul>', $current_level + 1);
?>