/usr/share/Yap/trees.yap is in yap 6.2.2-6.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 | % This file has been included as an YAP library by Vitor Santos Costa, 1999
% File : TREES.PL
% Author : R.A.O'Keefe
% Updated: 8 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.
*/
:- module(trees, [
get_label/3,
list_to_tree/2,
map_tree/3,
put_label/4,
tree_size/2,
tree_to_list/2
]).
:- meta_predicate
map_tree(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)) :-
once(call(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).
list(0, []).
list(N, [N|L]) :- M is N-1, list(M, L).
|