max(N1, N2, N1) :- N1 > N2, !.
max(N1, N2, N2).

height(empty, 0) :- !.
height(tree(L, W, R), H) :- height(L, N1), height(R, N2), max(N1, N2, N), H is N + 1.

isEmpty(empty) :- !.


pow(B, 0, 1) :- !.
pow(B, P, E) :- P1 is P - 1, pow(B, P1, E1), E is E1 * B.

chars(C, 0, "") :- !.
chars(C, N, S) :- N1 is N - 1, chars(C, N1, S1), string_concat(S1, C, S).

empty_string_list(0, []) :- !.
empty_string_list(N, [""|L]) :- N1 is N - 1, empty_string_list(N1, L).

draw_tree(empty) :- write("empty"), !.
draw_tree(T) :- height(T, H), H1 is H + 1, empty_string_list(H1, LIn), draw_tree_rek(T, H, 0, LIn, LOut), draw_tree_lines(LOut), nl(), nl().

draw_tree_lines([]) :- !.
draw_tree_lines([L|R]) :- write(L), nl(), draw_tree_lines(R).

/* draw_tree_real(in:Baum, in:Höhe des Baumes, in:Aktuelle Tiefe, in:Liste Substrings, out:Liste Substrings]

wenn Tiefe == Index: \n Am Ende */

draw_tree_rek(empty, T, T, L, L) :- !.
draw_tree_rek(empty, H, T, [SIn|LIn], [SOut|LOut]) :-   T1 is T + 1, draw_tree_rek(empty, H, T1, LIn, LTemp),
                                                        Height is H - T, pow(2, Height, N), NElements is N - 1, /* Calc number of elements in this subtree */
                                                        NSpaces is (NElements - 1) / 2, draw_tree_build_element(NSpaces, 2, "  ", empty, empty, SIn, SOut),
                                                        draw_tree_insert_padding(2, LTemp, LTemp2),
                                                        draw_tree_rek(empty, H, T1, LTemp2, LOut).


draw_tree_rek(tree(L, W, R), H, T, [SIn|LIn], [SOut|LOut]) :-   T1 is T + 1, draw_tree_rek(L, H, T1, LIn, LTemp),     /* Follow Left Tree */
                                                                Height is H - T, pow(2, Height, N), NElements is N - 1, /* Calc number of elements in this subtree */
                                                                NSpaces is (NElements - 1) / 2, draw_tree_build_element(NSpaces, 2, W, L, R, SIn, SOut),
                                                                draw_tree_insert_padding(2, LTemp, LTemp2),
                                                                draw_tree_rek(R, H, T1, LTemp2, LOut).


draw_tree_build_edge(ESize, NSpaces, StatusLeft, StatusRight, EdgeLeft, EdgeRight) :-   NFill is (ESize - 1) * NSpaces,
                                                                                        chars(" ", NFill, SpaceLeft), chars(" ", NFill, SpaceRight),
                                                                                        (isEmpty(StatusLeft), chars(" ", NSpaces, UnderLeft); chars("_", NSpaces, UnderLeft)),
                                                                                        (isEmpty(StatusRight), chars(" ", NSpaces, UnderRight); chars("_", NSpaces, UnderRight)),
                                                                                        string_concat(SpaceLeft, UnderLeft, EdgeLeft), string_concat(UnderRight, SpaceRight, EdgeRight).

draw_tree_build_element(NSpaces, ESize, E, StatusLeft, StatusRight, SBefore, SOut) :-   /* NFill is (ESize - 1) * NSpaces,
                                                                chars(" ", NFill, SpaceLeft), chars(" ", NFill, SpaceRight),
                                                                chars("_", NSpaces, UnderLeft), chars("_", NFill, UnderRight),
                                                                string_concat(SpaceLeft, UnderLeft, SLeft), string_concat(UnderRight, SpaceRight, SRight), */
                                                                draw_tree_build_edge(ESize, NSpaces, StatusLeft, StatusRight, SLeft, SRight),

                                                                atom_string(E, SElement), string_length(SElement, L),
                                                                Padding is 2 - L, chars(" ", Padding, SPadding), string_concat(SPadding, SElement, SInner),
                                                                string_concat(SLeft, SInner, S1), string_concat(S1, SRight, S2),
                                                                string_concat(SBefore, S2, SOut).

draw_tree_insert_padding(Padding, [], []) :- !.
draw_tree_insert_padding(Padding, [EIn|LIn], [EOut|LOut]) :- chars(" ", Padding, SPadding), string_concat(EIn, SPadding, EOut), draw_tree_insert_padding(Padding, LIn, LOut).