Есть модель Category, я в ней уже реализовал методы: Код (PHP): hasCategory($id) return bool hasChildren($id) return bool hasParent($id) return bool getChildren($id) return $this->where('parent_id', '=', $id) getParent($id) return $this->where('id', '=', $this->find($id)->parent_id) Затруднения возникли при построение деревьев сделал метод private loopParents($id, array &$parents) который сам себя вызывает и строит массив родительных категорий, и ещё обёртку для этого метода getParents($id). Начал делать метод loopChildrens($id, array &$children) и тут у меня окончательно фантазия кончилась, хотелось бы иметь вид массива на выходе: Код (PHP): array( 'id' => array( Данные категории 'children' => array( 'id' => дальше повторяется ) ) ) Как подобное реализовать? Подсказка от модератора: Любой код или текст конфигурации пишите между тегом [code=php] и [/code]. Используйте отступы в коде для форматирования текста. Это помогает быстрее понять вас, увеличивает шанс на получение ответа. Что выделять? Например: PHP, HTML, CSS, JavaScript, SQL, XML, .htaccess, ini, регулярные выражения, код шаблонизаторов, любая другая разметка, результаты array/object dump и т. д.
Гугло поиск не чего не дал. Мне хотя бы кто нибуть теорию построения деревьев объяснил, а дальше я сам бы уже написал.
Ты искал отдельно? Adjacency List Matherialized Path Nested Set Добавлено спустя 2 минуты 58 секунд: https://github.com/etrepat/baum
Да, с несколько дней назад ещё. Я на него посматривал, но я так и понял зачем в таблице иметь колонки left и right, поэтому мимо прошёл.
А как вывести всё дерево категорий, точнее как это правильно сделать. Можно конечно смешать вывод с контроллерами и написать функцию для вывода но это уже как то не правильно, не люблю я делать ТТУК'и. А в blade как это сделать в голову даже не приходит.
И в итоге у меня вот такая фигня получилась, не красиво и не правильно наверно. Код (PHP): <?php function loopCategories($array = null) { echo '<ul class="categories">'; foreach(($array ? $array : app('App\Category')->roots()->get()) as $category) { echo '<li>' . $category->name; loopCategories($category->getDescendants()); echo '</li>'; } echo '</ul>'; } ?> <div class="panel panel-default"> <div class="panel-heading"> <h3 class="panel-title">Категории</h3> </div> <div class="panel-body"> {{ loopCategories() }} </div> </div>
Это вы так с nested sets маетесь? Зачем? Вы же постоянными вызовами getDescendants() на нет сводите преимущества nested sets. У вас же есть поле depth. Вот из моего проекта, тоже nested sets, только с другим фреймворком. $menu здесь - это все потомки корневого узла, level - то, что у вас должно depth называться. Я, правда, не использовал multi root, у меня один самый коренной элемент всегда зарезервирован Код (PHP): <?php $levels = [$menu[0]->level]; echo "<ul>"; foreach ($menu as $ind=>$item) { if ($item->level > $levels[0]) { echo "<ul>"; array_unshift($levels, $item->level); } else { while ($item->level != $levels[0]) { echo "</li></ul>"; array_shift($levels); } } if ($ind != 0) echo "</li>"; echo "<li><a href='$item->url'>$item->name</a>"; } while (!empty($levels)) { echo "</li></ul>"; array_shift($levels); }
я сейчас использую getImmediateDescendants(), и объяснил бы в чём преимущество заключается. У меня level называется. А если вложенность меню не известна твой код заработает? И дай не много пояснений, я только рекурсий и пользовался.
в NS можно выбрать любое под-дерево за один запрос. его за этим придумали. поле "глубина" это уже не классика NS и оно необязательно. неизвестно, немного - слитно
Заработает. Я только на multi-root его не пробовал, в остальном - должен как часы. Так всё же очевидно. Мы выбираем дерево и всех его потомков за один запрос. level или depth есть во всех реализациях nested sets, которыми я пользовался, поэтому этот алгоритм на него рассчитан. Начинаем идти по дереву, одновременно занося уровень, с которым работаем, в стек $levels. Таким образом мы можем определить, с каким уровнем работаем, сравнив level текущего элемента с уровнем на вершине стека (правда, в итоге получается не совсем чистый стек, поскольку мы проверяем вершину, не выталкивая её из стека, но это уже тонкости). Если уровень оказался больше, чем на вершине стека, заносим новый уровень в стек (теперь он на вершине), выводим новый ul. Если уровень меньше - немного сложнее. Скачок может быть сразу на несколько уровней вниз, поэтому идёт цикл - пока уровень на вершине стека не достиг уровня текущего элемента, закрываем ul и li и выталкиваем один элемент из стека. Ну и после того, как все элементы выведены, повторяем цикл закрытия, до тех пор, пока стек не станет пустым. Добавлено спустя 8 минут 22 секунды: Кстати, artoodetoo, было бы интересно, если бы вы предложили решение этой задачи без стека и рекурсии, или хотя бы без глубины. Я не представляю себе такого решения.
в исходном алгоритме Joe Celko есть только left и right, насколько я помню. depth упрощает нахождение immediate children. зачем оно для вывода всего поддерева, я не понимаю, если честно. меню ведь строится по всему списку?! конкретно построение меню по NS: http://habrahabr.ru/post/188118/ Добавлено спустя 1 минуту 35 секунд: я бы предложил итерацию со стеком.
Ещё бы не забыть все эти построения дерева кэшировать, часть в массив, другую часть как сформированный html.
mkramer, как не странно но твой способ "не работает" всё зависит от порядка элементов массива, вот с этим массивом всё норм (left и right отпустил): Код (PHP): [ [ 'id' => 1, 'level' => 0, 'parent' => 0 ], [ 'id' => 2, 'level' => 1, 'parent' => 1, ], [ 'id' => 3, 'level' => 0, 'parent' => 0 ], ] Вот с таким заработает но вложеность будет не правильная: Код (PHP): [ [ 'id' => 1, 'level' => 0, 'parent' => 0 ], [ 'id' => 2, 'level' => 0, 'parent' => 0 ], [ 'id' => 3, 'level' => 1, 'parent' => 1, ], ] А если всё вразброс и неограниченный уровень вложенности, так вообще ошибок хренова туча. Это массив надо как то сортировать что бы дочерние элементы стояли за родительными.
Alex5646, со вторым да, не сработает. Но я же рассчитывал алгоритм на правильную выборку Nested Sets, с сортировкой по left. Иначе Nested Sets вообще смысла не имеют, если не делать сортировку по left при выборках. Эта сортировка как раз и обеспечит, что дочерние элементы будут идти за родительскими.
А моя выборка то есть не правильная? Я выбираю комментарии по post_id. Как мне узнать нужный left, если в комментариях полнейший хаос?
Ну так, к каждому post_id своё дерево комментариев строится, ведь комменты разные. Я обычно ставлю корневой комментарий к каждому посту, а потом выбираю его потомков. То есть при добавлении коммента к посту (если нужны древовидные), я создаю корневой сначала узел,с 0 уровнем, и содержанием типа "Comments for post 123", и потом уже добавляю к нему потомков. Таким образом полный порядок. Честно говоря, пришло решение это само собой. Надо решить, или использовать nested sets и его преимущества, или parent_id с вечной рекурсией. Есть люди, которым не нравятся Nested Sets, они предлагают строить рекурсивные массивы и потом использовать SPL для обхода, мне больше нравится мой способ. Если бы мы сразу обсуждали комменты, я бы это сразу написал, но мы обсуждали категории, которые обычно сами по себе