Генерация древовидного меню модели представления Nested Sets

В процессе работы над одним из проектов передо мной встала задача создания сворачиваемого дерева папок на основе сведений о нем в базе данных. Для уточнения, это выглядит примерно так:

image

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

Мы имеем следующую структуру таблицы в БД:
id — идентификатор строки
level — уровень элемента
left_key — левый ключ
right_key — правый ключ
caption — название каталога.
Более подробно о создании такой таблицы вы можете узнать здесь.
Посредством AJAX эти данные, отсортированные по значению поля left_key, поступают на клиента, где мы должны построить на их основе вложенный список.
Список должен иметь следующую структуру:
Элемент <ul>, содержащий:
    элемент <li>, представляющий собой каталог. 
        Далее, в нем всегда есть элемент <span>, содержащий название каталога. 
        При условии наличия дочерних папок, в нем есть элемент <ul>
            и так далее...
    и так далее... 

Приступим к генерации дерева.
В первую очередь, необходимо создать функцию, возвращающую дочерние элементы или пустой массив в случае их отсутствия.
var getChilds = function(trgt, arr){
    var childs = Array();
    var length = arr.length;
    for (var i = 0; i < length; i++){
        var curr = getInts(arr[i]);
        var under = (curr.level > trgt.level) ;
        var l_in =  (curr.left_key > trgt.left_key);
        var r_in =  (curr.right_key < trgt.right_key);
        if (under && l_in && r_in) childs.push(arr[i]);
    }
    return childs;
}

Эта функция делает не что иное, как проверку каждого элемента массива по заданному элементу этого же массива, то есть: если уровень рассматриваемого элемента ниже уровня заданного элемента, при том что левые и правые ключи соответственно находятся в промежутке между левым и правым ключом заданного элемента, то записываем рассматриваемый элемент в массив дочерних элементов.
Функция getInts в данном случае занимается преобразованием значений полей level, left_key и right_key в числовые значения. Нужно это для того, чтобы происходило сравнение чисел, а не строк.
var getInts = function(arr){
    temp = Object();
    for (var i in arr){
        if (i!='name') temp[i] = parseInt(arr[i])
        else temp[i] = arr[i]
    return temp
}

После получения дочерних элементов, необходимо очистить от них исходный массив. Я не придумал ничего лучше, чем написать еще одну функцию.
var cleanDuplicates = function(from, elements){
    var length = arr.length;
    for (var i = 0; i < length; i++){
        if ($.inArray(from[i], elements) > -1)
            delete from[i]
    }
    return from;
}

Здесь массив elements содержит элементы, которые требуется удалить из массива from.
И, наконец, строим список, используя вышеприведенные функции.
var ul = function(arr){
    if (!arr[0]) return ''
    else{
        var html = '<ul>';
        var length = arr.length;
        for (var i = 0; i < length; i++){
            var el = arr[i];
            var childs = getChilds(el, arr);
            arr = cleanDuplicates(arr, childs)
            html += '<li>'+'<span id="cat_'+el.id+'">'+el.name+'</span>'
            html += ul(childs)
            html += '</li>'
        }
        return html + '</ul>'
    }
}

Пример использования:
'<div class="tree">' + ul(data) + '</div>'

где data — данные, полученные с сервера.
Для конечного преобразования этого списка в древовидное меню существует достаточно большое количество плагинов для jQuery, к примеру jQuery Treeview.
Работа с ним достаточно проста. Необходимо сперва подключить сам jQuery, затем этот плагин. После подключения достаточно просто натравить его на блок, содержащий ваш сгенерированный список. Если брать из примера, то это элемент $('.tree').
$('.tree').treeview();

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

P. S. Обратите внимание, что плагин jQuery Treeview больше не развивается, но для построения простого древовидного меню функций этого плагина более чем достаточно. Сам разработчик предлагает использовать плагин JqTree.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 23

    +7
    Очередная тривиальная задача, решение которой гуглится ровно одну минуту.
    Скажите, какая религия помешала воспользоваться классическим parent вместо избыточных level, left_key и right_key?
      +4
      Отвечу за автора, это реализация Nested Set, довольно удобная штука если нужно вытягивать часть ветки целиком. А вообще да, задача тривиальная и parent тут больше подходит.
        0
        Вообще говоря, такую структуру завели для хранения большого количества папок с последующей AJAX-подгрузкой с целью уменьшить нагрузку на БД.
        0
        В моем конкретном случае, так удобнее задавать положение папки (выше-ниже), основываясь на значениях left key и right_key. А как вы предлагаете организовать сортировку «по-важности», как часто бывает у заказчиков?
          +2
          как вы предлагаете организовать сортировку «по-важности», как часто бывает у заказчиков?
          Дополнительным целочисленным полем «vazhnostj» в таблице, и сортировать по нему? :)
            +1
            Предлагаю такую таблицу
            id — идентификатор строки
            parent — id родителя
            caption — название каталога
            order — число задающее порядок сортировки элементов.

            Далее при рекурсивной отрисовке одного уровня делаем сортировку детей по важности. Ее можно сделать как средствами ЯП, так и СУБД, если делать для отрисовки детей каждого элемента отдельный запрос.
            0
            У меня два вопроса:
            1. Почему вы используете for(... in ...) для итерирования массивов?
            2. Почему вы не используете литералы для создания массивов и объектов?
              0
              1. Осталась плохая привычка от итерирования объектов, надо искоренять.
              2. Использовал сперва, но для пущей наглядности решил сделать как есть теперь.
                0
                Не совсем понимаю, что вы имеете в виду под пущей наглядностью. Дело в том, что использование литералов вместо конструкторов в JavaScript — это очень хорошая практика. Ваш код, например, может некорректно работать, если переопределить функцию Array(). Использование же литералов упасет вас от такой проблемы. К тому их использование соответствует принципу KISS.
                0
                А чем плох for(... in ...) для массива?
                  +1
                  Плох тем, что итерация идет и не по числовым индексам тоже, а среди них обычно бывают совсем не элементы массива. В общем случае желательно использовать обычный for по длине массива, или forEach(нет поддержки IE). У jQuery также есть свои методы, к примеру тот же $.each()
                    0
                    Всегда делал так for (var i in arr) if (arr.hasOwnProperty(i)) { ... } и не парился массив это или объект.
                    Думал может дело в скорости.
              +1
              А почему бы всем дружно не добавить в комментарии свои варианты реализации?
              Получится нормальный справочник по реализации конкретной задачи, с примерами, обсуждением и т.п.

              P.S. Не девелопер.
                +2
                Oracle и Ruby.

                В БД таблица с полями id, pid и другими. К ней выполняется иерархичный запрос вида

                …
                CONNECT BY PRIOR id = pid AND PRIOR pid <> PRIOR id START WITH pid = 0
                

                (в последних версиях Oracle можно дописать NOCYCLE вместо второго условия) возвращающий level помимо прочих полей.

                На основе запроса следующий код формирует HTML:
                html = "<ul>\n"
                prev_lvl = 1
                
                DB.fetch(sql) do |row|
                  cur_lvl = row[:lvl].to_i
                
                  0.upto(prev_lvl - cur_lvl) { html += "</ul>\n" } if cur_lvl < prev_lvl
                
                  html += "<ul>\n" if cur_lvl != prev_lvl
                
                  html += "<li>#{row[:title]}\n"
                
                  prev_lvl = cur_lvl
                end
                
                html += "</ul>"
                
                0
                > проверку каждого элемента массива по заданному элементу этого же массива

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


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

                Вам нужно построить массив-индекс по полю parent_id

                TREE — исходный массив
                BOOST — массив-индекс

                1) Один раз пробегаетесь TREE и для каждого элемента

                for NODE in TREE
                   BOOST[NODE.parent_id].push NODE
                


                Теперь дочки для любого узла выбираются очень просто:

                 BOOST[NODE.id] #=> массив вложенных
                


                Готовое и весьма быстрое решение для больших деревьев в моей репе на гитхабе:

                github.com/the-teacher/the_sortable_tree/blob/master/app/assets/javascripts/render_tree_helper.js.coffee#L29

                Алгоритм настолько хорош, что прекрасно работает даже на ruby. Что уже само по себе является хорошим доказательством целесообразности подхода.
                  0
                  В чем именно заключается
                  рекурсивный ад
                  ?
                    0
                    — берем узел => перебираем массив для поиска дочерних элементов
                    — — берем дочерний 0, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
                    — — — берем дочерний 0, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
                    — — — берем дочерний 1, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
                    — — — берем дочерний 2, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
                    — — берем дочерний 1, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
                    — — — берем дочерний 0, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
                    — — — берем дочерний 1, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
                    — — — берем дочерний 2, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
                    — берем узел => перебираем массив для поиска дочерних элементов. Удаляем дочерние из исходного

                    Ваш алгоритм так работает?
                    При выборке дочерних проверяются условия на left, right?
                    Вы еще и перебираете исходный, что бы очистить его?

                    OMG! это и есть ад.

                    Попробуйте построить дерево из 16.000 элементов не на JS или на JS, но на слабой машине.

                    Вы пытаетесь оптимизировать

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

                    Но это

                    1) не очень эффективно
                    2) уничтожает исходный массив, который еще может пригодиться

                    Как бы не злословили в ваш адрес комментаторы, о том, что построить дерево — это очень просто и тривиально — никому не верьте, здесь тоже нужно пошевелить мозгами.
                      0
                      Да, код работает именно так, спасибо за замечания, обязательно учту в дальнейшем. Скажите пожалуйста, как именно может понадобиться исходный массив? Просто склонировать и оставить жить его можно без проблем, но я не могу понять смысла в его существовании, по крайней мере в пределах этой задачи.
                      При выборке дочерних проверяются условия на left, right?

                      А ведь без этого никуда, чем предлагаете заменить?
                      1) не очень эффективно

                      Как по-вашему, увеличит ли эффективность кода удаление элемента из массива элемента сразу при выполнении условия
                      if (under && l_in && r_in) {childs.push(arr[i]); /*здесь что-то вроде delete arr[i]*/}
                      
                        0
                        я не могу понять смысла в его существовании

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

                        В этом случае удалять элементы дерева не следует.

                        ключи left и right требуются в основном для сортировки. А потому с этой задачей прекрасно справляется серверная часть при выборке из БД.

                        Как по-вашему, увеличит ли эффективность кода удаление элемента из массива элемента сразу при выполнении условия

                        Удаление элементов никакого существенного прироста не дает.

                        Еще раз повторюсь — вам нужен массив-индекс, который позволит выбирать дочерние элементы мгновенно и пачками для заданного узла.

                        По сути, вы получаете мега-прирост производительности за счет 2-х кратного увеличения памяти. Т.к. массив фактически копируется, но с другим порядком элементов.

                        В языках, где элементы массива не копируются, а на них создается ссылка — вообще сказка, даже 2-х кратного увеличения памяти нет.

                        с 2008 года я лично адекватного решения задачи отрисовки Nested Set не нашел, потому сделал сам. И судя по всему весьма успешно.

                        Внутри моего гема вы сможете найти и руби реализацию и JS (CoffeeScript) реализацию.
                          0
                          Спасибо за разъяснения, очень познавательно. Вы оправдываете ваш ник на гитхабе)

                Only users with full accounts can post comments. Log in, please.