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;
 118   if (bp_getbit(b->B, s - 1) == OP) return s - 1;
 119   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
 294 //0: success 1: failure (errno)
 295 int bp_save(bp *b, int fd);
 296
 297 //non-null: sucess, null: failure (errno)
 298
 299 bp * bp_load(int fd);
 300 void bp_delete(bp *b);
 301
 302
 303 static inline int blog(int x)
 304 {
 305   int l;
 306   l = 0;
 307   while (x>0) {
 308     x>>=1;
 309     l++;
 310   }
 311   return l;
 312 }
 313
 314
 315
 316
 317 extern int *matchtbl,*parenttbl;
 318
 319 extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
 320 extern int bwdtbl[(2*ETW+1)*(1<<ETW)];
 321 extern int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
 322 extern int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
 323 extern int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
 324 extern int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
 325
 326 extern int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
 327 extern int degtbl[1<<ETW];
 328 extern int degtbl2[(2*ETW+1)*(1<<ETW)];
 329 extern int childtbl[(ETW)*(1<<ETW)];
 330 extern int depthtbl[(2*ETW+1)*(1<<ETW)];
 331 extern int childtbl2[2*ETW+1][ETW][(1<<ETW)];
 332
 333 #ifdef __cplusplus
 334 }
 335 #endif
 336
 337
 338 #endif