Как из дерева сделать 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 = "
<ul>";
	$open  = "</li>
<li>";
	$close = "</li>
</ul>";
	$left  = "
<ul>
<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("
", $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);
?>