Pull to refresh

Жемчужины функционального программирования: рисуем деревья

Programming
В этой статье я собираюсь поведать читателям о рисовании деревьев. Нет, не тех деревьев, которые растут из почвы и в которых селятся белки. Сегодня мы будем визуализировать деревья как структуры данных. Данная статья написана по мотивам статьи Andrew Kennedy «Functional Pearls: Drawing Trees» из журнала Journal of Functional Programming, 6(3): 527-534, Cambridge University Press, May 1996 (электронная версия статьи тут), и является, в некотором роде, её переводом.


В оригинале статья написана на английском и использует реализацию на Standart ML. Откровенно говоря, я просто украл всё из вышеупомянутой статьи, английский перевёл на русский (что-то своими словами), Standart ML перевёл на Erlang, что-то выкинул (больше), что-то добавил (меньше). Примеры кода будут даваться как на оригинальном Standart ML, так и на Erlang для того, чтобы любопытный читатель мог узреть разницу.

Зачем это надо



Статья меня сразу заинтересовала, и мне захотелось получить готовую программу для подобной визуализации. Нет, не для какого-то полезного пользования, а лишь из-за желания получить такой же вывод, что и в статье. Попутно можно было поиграться с Erlang и познакомиться с синтаксисом незнакомого мне Standart ML.

Проблема и решение



Суть такова: имея дерево с текстовыми метками каждого узла, назначить им позицию и красиво, эстетично нарисовать дерево на экране. Условимся, что узлы, имеющие в дереве одинаковую глубину рисуются на одном уровне, поэтому проблема сводится к поиску горизонтальной позиции каждого узла. Но что значит эстетично и красиво? Перечислим правила, чётко определяющие красивость и эстетичность:

  1. Два узла, находящиеся на одном уровне должны располагаться по крайней мере на определённой, заданной дистанции друг от друга.
  2. Родительский узел должен быть центрирован относительно дочерних узлов.
  3. Рисование дерева должно быть симметричным и должно учитывать отражение — дерево и зеркальное отражение его узлов должны порождать изображения, которые являются отражениями друг друга.
  4. Идентичные деревья должны быть нарисованы одинаково — позиции узлов в большем дереве не должны влиять на то, как они рисуются.


Пример для 3 правила:
image

Пример для 4 правила:
image

Проблему представления решаем следующим образом. Во-первых, рисуем все дочерние узлы так, чтобы не нарушить ни одно из перечисленных правил. Подгоняем их вместе без изменения их формы (иначе нарушим правило 4) так, чтобы не нарушить правила 1 и 3. И, наконец, центрируем родительский узел относительно дочерних узлов и завершаем обработку.
Критической операцией является подгонка поддеревьев. У каждого поддерева есть пространство — пустая зона вокруг дерева. Так как форма поддеревьев не должна меняться, их пространства подгоняются так плотно, насколько это возможно. К сожалению, конечная позиция поддеревьев в этом случае будет зависеть от порядка, в котором мы производим подгонку. Пример двух различных подгонок одинаковых пространств:

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

Представление дерева



В оригинале для представления деревьев пользуются полиморфизмом ML и описывают данные так:
datatype ’a Tree = Node of ’a * (’a Tree list)

Это означает, что узел состоит из значения (тип ’a) и списка дочерних деревьев. В оригинале алгоритм принимает на вход деревья типа ’a Tree и возвращает позиционированные деревья типа (’a*real) Tree. Здесь второй элемент хранит горизонтальную позицию узла относительно родительского узла. Так как о полиморфизме в Erlang мне ничего не известно, то на нём тип данных для узла один, и он уже содержит горизонтальную позицию:
-record(pnode, {label = "LABEL", pos = 0, children = []}).


Так как мы решили использовать относительную позицию узла, то операция смещения узла может быть выполнена за константное время:

fun movetree (Node((label, x), subtrees), x’ : real) =
    Node((label, x+x’), subtrees)


move_ptree({[], _X}) -> [];
move_ptree({#pnode{pos = Pos} = Node, X}) ->
    Node#pnode{pos = Pos + X}.


Представление пространства



Пространство дерева представляется списком пар на ML и просто парой на Erlang:

type Extent = (real*real) list


-record(extent, {left, right}).


Компоненты пар, соответственно, содержат левую и правую границу пространства. Первая пара в списке соответствует корню дерева. Важно упомянуть, что в отличие от представления дерева, позиции пространства абсолютные.

Функция для горизонтального перемещения пространства будет выглядеть так:

fun moveextent (e : Extent, x) = map (fn (p,q) => (p+x, q+x)) e


move_extent({#extent{left = Left, right = Right} = Extent, Offset}) ->
    Extent#extent{left = Left + Offset, right = Right + Offset};
move_extent({ExtentList, Offset}) ->
    lists:map(fun(Extent) -> move_extent({Extent, Offset}) end, ExtentList).


В версии на Erlang читатель наверняка заметил странное использование кортежей в аргументах функции. Такой стиль будет использоваться во многих последующих функциях для предоставления удобства lists:zip.

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

fun   merge ([], qs)                 = qs
    | merge (ps, [])                 = ps
    | merge ((p, _)::ps, (_, q)::qs) = (p,q) :: merge (ps,qs)


Автор оригинальной статьи обращает наше внимание на то, как обрабатываются списки пространств разной глубины. На Erlang оно выглядит так:

merge_extent({#extent{left = Left}, #extent{right = Right}}) ->
    #extent{left = Left, right = Right};
merge_extent({[], []}) -> [];
merge_extent({[], Extent}) -> Extent;
merge_extent({Extent, []}) -> Extent;
merge_extent({[Left | LeftRest], [Right | RightRest]}) ->
    [merge_extent({Left, Right}) | merge_extent({LeftRest, RightRest})].


Эта операция может быть расширена на список пространств следующим образом:

fun mergelist es = fold merge es []


merge_extent_list(ExtentList) ->
    lists:foldl(fun(Elem, Acc) -> merge_extent({Acc, Elem}) end, [], ExtentList).


От себя прошу обратить особое, пристальное внимание на вариант на Erlang. В первый аргумент свёртки — в лямба-функцию — передаётся два аргумента: Elem, Acc. Однако в merge_extent они передаются в обратном порядке: Acc, Elem. Когда я передирал код на Erlang, то по невнимательности этого не заметил, и сделал порядок таким же. Как следствие, объединение пространств работало местами неправильно, и вывод был кривоват в некоторых участках дерева.

Чтобы лучше понять причину неправильной работы, рассмотрим, что будет, если на вход этой функции (неправильный вариант):

merge_extent_list(ExtentList) ->
    lists:foldl(fun(Elem, Acc) -> merge_extent({Elem, Acc}) end, [], ExtentList).


подаются такие значения:

[[{extent,-80,-73}],
 [{extent,-48,-41}],
 [{extent,-16,-9}],
 [{extent,16,23}],
 [{extent,48,55}],
 [{extent,80,87}]]


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

merge_extent: Ex1: {extent,-48,-41}, Ex2: {extent,-80,-73}
merge_extent: Result: {extent,-48,-73}
merge_extent: Ex1: {extent,-16,-9}, Ex2: {extent,-48,-73}
merge_extent: Result: {extent,-16,-73}
merge_extent: Ex1: {extent,16,23}, Ex2: {extent,-16,-73}
merge_extent: Result: {extent,16,-73}
merge_extent: Ex1: {extent,48,55}, Ex2: {extent,16,-73}
merge_extent: Result: {extent,48,-73}
merge_extent: Ex1: {extent,80,87}, Ex2: {extent,48,-73}
merge_extent: Result: {extent,80,-73}
merge_extent_list: Result: [{extent,80,-73}]


Как видим, мы получили странное пространство {extent,80,-73}, где левая граница находится справа от правой. Причину легко увидеть, если посмотреть на функцию merge_extent. Впрочем, если не трогать порядок аргументов, то этот «неправильный» вариант можно сделать правильным, заменив левую свёртку на правую: заменив foldl на foldr.

Странно, но автор в своей статье ниже отмечает, что: «We could have used a left-associating version of fold instead because merge is associative» («мы могли бы использовать левоассоциативную свёртку, потому что функция merge ассоциативна»). Может я чего-то не понял, но на мой взгляд это ложь и провокация. Прошу меня поправить, если я что-то упустил.

Пример использования функции merge_extent_list представлен на рисунке:


Подгонка пространств



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

fun rmax (p : real, q : real)   = if p > q then p else q
fun fit ((_,p)::ps) ((q,_)::qs) = rmax(fit ps qs, p - q + 1.0)
  | fit _           _           =0.0


fit_extent({#extent{right = Right}, #extent{left = Left}}) ->
    Right - Left + ?EXTENT_SEPARATOR;
fit_extent({[], []}) ->
    0;
fit_extent({[First | FirstRest], [Second | SecondRest]}) ->
    erlang:max(fit_extent({First, Second}), fit_extent({FirstRest, SecondRest}));
fit_extent({_A, _B}) ->
    0.


В оригинальной статье минимальным расстоянием является 1.0, а я использовал константу:

-define(EXTENT_SEPARATOR, 15).


Теперь расширим эту функцию до списка пространств. Будем рассчитывать позиции для каждого из них предполагая, что самое левое имеет нулевую позицию. Функция работает за счёт накапливания результирующего пространства, поочерёдно подгоняя его к очередному пространству. Результат работы функции асимметричен, поскольку обход списка происходит слева направо.

fun fitlistl es =
let
    fun fitlistl’ acc [] = []
      | fitlistl’ acc (e::es) =
      let val x = fit acc e
      in
          x :: fitlistl’ (merge (acc, moveextent (e,x))) es
      end
in
    fitlistl’[]es
end


fit_extent_list_l(ExtentList) ->
    fit_extent_list_l([], ExtentList).

fit_extent_list_l(_Acc, []) -> [];
fit_extent_list_l(Acc, [Extent | Rest]) ->
    X = fit_extent({Acc, Extent}),
    [X | fit_extent_list_l(merge_extent({Acc, move_extent({Extent, X})}), Rest)].


Обратный эффект получается в следующей функции, рассчитывающей позиции относительно самого правого пространства, чья позиция равна нулю. Здесь rev — реверсирование списка, а ~ — знаковое отрицание.

fun fitlistr es =
let
    fun fitlistr’ acc [] = []
      | fitlistr’ acc (e::es) =
      let val x = ~(fit e acc)
      in
          x :: fitlistr’ (merge (moveextent (e,x), acc)) es
      end
in
    rev (fitlistr’ [] (rev es))
end


fit_extent_list_r(ExtentList) ->
    lists:reverse(fit_extent_list_r([], lists:reverse(ExtentList))).

fit_extent_list_r(_Acc, []) -> [];
fit_extent_list_r(Acc, [Extent | Rest]) ->
    X = - fit_extent({Extent, Acc}),
    [X | fit_extent_list_r(merge_extent({move_extent({Extent, X}), Acc}), Rest)].


Однако последнюю функцию можно реализовать и иначе. fitlistr можно определить через fitlistl используя композицию функций.

val flipextent : Extent -> Extent = map (fn (p,q) => (~q,~p))
val fitlistr = rev o map ~ o fitlistl o map flipextent o rev


flip_extent(#extent{left = Left, right = Right} = Extent) ->
    Extent#extent{left = -Right, right = -Left};
flip_extent(ExtentList) ->
    [flip_extent(Extent) || Extent <- ExtentList].

fit_extent_list_r(ExtentList) ->
    lists:reverse(
        [-X || X <- fit_extent_list_l(
            lists:map(
                fun flip_extent/1,
                lists:reverse(ExtentList)
            )
        )]
    ).

Наконец, чтобы достигнуть симметричности в отображении дерева, мы рассчитываем позиции обоими способами и берём среднее от их результатов.
fun mean (x,y) = (x+y)/2.0
fun fitlist es = map mean (zip (fitlistl es, fitlistr es))

mean({X, Y}) ->
    trunc((X + Y) / 2).

fit_extent_list(ExtentList) ->
    lists:map(
        fun mean/1,
        lists:zip(fit_extent_list_l(ExtentList), fit_extent_list_r(ExtentList))
    ).


Составление дерева



Теперь пора собрать все компоненты воедино и написать функцию, которая принимает на вход дерево с метками в узлах и выдаёт такое же дерево, но с координатами для каждого узла. Корень дерева имеет нулевую позицию.
fun design tree =
let
    fun design’ (Node(label, subtrees)) =
    let
        val (trees, extents) = unzip (map design’ subtrees)
        val positions        = fitlist extents
        val ptrees           = map movetree (zip (trees, positions))
        val pextents         = map moveextent (zip (extents, positions))
        val resultextent     = (0.0, 0.0) :: mergelist pextents
        val resulttree       = Node((label, 0.0), ptrees)
    in
        (resulttree, resultextent)
    end
in
    fst (design’ tree)
end

design_tree(#pnode{label = Label, children = []}) ->
    {make_pnode(Label, 0, []), [make_extent(0, 0)]};
design_tree(#pnode{label = Label, children = Children} = Node) ->
    {Trees, Extents} = lists:unzip(lists:map(fun design_tree/1, Children)),
    Positions = fit_extent_list(Extents),
    PTrees = lists:map(fun move_ptree/1, lists:zip(Trees, Positions)),
    PExtents = lists:map(fun move_extent/1, lists:zip(Extents, Positions)),
    ResultExtent = [make_extent(0, 0) | merge_extent_list(PExtents)],
    ResultTree = Node#pnode{pos = 0, children = PTrees},
    {ResultTree, ResultExtent}.

Вот как оно работает: сначала рекурсивно составляются все деревья. В результате получается список пар (tree, extent), к которому мы применяем unzip и получаем два списка. Корни всех поддеревьев имеют нулевую позицию. Далее мы подгоняем пространства функцией fillist (fit_extent_list), получая список смещений в positions. Затем смещаем каждое поддерево в trees на соответствующее ему смещение из positions и получаем ptrees. Делаем то же самое для пространств и получаем pextents. В завершение мы рассчитываем результирующее пространство и дерево с корнем в нулевой позиции.

Алгоритмическая сложность



Сложность представленного алгоритма составляет O(n²) в худшем случае, где n — число узлов в дереве. К счастью, можно переписать программу для достижения линейной сложности, но с некоторой потерей ясности кода. Неэффективность получается из-за представления пространств. Перемещение дерева требует константного времени в силу относительности координат, а перемещение пространства имеет линейную сложность в силу использования абсолютных координат. Использование относительных координат позволит уменьшить сложность mergelist (merge_extent_list) с квадратичной до линейной. К сожалению, функции fit (fit_extent) и merge (merge_extent) станут менее элегантными.

Отрисовка дерева



В оригинальной статье графическое представление дерева внезапно появляется без какого-либо кода, его генерирующего. Поэтому от себя я добавлю пример такого кода на Erlang.
-define(LAYER_HEIGHT, 30).
-define(LINE_Y_OFFSET, 10).
-define(LINE_X_OFFSET, 3).
-define(LINE_VERTICAL_LENGTH, 7).

draw_designed_tree(Canvas, X, Y,
                   #pnode{label = Label, pos = Pos, children = Children}) ->
    NewX = X + ?LINE_X_OFFSET,
    NewY = Y - ?LINE_Y_OFFSET,
    gs:line(Canvas, [{coords, [
        {NewX, NewY - ?LINE_VERTICAL_LENGTH},
        {NewX, NewY},
        {NewX + Pos, NewY},
        {NewX + Pos, NewY + ?LINE_VERTICAL_LENGTH}
    ]}]),

    gs:text(Canvas, [
        {coords, [{X + Pos, Y}]},
        {text, Label}
    ]),
    
    lists:map(
        fun(Node) ->
            draw_designed_tree(Canvas, X + Pos, Y + ?LAYER_HEIGHT, Node)
        end,
        Children),
    ok.

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

Создание тестового дерева



Для полноты описания приведу код, который создаёт тестовое дерево:
Tree = add_pnodes(
    add_pnode(
        make_pnode("@"),
        add_pnodes(
            make_pnode("B"),
            [make_pnode("C"),
             add_pnodes(
                make_pnode("D"),
                [make_pnode("1"),
                 make_pnode("2")]
             ),
             make_pnode("E"),
             add_pnodes(
                make_pnode("F"),
                [make_pnode("1"),
                 make_pnode("2"),
                 make_pnode("3"),
                 make_pnode("4"),
                 make_pnode("5"),
                 make_pnode("6")]
             ),
             add_pnodes(
                make_pnode("G"),
                [make_pnode("1"),
                 make_pnode("2"),
                 make_pnode("3"),
                 make_pnode("4"),
                 make_pnode("5")]
             ),
             make_pnode("H"),
             make_pnode("I"),
             make_pnode("J")]
        )
    ),
    [add_pnodes(
        make_pnode("K"),
        [make_pnode("L"),
         make_pnode("M"),
         make_pnode("N"),
         make_pnode("O"),
         make_pnode("P")]
     ),
     make_pnode("Q"),
     make_pnode("R"),
     make_pnode("S"),
     make_pnode("T")]
),


Графический вывод



Вот что получилось у автора статьи:


Вот что получилось у меня:


Доводка напильником



Очень хотелось в метках узлов писать не один символ, а слово. К счастью, это легко решается. В функции design_tree надо поправить создание пространств с учётом ширины текста метки узла: второй аргумент make_extent(0, 0) заменить на что-то из реального мира. Так как я не нашёл функций для получения ширины текста в gs, было решено сделать по-простому: умножать число букв в метке на некий коэффициент. Для этого введём функцию:

-define(LETTER_WIDTH, 7).

label_width(Label) ->
    ?LETTER_WIDTH * length(Label).


И будем использовать эту функцию при получении результирующего дерева. design_tree примет вид:

design_tree(#pnode{label = Label, children = []}) ->
    {make_pnode(Label, 0, []), [make_extent(0, label_width(Label))]};
design_tree(#pnode{label = Label, children = Children} = Node) ->
    {Trees, Extents} = lists:unzip(lists:map(fun design_tree/1, Children)),
    Positions = fit_extent_list(Extents),
    PTrees = lists:map(fun move_ptree/1, lists:zip(Trees, Positions)),
    PExtents = lists:map(fun move_extent/1, lists:zip(Extents, Positions)),
    ResultExtent = [make_extent(0, label_width(Label)) | merge_extent_list(PExtents)],
    ResultTree = Node#pnode{pos = 0, children = PTrees},
    {ResultTree, ResultExtent}.


Протестируем. Для входного дерева:

Tree = add_pnodes(
    add_pnode(
        make_pnode("@"),
        add_pnodes(
            make_pnode("Beta"),
            [make_pnode("Code"),
             add_pnodes(
                make_pnode("Dad"),
                [make_pnode("1st"),
                 make_pnode("2dn")]
             ),
             make_pnode("Exit"),
             add_pnodes(
                make_pnode("Fall"),
                [make_pnode("111"),
                 make_pnode("222"),
                 make_pnode("333"),
                 make_pnode("444"),
                 make_pnode("555"),
                 make_pnode("666")]
             ),
             add_pnodes(
                make_pnode("Gravity"),
                [make_pnode("1_milk"),
                 make_pnode("2_apple"),
                 make_pnode("3_juice"),
                 make_pnode("4_banana"),
                 make_pnode("5_orange")]
             ),
             make_pnode("Hope"),
             make_pnode("Illness"),
             make_pnode("Joke")]
        )
    ),
    [add_pnodes(
        make_pnode("Kernel"),
        [make_pnode("Load"),
         make_pnode("Module"),
         make_pnode("Nop"),
         make_pnode("Operator"),
         make_pnode("Point")]
     ),
     make_pnode("Quit"),
     make_pnode("Rest"),
     make_pnode("Set"),
     make_pnode("Terminate")]
),


я получил:


Выводы



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

Код



Полного кода программы автора не имею, поэтому привожу только свой (копия тут):

-module(drawtree).
-compile(export_all).

-define(EXTENT_SEPARATOR, 15).
-define(LAYER_HEIGHT, 30).
-define(LINE_Y_OFFSET, 10).
-define(LINE_X_OFFSET, 3).
-define(LINE_VERTICAL_LENGTH, 7).
-define(LETTER_WIDTH, 7).
-define(TREE_POS_X, 350).
-define(TREE_POS_Y, 30).

-define(WINDOW_WIDTH, 1000).
-define(WINDOW_HEIGHT, 500).

-record(pnode, {label = "LABEL", pos = 0, children = []}).
-record(extent, {left, right}).

init() ->
    S = gs:start(),
    Win = gs:window(ui_main_window, S, [{width, ?WINDOW_WIDTH}, {height, ?WINDOW_HEIGHT}]),
    gs:config(Win, {map, true}),
    Canvas = gs:canvas(Win, [{x, 0}, {y, 0}, {width, ?WINDOW_WIDTH}, {height, ?WINDOW_HEIGHT}]),

    do_drawings(Canvas),
    
    loop(),
    init:stop().

move_ptree({[], _X}) -> [];
move_ptree({#pnode{pos = Pos} = Node, X}) ->
    Node#pnode{pos = Pos + X}.

make_extent(Left, Right) ->
    #extent{left = Left, right = Right}.

make_pnode(Label) ->
    #pnode{label = Label}.
make_pnode(Label, Pos, Children) ->
    #pnode{label = Label, pos = Pos, children = Children}.

add_pnode(#pnode{children = Children} = Tree, PNode) ->
    Tree#pnode{children = [PNode | Children]}.

add_pnodes(#pnode{children = Children} = Tree, PNodes) ->
    Tree#pnode{children = PNodes ++ Children}.

do_drawings(Canvas) ->
    Tree = add_pnodes(
        add_pnode(
            make_pnode("@"),
            add_pnodes(
                make_pnode("Beta"),
                [make_pnode("Code"),
                 add_pnodes(
                    make_pnode("Dad"),
                    [make_pnode("1st"),
                     make_pnode("2nd")]
                 ),
                 make_pnode("Exit"),
                 add_pnodes(
                    make_pnode("Fall"),
                    [make_pnode("111"),
                     make_pnode("222"),
                     make_pnode("333"),
                     make_pnode("444"),
                     make_pnode("555"),
                     make_pnode("666")]
                 ),
                 add_pnodes(
                    make_pnode("Gravity"),
                    [make_pnode("1_milk"),
                     make_pnode("2_apple"),
                     make_pnode("3_juice"),
                     make_pnode("4_banana"),
                     make_pnode("5_orange")]
                 ),
                 make_pnode("Hope"),
                 make_pnode("Illness"),
                 make_pnode("Joke")]
            )
        ),
        [add_pnodes(
            make_pnode("Kernel"),
            [make_pnode("Load"),
             make_pnode("Module"),
             make_pnode("Nop"),
             make_pnode("Operator"),
             make_pnode("Point")]
         ),
         make_pnode("Quit"),
         make_pnode("Rest"),
         make_pnode("Set"),
         make_pnode("Terminate")]
    ),
    io:format("Source = ~p~n", [Tree]),
    {DesignedTree, Extents} = design_tree(Tree),
    io:format("DesignedTree = ~p~n", [DesignedTree]),
    io:format("Extents = ~p~n", [Extents]),

    draw_designed_tree(Canvas, ?TREE_POS_X, ?TREE_POS_Y, DesignedTree).

move_extent({#extent{left = Left, right = Right} = Extent, Offset}) ->
    Extent#extent{left = Left + Offset, right = Right + Offset};
move_extent({ExtentList, Offset}) ->
    lists:map(fun(Extent) -> move_extent({Extent, Offset}) end, ExtentList).

merge_extent({#extent{left = Left}, #extent{right = Right}}) ->
    #extent{left = Left, right = Right};
merge_extent({[], []}) -> [];
merge_extent({[], Extent}) -> Extent;
merge_extent({Extent, []}) -> Extent;
merge_extent({[Left | LeftRest], [Right | RightRest]}) ->
    [merge_extent({Left, Right}) | merge_extent({LeftRest, RightRest})].

merge_extent_list(ExtentList) ->
    % IMPORTANT: Notice Elem and Acc change!
    % fun(Elem, Acc) -> merge_extent({Acc, Elem}
    lists:foldl(fun(Elem, Acc) -> merge_extent({Acc, Elem}) end, [], ExtentList).

fit_extent({#extent{right = Right}, #extent{left = Left}}) ->
    Right - Left + ?EXTENT_SEPARATOR;
fit_extent({[], []}) ->
    0;
fit_extent({[First | FirstRest], [Second | SecondRest]}) ->
    erlang:max(fit_extent({First, Second}), fit_extent({FirstRest, SecondRest}));
fit_extent({_A, _B}) ->
    0.

fit_extent_list_l(ExtentList) ->
    fit_extent_list_l([], ExtentList).

fit_extent_list_l(_Acc, []) -> [];
fit_extent_list_l(Acc, [Extent | Rest]) ->
    X = fit_extent({Acc, Extent}),
    [X | fit_extent_list_l(merge_extent({Acc, move_extent({Extent, X})}), Rest)].

flip_extent(#extent{left = Left, right = Right} = Extent) ->
    Extent#extent{left = -Right, right = -Left};
flip_extent(ExtentList) ->
    [flip_extent(Extent) || Extent <- ExtentList].

fit_extent_list_r(ExtentList) ->
    lists:reverse(
        [-X || X <- fit_extent_list_l(
            lists:map(
                fun flip_extent/1,
                lists:reverse(ExtentList)
            )
        )]
    ).

% fit_extent_list_r(ExtentList) ->
    % lists:reverse(fit_extent_list_r([], lists:reverse(ExtentList))).

% fit_extent_list_r(_Acc, []) -> [];
% fit_extent_list_r(Acc, [Extent | Rest]) ->
    % X = - fit_extent({Extent, Acc}),
    % [X | fit_extent_list_r(merge_extent({move_extent({Extent, X}), Acc}), Rest)].

mean({X, Y}) ->
    trunc((X + Y) / 2).

fit_extent_list(ExtentList) ->
    lists:map(
        fun mean/1,
        lists:zip(fit_extent_list_l(ExtentList), fit_extent_list_r(ExtentList))
    ).

label_width(Label) ->
    ?LETTER_WIDTH * length(Label).

design_tree(#pnode{label = Label, children = []}) ->
    {make_pnode(Label, 0, []), [make_extent(0, label_width(Label))]};
design_tree(#pnode{label = Label, children = Children} = Node) ->
    {Trees, Extents} = lists:unzip(lists:map(fun design_tree/1, Children)),
    Positions = fit_extent_list(Extents),
    PTrees = lists:map(fun move_ptree/1, lists:zip(Trees, Positions)),
    PExtents = lists:map(fun move_extent/1, lists:zip(Extents, Positions)),
    ResultExtent = [make_extent(0, label_width(Label)) | merge_extent_list(PExtents)],
    ResultTree = Node#pnode{pos = 0, children = PTrees},
    {ResultTree, ResultExtent}.

draw_designed_tree(Canvas, X, Y,
                   #pnode{label = Label, pos = Pos, children = Children}) ->
    NewX = X + ?LINE_X_OFFSET,
    NewY = Y - ?LINE_Y_OFFSET,
    gs:line(Canvas, [{coords, [
        {NewX, NewY - ?LINE_VERTICAL_LENGTH},
        {NewX, NewY},
        {NewX + Pos, NewY},
        {NewX + Pos, NewY + ?LINE_VERTICAL_LENGTH}
    ]}]),

    gs:text(Canvas, [
        {coords, [{X + Pos, Y}]},
        {text, Label}
    ]),
    
    lists:map(
        fun(Node) ->
            draw_designed_tree(Canvas, X + Pos, Y + ?LAYER_HEIGHT, Node)
        end,
        Children),
    ok.
    
loop() ->
    receive
        {gs, ui_main_window, destroy, _Data, _Args} ->
            ok;
        _Other ->
            loop()
    end.
Tags:erlangфпграфикапрограммированиерекурсияstandart mlдеревья
Hubs: Programming
Total votes 26: ↑26 and ↓0 +26
Views3.9K

Popular right now

Программирование на Python: Введение
October 18, 202130,000 ₽Сетевая Академия ЛАНИТ
Программирование на Python: Продвинутый уровень
October 25, 202118,000 ₽Сетевая Академия ЛАНИТ
Data Scientist
June 18, 2021126,000 ₽Нетология
Аналитик данных
June 18, 202166,000 ₽Нетология