bp.h

   1 #ifndef BP_H_
   2 #define BP_H_
   3
   4
   5 #ifdef __cplusplus
   6 extern "C" {
   7 #endif
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include "bp-darray.h"
  12 #include "bp-utils.h"
  13
  14 #define OP 1
  15 #define CP 0
  16
  17 #define OPT_MIN 0
  18 #define OPT_MAX 1
  19 #define OPT_LEFT 0
  20 #define OPT_RIGHT 2
  21
  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)
  31
  32 //#define logSB 9
  33 #define logSB 7
  34 //#define logSB 2
  35 #define SB (1<<logSB)
  36 //#define logMB 16
  37 //#define logMB 12
  38 #define logMB 15
  39 //#define logMB 3
  40 #define MB (1<<logMB)
  41
  42 #define ETW 8   // width of excess lookup table
  43 #define W1 2    // branching factor
  44
  45
  46
  47 typedef struct {
  48   int n;
  49   pb *B;
  50   darray *da;
  51   byte *sm, *sM;
  52   byte *sd;
  53   int *mm, *mM;
  54   int *md;
  55   int m_ofs;
  56
  57   darray *da_leaf;
  58   darray *da_inorder;
  59   darray *da_postorder;
  60   darray *da_dfuds_leaf;
  61   int idx_size;
  62   int opt;
  63 } bp;
  64
  65 pb getpat_preorder(pb *b);
  66 pb getpat_leaf(pb *b);
  67 pb getpat_inorder(pb *b);
  68 pb getpat_postorder(pb *b);
  69
  70 bp * bp_construct(int n, pb *B, int opt);
  71 void bp_print(bp *b, int s, int t);
  72
  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);
  77
  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);
  82
  83
  84 static inline int bp_root_node(bp *b)
  85 {
  86   return 0;
  87 }
  88
  89
  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)
  95 {
  96   return bp_fwd_excess(b, s, -1);
  97 }
  98
  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)
 104 {
 105   int r = bp_bwd_excess(b, s, 0);
 106   return (r >= -1) ? r+1 : -1;
 107 }
 108
 109
 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)
 116 {
 117   int r = bp_bwd_excess(b,s,-2);
 118   return (r >= -1) ? r+1 : -1;
 119 }
 120
 121 ///////////////////////////////////////////
 122 //  bp_parent_close(bp *b,int s)
 123 //    returns the closing parenthesis of the parent
 124 //    of s
 125 //            -1 if s is the root
 126 ///////////////////////////////////////////
 127
 128 static inline int bp_parent_close(bp *b, int s)
 129 {
 130   return bp_fwd_excess(b,s,-2);
 131 }
 132
 133
 134 static inline int bp_enclose(bp *b, int s)
 135 {
 136   return bp_parent(b, s);;
 137 }
 138
 139
 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)
 146 {
 147   int r = bp_bwd_excess(b,s,d-1);
 148   return (r >= -1) ? r+1 :-1;
 149 }
 150
 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)
 156 {
 157   return bp_parent(b, bp_rmq(b,s,t,0)+1);
 158 }
 159
 160 ///////////////////////////////////////////
 161 //  preorder_rank(bp *b,int s)
 162 //    returns the preorder (>= 1) of node s (s >= 0)
 163 ///////////////////////////////////////////
 164
 165 static inline int bp_preorder_rank(bp *b,int s)
 166 {
 167   return bp_darray_rank(b->da,s);
 168 }
 169
 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)
 176 {
 177   //  no error handling
 178   if (b->opt & OPT_FAST_PREORDER_SELECT) {
 179     return bp_darray_select(b->da,s,1);
 180   } else {
 181     return bp_darray_select_bsearch(b->da,s, getpat_preorder);
 182   }
 183 }
 184
 185
 186 int bp_postorder_rank(bp *b,int s);
 187
 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)
 193 {
 194   return bp_getbit(b->B, s);
 195 }
 196
 197 static inline int bp_isleaf(bp *b, int s)
 198 {
 199   return (bp_inspect(b, s+1) == CP);
 200 }
 201
 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)
 207 {
 208   return (bp_find_close(b, s) - s + 1) / 2;
 209 }
 210
 211 ///////////////////////////////////////////
 212 //  first_child(bp *b, int s)
 213 //    returns the first child
 214 //            -1 if s is a leaf
 215 ///////////////////////////////////////////
 216
 217 static inline int bp_first_child(bp *b, int s)
 218 {
 219   return (bp_inspect(b, s+1) == CP) ? -1 : s+1;
 220 }
 221
 222
 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)
 229 {
 230   int t;
 231   t = bp_find_close(b,s) + 1;
 232   return (bp_inspect(b, t) == CP) ? -1 : t;
 233
 234 }
 235
 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
 242 //             0 otherwise
 243 ///////////////////////////////////////////
 244 static inline int bp_is_ancestor(bp *b, int s, int t)
 245 {
 246   int v;
 247   if (s == 0) return 1;
 248   v = bp_find_close(b, s);
 249   return (s <= t && t <= v);
 250 }
 251
 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);
 256
 257 // not efficient
 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);
 263
 264 // using preorder select index
 265 int preorder_select(bp *b,int s);
 266
 267 // using leaf index
 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);
 272
 273 // using leaf select index
 274 int bp_leaf_select(bp *b,int s);
 275
 276 // using inorder index
 277 int bp_inorder_rank(bp *b,int s);
 278
 279 // using inorder select index
 280 int bp_inorder_select(bp *b,int s);
 281
 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);
 286
 287
 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);
 292
 293
 294 static inline int blog(int x)
 295 {
 296   int l;
 297   l = 0;
 298   while (x>0) {
 299     x>>=1;
 300     l++;
 301   }
 302   return l;
 303 }
 304
 305
 306
 307
 308 extern int *matchtbl,*parenttbl;
 309
 310 extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
 311 extern int bwdtbl[(2*ETW+1)*(1<<ETW)];
 312 extern int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
 313 extern int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
 314 extern int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
 315 extern int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
 316
 317 extern int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
 318 extern int degtbl[1<<ETW];
 319 extern int degtbl2[(2*ETW+1)*(1<<ETW)];
 320 extern int childtbl[(ETW)*(1<<ETW)];
 321 extern int depthtbl[(2*ETW+1)*(1<<ETW)];
 322 extern int childtbl2[2*ETW+1][ETW][(1<<ETW)];
 323
 324 #ifdef __cplusplus
 325 }
 326 #endif
 327
 328
 329 #endif