bp.h

   1 #ifndef BP_H_
   2 #define BP_H_
   3
   4 #ifdef __cplusplus
   5 extern "C" {
   6 #endif
   7
   8
   9 #include <stdio.h>
  10 #include <stdlib.h>
  11 #include "darray.h"
  12
  13 #define OP 1
  14 #define CP 0
  15
  16 #define OPT_MIN 0
  17 #define OPT_MAX 1
  18 #define OPT_LEFT 0
  19 #define OPT_RIGHT 2
  20
  21 #define OPT_LEAF (1<<0)
  22 #define OPT_INORDER (1<<1)
  23 #define OPT_DEGREE (1<<2)
  24 #define OPT_FAST_PREORDER_SELECT (1<<3)
  25 #define OPT_FAST_LEAF_SELECT (1<<4)
  26 #define OPT_FAST_INORDER_SELECT (1<<5)
  27 #define OPT_FAST_POSTORDER_SELECT (1<<6)
  28 #define OPT_DFUDS_LEAF (1<<7)
  29 #define OPT_FAST_DFUDS_LEAF_SELECT (1<<8)
  30
  31 //#define logSB 9
  32 #define logSB 7
  33 //#define logSB 2
  34 #define SB (1<<logSB)
  35 //#define logMB 16
  36 //#define logMB 12
  37 #define logMB 15
  38 //#define logMB 3
  39 #define MB (1<<logMB)
  40
  41 #define ETW 8   // width of excess lookup table
  42 #define W1 2    // branching factor
  43
  44
  45
  46 typedef struct {
  47   int n;
  48   pb *B;
  49   darray *da;
  50   byte *sm, *sM;
  51   byte *sd;
  52   int *mm, *mM;
  53   int *md;
  54   int m_ofs;
  55
  56   darray *da_leaf;
  57   darray *da_inorder;
  58   darray *da_postorder;
  59   darray *da_dfuds_leaf;
  60   int idx_size;
  61   int opt;
  62 } bp;
  63
  64 int bp_construct(bp *b,int n, pb *B, int opt);
  65 void printbp(bp *b, int s, int t);
  66
  67
  68 int rank_open(bp *b, int s);
  69 int rank_close(bp *b, int s);
  70 int select_open(bp *b, int s);
  71 int select_close(bp *b, int s);
  72
  73
  74 int root_node(bp *b);
  75 int find_close(bp *b,int s);
  76 int find_open(bp *b,int s);
  77 int enclose(bp *b,int s);
  78 int parent(bp *b,int s);
  79 int level_ancestor(bp *b,int s,int d);
  80 int depth(bp *b, int s);
  81 int preorder_rank(bp *b,int s);
  82 int postorder_rank(bp *b,int s);
  83 int inspect(bp *b, int s);
  84 int isleaf(bp *b, int s);
  85 int rmq(bp *b, int s, int t, int opt);
  86 int subtree_size(bp *b, int s);
  87 int first_child(bp *b, int s);
  88 int next_sibling(bp *b, int s);
  89 int prev_sibling(bp *b, int s);
  90 int deepest_node(bp *b,int s);
  91 int subtree_height(bp *b,int s);
  92 int is_ancestor(bp *b, int s, int t);
  93 int distance(bp *b, int s, int t);
  94 int level_lefthmost(bp *b, int d);
  95 int level_rigthmost(bp *b, int d);
  96 int degree(bp *b,int s);
  97
  98 // not efficient
  99 int naive_degree(bp *b, int s);
 100 int naive_child(bp *b, int s, int d);
 101 int naive_child_rank(bp *b, int t);
 102 int naive_rmq(bp *b, int s, int t,int opt);
 103 int postorder_select(bp *b,int s);
 104
 105 // using preorder select index
 106 int preorder_select(bp *b,int s);
 107
 108 // using leaf index
 109 int leaf_rank(bp *b,int s);
 110 int leaf_size(bp *b, int s);
 111 int leftmost_leaf(bp *b, int s);
 112 int rightmost_leaf(bp *b, int s);
 113
 114 // using leaf select index
 115 int leaf_select(bp *b,int s);
 116
 117 // using inorder index
 118 int inorder_rank(bp *b,int s);
 119
 120 // using inorder select index
 121 int inorder_select(bp *b,int s);
 122
 123 // using degree index
 124 int fast_degree(bp *b,int s, int t, int ith);
 125 int child_rank(bp *b, int t);
 126 int child(bp *b, int s, int d);
 127
 128
 129 // new functions for persistence purposes, added by Diego Arroyuelo
 130 void saveTree(bp *b, FILE *fp);
 131 void loadTree(bp *b, FILE *fp);
 132 void destroyTree(bp *b);
 133
 134
 135 static inline int blog(int x)
 136 {
 137   int l;
 138   l = 0;
 139   while (x>0) {
 140     x>>=1;
 141     l++;
 142   }
 143   return l;
 144 }
 145
 146 pb getpat_preorder(pb *b);
 147 pb getpat_leaf(pb *b);
 148 pb getpat_inorder(pb *b);
 149 pb getpat_postorder(pb *b);
 150
 151
 152 int fwd_excess(bp *b,int s, int rel);
 153 int bwd_excess(bp *b,int s, int rel);
 154
 155 extern int *matchtbl,*parenttbl;
 156 void make_naivetbl(pb *B,int n);
 157
 158 extern int popCount[1<<ETW];
 159 extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
 160 extern int bwdtbl[(2*ETW+1)*(1<<ETW)];
 161 extern int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
 162 extern int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
 163 extern int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
 164 extern int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
 165
 166 extern int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
 167 extern int degtbl[1<<ETW];
 168 extern int degtbl2[(2*ETW+1)*(1<<ETW)];
 169 extern int childtbl[(ETW)*(1<<ETW)];
 170 extern int depthtbl[(2*ETW+1)*(1<<ETW)];
 171 extern int childtbl2[2*ETW+1][ETW][(1<<ETW)];
 172
 173 #ifdef __cplusplus
 174 }
 175 #endif
 176
 177
 178 #endif