Мой взгляд на деревья в PHP

Привет, собственно, этот пост я решил написать в ответ воот на это сообщение из песочницы.
Я не считаю себя профи в программировании, хотя иногда очень хочется, но все-же, я считаю, что неправильно таким способом строить деревья).
Я Буду строить не дерево комментариев, а дерево меню. Мой способ построения меню легко модифицировать и для построения дерева комментариев. Меню может иметь любое количество вложенных подменю. Моя структура таблицы меню такая:

m_Id
m_Position
m_LineId
m_ParentId
m_Type
m_Title
m_Description
m_Data


Когда я озадачился построением дерева, мне было лень думать самому, я решил поискать по этим вашим тырнетам готовые решения. Готовые решения вроде как, кто-то предлагал, но эти готовые решения были реализованы во фреймворках, что мне не подходило, остальные же, деревья строили с кучей запросов к БД, но я верил что есть способ построить сколь угодно огромное дерево всего в 1 запрос, причем, безо всяких извращенств со всякими там COUNT() и прочей лабуды. Не буду тянуть время, приведу код своего класса, который строит дерево меню:

class MenuFactory extends BaseClass 
{
    /**
     *
     * var mixed Здесь будет храниться меню в виде дерева
     */
    public $MenuTree;
    /**
     *
     * @var mixed Здесь будет храниться меню в виде списка, т.е. так, как оно хранится в базе
     */
    public $MenuList;
    
    private $level=0;
    
    /**
     *
     * @param int Id ленты меню для загрузки
     * @param int/bool Если bool==true - возвращаем меню в виде списка стиле, иначе в виде дерева меню. Если число, возвращает меню в виде дерева с глубиной равной числу
     * @return mixed 
     */
     public function GetMenu($menu_id, $return_as_list = false)
     {
         // выбираем все пункты меню из заданной ленты меню
         $this->sql->Query("SELECT * FROM `menus` WHERE `m_LineId`=?d ORDER BY m_Position, m_ParentId", $menu_id);
         // 
         $this->MenuList = array();
         $ml = array();
         while($r = $this->sql->Assoc())
         {
             // создаем экземпляр типа MenuItem из результата запроса
             $m = CommonUtils::ObjectFromArray('MenuItem', CommonUtils::DelPrefix($r,'m_'));
             // добавляем его в список элементов меню
             $this->MenuList[] = $m;
             // создаем дубликат элемента меню для того, чтобы в дальнейшем можно было построить дерево
             $ml[] = clone $m;
         }
         
         // если $return_as_list == true возвращаем меню в виде обычного списка
         if(is_bool($return_as_list) && $return_as_list)
         {
             return $this->MenuList;
         }
         // иначе, если $return_as_list == false возвращаем дерево меню
         else if(!$return_as_list)
         {
            $this->MenuTree = array();
            $this->MenuTree = $this->GetMenuChilds(0,$ml);
            
            return $this->MenuTree;
         }
         // иначе, если $return_as_list == число, возвращаем дерево меню со степенью бложенности, равной этому числу
         else if(is_numeric($return_as_list))
         {
            $this->MenuTree = array();
            $this->MenuTree = $this->GetMenuChilds(0,$ml, $return_as_list);

            return $this->MenuTree;
         }
         //print_r($this->menuTree);
     }
     
     /**
      *
      * @param int $p_id Id родительского пункта меню
      * @param mixed $menuList список элементов меню, среди которых будет осуществлен поиск дочерних пунктов
      * @param int $levels глубина поиска 
      * @return mixed Возвращает список дочерних пунктов меню
      */
     private function GetMenuChilds($p_id, $menuList, $levels = null)
     {
         // Здесь будет храниться список веток, расположенных на текущем уровне
         $a = array();
         // Проверяем каждый элемент списка
         foreach($menuList as $item)
         {
             //TODO: Optimize code
             // Если ParentId текущего элемента меню совпадает с искомым id,
             // значит, что мы нашли дочерний элемент меню. Сделаем несколько проверок
             if($item->ParentId == $p_id)
             {
                 $this->level++;
                 // если $levels указан, и его значение меньше $this->levels,
                 // значит нас просят вернуть дерево меню со вложенностью, равной $levels
                 if($levels != null && $this->level <= $levels)
                 {
                     // Получаем список дочерних пунктов меню относительно текущего. Говорим методу что нам нужно получить из 
                     // $this->MenuList список элементов меню, ParentId которых равен id текущего элемента меню,
                     // ну, и передаем информацию о текущей глубине
                     $item->ChildMenus = $this->GetMenuChilds($item->Id, $menuList, $levels);
                     // Сообщаем текущему элементу меню что он находится на глубине $this->level
                     $item->Level = $this->level;
                     // Добавляем его в список веток
                     $a[] = $item;
                 }
                 else
                 {
                     // иначе нас просто просят вернуть список дочерних пунктов меню из $this->MenuList
                     $item->ChildMenus = $this->GetMenuChilds($item->Id, $menuList);
                     $item->Level = $this->level;
                 }
                 $this->level--;
                 // $levels не указан, но ParentId текущего элемента меню равен искомому, значит он
                 // является дочерним, просто положим его в список дочерних элементов
                 if($levels == null)
                 {
                     $a[] = $item;
                 } 
             }
         }
         // отдаем список дочерних элементов меню
         return $a;
     }

     /**
      *
      * @return mixed  Возвращает обычный список элементов меню
      */
     public  function GetMenuList()
     {
         return $this->MenuList;
     }

     /**
      *
      * @param int $menu_id Id элемента меню, путь от которого до корня будет найдет
      * @return mixed список элементов меню 
      */
     public function GetMenuPathTo($menu_id)
     {
         // здесь будем хранить список элементов меню, через которые можно добраться до
         // элемента меню, путь до которого нужно найти. Назовем его ПутевойЛист
         $a = array();
         for($i=0; $i<count($this->MenuList); $i++)
         {
             // Если у текущего элемента меню id равен id искомого меню
             if($this->MenuList[$i]->Id == $menu_id)
             {
                 // добавляем его в ПутевойЛист
                 $a[] = $this->MenuList[$i];
                 // Поскольку мы нашли текущий пункт меню, нам необходимо найти его родителя,
                 // для этого переменной $menu_id устанавливаем значение, равное id родительского пункта меню
                 $menu_id = $this->MenuList[$i]->ParentId;
                 // особая, уличная магия)
                 $i=-1;
             }
         }
         // поскольку ПутевойЛист сейчас представлен в виде Ветка -> Корень,
         // переворачиваем его, и теперь он у нас представлен в правильном виде: Корень -> Ветка
         return array_reverse($a);
     }
     
     /**
      *
      * @param int $menu_id Id меню, экземпляр которого необходимо получить
      * @return MenuItem Экземплят меню 
      */
     public function GetMenuById($menu_id)
     {
         $this->sql->Query("SELECT * FROM `menus` WHERE `m_Id`=?d LIMIT 1", $menu_id);
         $record =  $this->sql->Assoc();
         if($record)
         {
             $record = CommonUtils::DelPrefix($record,'m_');
             return CommonUtils::ObjectFromArray('MenuItem', $record);
         }
         return null;
     }

    
}

Код класса, представляющего собой элемент меню:

class MenuItem 
{
    public $Id;
    public $Position;
    public $ParentId;
    public $LineId;
    public $Type;
    public $Title;
    public $Description;
    public $Data;
    public $Level;
    public $ChildMenus;
}

Не знаю, как сделать подсветку php кода, но не о том речь.
В принципе, думаю, понятно, что метод GetMenu() позволяет получить как дерево меню, так и меню в виде списка. Кроме того, если в качестве второго аргумента указать число от 0 — до бесконечности, то дерево меню загрузится с глубиной, равной этому числу.

метод GetMenuPathTo() ищет путь до элемента меню, чей id передается в качестве параметра, этот метод был реализован для огранизации хлебных крошек на сайте

CommonUtils::DelPrefix() позволяет удалить префиксы в ассоциативных массивах, позволяя получить реальные имена свойств элементов меню.
CommonUtils::ObjectFromArray() возвращает объект заданного ему класса, который будет заполнен значениями из ассоциативного массива, переданного вторым параметром.

Не спорю, возможно, кому то этот код может чем то не понравиться, но зато он отлично справляется с построением деревьев меню, всего за 1 запрос к БД.

Всем успехов.

upd:// всем, кто оставляет каменты в стиле: «чем не устроил %methodname% для построения деревьев», или «а почему не %methodname%?» торжественно заявляю: Существует куча способов построения деревьев. Я привел свою реализацию, т.к. скорее всего не знал о Ваших %methodname%. В Любом случае, Ваши комментарии для меня важны и не останутся без должного внимания.