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 //  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)
  94 {
  95   return bp_getbit(b->B, s);
  96 }
  97
  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)
 103 {
 104   int s1 = s + 1;
 105   if (bp_inspect(b, s1) == CP)
 106     return s1;
 107   else
 108     return bp_fwd_excess(b, s, -1);
 109 }
 110
 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)
 116 {
 117   int r = bp_bwd_excess(b, s, 0);
 118   return (r >= -1) ? r+1 : -1;
 119 }
 120
 121
 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)
 128 {
 129   int r;
 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;
 133 }
 134
 135 ///////////////////////////////////////////
 136 //  bp_parent_close(bp *b,int s)
 137 //    returns the closing parenthesis of the parent
 138 //    of s
 139 //            -1 if s is the root
 140 ///////////////////////////////////////////
 141
 142 static inline int bp_parent_close(bp *b, int s)
 143 {
 144   return bp_fwd_excess(b,s,-2);
 145 }
 146
 147
 148 static inline int bp_enclose(bp *b, int s)
 149 {
 150   return bp_parent(b, s);;
 151 }
 152
 153
 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)
 160 {
 161   int r = bp_bwd_excess(b,s,d-1);
 162   return (r >= -1) ? r+1 :-1;
 163 }
 164
 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)
 170 {
 171   return bp_parent(b, bp_rmq(b,s,t,0)+1);
 172 }
 173
 174 ///////////////////////////////////////////
 175 //  preorder_rank(bp *b,int s)
 176 //    returns the preorder (>= 1) of node s (s >= 0)
 177 ///////////////////////////////////////////
 178
 179 static inline int bp_preorder_rank(bp *b,int s)
 180 {
 181   return bp_darray_rank(b->da,s);
 182 }
 183
 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)
 190 {
 191   //  no error handling
 192   if (b->opt & OPT_FAST_PREORDER_SELECT) {
 193     return bp_darray_select(b->da,s,1);
 194   } else {
 195     return bp_darray_select_bsearch(b->da,s, getpat_preorder);
 196   }
 197 }
 198
 199
 200 int bp_postorder_rank(bp *b,int s);
 201
 202 static inline int bp_isleaf(bp *b, int s)
 203 {
 204   return (bp_inspect(b, s+1) == CP);
 205 }
 206
 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)
 212 {
 213   return (bp_find_close(b, s) - s + 1) / 2;
 214 }
 215
 216 ///////////////////////////////////////////
 217 //  first_child(bp *b, int s)
 218 //    returns the first child
 219 //            -1 if s is a leaf
 220 ///////////////////////////////////////////
 221
 222 static inline int bp_first_child(bp *b, int s)
 223 {
 224   int s1 = s + 1;
 225   return bp_inspect(b, s1) ? s1 : -1;
 226 }
 227
 228
 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)
 235 {
 236   int t;
 237   t = bp_find_close(b, s) + 1;
 238   return bp_inspect(b, t) ? t : -1;
 239
 240 }
 241
 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
 248 //             0 otherwise
 249 ///////////////////////////////////////////
 250 static inline int bp_is_ancestor(bp *b, int s, int t)
 251 {
 252   int v;
 253   if (s == 0) return 1;
 254   v = bp_find_close(b, s);
 255   return (s <= t && t <= v);
 256 }
 257
 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);
 262
 263 // not efficient
 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);
 269
 270 // using preorder select index
 271 int preorder_select(bp *b,int s);
 272
 273 // using leaf index
 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);
 278
 279 // using leaf select index
 280 int bp_leaf_select(bp *b,int s);
 281
 282 // using inorder index
 283 int bp_inorder_rank(bp *b,int s);
 284
 285 // using inorder select index
 286 int bp_inorder_select(bp *b,int s);
 287
 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);
 292
 293
 294 // new functions for persistence purposes, added by Diego Arroyuelo
 295 void saveTree(bp *b, FILE *fp);
 296 bp * loadTree(FILE *fp);
 297
 298 //0: success 1: failure (errno)
 299 int bp_save(bp *b, int fd);
 300
 301 //non-null: sucess, null: failure (errno)
 302
 303 bp * bp_load(int fd);
 304 void bp_delete(bp *b);
 305
 306
 307 static inline int blog(int x)
 308 {
 309   int l;
 310   l = 0;
 311   while (x>0) {
 312     x>>=1;
 313     l++;
 314   }
 315   return l;
 316 }
 317
 318
 319
 320
 321 extern int *matchtbl,*parenttbl;
 322
 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];
 329
 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)];
 336
 337 #ifdef __cplusplus
 338 }
 339 #endif
 340
 341
 342 #endif