Использование простых алгоритмов в PHP: рекурсивный метод

Заметил забавную тенденцию в развитии современных web-программистов: мы с уверенностью работаем с фабриками, синглтонами и декораторами, но пренебрегаем основополагающими аспектами программирования, такими как классические алгоритмы.

Ведь если пристально рассмотреть способы их реализации, можно заметить, что они, по сути, являются разновидностями паттернов. Например, вспомнив учебные примеры из института, мы можем вспомнить такие реализации, как nested sets, b-tree и сортировку «пузырьком». Множество алгоритмов уже давно устоялось и сегодня я бы хотел рассмотреть их применение в PHP.

Для начала, я хотел бы рассказать о самом простом алгоритме – построении древовидной иерархии.

Казалось бы, что тут сложного? В базе данных есть таблица примерно следующего содержания:

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

Алгоритм (паттерн, если так хотите) будет примерно следующим:

0. Создаём объект дерева и выбираем все элементы в таблице.

1. Вызываем метод построения. Он инициализирует сборку массива родительских категорий. Именно этот момент является ноу-хау данного алгоритма. Он позволяет нам организовать изящную рекурсию.

2. Итеративно обходим массив, начиная с нулевого элемента. Выводим информацию о текущем элементе.

3. Увеличиваем уровень погружения. Рекурсивно вызываем метод для дочернего элемента. Если он есть в массиве родительских категорий, то идем к шагу 2, иначе — выходим в шаг-инициализатор.

4. Уменьшаем уровень погружения. Выходим из итерации.

Итак, метод сборки массива категорий будет выглядеть примерно вот так:

   private function getCategoryArray() {
        $query = $this->db_connect->prepare("SELECT * FROM tree_table");
        $query->execute();
        $result = $query->fetchAll(PDO::FETCH_OBJ);

        $category_array = array();
        foreach ($result as $value) {
            $category_array[$value->id_parent][] = $value;
        }

        return $category_array;
    }

Далее напишем наш рекурсивный метод в соответствии с приведенным выше алгоритмом:

    public function buildTree($parent_id, $tree_level) {
        if (isset($this->category[$parent_id])) { 
            foreach ($this->category[$parent_id] as $value) { 
                echo "
" . $value->id_tree_test . " : " . $value->title . "
";
                $tree_level++;
                $this->buildTree($value->id_tree_test, $tree_level); 
                $tree_level--;
            }
        }
    }

Теперь можем вызвать построение дерева, начиная с 0 элемента и 0 уровня. Замечу, что приведённый метод может вызывать построение с любой вложенной ноды и не ограничен по глубине.

    $tree = new Tree();
    $tree->buildTree(0, 0); 

А вот как будет выглядеть наше дерево в итоге:

<?php

class Tree {

    private $db_connect = null;
    public  $category = array();
    public  $tree = array();

    public function __construct() {
#        $this->db_connect = new PDO("mysql:dbname=devenergru_drup1;host=localhost", "devenergru_drup1", "weduucixwa");
        $this->category = $this->getCategoryArray();
     }

    private function getCategoryArray() {
        $category_array = [
        0 => [
            [
                'id_tree_test' => 2,
                'id_parent' => 0,
                'title' => "Два"
            ]
        ],
        1 => [
            [
                'id_tree_test' => 4,
                'id_parent' => 1,
                'title' => "Четыре"
            ]

        ],
        2 => [
            [
                'id_tree_test' => 1,
                'id_parent' => 2,
                'title' => "Один"
            ],
            [
                'id_tree_test' => 5,
                'id_parent' => 2,
                'title' => "Пять"
            ]
        ],
        4 => [
            [
                'id_tree_test' => 3,
                'id_parent' => 4,
                'title' => "Три"
            ]
        ]
    ];

        return $category_array;
    }

    public function buildTree($parent_id, $level) {
        if (isset($this->category[$parent_id])) { 
            foreach ($this->category[$parent_id] as $value) { 
                echo "<div style=\"margin-left:" . ($level * 25) . "px;\">" . $value["id_tree_test"] . " : " . $value["title"] . "</div>";
                $level++;
                $this->buildTree($value["id_tree_test"], $level); 
                $level--;
            }
        }
    }

}

$tree = new Tree();
$tree->buildTree(0, 0); 

?>

Данный подход может быть использован при создании меню на веб-сайте или каталогов товаров и так далее. Он, конечно, имеет свои недостатки. Если иметь дело с большим каталогом, то время работы метода может занимать длительное время. Но здесь есть выгода в том, что метод может быть изменен и ограничен не только уровнем входа, но и уровнем погружения. Таким образом, можно постепенно расширять дерево по мере запросов пользователей, что позволит решить данную проблему.

Стоит отметить, что я не рассматриваю здесь вопросы хранения такой структуры данных, так как в данный момент нас интересует только обход массива.

На этом всё!