Skip to content

Instantly share code, notes, and snippets.

@pichi
Last active December 31, 2015 02:09
Show Gist options
  • Save pichi/7919360 to your computer and use it in GitHub Desktop.
Save pichi/7919360 to your computer and use it in GitHub Desktop.
Module for getting "vertical lines" (see http://stackoverflow.com/q/20521098/49197) It also contain tree pretty printer (far more sophisticated then getting vertical lines BTW)
-module(vertical_tree).
-export([draw/1, get_verical_lines/1]).
-record(node, {
value,
left = nil,
right = nil
}).
get_verical_lines(Root) ->
{L, R} = get_verical_lines(Root, zip_new()),
tl(lists:reverse(L, R)). % concatenate zipper and cut off surplus empty list
get_verical_lines(nil, Zip) -> Zip;
get_verical_lines(#node{value = V, left = L, right = R}, Zip) ->
Zip1 = zip_right(get_verical_lines(L, zip_left(Zip))),
Zip2 = zip_left(get_verical_lines(R, zip_right(Zip1))),
zip_add(V, Zip2).
zip_new() -> {[], []}.
zip_add(V, {L, [] }) -> {L, [[V] ]};
zip_add(V, {L, [H|R]}) -> {L, [[V|H]|R]}.
zip_left({[], R}) -> {[], [[]|R]};
zip_left({[H|T], R}) -> {T, [H |R]}.
zip_right({L, [] }) -> {[[]|L], []};
zip_right({L, [H|T]}) -> {[H |L], T }.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Drawing of tree
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%
%%% It returns io_list so use for real visualisation
%%% io:put_chars(vertical_tree:draw(Tree)).
%%%
-record(box, {
width = 0,
draw = []
}).
draw(nil) -> [];
draw(#node{value = V, left = L, right = R}) ->
LB = draw_box(left, L, #box{}),
{LPos, Label} = label_to_right(V, LB, []),
RB = draw_box(right, R, boundbox(expand_box(LB), LPos+1)),
[lists:reverse(X, [$\n]) || X <- [Label | RB#box.draw]].
draw_box(_, nil, Box) -> Box;
draw_box(Dir, #node{value = V, left = L, right = R}, Box) ->
{LineT, LabelT, B} = cut2lines(Box),
LB = draw_box(left, L, B),
{LPos, Label} = label_to_right(V, LB, LabelT),
RB = draw_box(right, R, boundbox(expand_box(LB), LPos+1)),
BBox = boundbox(RB, length(Label)-1),
Line = case Dir of
right -> drawline($\\, LPos, Box#box.width, LineT);
left -> drawline($/, LPos, BBox#box.width, LineT)
end,
add2lines(Line, Label, BBox).
cut2lines(#box{draw = [Line, Label|Rest]} = Box) ->
{Line, Label, Box#box{draw = Rest}};
cut2lines(#box{draw = []} = Box) -> {[], [], Box}.
add2lines(A, B, Box) ->
Box#box{ draw = [A, B | Box#box.draw] }.
label_to_right(V, Box, Tail) ->
label(V, Box#box.width, Tail).
label(V, Pos, Tail) ->
Str = lists:flatten(io_lib:write(V)),
HalfStr = length(Str) div 2,
Line = expandline(Pos - HalfStr, Tail),
{length(Line) + HalfStr, [$\s|lists:reverse(Str, Line)]}.
expand_box(Box) ->
expand_box(Box, 1).
expand_box(Box, Width) ->
setwidth(Box, Box#box.width + Width).
boundbox(Box, Width) ->
setwidth(Box, max(Box#box.width, Width)).
setwidth(Box, Width) ->
Box#box{width = Width}.
drawline(Symb, A, B, Tail) ->
[Symb | expandline((A+B) div 2, Tail)].
expandline(Pos, Tail) ->
spaces(Pos - length(Tail), Tail).
spaces(Left, Line) when Left > 0 ->
spaces(Left - 1, [$\s|Line]);
spaces(_, Line) -> Line.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment