1% This file has been included as an YAP library by Vitor Santos Costa, 1999
2
3%   File   : TREES.PL
4%   Author : R.A.O'Keefe
5%   Updated: 8 November 1983
6%   Purpose: Updatable binary trees.
7
8/*  These are the routines I meant to describe in DAI-WP-150, but the
9    wrong version went in.  We have
10	list_to_tree : O(N)
11	tree_to_list : O(N)
12	tree_size    : O(N)
13	map_tree     : O(N)
14	get_label    : O(lg N)
15	put_label    : O(lg N)
16    where N is the number of elements in the tree.  The way get_label
17    and put_label work is worth noting: they build up a pattern which
18    is matched against the whole tree when the position number finally
19    reaches 1.  In effect they start out from the desired node and
20    build up a path to the root.  They still cost O(lg N) time rather
21    than O(N) because the patterns contain O(lg N) distinct variables,
22    with no duplications.  put_label simultaneously builds up a pattern
23    to match the old tree and a pattern to match the new tree.
24*/
25
26:- module(trees, [
27	get_label/3,
28	list_to_tree/2,
29	map_tree/3,
30	put_label/4,
31	tree_size/2,
32	tree_to_list/2
33    ]).
34
35:- meta_predicate
36        map_tree(2, ?, ?).
37
38/*
39:- mode
40	get_label(+, +, ?),
41	find_node(+, +, +),
42	list_to_tree(+, -),
43	list_to_tree(+, +, -),
44	list_to_tree(+),
45	map_tree(+, +, -),
46	put_label(+, +, +, -),
47	find_node(+, +, +, -, +),
48	tree_size(+, ?),
49	tree_size(+, +, -),
50	tree_to_list(+, -),
51	tree_to_list(+, -, -).
52*/
53
54
55%   get_label(Index, Tree, Label)
56%   treats the tree as an array of N elements and returns the Index-th.
57%   If Index < 1 or > N it simply fails, there is no such element.
58
59get_label(N, Tree, Label) :-
60	find_node(N, Tree, t(Label,_,_)).
61
62
63	find_node(1, Tree, Tree) :- !.
64	find_node(N, Tree, Node) :-
65		N > 1,
66		0 is N mod 2,
67		M is N  /  2, !,
68		find_node(M, Tree, t(_,Node,_)).
69	find_node(N, Tree, Node) :-
70		N > 2,
71		1 is N mod 2,
72		M is N  /  2, !,
73		find_node(M, Tree, t(_,_,Node)).
74
75
76
77%   list_to_tree(List, Tree)
78%   takes a given List of N elements and constructs a binary Tree
79%   where get_label(K, Tree, Lab) <=> Lab is the Kth element of List.
80
81list_to_tree(List, Tree) :-
82	list_to_tree(List, [Tree|Tail], Tail).
83
84
85	list_to_tree([Head|Tail], [t(Head,Left,Right)|Qhead], [Left,Right|Qtail]) :-
86		list_to_tree(Tail, Qhead, Qtail).
87	list_to_tree([], Qhead, []) :-
88		list_to_tree(Qhead).
89
90
91		list_to_tree([t|Qhead]) :-
92			list_to_tree(Qhead).
93		list_to_tree([]).
94
95
96
97%   map_tree(Pred, OldTree, NewTree)
98%   is true when OldTree and NewTree are binary trees of the same shape
99%   and Pred(Old,New) is true for corresponding elements of the two trees.
100%   In fact this routine is perfectly happy constructing either tree given
101%   the other, I have given it the mode I have for that bogus reason
102%   "efficiency" and because it is normally used this way round.  This is
103%   really meant more as an illustration of how to map over trees than as
104%   a tool for everyday use.
105
106map_tree(Pred, t(Old,OLeft,ORight), t(New,NLeft,NRight)) :-
107	once(call(Pred, Old, New)),
108	map_tree(Pred, OLeft, NLeft),
109	map_tree(Pred, ORight, NRight).
110map_tree(_, t, t).
111
112%   put_label(Index, OldTree, Label, NewTree)
113%   constructs a new tree the same shape as the old which moreover has the
114%   same elements except that the Index-th one is Label.  Unlike the
115%   "arrays" of Arrays.Pl, OldTree is not modified and you can hang on to
116%   it as long as you please.  Note that O(lg N) new space is needed.
117
118put_label(N, Old, Label, New) :-
119	find_node(N, Old, t(_,Left,Right), New, t(Label,Left,Right)).
120
121
122	find_node(1, Old, Old, New, New) :- !.
123	find_node(N, Old, OldSub, New, NewSub) :-
124		N > 1,
125		0 is N mod 2,
126		M is N  /  2, !,
127		find_node(M, Old, t(Label,OldSub,Right), New, t(Label,NewSub,Right)).
128	find_node(N, Old, OldSub, New, NewSub) :-
129		N > 2,
130		1 is N mod 2,
131		M is N  /  2, !,
132		find_node(M, Old, t(Label,Left,OldSub), New, t(Label,Left,NewSub)).
133
134
135
136%   tree_size(Tree, Size)
137%   calculates the number of elements in the Tree.  All trees made by
138%   list_to_tree that are the same size have the same shape.
139
140tree_size(Tree, Size) :-
141	tree_size(Tree, 0, Total), !,
142	Size = Total.
143
144
145	tree_size(t(_,Left,Right), SoFar, Total) :-
146		tree_size(Right, SoFar, M),
147		N is M+1, !,
148		tree_size(Left, N, Total).
149	tree_size(t, Accum, Accum).
150
151
152
153%   tree_to_list(Tree, List)
154%   is the converse operation to list_to_tree.  Any mapping or checking
155%   operation can be done by converting the tree to a list, mapping or
156%   checking the list, and converting the result, if any, back to a tree.
157%   It is also easier for a human to read a list than a tree, as the
158%   order in the tree goes all over the place.
159
160tree_to_list(Tree, List) :-
161	tree_to_list([Tree|Tail], Tail, List).
162
163
164	tree_to_list([], [], []) :- !.
165	tree_to_list([t|_], _, []) :- !.
166	tree_to_list([t(Head,Left,Right)|Qhead], [Left,Right|Qtail], [Head|Tail]) :-
167		tree_to_list(Qhead, Qtail, Tail).
168
169
170
171list(0, []).
172list(N, [N|L]) :- M is N-1, list(M, L).
173
174
175
176
177