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