%                           d
%                    _______|_______
%                   |               |
%                   a               g
%                ___|___         ___|___
%               |       |       |       |
%               b       c       *       j
%              _|_     _|_             _|_
%             |   |   |   |           |   |
%             *   *   *   *           *   *
%             0123456789012345678901234567890

%                           d
%                    _______|_______
%                   |               |
%                   g               a
%          	     ___|___         ___|___
%               |       |       |       |
%               *       j       b       c
%                      _|_     _|_     _|_
%                     |   |   |   |   |   |
%                     *   *   *   *   *   *
%             0123456789012345678901234567890



tree_width(*, 1).
tree_width(tree(L, _, R), W) :-
        tree_width(L, LW),
        tree_width(R, RW),
        larger(LW, RW, MW),
        W is 2 * MW + 3.

larger(X, Y, X) :- X >= Y.
larger(X, Y, Y) :- X < Y.

draw_tree(InTree) :-
	make_tree(1, 0, InTree, OutTree),
        order(OutTree, L),
        porder(L).

make_tree(Level, Offset, *, put(*, Level, Offset)).
make_tree(Level, Offset, tree(L, D, R), tree(Ltree, put(D, Level, C), Rtree)) :-
        tree_width(L, LW),
        tree_width(R, RW),
        (LW >= RW ->
                C is Offset + LW + 1,
                L_offset is Offset,
                R_offset is Offset + LW + 3
        |LW < RW ->
                C is Offset + RW + 1,
                L_offset is Offset + (RW - LW)/2,
                R_offset is Offset + RW + 3
         ),
        Next_level is Level + 1,
        make_tree(Next_level, L_offset, L, Ltree),
        make_tree(Next_level, R_offset, R, Rtree).

order(put(X, Level, Offset), L) :- !,
        member([Level|NodeList], L),
        member(put(X, Offset), NodeList).
order(tree(Left, Data, Right), L) :-
        order(Data, L),
        order(Left, L),
        order(Right, L).

member(X, [X|_]) :- !.
member(X, [_|Y]) :- member(X, Y).

porder([]) :- !.
porder([[Level|List]|B]) :-
%       prin(Level, ':'),
        pline(List, 0), nl,
        pbars(List, 0), nl,
        plist(List, 0),
        porder(B).

pline([], _) :- !.
pline([_], _) :- !.
pline([put(_, X), put(_, Y)|Rest], Already) :-
        Tab is X - Already + 1,
        Length is (Y - X)/2 - 1,
        tab(Tab),
        line(Length),
        pline(Rest, Y).

pbars([], _) :- !.
pbars([_], _) :- !.
pbars([put(_, X), put(_, Y)|Rest], Already) :-
        Tab is X - Already ,
        Length is Y - X - 1,
        tab(Tab),
        putc('|'),
        tab(Length),
        putc('|'),
        NewOffset is Y + 1,
        pbars(Rest, NewOffset).

plist([], _) :- !, nl.
plist([put(D, Offset)|B], Already) :-
        Tab is Offset - Already,
        tab(Tab),
        prin(D),
        NewOffset is Offset + 1,
        plist(B, NewOffset).

plist1([]) :- !, nl.
plist1([put(D, Offset)|B]) :-
        prin(' ', D, '@', Offset),
        plist1(B).

line(N) :-
        nput(N),
        putc('|'),
        nput(N).

nput(0) :- !.
nput(N) :-
        putc('_'),
        N1 is N - 1,
        nput(N1).

draw_tree(
          tree(
               tree(tree(*, b, *), a, tree(*, c, *)),
               d,
               tree(*, g, tree(*, j, *))
          )
)!

draw_tree(
          tree(
               tree(*, g, tree(*, j, *)),
               d,
               tree(tree(*, b, *), a, tree(*, c, *))
          )
)!

