-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);
+pb getpat_preorder(pb *b);
+pb getpat_leaf(pb *b);
+pb getpat_inorder(pb *b);
+pb getpat_postorder(pb *b);
+
+bp * bp_construct(int n, pb *B, int opt);
+void bp_print(bp *b, int s, int t);
+
+int bp_fwd_excess(bp *b,int s, int rel);
+int bp_bwd_excess(bp *b,int s, int rel);
+int bp_rmq(bp *b, int s, int t, int opt);
+int bp_depth(bp *b, int s);
+
+int bp_rank_open(bp *b, int s);
+int bp_rank_close(bp *b, int s);
+int bp_select_open(bp *b, int s);
+int bp_select_close(bp *b, int s);
+
+
+static inline int bp_root_node(bp *b)
+{
+ return 0;
+}
+
+///////////////////////////////////////////
+// inspect(bp *b, int s)
+// returns OP (==1) or CP (==0) at s-th bit (0 <= s < n)
+///////////////////////////////////////////
+static inline int bp_inspect(bp *b, int s)
+{
+ return bp_getbit(b->B, s);
+}
+
+///////////////////////////////////////////
+// find_close(bp *b,int s)
+// returns the matching close parenthesis of s
+///////////////////////////////////////////
+static inline int bp_find_close(bp *b,int s)
+{
+ int s1 = s + 1;
+ if (bp_inspect(b, s1) == CP)
+ return s1;
+ else
+ return bp_fwd_excess(b, s, -1);
+}
+
+///////////////////////////////////////////
+// bp_find_open(bp *b,int s)
+// returns the matching open parenthesis of s
+///////////////////////////////////////////
+static inline int bp_find_open(bp *b,int s)
+{
+ int r = bp_bwd_excess(b, s, 0);
+ return (r >= -1) ? r+1 : -1;
+}
+
+
+///////////////////////////////////////////
+// bp_parent(bp *b,int s)
+// returns the parent of s
+// -1 if s is the root
+///////////////////////////////////////////
+static inline int bp_parent(bp *b, int s)
+{
+ int r;
+ if (bp_getbit(b->B, s - 1) == OP) return s - 1;
+ r = bp_bwd_excess(b,s,-2);
+ return (r >= -1) ? r+1 : -1;
+}
+
+///////////////////////////////////////////
+// bp_parent_close(bp *b,int s)
+// returns the closing parenthesis of the parent
+// of s
+// -1 if s is the root
+///////////////////////////////////////////
+
+static inline int bp_parent_close(bp *b, int s)
+{
+ return bp_fwd_excess(b,s,-2);
+}
+
+
+static inline int bp_enclose(bp *b, int s)
+{
+ return bp_parent(b, s);;
+}
+
+
+///////////////////////////////////////////
+// bp_level_ancestor(bp *b,int s,int d)
+// returns the ancestor of s with relative depth d (d < 0)
+// -1 if no such node
+///////////////////////////////////////////
+static inline int bp_level_ancestor(bp *b,int s,int d)
+{
+ int r = bp_bwd_excess(b,s,d-1);
+ return (r >= -1) ? r+1 :-1;
+}
+
+///////////////////////////////////////////
+// bp_lca(bp *b, int s, int t)
+// returns the lowest common ancestor of s and t
+///////////////////////////////////////////
+static inline int bp_lca(bp *b, int s, int t)
+{
+ return bp_parent(b, bp_rmq(b,s,t,0)+1);
+}
+
+///////////////////////////////////////////
+// preorder_rank(bp *b,int s)
+// returns the preorder (>= 1) of node s (s >= 0)
+///////////////////////////////////////////
+
+static inline int bp_preorder_rank(bp *b,int s)
+{
+ return bp_darray_rank(b->da,s);
+}
+
+///////////////////////////////////////////
+// preorder_select(bp *b,int s)
+// returns the node with preorder s (s >= 1)
+// -1 if no such node
+///////////////////////////////////////////
+static inline int bp_preorder_select(bp *b,int s)
+{
+ // no error handling
+ if (b->opt & OPT_FAST_PREORDER_SELECT) {
+ return bp_darray_select(b->da,s,1);
+ } else {
+ return bp_darray_select_bsearch(b->da,s, getpat_preorder);
+ }
+}
+
+
+int bp_postorder_rank(bp *b,int s);
+
+static inline int bp_isleaf(bp *b, int s)
+{
+ return (bp_inspect(b, s+1) == CP);
+}
+
+///////////////////////////////////////////
+// bp_subtree_size(bp *b, int s)
+// returns the number of nodes in the subtree of s
+///////////////////////////////////////////
+static inline int bp_subtree_size(bp *b, int s)
+{
+ return (bp_find_close(b, s) - s + 1) / 2;
+}
+
+///////////////////////////////////////////
+// first_child(bp *b, int s)
+// returns the first child
+// -1 if s is a leaf
+///////////////////////////////////////////
+
+static inline int bp_first_child(bp *b, int s)
+{
+ int s1 = s + 1;
+ return bp_inspect(b, s1) ? s1 : -1;
+}
+
+
+///////////////////////////////////////////
+// next_sibling(bp *b,int s)
+// returns the next sibling of parent(s)
+// -1 if s is the last child
+//////////////////////////////////////////
+static inline int bp_next_sibling(bp *b, int s)
+{
+ int t;
+ t = bp_find_close(b, s) + 1;
+ return bp_inspect(b, t) ? t : -1;
+
+}
+
+int bp_prev_sibling(bp *b, int s);
+int bp_deepest_node(bp *b,int s);
+int bp_subtree_height(bp *b,int s);
+///////////////////////////////////////////
+// bp_is_ancestor(bp *b, int s, int t)
+// returns 1 if s is an ancestor of t
+// 0 otherwise
+///////////////////////////////////////////
+static inline int bp_is_ancestor(bp *b, int s, int t)
+{
+ int v;
+ if (s == 0) return 1;
+ v = bp_find_close(b, s);
+ return (s <= t && t <= v);
+}
+
+int bp_distance(bp *b, int s, int t);
+int bp_level_lefthmost(bp *b, int d);
+int bp_level_rigthmost(bp *b, int d);
+int bp_degree(bp *b,int s);