predsort
, dem man ein Prädikat zum Sortieren von Listen übergeben kann.
Das Prädikat print_nodes
bekommt eine sortierte Liste, in der die Baumknoten in der Form
p(Name, c(X, Y)
angegeben sind, außerdem die letzte x- und y-Koordinate. Der
Rekursionsabbruch ist trivial. Rekursiv wird dann zunächst das Prädikat print_node
für jeden
Knoten mit dem Abstand zwischen dieser und dem letzten Knoten aufgerufen. Das Problem ist, wenn eine
neue Ebene anfängt - der letzte Parameter wird gebraucht, um das Prädikat nl
zu beweisen und
X auf 0 zu setzen. print_node
muss zunächst den Abstand zum letzten Knoten in ein Atom
schreiben, um dann soviele Leerzeichen auszugeben und dann den Knoten.
print_nodes([], _, _). print_nodes([p(Node, c(X, Y)) | R], LastX, Y) :- NewX is X - LastX, print_node(Node, NewX), print_nodes(R, NewX, Y). print_nodes([p(Node, c(X, Y)) | R], _, Depth) :- Depth \= Y, nl, print_node(Node, X), print_nodes(R, X, Y). print_node(Node, Width) :- format_to_atom(Format, "~~~dc~~a", [Width]), format(Format, [" ", Node]), !.
Der Baum muß allerdings sortiert sein, um ihn auszugeben - und zwar ebenenweise von links nach
rechts. Hier kommen xy_sort
und myorder
ins Spiel. xy_sort
benutzt predsort,
das als SWI-Prolog-Modul in Prolog implementiert ist und deshalb mit einigen Änderungen auch in
GNUProlog verfügbar. myorder
gibt als ersten Parameter entweder <, >
oder =
zurück, je nachdem, wie das erste übergebene Element sich zum zweiten verhält. Dabei sind Element in
tieferen Ebenen oder weiter rechts im Baum (Ursprung links unten) größer als höhere linke, so daß
bei der Sortierung schließlich die Wurzel das Minimum ist.
print_tree(AL) :- xy_sort(AL, SL), print_nodes(SL, 0, 0). xy_sort(L, SL) :- predsort(myorder, L, SL). myorder(=, p(N, c(X, Y)), p(N, c(X, Y))). myorder(>, p(_, c(_, Y1)), p(_, c(_, Y2))) :- Y1 < Y2. myorder(>, p(_, c(X1, Y1)), p(_, c(X2, Y2))) :- X1 > X2, Y1 =< Y2. myorder(<, p(_, c(_, Y1)), p(_, c(_, Y2))) :- Y1 > Y2. myorder(<, p(_, c(X1, Y1)), p(_, c(X2, Y2))) :- X1 < X2, Y1 >= Y2.