extern "C" {
#endif
-
#include <stdio.h>
#include <stdlib.h>
#include "bp-darray.h"
#include "bp-utils.h"
-
#define OP 1
#define CP 0
#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
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)
///////////////////////////////////////////
static inline int bp_find_close(bp *b,int s)
{
- return bp_fwd_excess(b, s, -1);
+ int s1 = s + 1;
+ if (bp_inspect(b, s1) == CP)
+ return s1;
+ else
+ return bp_fwd_excess(b, s, -1);
}
///////////////////////////////////////////
///////////////////////////////////////////
static inline int bp_parent(bp *b, int s)
{
- int r = bp_bwd_excess(b,s,-2);
+ 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;
}
int bp_postorder_rank(bp *b,int s);
-///////////////////////////////////////////
-// 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);
-}
-
static inline int bp_isleaf(bp *b, int s)
{
return (bp_inspect(b, s+1) == CP);
static inline int bp_first_child(bp *b, int s)
{
- return (bp_inspect(b, s+1) == CP) ? -1 : s+1;
+ int s1 = s + 1;
+ return bp_inspect(b, s1) ? s1 : -1;
}
static inline int bp_next_sibling(bp *b, int s)
{
int t;
- t = bp_find_close(b,s) + 1;
- return (bp_inspect(b, t) == CP) ? -1 : t;
+ t = bp_find_close(b, s) + 1;
+ return bp_inspect(b, t) ? t : -1;
}
// new functions for persistence purposes, added by Diego Arroyuelo
void saveTree(bp *b, FILE *fp);
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);
extern int *matchtbl,*parenttbl;
-void make_naivetbl(pb *B,int n);
-
extern int fwdtbl[(2*ETW+1)*(1<<ETW)];
extern int bwdtbl[(2*ETW+1)*(1<<ETW)];