bp.h

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