Building a nested sets tree consisting of collapse \ spoiler

Question

In the database there is a data structure Nested sets and a project using yii2 / It is necessary to display this structure, as a nested Collapse .

Here is the structure sorted by RGT:

The result should be the following:

 -*spoiler* --*spoiler* --*spoiler* ----*spoiler* -*spoiler* --*spoiler* ----*spoiler* -*spoiler* -*spoiler* -*spoiler* -*spoiler* -*spoiler* -*spoiler* -*spoiler* --*spoiler* -*spoiler*

Adding spoiler is as follows. This is a yii2 widget that returns the layout of spoilers, with styles already applied and id on which will be js minimized:

 private static function createCollapse($label, $content) { return Collapse::widget( [ 'items' => [ [ //В таблице поле LABEL 'label' => $label, //В качестве контента ID записи 'content' => $content ] ] ] ); }

The layout looks like this:

 <div class="panel panel-default"> <div class="panel-heading"> <h4 class="panel-title"><a class="collapse-toggle collapsed" href="#w7-collapse7" data-toggle="collapse" data-parent="#w7" aria-expanded="false">Main Spoiler</a></h4> </div> <div id="w7-collapse7" class="panel-collapse collapse" aria-expanded="false" style="height: 0px;"> <div class="panel-body"> <div id="w6" class="panel-group collapse in" aria-expanded="true" style=""> <div class="panel panel-default"> <div class="panel-heading"> <h4 class="panel-title"><a class="collapse-toggle collapsed" href="#w6-collapse1" data-toggle="collapse" data-parent="#w6" aria-expanded="false">Sub spoiler</a></h4> </div> <div id="w6-collapse1" class="panel-collapse collapse" aria-expanded="false" style="height: 0px;"> <div class="panel-body"> content </div> </div> </div> <div class="panel panel-default"> <div class="panel-heading"> <h4 class="panel-title"><a class="collapse-toggle collapsed" href="#w6-collapse2" data-toggle="collapse" data-parent="#w6" aria-expanded="false">Sub Spoiler</a></h4> </div> <div id="w6-collapse2" class="panel-collapse collapse" aria-expanded="false" style="height: 0px;"> <div class="panel-body"> content </div> </div> </div> </div> </div> </div> </div>

As I understand it, just going through the root for all children will not work, because every top spoiler widget should already be aware of its content, which can in turn consist of an unlimited number of same spoiler widgets, and so on to infinity.

One solution is to get the table sorted by RGT in one request and check the current LVL for 3 cases - more \ less \ equal - an example of implementation with <ul><li> . But I can’t adapt this example to the use of the widget :(

The second option, as suggested by @fedornabilkin, but nested sets do not store the parent id , and again, there is a difficulty with wrapping it in Collapse::widget

I will be glad to any help!

Let us briefly and clearly, an example of a tree (data) and an example of output (html)?
I am now thinking about such a decision, but there is no result yet :( One of the drawbacks is a very large number of queries to the database. It turns out at each recursion step I should contact the database for the number of children or parents. And it is not clear which side to start from parents, and go down the kids, or vice versa?
if the widget goes to the database in each, then do not use it, build it manually.

Answer 1 · 2019-02-26T09:40:51

I believe that it is necessary to receive all data in one request. Then prepare a multidimensional array in which the children are expanded for each parent.

 $cats = []; foreach($rows as $model){ $cats[$model->parent][] = $model; }

And then throw this array into the recursive method. Something like this for building lists in a tree.

 public static function createTree($cats, $parent) { if(isset($cats[$parent]) && is_array($cats[$parent])) { $tree = '<ul>'; foreach ($cats[$parent] as $model) { $tree .= '<li>' . $model->title; $tree .= self::createTree($cats, $model->id); $tree .= '</li>'; } $tree .= '</ul>'; } else{ return null; } return $tree; }

In the view, we call the echo className::createTree($cats, 1); method echo className::createTree($cats, 1);

UPD
For clarity, you can run sample code:

 $rows = []; $rows[] = ['id' => 1, 'title' => 'title 1', 'parent' => 0]; $rows[] = ['id' => 2, 'title' => 'title 2', 'parent' => 0]; $rows[] = ['id' => 3, 'title' => 'title 1 1', 'parent' => 1]; $rows[] = ['id' => 4, 'title' => 'title 1 2', 'parent' => 1]; $rows[] = ['id' => 5, 'title' => 'title 1 2 1', 'parent' => 4]; $rows[] = ['id' => 6, 'title' => 'title 1 2 2', 'parent' => 4]; $rows[] = ['id' => 7, 'title' => 'title 3', 'parent' => 0]; $rows[] = ['id' => 8, 'title' => 'title 3 1', 'parent' => 7]; $rows[] = ['id' => 9, 'title' => 'title 3 2', 'parent' => 7]; foreach($rows as $model){ $cats[$model['parent']][] = $model; } function createTree($cats, $parent) { if(isset($cats[$parent]) && is_array($cats[$parent])) { $tree = '<ul>'; foreach ($cats[$parent] as $model) { $tree .= '<li>' . $model['title']; $tree .= createTree($cats, $model['id']); $tree .= '</li>'; } $tree .= '</ul>'; } else{ return null; } return $tree; } echo createTree($cats, 0);

This option means only double nesting, but my nesting is unlimited: (
Added code for example and a screen with the result of the output.
Initially, I didn’t quite understand your code, but it became much clearer with the update and example.
But there are several nuances: 1) nested sets do not store parentID data in their records, so preparing a multidimensional array using one request, as you suggest, will not work.
2) To wrap tags <li> and <ul> is much easier than to wrap in a widget.
As I understand it, each top-level widget already owes its content.
The task is complicated by the fact that at each level there can be the same unlimited number of widgets.
If the node does not store the id of the parent, it can be obtained by the left and right keys.
At the parent the left key is always smaller, and the right one is always larger.
When retrieving data, you can create a virtual field (a property of the model) and write the parent ID there.
The recursive method will allow to process any number of levels.

Roman Andreev Roman Andreev 258 one 14 · Accepted Answer · 2019-03-03T08:42:44

So, having a little understood with recursion and nested sets , this solution was written:

We get the tree that needs to be drawn, in one request from the database:
SELECT * FROM table WHERE ROOT = $ root ORDER BY lft

Next, create auxiliary functions to search for children and filter the tree by LVL :

 /** * Выделяет из дерева $tree потомков узла $node * * @param Tree[] $tree Массив узлов дерева для фильтрации * @param Tree $node Узел дерева потомки которого будут возвращены * @return Tree[]|[] */ public static function filterChildren(array $tree, Tree $node) { return array_filter( $tree, function ($element) use ($node) { return $element->LFT > $node->LFT && $element->RGT < $node->RGT && $element->ROOT === $node->ROOT; } ); } /** * Фильтрация дерева по параметру LVL; * Результирующий массив будет содержать только узлы с уровнем `$lvl` * * @param Tree[] $tree Массив узлов дерева для фильтрации * @param int $lvl Уровень по которому осущесвляется фильтрация * @return Tree[] */ public static function filterByLvl(array $tree, $lvl) { return array_filter( $tree, function ($element) use ($lvl) { return $element->LVL === $lvl; } ); }

Method for rendering collapses, in fact, to reduce the code:

 private static function createCollapse(Tree $node, $content) { return Collapse::widget( [ 'items' => [ [ 'label' => $node->NAME, 'content' => $content ] ] ] ); }

The recursive function itself will look like this:

 /** * Рендеринг дерева в виде спойлеров. * * Метод возвращает HTML верстку дерева выполненную в виде вложенных друг в друга спойлеров. * * @param array $roots Массив узлов дерева для которых необходимо построить спойлеры * @param array $fullTree Полное дерево, включая детей и предков всех элементов * * @return string */ public static function renderAsCollapses(array $roots, array $fullTree) { $collapses = ''; foreach ($roots as $key => $node) { /** @var Tree $node */ //Проверка на наличие потомков if ($node->RGT - $node->LFT > 1) { $collapses .= self::createCollapse( $node, self::renderAsCollapses( ClassifierTree::filterChildren($fullTree, $node), $fullTree, ) ); } else { $collapses .= self::createCollapse( $node, 'content' ); } } return $collapses; }

Using:

  //$tree содержит массив элементов дерева, полученный из БД с помощью запроса //SELECT * FROM table WHERE ROOT = $root ORDER BY lft $collapses = TreeViewHelper::renderAsCollapses( //Для корректной работы функции, первым аргументом необходимо передать //массив корневых элементов, для которого будет строится дерево. //Начинать построение можно от любого уровня вложенности. Tree::filterByLvl($tree, 1), $tree, );

It looks a bit strange that two arrays must be passed to the function. This is done so that when the function is called for the first time, spoilers are drawn only for the root elements. If the entire tree is transferred to the function, the rendering function will be executed in general for each node of the tree. In this case, the output we get as many spoilers as there are elements in our tree, plus each element having descendants will also contain nested spoilers. Perhaps this problem can be avoided in a more concise way, but, unfortunately, I could not find it. I would be glad if someone tells you.

The only thing that confuses me in this decision is the question of stack overflow. How big should the nesting be to make the stack overflow?

Building a nested sets tree consisting of collapse \ spoiler

2 answers 2

More articles: