1% BEGIN LICENSE BLOCK 2% Version: CMPL 1.1 3% 4% The contents of this file are subject to the Cisco-style Mozilla Public 5% License Version 1.1 (the "License"); you may not use this file except 6% in compliance with the License. You may obtain a copy of the License 7% at www.eclipse-clp.org/license. 8% 9% Software distributed under the License is distributed on an "AS IS" 10% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See 11% the License for the specific language governing rights and limitations 12% under the License. 13% 14% The Original Code is The ECLiPSe Constraint Logic Programming System. 15% The Initial Developer of the Original Code is Cisco Systems, Inc. 16% Portions created by the Initial Developer are 17% Copyright (C) 1995-2006 Cisco Systems, Inc. All Rights Reserved. 18% 19% Contributor(s): Andrew Eremin, IC-Parc 20% 21% END LICENSE BLOCK 22% ---------------------------------------------------------------------- 23% 24% Description: ECLiPSe n-ary search tree library 25% 26% System: ECLiPSe Constraint Logic Programming System 27% Author/s: Andrew Eremin, IC-Parc 28% 29% ---------------------------------------------------------------------- 30 31 32% ---------------------------------------------------------------------- 33:- module(n_trees). 34 35:- ensure_loaded(b_trees). 36 37% ---------------------------------------------------------------------- 38% 39% user level predicates 40% 41% ---------------------------------------------------------------------- 42 43% ---------------------------------------------------------------------- 44% tree creation 45:- export 46 n_tree/2. 47 48:- mode n_tree(++, -). 49n_tree(Order, Tree) :- 50 b_trees:b_tree(Order, Tree). 51 52% ---------------------------------------------------------------------- 53% node expansion and fathoming 54:- export 55 n_tree_expand/3, 56 n_tree_fathom/1. 57 58:- mode n_tree_expand(+, ++, -). 59n_tree_expand(Tree, Rank, Child) :- 60 n_tree_get(status, Tree, PStatus), 61 n_tree_get(rank, Tree, PRank), 62 ( PStatus == open -> 63 % has no children yet, create a lchild under the node in 64 % the b_tree with rank PRank to be the head of the child 65 % b_tree, and a lchild under that with rank Rank to be the 66 % actual child node 67 b_trees:b_tree_expand(Tree, PRank, CTreeHead), 68 b_trees:b_tree_expand(CTreeHead, Rank, Child) 69 ; PStatus == expanded -> 70 % has chidren, create a rchild under the last rchild in 71 % the child b_tree with rank PRank to be the head of the 72 % rest of the child b_tree, and a lchild under that with 73 % rank Rank to be the actual child node 74 b_trees:lchild(Tree, LCTreeHead), 75 last_child_head(LCTreeHead, RCTreeHead), 76 b_trees:b_tree_expand(RCTreeHead, PRank, CTreeHead), 77 b_trees:b_tree_expand(CTreeHead, Rank, Child) 78 ; % PStatus == fathomed 79 fail 80 ). 81 82last_child_head(CTreeHead, RCTreeHead) :- 83 ( b_trees:rchild(CTreeHead, RTreeHead) -> 84 last_child_head(RTreeHead, RCTreeHead) 85 ; 86 RCTreeHead = CTreeHead 87 ). 88 89:- mode n_tree_fathom(+). 90n_tree_fathom(Leaf) :- 91 b_trees:b_tree_fathom(Leaf). 92 93% ---------------------------------------------------------------------- 94% tree access/update 95:- export 96 n_tree_get/3, 97 n_tree_set/3. 98 99:- mode n_tree_get(++, +, ?). 100n_tree_get(depth, Tree, Val) ?- !, 101 ( parent(Tree, Parent) -> 102 b_trees:b_tree_get(depth, Parent, PDepth), 103 Val is PDepth + 1 104 ; 105 Val = 1 106 ). 107n_tree_get(What, Tree, Val) :- 108 b_trees:b_tree_get(What, Tree, Val). 109 110:- mode n_tree_set(++, +, ?). 111n_tree_set(What, Tree, Val) ?- !, 112 b_trees:b_tree_set(What, Tree, Val). 113 114% ---------------------------------------------------------------------- 115% testing 116:- export 117 is_n_tree/1. 118 119:- mode is_n_tree(+). 120is_n_tree(Tree) :- 121 b_trees:is_b_tree(Tree). 122 123% ---------------------------------------------------------------------- 124% tree navigation 125:- export 126 parent/2, 127 ancestor/2, 128 lsib/2, 129 rsib/2, 130 sib/2, 131 child/2, 132 descendant/2, 133 next/3. 134 135:- mode parent(+, ?). 136parent(Node, Parent) :- 137 b_trees:parent(Node, BParent), 138 ( n_tree_get(id, BParent, Id), 139 0 is getbit(Id, 0) -> 140 b_trees:parent(BParent, Parent) 141 ; 142 parent(BParent, Parent) 143 ). 144 145:- mode ancestor(+, ?). 146ancestor(Node, Ancestor) :- 147 parent(Node, Parent), 148 ( Ancestor = Parent ; ancestor(Parent, Ancestor) ). 149 150:- mode lsib(+, ?). 151lsib(Node, Sib) :- 152 b_trees:parent(Node, BParent), 153 n_tree_get(id, BParent, Id), 154 1 is getbit(Id, 0), 155 b_trees:parent(BParent, LSibBParent), 156 lsib_body(LSibBParent, Sib). 157 158:- mode lsib_body(+, ?). 159lsib_body(BParent, Sib) :- 160 n_tree_get(id, BParent, Id), 161 1 is getbit(Id, 0), 162 b_trees:parent(BParent, LBParent), 163 lsib_body(LBParent, Sib). 164lsib_body(BParent, Sib) :- 165 b_trees:lchild(BParent, Sib). 166 167:- mode rsib(+, ?). 168rsib(Node, Sib) :- 169 b_trees:parent(Node, BParent), 170 b_trees:rchild(BParent, RSibBParent), 171 rsib_body(RSibBParent, Sib). 172 173:- mode rsib_body(+, ?). 174rsib_body(BParent, Sib) :- 175 b_trees:lchild(BParent, Sib). 176rsib_body(BParent, Sib) :- 177 b_trees:rchild(BParent, RBParent), 178 rsib_body(RBParent, Sib). 179 180:- mode sib(+, ?). 181sib(Node, Sib) :- 182 ( lsib(Node, Sib) ; rsib(Node, Sib) ). 183 184:- mode child(+, ?). 185child(Node, Child) :- 186 b_trees:lchild(Node, CBParent), 187 rsib_body(CBParent, Child). 188 189:- mode descendant(+, ?). 190descendant(Node, Descendant) :- 191 child(Node, Child), 192 ( Descendant = Child ; descendant(Child, Descendant) ). 193 194:- mode next(++, +, ?). 195next(bfs, Node, Next) :- 196 n_tree_get(status, Node, Status), 197 ( Status == open -> 198 % Node has not been expanded yet 199 Next = Node 200 ; Status == fathomed -> 201 % subtree rooted at Node is fathomed 202 fail 203 ; 204 b_trees:next(bfs, Node, Next) 205 ). 206next(bfs(Id), Node, Next) ?- 207 b_trees:tree_get_node(Id, Node, SubTree), 208 next(bfs, SubTree, Next). 209next(dfs, Node, Next) :- 210 n_tree_get(status, Node, Status), 211 ( Status == open -> 212 % Node has not been expanded yet 213 Next = Node 214 ; Status == fathomed -> 215 % subtree rooted at Node is fathomed 216 fail 217 ; 218 b_trees:next(dfs, Node, Next) 219 ). 220next(dfs(Id), Node, Next) ?- 221 b_trees:tree_get_node(Id, Node, SubTree), 222 next(dfs, SubTree, Next). 223 224% ---------------------------------------------------------------------- 225 226:- comment(categories, ["Constraints"]). 227:- comment(summary, "n-ary search tree library"). 228:- comment(author, "Andrew Eremin"). 229:- comment(copyright, "Cisco Systems, INc."). 230:- comment(status, prototype). 231 232:- comment(include, n_trees_comments). 233