Initial import of libbp

[SXSI/libbp.git] / bp.h

diff --git a/bp.h b/bp.h
new file mode 100644 (file)
index 0000000..b4da26f
--- /dev/null
+++ b/bp.h
@@ -0,0 +1,178 @@
+#ifndef BP_H_
+#define BP_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include "darray.h"
+
+#define OP 1
+#define CP 0
+
+#define OPT_MIN 0
+#define OPT_MAX 1
+#define OPT_LEFT 0
+#define OPT_RIGHT 2
+
+#define OPT_LEAF (1<<0)
+#define OPT_INORDER (1<<1)
+#define OPT_DEGREE (1<<2)
+#define OPT_FAST_PREORDER_SELECT (1<<3)
+#define OPT_FAST_LEAF_SELECT (1<<4)
+#define OPT_FAST_INORDER_SELECT (1<<5)
+#define OPT_FAST_POSTORDER_SELECT (1<<6)
+#define OPT_DFUDS_LEAF (1<<7)
+#define OPT_FAST_DFUDS_LEAF_SELECT (1<<8)
+
+//#define logSB 9
+#define logSB 7
+//#define logSB 2
+#define SB (1<<logSB)
+//#define logMB 16
+//#define logMB 12
+#define logMB 15
+//#define logMB 3
+#define MB (1<<logMB)
+
+#define ETW 8   // width of excess lookup table
+#define W1 2    // branching factor
+
+
+
+typedef struct {
+  int n;
+  pb *B;
+  darray *da;
+  byte *sm, *sM;
+  byte *sd;
+  int *mm, *mM;
+  int *md;
+  int m_ofs;
+
+  darray *da_leaf;
+  darray *da_inorder;
+  darray *da_postorder;
+  darray *da_dfuds_leaf;
+  int idx_size;
+  int opt;
+} bp;
+
+int bp_construct(bp *b,int n, pb *B, int opt);
+void printbp(bp *b, int s, int t);
+
+
+int rank_open(bp *b, int s);
+int rank_close(bp *b, int s);
+int select_open(bp *b, int s);
+int select_close(bp *b, int s);
+
+
+int root_node(bp *b);
+int find_close(bp *b,int s);
+int find_open(bp *b,int s);
+int enclose(bp *b,int s);
+int parent(bp *b,int s);
+int level_ancestor(bp *b,int s,int d);
+int depth(bp *b, int s);
+int preorder_rank(bp *b,int s);
+int postorder_rank(bp *b,int s);
+int inspect(bp *b, int s);
+int isleaf(bp *b, int s);
+int rmq(bp *b, int s, int t, int opt);
+int subtree_size(bp *b, int s);
+int first_child(bp *b, int s);
+int next_sibling(bp *b, int s);
+int prev_sibling(bp *b, int s);
+int deepest_node(bp *b,int s);
+int subtree_height(bp *b,int s);
+int is_ancestor(bp *b, int s, int t);
+int distance(bp *b, int s, int t);
+int level_lefthmost(bp *b, int d);
+int level_rigthmost(bp *b, int d);
+int degree(bp *b,int s);
+
+// not efficient
+int naive_degree(bp *b, int s);
+int naive_child(bp *b, int s, int d);
+int naive_child_rank(bp *b, int t);
+int naive_rmq(bp *b, int s, int t,int opt);
+int postorder_select(bp *b,int s);
+
+// using preorder select index
+int preorder_select(bp *b,int s);
+
+// using leaf index
+int leaf_rank(bp *b,int s);
+int leaf_size(bp *b, int s);
+int leftmost_leaf(bp *b, int s);
+int rightmost_leaf(bp *b, int s);
+
+// using leaf select index
+int leaf_select(bp *b,int s);
+
+// using inorder index
+int inorder_rank(bp *b,int s);
+
+// using inorder select index
+int inorder_select(bp *b,int s);
+
+// using degree index
+int fast_degree(bp *b,int s, int t, int ith);
+int child_rank(bp *b, int t);
+int child(bp *b, int s, int d);
+
+
+// new functions for persistence purposes, added by Diego Arroyuelo
+void saveTree(bp *b, FILE *fp);
+void loadTree(bp *b, FILE *fp);
+void destroyTree(bp *b);
+
+
+inline int blog(int x)
+{
+  int l;
+  l = 0;
+  while (x>0) {
+    x>>=1;
+    l++;
+  }
+  return l;
+}
+
+pb getpat_preorder(pb *b);
+pb getpat_leaf(pb *b);
+pb getpat_inorder(pb *b);
+pb getpat_postorder(pb *b);
+
+
+int fwd_excess(bp *b,int s, int rel);
+int bwd_excess(bp *b,int s, int rel);
+
+extern int *matchtbl,*parenttbl;
+void make_naivetbl(pb *B,int n);
+
+extern int popCount[1<<ETW];
+extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
+extern int bwdtbl[(2*ETW+1)*(1<<ETW)];
+extern int mintbl_li[1<<ETW], mintbl_lv[1<<ETW];
+extern int mintbl_ri[1<<ETW], mintbl_rv[1<<ETW];
+extern int maxtbl_li[1<<ETW], maxtbl_lv[1<<ETW];
+extern int maxtbl_ri[1<<ETW], maxtbl_rv[1<<ETW];
+
+extern int minmaxtbl_i[4][1<<ETW], minmaxtbl_v[4][1<<ETW];
+extern int degtbl[1<<ETW];
+extern int degtbl2[(2*ETW+1)*(1<<ETW)];
+extern int childtbl[(ETW)*(1<<ETW)];
+extern int depthtbl[(2*ETW+1)*(1<<ETW)];
+extern int childtbl2[2*ETW+1][ETW][(1<<ETW)];
+
+#ifdef __cplusplus
+}
+#endif
+
+
+#endif