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)
89 ///////////////////////////////////////////
90 // inspect(bp *b, int s)
91 // returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
92 ///////////////////////////////////////////
93 static inline int bp_inspect(bp *b, int s)
95 return bp_getbit(b->B, s);
98 ///////////////////////////////////////////
99 // find_close(bp *b,int s)
100 // returns the matching close parenthesis of s
101 ///////////////////////////////////////////
102 static inline int bp_find_close(bp *b,int s)
105 if (bp_inspect(b, s1) == CP)
108 return bp_fwd_excess(b, s, -1);
111 ///////////////////////////////////////////
112 // bp_find_open(bp *b,int s)
113 // returns the matching open parenthesis of s
114 ///////////////////////////////////////////
115 static inline int bp_find_open(bp *b,int s)
117 int r = bp_bwd_excess(b, s, 0);
118 return (r >= -1) ? r+1 : -1;
122 ///////////////////////////////////////////
123 // bp_parent(bp *b,int s)
124 // returns the parent of s
125 // -1 if s is the root
126 ///////////////////////////////////////////
127 static inline int bp_parent(bp *b, int s)
130 if (bp_getbit(b->B, s - 1) == OP) return s - 1;
131 r = bp_bwd_excess(b,s,-2);
132 return (r >= -1) ? r+1 : -1;
135 ///////////////////////////////////////////
136 // bp_parent_close(bp *b,int s)
137 // returns the closing parenthesis of the parent
139 // -1 if s is the root
140 ///////////////////////////////////////////
142 static inline int bp_parent_close(bp *b, int s)
144 return bp_fwd_excess(b,s,-2);
148 static inline int bp_enclose(bp *b, int s)
150 return bp_parent(b, s);;
154 ///////////////////////////////////////////
155 // bp_level_ancestor(bp *b,int s,int d)
156 // returns the ancestor of s with relative depth d (d < 0)
157 // -1 if no such node
158 ///////////////////////////////////////////
159 static inline int bp_level_ancestor(bp *b,int s,int d)
161 int r = bp_bwd_excess(b,s,d-1);
162 return (r >= -1) ? r+1 :-1;
165 ///////////////////////////////////////////
166 // bp_lca(bp *b, int s, int t)
167 // returns the lowest common ancestor of s and t
168 ///////////////////////////////////////////
169 static inline int bp_lca(bp *b, int s, int t)
171 return bp_parent(b, bp_rmq(b,s,t,0)+1);
174 ///////////////////////////////////////////
175 // preorder_rank(bp *b,int s)
176 // returns the preorder (>= 1) of node s (s >= 0)
177 ///////////////////////////////////////////
179 static inline int bp_preorder_rank(bp *b,int s)
181 return bp_darray_rank(b->da,s);
184 ///////////////////////////////////////////
185 // preorder_select(bp *b,int s)
186 // returns the node with preorder s (s >= 1)
187 // -1 if no such node
188 ///////////////////////////////////////////
189 static inline int bp_preorder_select(bp *b,int s)
192 if (b->opt & OPT_FAST_PREORDER_SELECT) {
193 return bp_darray_select(b->da,s,1);
195 return bp_darray_select_bsearch(b->da,s, getpat_preorder);
200 int bp_postorder_rank(bp *b,int s);
202 static inline int bp_isleaf(bp *b, int s)
204 return (bp_inspect(b, s+1) == CP);
207 ///////////////////////////////////////////
208 // bp_subtree_size(bp *b, int s)
209 // returns the number of nodes in the subtree of s
210 ///////////////////////////////////////////
211 static inline int bp_subtree_size(bp *b, int s)
213 return (bp_find_close(b, s) - s + 1) / 2;
216 ///////////////////////////////////////////
217 // first_child(bp *b, int s)
218 // returns the first child
220 ///////////////////////////////////////////
222 static inline int bp_first_child(bp *b, int s)
225 return bp_inspect(b, s1) ? s1 : -1;
229 ///////////////////////////////////////////
230 // next_sibling(bp *b,int s)
231 // returns the next sibling of parent(s)
232 // -1 if s is the last child
233 //////////////////////////////////////////
234 static inline int bp_next_sibling(bp *b, int s)
237 t = bp_find_close(b, s) + 1;
238 return bp_inspect(b, t) ? t : -1;
242 int bp_prev_sibling(bp *b, int s);
243 int bp_deepest_node(bp *b,int s);
244 int bp_subtree_height(bp *b,int s);
245 ///////////////////////////////////////////
246 // bp_is_ancestor(bp *b, int s, int t)
247 // returns 1 if s is an ancestor of t
249 ///////////////////////////////////////////
250 static inline int bp_is_ancestor(bp *b, int s, int t)
253 if (s == 0) return 1;
254 v = bp_find_close(b, s);
255 return (s <= t && t <= v);
258 int bp_distance(bp *b, int s, int t);
259 int bp_level_lefthmost(bp *b, int d);
260 int bp_level_rigthmost(bp *b, int d);
261 int bp_degree(bp *b,int s);
264 int bp_naive_degree(bp *b, int s);
265 int bp_naive_child(bp *b, int s, int d);
266 int bp_naive_child_rank(bp *b, int t);
267 int bp_naive_rmq(bp *b, int s, int t,int opt);
268 int bp_postorder_select(bp *b,int s);
270 // using preorder select index
271 int preorder_select(bp *b,int s);
274 int bp_leaf_rank(bp *b,int s);
275 int bp_leaf_size(bp *b, int s);
276 int bp_leftmost_leaf(bp *b, int s);
277 int bp_rightmost_leaf(bp *b, int s);
279 // using leaf select index
280 int bp_leaf_select(bp *b,int s);
282 // using inorder index
283 int bp_inorder_rank(bp *b,int s);
285 // using inorder select index
286 int bp_inorder_select(bp *b,int s);
288 // using degree index
289 int bp_fast_degree(bp *b,int s, int t, int ith);
290 int bp_child_rank(bp *b, int t);
291 int bp_child(bp *b, int s, int d);
294 // new functions for persistence purposes, added by Diego Arroyuelo
295 void saveTree(bp *b, FILE *fp);
296 bp * loadTree(FILE *fp);
298 //0: success 1: failure (errno)
299 int bp_save(bp *b, int fd);
301 //non-null: sucess, null: failure (errno)
303 bp * bp_load(int fd);
304 void bp_delete(bp *b);
307 static inline int blog(int x)
321 extern int *matchtbl,*parenttbl;
323 extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
324 extern int bwdtbl[(2*ETW+1)*(1<<ETW)];
325 extern int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
326 extern int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
327 extern int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
328 extern int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
330 extern int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
331 extern int degtbl[1<<ETW];
332 extern int degtbl2[(2*ETW+1)*(1<<ETW)];
333 extern int childtbl[(ETW)*(1<<ETW)];
334 extern int depthtbl[(2*ETW+1)*(1<<ETW)];
335 extern int childtbl2[2*ETW+1][ETW][(1<<ETW)];