% File : TREES.PL
% Author : R.A.O'Keefe
% Updated: 25 November 1983
% Purpose: Updatable binary trees.
/* These are the routines I meant to describe in DAI-WP-150, but the
wrong version went in. We have
list_to_tree : O(N)
tree_to_list : O(N)
tree_size : O(N)
map_tree : O(N)
get_label : O(lg N)
put_label : O(lg N)
where N is the number of elements in the tree. The way get_label
and put_label work is worth noting: they build up a pattern which
is matched against the whole tree when the position number finally
reaches 1. In effect they start out from the desired node and
build up a path to the root. They still cost O(lg N) time rather
than O(N) because the patterns contain O(lg N) distinct variables,
with no duplications. put_label simultaneously builds up a pattern
to match the old tree and a pattern to match the new tree.
*/
:- public
get_label/3,
list_to_tree/2,
map_tree/3,
put_label/4,
tree_size/2,
tree_to_list/2.
:- mode
get_label(+, +, ?),
find_node(+, +, +),
list_to_tree(+, -),
list_to_tree(+, +, -),
list_to_tree(+),
map_tree(+, +, -),
put_label(+, +, +, -),
find_node(+, +, +, -, +),
tree_size(+, ?),
tree_size(+, +, -),
tree_to_list(+, -),
tree_to_list(+, -, -).
% get_label(Index, Tree, Label)
% treats the tree as an array of N elements and returns the Index-th.
% If Index < 1 or > N it simply fails, there is no such element.
get_label(N, Tree, Label) :-
find_node(N, Tree, t(Label,_,_)).
find_node(1, Tree, Tree) :- !.
find_node(N, Tree, Node) :-
N > 1,
0 is N mod 2,
M is N / 2, !,
find_node(M, Tree, t(_,Node,_)).
find_node(N, Tree, Node) :-
N > 2,
1 is N mod 2,
M is N / 2, !,
find_node(M, Tree, t(_,_,Node)).
% list_to_tree(List, Tree)
% takes a given List of N elements and constructs a binary Tree
% where get_label(K, Tree, Lab) <=> Lab is the Kth element of List.
list_to_tree(List, Tree) :-
list_to_tree(List, [Tree|Tail], Tail).
list_to_tree([Head|Tail], [t(Head,Left,Right)|Qhead], [Left,Right|Qtail]) :-
list_to_tree(Tail, Qhead, Qtail).
list_to_tree([], Qhead, []) :-
list_to_tree(Qhead).
list_to_tree([t|Qhead]) :-
list_to_tree(Qhead).
list_to_tree([]).
% map_tree(Pred, OldTree, NewTree)
% is true when OldTree and NewTree are binary trees of the same shape
% and Pred(Old,New) is true for corresponding elements of the two trees.
% In fact this routine is perfectly happy constructing either tree given
% the other, I have given it the mode I have for that bogus reason
% "efficiency" and because it is normally used this way round. This is
% really meant more as an illustration of how to map over trees than as
% a tool for everyday use.
map_tree(Pred, t(Old,OLeft,ORight), t(New,NLeft,NRight)) :-
apply(Pred, [Old,New]),
map_tree(Pred, OLeft, NLeft),
map_tree(Pred, ORight, NRight).
map_tree(_, t, t).
% put_label(Index, OldTree, Label, NewTree)
% constructs a new tree the same shape as the old which moreover has the
% same elements except that the Index-th one is Label. Unlike the
% "arrays" of Arrays.Pl, OldTree is not modified and you can hang on to
% it as long as you please. Note that O(lg N) new space is needed.
put_label(N, Old, Label, New) :-
find_node(N, Old, t(_,Left,Right), New, t(Label,Left,Right)).
find_node(1, Old, Old, New, New) :- !.
find_node(N, Old, OldSub, New, NewSub) :-
N > 1,
0 is N mod 2,
M is N / 2, !,
find_node(M, Old, t(Label,OldSub,Right), New, t(Label,NewSub,Right)).
find_node(N, Old, OldSub, New, NewSub) :-
N > 2,
1 is N mod 2,
M is N / 2, !,
find_node(M, Old, t(Label,Left,OldSub), New, t(Label,Left,NewSub)).
% tree_size(Tree, Size)
% calculates the number of elements in the Tree. All trees made by
% list_to_tree that are the same size have the same shape.
tree_size(Tree, Size) :-
tree_size(Tree, 0, Total), !,
Size = Total.
tree_size(t(_,Left,Right), SoFar, Total) :-
tree_size(Right, SoFar, M),
N is M+1, !,
tree_size(Left, N, Total).
tree_size(t, Accum, Accum).
% tree_to_list(Tree, List)
% is the converse operation to list_to_tree. Any mapping or checking
% operation can be done by converting the tree to a list, mapping or
% checking the list, and converting the result, if any, back to a tree.
% It is also easier for a human to read a list than a tree, as the
% order in the tree goes all over the place.
tree_to_list(Tree, List) :-
tree_to_list([Tree|Tail], Tail, List).
tree_to_list([], [], []) :- !.
tree_to_list([t|_], _, []) :- !.
tree_to_list([t(Head,Left,Right)|Qhead], [Left,Right|Qtail], [Head|Tail]) :-
tree_to_list(Qhead, Qtail, Tail).