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