```%   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([]).

%   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|_], _, []) :- !.