Низкие ветвистые деревья

Под сим поэтическим названием скрывается идея удобного представления древовидных структур данных и практической его реализации. Может, что-то подобное где-то уже было, но я не встречал; и тут мой приятель Эдуард Аверюшкин предложил интересную идею, которую я попытался развить.

Классическое представление дерева сущностей (например, меню разделов сайта, главное меню в программах) довольно удобно и наглядно в случае «высокого» дерева с не слишком глубокой вложенностью элементов. Будь то выпадающее меню (как главное строковое меню программ) или раскрывающееся (как в левой панели популярных файловых менеджеров), всё довольно удобно и наглядно. А что если дерево низкое и развесистое? У каждого родителя детей мало, зато вложенность достигает, скажем, 10. Или 50…

Тогда в случае раскрывающегося меню мы получаем огромные отступы по горизонтали. В случае выпадающего… Рай для мазохиста.

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

Итак, вывод очевиден. Спиральная реализация. Но как это перенести на плоскость? Минус одно измерение. Здесь нам придётся пожертвовать одновременным раскрытием нескольких ветвей. Может (да и наверняка), существует лучшее решение, но я не математик, а то, о чём я пишу, хоть как-то решает задачу — тоннель.

Пример реализации

Реализовать захотелось на более-менее практическом примере. Возьмём некую базу данных по ресторанам с определённым общим набором признаков (тэгов), организованных в дерево.

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

Допустим, у нас есть задача спроектировать систему поиска ресторанов по этом тэгам. Например, среднестатистическая богатая семья деревни Подвыхухолевка решила на выходных пойти в ресторан, коих в деревне насчитывается 351 штука. Семья привередливая, каждый член её с характером, но после долгих обсуждений со скандалами они решили, что хотят в дорогой ресторан, с раздельными залами для курящих и некурящих, с громкой живой музыкой и в полном составе — мама, папа и пять детей от разных браков. Простите. Понесло.

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

Дерево тэгов

Рассмотрим чуть подробнее сами тэги. У каждого есть (помимо очевидных родителя, братьев, детей и пр. id) два важных признака:

1. virtual — означает, что этот тэг является лишь контейнером (папкой) и в поиске не участвует (нельзя добавить в фильтр);
2. replaces — перечень других тэгов, которые данный тэг заменяет; к примеру, тэги «Для курящих» и «Можно с детьми» несколько малосовместимы; тогда при добавлении в фильтр данного тэга, из фильтра выпадают те, которые он “replaces”.

<?xml version="1.0" ?>
<tags>
    <tag id="1" name="Дороговизна" virtual="1">
        <tag id="11" name="Дешёвый" replaces="12 13" />
        <tag id="12" name="Средний" replaces="11 13" />
        <tag id="13" name="Дорогой" replaces="11 12" />
    </tag>
    <tag id="2" name="Курение" virtual="1">
        <tag id="21" name="Для некурящих" replaces="221 222 23" />
        <tag id="22" name="Смешанный" virtual="1">
            <tag id="221" name="Один курящий зал" replaces="21 23 222 4" />
            <tag id="222" name="Раздельные залы" replaces="21 23 221" />
        </tag>
        <tag id="23" name="Для курящих" replaces="21 221 222 4" />
    </tag>
    <tag id="3" name="Звук" virtual="1">
        <tag id="31" name="Музыка" replaces="311 312">
            <tag id="311" name="Живая музыка" replaces="31" />
            <tag id="312" name="Музыка в записях" replaces="31" />
        </tag>
        <tag id="32" name="Громко" />
        <tag id="33" name="Тихо" />
    </tag>
    <tag id="4" name="Можно с детьми" replaces="23 221" />
</tags>

<?xml version="1.0" ?>
<items>
    <item id="1" name="Первый ресторан" tags="13 221 311 312 32 33 4" />
    <item id="2" name="Второй ресторан" tags="11 23 32 33" />
    <item id="3" name="Третий ресторан" tags="12 21 311 32 4" />
</items>

Опять же, реализация демонстрационная. Можно JSON-ом, можно хоть голосовой записью с системой распознавания речи.

Клиентская часть — тоннель

Далее, каждый житель деревни может зайти со своего айпада (вся Подвыхухолевка накрыта высокоскоростной Wi-Fi-сетью) на специальный сайт, на котором увидит что-то похожее на это (по ссылке живой пример; прошу прощения за некоторую сырость воплощения — это демонстрационный прототип, который ещё в разработке; SVG + JS + CSS):

Кликабельно, ссылка на живой пример

• Для того, чтобы добавить в поисковой фильтр тэг, надо перетащить его в центр.
• При перетаскивании в центр «виртуального» тэга просто открываются его дети; невиртуального — и открываются его дети (если есть), и сам он добавляется в фильтр.
• При простом клике (тапе) на тэге открываются его дети (если есть).
• При перетаскивании тэга «вовне» закрываются его дети.
• Выбранные тэги в центре можно удалить оттуда, перетащив их вовне.

Теперь, в общем-то, суть этого тоннеля. При открытии детей окружность их родителя и его братьев увеличивается, на её месте появляется окружность детей. То есть, мы как бы продвигаемся дальше внутрь тоннеля. При закрытии детей (или выборе брата их родителя), соответственно, пятимся по тоннелю назад. Просто искусственно подвигаться по тоннелю без открытия / раскрытия детей можно колесом мыши (или пятернёй).

Таким образом достигается цель — при дереве, в котором немного братьев одного уровня (в окружность много не влезет), мы имеем практически неограниченные возможности представления очень развесистого, глубокого дерева без потери наглядности.

Буду рад комментариям, предложениям и критике.

Автор: Assador

Источник