13 #define OPT_LEAF (1<<0)
14 #define OPT_INORDER (1<<1)
15 #define OPT_DEGREE (1<<2)
16 #define OPT_FAST_PREORDER_SELECT (1<<3)
17 #define OPT_FAST_LEAF_SELECT (1<<4)
18 #define OPT_FAST_INORDER_SELECT (1<<5)
19 #define OPT_FAST_POSTORDER_SELECT (1<<6)
20 #define OPT_DFUDS_LEAF (1<<7)
21 #define OPT_FAST_DFUDS_LEAF_SELECT (1<<8)
33 #define ETW 8 // width of excess lookup table
34 #define W1 2 // branching factor
37 #define min(x,y) ((x)<(y)?(x):(y))
40 #define max(x,y) ((x)>(y)?(x):(y))
57 darray *da_dfuds_leaf;
62 int bp_construct(bp *b,int n, pb *B, int opt);
63 void printbp(bp *b, int s, int t);
66 int rank_open(bp *b, int s);
67 int rank_close(bp *b, int s);
68 int select_open(bp *b, int s);
69 int select_close(bp *b, int s);
73 int find_close(bp *b,int s);
74 int find_open(bp *b,int s);
75 int enclose(bp *b,int s);
76 int parent(bp *b,int s);
77 int level_ancestor(bp *b,int s,int d);
78 int depth(bp *b, int s);
79 int preorder_rank(bp *b,int s);
80 int postorder_rank(bp *b,int s);
81 int inspect(bp *b, int s);
82 int isleaf(bp *b, int s);
83 int rmq(bp *b, int s, int t, int opt);
84 int subtree_size(bp *b, int s);
85 int first_child(bp *b, int s);
86 int next_sibling(bp *b, int s);
87 int prev_sibling(bp *b, int s);
88 int deepest_node(bp *b,int s);
89 int subtree_height(bp *b,int s);
90 int is_ancestor(bp *b, int s, int t);
91 int distance(bp *b, int s, int t);
92 int level_lefthmost(bp *b, int d);
93 int level_rigthmost(bp *b, int d);
94 int degree(bp *b,int s);
97 int naive_degree(bp *b, int s);
98 int naive_child(bp *b, int s, int d);
99 int naive_child_rank(bp *b, int t);
100 int naive_rmq(bp *b, int s, int t,int opt);
101 int postorder_select(bp *b,int s);
103 // using preorder select index
104 int preorder_select(bp *b,int s);
107 int leaf_rank(bp *b,int s);
108 int leaf_size(bp *b, int s);
109 int leftmost_leaf(bp *b, int s);
110 int rightmost_leaf(bp *b, int s);
112 // using leaf select index
113 int leaf_select(bp *b,int s);
115 // using inorder index
116 int inorder_rank(bp *b,int s);
118 // using inorder select index
119 int inorder_select(bp *b,int s);
121 // using degree index
122 int fast_degree(bp *b,int s, int t, int ith);
123 int child_rank(bp *b, int t);
124 int child(bp *b, int s, int d);
127 // new functions for persistence purposes, added by Diego Arroyuelo
128 void saveTree(bp *b, FILE *fp);
129 void loadTree(bp *b, FILE *fp);
130 void destroyTree(bp *b);
133 pb getpat_preorder(pb *b);
134 pb getpat_leaf(pb *b);
135 pb getpat_inorder(pb *b);
136 pb getpat_postorder(pb *b);
139 int fwd_excess(bp *b,int s, int rel);
140 int bwd_excess(bp *b,int s, int rel);
142 extern int *matchtbl,*parenttbl;
143 void make_naivetbl(pb *B,int n);
145 extern int popCount[1<<ETW];
146 extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
147 extern int bwdtbl[(2*ETW+1)*(1<<ETW)];
148 extern int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
149 extern int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
150 extern int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
151 extern int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
153 extern int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
154 extern int degtbl[1<<ETW];
155 extern int degtbl2[(2*ETW+1)*(1<<ETW)];
156 extern int childtbl[(ETW)*(1<<ETW)];
157 extern int depthtbl[(2*ETW+1)*(1<<ETW)];
158 extern int childtbl2[2*ETW+1][ETW][(1<<ETW)];