bp.h

   1 #ifndef BP_H_
   2 #define BP_H_
   3
   4
   5 #ifdef __cplusplus
   6 extern "C" {
   7 #endif
   8
   9
  10 #include <stdio.h>
  11 #include <stdlib.h>
  12 #include "bp-darray.h"
  13 #include "bp-utils.h"
  14
  15
  16 #define OP 1
  17 #define CP 0
  18
  19 #define OPT_MIN 0
  20 #define OPT_MAX 1
  21 #define OPT_LEFT 0
  22 #define OPT_RIGHT 2
  23
  24 #define OPT_LEAF (1<<0)
  25 #define OPT_INORDER (1<<1)
  26 #define OPT_DEGREE (1<<2)
  27 #define OPT_FAST_PREORDER_SELECT (1<<3)
  28 #define OPT_FAST_LEAF_SELECT (1<<4)
  29 #define OPT_FAST_INORDER_SELECT (1<<5)
  30 #define OPT_FAST_POSTORDER_SELECT (1<<6)
  31 #define OPT_DFUDS_LEAF (1<<7)
  32 #define OPT_FAST_DFUDS_LEAF_SELECT (1<<8)
  33
  34 //#define logSB 9
  35 #define logSB 7
  36 //#define logSB 2
  37 #define SB (1<<logSB)
  38 //#define logMB 16
  39 //#define logMB 12
  40 #define logMB 15
  41 //#define logMB 3
  42 #define MB (1<<logMB)
  43
  44 #define ETW 8   // width of excess lookup table
  45 #define W1 2    // branching factor
  46
  47
  48
  49 typedef struct {
  50   int n;
  51   pb *B;
  52   darray *da;
  53   byte *sm, *sM;
  54   byte *sd;
  55   int *mm, *mM;
  56   int *md;
  57   int m_ofs;
  58
  59   darray *da_leaf;
  60   darray *da_inorder;
  61   darray *da_postorder;
  62   darray *da_dfuds_leaf;
  63   int idx_size;
  64   int opt;
  65 } bp;
  66
  67 pb getpat_preorder(pb *b);
  68 pb getpat_leaf(pb *b);
  69 pb getpat_inorder(pb *b);
  70 pb getpat_postorder(pb *b);
  71
  72 bp * bp_construct(int n, pb *B, int opt);
  73 void bp_print(bp *b, int s, int t);
  74
  75 int bp_fwd_excess(bp *b,int s, int rel);
  76 int bp_bwd_excess(bp *b,int s, int rel);
  77 int bp_rmq(bp *b, int s, int t, int opt);
  78 int bp_depth(bp *b, int s);
  79
  80 int bp_rank_open(bp *b, int s);
  81 int bp_rank_close(bp *b, int s);
  82 int bp_select_open(bp *b, int s);
  83 int bp_select_close(bp *b, int s);
  84
  85
  86 static inline int bp_root_node(bp *b)
  87 {
  88   return 0;
  89 }
  90
  91
  92 ///////////////////////////////////////////
  93 //  find_close(bp *b,int s)
  94 //    returns the matching close parenthesis of s
  95 ///////////////////////////////////////////
  96 static inline int bp_find_close(bp *b,int s)
  97 {
  98   return bp_fwd_excess(b, s, -1);
  99 }
 100
 101 ///////////////////////////////////////////
 102 //  bp_find_open(bp *b,int s)
 103 //    returns the matching open parenthesis of s
 104 ///////////////////////////////////////////
 105 static inline int bp_find_open(bp *b,int s)
 106 {
 107   int r = bp_bwd_excess(b, s, 0);
 108   return (r >= -1) ? r+1 : -1;
 109 }
 110
 111
 112 ///////////////////////////////////////////
 113 //  bp_parent(bp *b,int s)
 114 //    returns the parent of s
 115 //            -1 if s is the root
 116 ///////////////////////////////////////////
 117 static inline int bp_parent(bp *b, int s)
 118 {
 119   int r = bp_bwd_excess(b,s,-2);
 120   return (r >= -1) ? r+1 : -1;
 121 }
 122
 123 ///////////////////////////////////////////
 124 //  bp_parent_close(bp *b,int s)
 125 //    returns the closing parenthesis of the parent
 126 //    of s
 127 //            -1 if s is the root
 128 ///////////////////////////////////////////
 129
 130 static inline int bp_parent_close(bp *b, int s)
 131 {
 132   return bp_fwd_excess(b,s,-2);
 133 }
 134
 135
 136 static inline int bp_enclose(bp *b, int s)
 137 {
 138   return bp_parent(b, s);;
 139 }
 140
 141
 142 ///////////////////////////////////////////
 143 //  bp_level_ancestor(bp *b,int s,int d)
 144 //    returns the ancestor of s with relative depth d (d < 0)
 145 //            -1 if no such node
 146 ///////////////////////////////////////////
 147 static inline int bp_level_ancestor(bp *b,int s,int d)
 148 {
 149   int r = bp_bwd_excess(b,s,d-1);
 150   return (r >= -1) ? r+1 :-1;
 151 }
 152
 153 ///////////////////////////////////////////
 154 //  bp_lca(bp *b, int s, int t)
 155 //    returns the lowest common ancestor of s and t
 156 ///////////////////////////////////////////
 157 static inline int bp_lca(bp *b, int s, int t)
 158 {
 159   return bp_parent(b, bp_rmq(b,s,t,0)+1);
 160 }
 161
 162 ///////////////////////////////////////////
 163 //  preorder_rank(bp *b,int s)
 164 //    returns the preorder (>= 1) of node s (s >= 0)
 165 ///////////////////////////////////////////
 166
 167 static inline int bp_preorder_rank(bp *b,int s)
 168 {
 169   return bp_darray_rank(b->da,s);
 170 }
 171
 172 ///////////////////////////////////////////
 173 //  preorder_select(bp *b,int s)
 174 //    returns the node with preorder s (s >= 1)
 175 //            -1 if no such node
 176 ///////////////////////////////////////////
 177 static inline int bp_preorder_select(bp *b,int s)
 178 {
 179   //  no error handling
 180   if (b->opt & OPT_FAST_PREORDER_SELECT) {
 181     return bp_darray_select(b->da,s,1);
 182   } else {
 183     return bp_darray_select_bsearch(b->da,s, getpat_preorder);
 184   }
 185 }
 186
 187
 188 int bp_postorder_rank(bp *b,int s);
 189
 190 ///////////////////////////////////////////
 191 //  inspect(bp *b, int s)
 192 //    returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
 193 ///////////////////////////////////////////
 194 static inline int bp_inspect(bp *b, int s)
 195 {
 196   return bp_getbit(b->B,s);
 197 }
 198
 199 static inline int bp_isleaf(bp *b, int s)
 200 {
 201   return (bp_inspect(b, s+1) == CP);
 202 }
 203
 204 ///////////////////////////////////////////
 205 //  bp_subtree_size(bp *b, int s)
 206 //    returns the number of nodes in the subtree of s
 207 ///////////////////////////////////////////
 208 static inline int bp_subtree_size(bp *b, int s)
 209 {
 210   return (bp_find_close(b, s) - s + 1) / 2;
 211 }
 212
 213 ///////////////////////////////////////////
 214 //  first_child(bp *b, int s)
 215 //    returns the first child
 216 //            -1 if s is a leaf
 217 ///////////////////////////////////////////
 218
 219 static inline int bp_first_child(bp *b, int s)
 220 {
 221   return (bp_inspect(b, s+1) == CP) ? -1 : s+1;
 222 }
 223
 224
 225 ///////////////////////////////////////////
 226 //  next_sibling(bp *b,int s)
 227 //    returns the next sibling of parent(s)
 228 //            -1 if s is the last child
 229 //////////////////////////////////////////
 230 static inline int bp_next_sibling(bp *b, int s)
 231 {
 232   int t;
 233   t = bp_find_close(b,s) + 1;
 234   return (bp_inspect(b, t) == CP) ? -1 : t;
 235
 236 }
 237
 238 int bp_prev_sibling(bp *b, int s);
 239 int bp_deepest_node(bp *b,int s);
 240 int bp_subtree_height(bp *b,int s);
 241 ///////////////////////////////////////////
 242 //  bp_is_ancestor(bp *b, int s, int t)
 243 //     returns 1 if s is an ancestor of t
 244 //             0 otherwise
 245 ///////////////////////////////////////////
 246 static inline int bp_is_ancestor(bp *b, int s, int t)
 247 {
 248   int v;
 249   if (s == 0) return 1;
 250   v = bp_find_close(b, s);
 251   return (s <= t && t <= v);
 252 }
 253
 254 int bp_distance(bp *b, int s, int t);
 255 int bp_level_lefthmost(bp *b, int d);
 256 int bp_level_rigthmost(bp *b, int d);
 257 int bp_degree(bp *b,int s);
 258
 259 // not efficient
 260 int bp_naive_degree(bp *b, int s);
 261 int bp_naive_child(bp *b, int s, int d);
 262 int bp_naive_child_rank(bp *b, int t);
 263 int bp_naive_rmq(bp *b, int s, int t,int opt);
 264 int bp_postorder_select(bp *b,int s);
 265
 266 // using preorder select index
 267 int preorder_select(bp *b,int s);
 268
 269 // using leaf index
 270 int bp_leaf_rank(bp *b,int s);
 271 int bp_leaf_size(bp *b, int s);
 272 int bp_leftmost_leaf(bp *b, int s);
 273 int bp_rightmost_leaf(bp *b, int s);
 274
 275 // using leaf select index
 276 int bp_leaf_select(bp *b,int s);
 277
 278 // using inorder index
 279 int bp_inorder_rank(bp *b,int s);
 280
 281 // using inorder select index
 282 int bp_inorder_select(bp *b,int s);
 283
 284 // using degree index
 285 int bp_fast_degree(bp *b,int s, int t, int ith);
 286 int bp_child_rank(bp *b, int t);
 287 int bp_child(bp *b, int s, int d);
 288
 289
 290 // new functions for persistence purposes, added by Diego Arroyuelo
 291 void saveTree(bp *b, FILE *fp);
 292 bp * loadTree(FILE *fp);
 293 void bp_delete(bp *b);
 294
 295
 296 static inline int blog(int x)
 297 {
 298   int l;
 299   l = 0;
 300   while (x>0) {
 301     x>>=1;
 302     l++;
 303   }
 304   return l;
 305 }
 306
 307
 308
 309
 310 extern int *matchtbl,*parenttbl;
 311 void make_naivetbl(pb *B,int n);
 312
 313
 314 extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
 315 extern int bwdtbl[(2*ETW+1)*(1<<ETW)];
 316 extern int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
 317 extern int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
 318 extern int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
 319 extern int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
 320
 321 extern int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
 322 extern int degtbl[1<<ETW];
 323 extern int degtbl2[(2*ETW+1)*(1<<ETW)];
 324 extern int childtbl[(ETW)*(1<<ETW)];
 325 extern int depthtbl[(2*ETW+1)*(1<<ETW)];
 326 extern int childtbl2[2*ETW+1][ETW][(1<<ETW)];
 327
 328 #ifdef __cplusplus
 329 }
 330 #endif
 331
 332
 333 #endif