11 #include "bp-darray.h"
22 #define OPT_LEAF (1 << 0)
23 #define OPT_INORDER (1 << 1)
24 #define OPT_DEGREE (1 << 2)
25 #define OPT_FAST_PREORDER_SELECT (1 << 3)
26 #define OPT_FAST_LEAF_SELECT (1 << 4)
27 #define OPT_FAST_INORDER_SELECT (1 << 5)
28 #define OPT_FAST_POSTORDER_SELECT (1 << 6)
29 #define OPT_DFUDS_LEAF (1 << 7)
30 #define OPT_FAST_DFUDS_LEAF_SELECT (1 << 8)
42 #define ETW 8 // width of excess lookup table
43 #define W1 2 // branching factor
60 darray *da_dfuds_leaf;
65 pb getpat_preorder(pb *b);
66 pb getpat_leaf(pb *b);
67 pb getpat_inorder(pb *b);
68 pb getpat_postorder(pb *b);
70 bp * bp_construct(int n, pb *B, int opt);
71 void bp_print(bp *b, int s, int t);
73 int bp_fwd_excess(bp *b,int s, int rel);
74 int bp_bwd_excess(bp *b,int s, int rel);
75 int bp_rmq(bp *b, int s, int t, int opt);
76 int bp_depth(bp *b, int s);
78 int bp_rank_open(bp *b, int s);
79 int bp_rank_close(bp *b, int s);
80 int bp_select_open(bp *b, int s);
81 int bp_select_close(bp *b, int s);
84 static inline int bp_root_node(bp *b)
90 ///////////////////////////////////////////
91 // find_close(bp *b,int s)
92 // returns the matching close parenthesis of s
93 ///////////////////////////////////////////
94 static inline int bp_find_close(bp *b,int s)
96 return bp_fwd_excess(b, s, -1);
99 ///////////////////////////////////////////
100 // bp_find_open(bp *b,int s)
101 // returns the matching open parenthesis of s
102 ///////////////////////////////////////////
103 static inline int bp_find_open(bp *b,int s)
105 int r = bp_bwd_excess(b, s, 0);
106 return (r >= -1) ? r+1 : -1;
110 ///////////////////////////////////////////
111 // bp_parent(bp *b,int s)
112 // returns the parent of s
113 // -1 if s is the root
114 ///////////////////////////////////////////
115 static inline int bp_parent(bp *b, int s)
117 int r = bp_bwd_excess(b,s,-2);
118 return (r >= -1) ? r+1 : -1;
121 ///////////////////////////////////////////
122 // bp_parent_close(bp *b,int s)
123 // returns the closing parenthesis of the parent
125 // -1 if s is the root
126 ///////////////////////////////////////////
128 static inline int bp_parent_close(bp *b, int s)
130 return bp_fwd_excess(b,s,-2);
134 static inline int bp_enclose(bp *b, int s)
136 return bp_parent(b, s);;
140 ///////////////////////////////////////////
141 // bp_level_ancestor(bp *b,int s,int d)
142 // returns the ancestor of s with relative depth d (d < 0)
143 // -1 if no such node
144 ///////////////////////////////////////////
145 static inline int bp_level_ancestor(bp *b,int s,int d)
147 int r = bp_bwd_excess(b,s,d-1);
148 return (r >= -1) ? r+1 :-1;
151 ///////////////////////////////////////////
152 // bp_lca(bp *b, int s, int t)
153 // returns the lowest common ancestor of s and t
154 ///////////////////////////////////////////
155 static inline int bp_lca(bp *b, int s, int t)
157 return bp_parent(b, bp_rmq(b,s,t,0)+1);
160 ///////////////////////////////////////////
161 // preorder_rank(bp *b,int s)
162 // returns the preorder (>= 1) of node s (s >= 0)
163 ///////////////////////////////////////////
165 static inline int bp_preorder_rank(bp *b,int s)
167 return bp_darray_rank(b->da,s);
170 ///////////////////////////////////////////
171 // preorder_select(bp *b,int s)
172 // returns the node with preorder s (s >= 1)
173 // -1 if no such node
174 ///////////////////////////////////////////
175 static inline int bp_preorder_select(bp *b,int s)
178 if (b->opt & OPT_FAST_PREORDER_SELECT) {
179 return bp_darray_select(b->da,s,1);
181 return bp_darray_select_bsearch(b->da,s, getpat_preorder);
186 int bp_postorder_rank(bp *b,int s);
188 ///////////////////////////////////////////
189 // inspect(bp *b, int s)
190 // returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
191 ///////////////////////////////////////////
192 static inline int bp_inspect(bp *b, int s)
194 return bp_getbit(b->B, s);
197 static inline int bp_isleaf(bp *b, int s)
199 return (bp_inspect(b, s+1) == CP);
202 ///////////////////////////////////////////
203 // bp_subtree_size(bp *b, int s)
204 // returns the number of nodes in the subtree of s
205 ///////////////////////////////////////////
206 static inline int bp_subtree_size(bp *b, int s)
208 return (bp_find_close(b, s) - s + 1) / 2;
211 ///////////////////////////////////////////
212 // first_child(bp *b, int s)
213 // returns the first child
215 ///////////////////////////////////////////
217 static inline int bp_first_child(bp *b, int s)
219 return (bp_inspect(b, s+1) == CP) ? -1 : s+1;
223 ///////////////////////////////////////////
224 // next_sibling(bp *b,int s)
225 // returns the next sibling of parent(s)
226 // -1 if s is the last child
227 //////////////////////////////////////////
228 static inline int bp_next_sibling(bp *b, int s)
231 t = bp_find_close(b,s) + 1;
232 return (bp_inspect(b, t) == CP) ? -1 : t;
236 int bp_prev_sibling(bp *b, int s);
237 int bp_deepest_node(bp *b,int s);
238 int bp_subtree_height(bp *b,int s);
239 ///////////////////////////////////////////
240 // bp_is_ancestor(bp *b, int s, int t)
241 // returns 1 if s is an ancestor of t
243 ///////////////////////////////////////////
244 static inline int bp_is_ancestor(bp *b, int s, int t)
247 if (s == 0) return 1;
248 v = bp_find_close(b, s);
249 return (s <= t && t <= v);
252 int bp_distance(bp *b, int s, int t);
253 int bp_level_lefthmost(bp *b, int d);
254 int bp_level_rigthmost(bp *b, int d);
255 int bp_degree(bp *b,int s);
258 int bp_naive_degree(bp *b, int s);
259 int bp_naive_child(bp *b, int s, int d);
260 int bp_naive_child_rank(bp *b, int t);
261 int bp_naive_rmq(bp *b, int s, int t,int opt);
262 int bp_postorder_select(bp *b,int s);
264 // using preorder select index
265 int preorder_select(bp *b,int s);
268 int bp_leaf_rank(bp *b,int s);
269 int bp_leaf_size(bp *b, int s);
270 int bp_leftmost_leaf(bp *b, int s);
271 int bp_rightmost_leaf(bp *b, int s);
273 // using leaf select index
274 int bp_leaf_select(bp *b,int s);
276 // using inorder index
277 int bp_inorder_rank(bp *b,int s);
279 // using inorder select index
280 int bp_inorder_select(bp *b,int s);
282 // using degree index
283 int bp_fast_degree(bp *b,int s, int t, int ith);
284 int bp_child_rank(bp *b, int t);
285 int bp_child(bp *b, int s, int d);
288 // new functions for persistence purposes, added by Diego Arroyuelo
289 void saveTree(bp *b, FILE *fp);
290 bp * loadTree(FILE *fp);
291 void bp_delete(bp *b);
294 static inline int blog(int x)
308 extern int *matchtbl,*parenttbl;
309 void make_naivetbl(pb *B,int n);
312 extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
313 extern int bwdtbl[(2*ETW+1)*(1<<ETW)];
314 extern int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
315 extern int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
316 extern int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
317 extern int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
319 extern int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
320 extern int degtbl[1<<ETW];
321 extern int degtbl2[(2*ETW+1)*(1<<ETW)];
322 extern int childtbl[(ETW)*(1<<ETW)];
323 extern int depthtbl[(2*ETW+1)*(1<<ETW)];
324 extern int childtbl2[2*ETW+1][ETW][(1<<ETW)];