X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2Flibbp.git;a=blobdiff_plain;f=bp.h;h=e0eb4c9ad241c1a90055ea2a4af7674fefd19078;hp=997934501cea08d66c6d5176b76a5e3275d993b2;hb=HEAD;hpb=7a6ee10ff66541dce5392ccabfdecf7ffffed388 diff --git a/bp.h b/bp.h index 9979345..e0eb4c9 100644 --- a/bp.h +++ b/bp.h @@ -1,14 +1,15 @@ #ifndef BP_H_ #define BP_H_ + #ifdef __cplusplus extern "C" { #endif - #include #include -#include "darray.h" +#include "bp-darray.h" +#include "bp-utils.h" #define OP 1 #define CP 0 @@ -18,15 +19,15 @@ extern "C" { #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 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 @@ -61,75 +62,246 @@ typedef struct { 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); +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); // 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); +int bp_naive_degree(bp *b, int s); +int bp_naive_child(bp *b, int s, int d); +int bp_naive_child_rank(bp *b, int t); +int bp_naive_rmq(bp *b, int s, int t,int opt); +int bp_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); +int bp_leaf_rank(bp *b,int s); +int bp_leaf_size(bp *b, int s); +int bp_leftmost_leaf(bp *b, int s); +int bp_rightmost_leaf(bp *b, int s); // using leaf select index -int leaf_select(bp *b,int s); +int bp_leaf_select(bp *b,int s); // using inorder index -int inorder_rank(bp *b,int s); +int bp_inorder_rank(bp *b,int s); // using inorder select index -int inorder_select(bp *b,int s); +int bp_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); +int bp_fast_degree(bp *b,int s, int t, int ith); +int bp_child_rank(bp *b, int t); +int bp_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); +bp * loadTree(FILE *fp); + +//0: success 1: failure (errno) +int bp_save(bp *b, int fd); + +//non-null: sucess, null: failure (errno) + +bp * bp_load(int fd); +void bp_delete(bp *b); static inline int blog(int x) @@ -143,19 +315,11 @@ static inline int blog(int x) 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<