#include <unordered_set>
#include <unordered_map>
#include <sstream>
-#include "TextCollection/TextCollectionBuilder.h"
+#include <TextCollection/TextCollectionBuilder.h>
#undef W
#undef WW
#undef Wminusone
-#include "bp.h"
+#include <bp/bp.h>
+#include <bp/bp-darray.h>
#include <libcds/includes/basics.h>
-#include <static_bitsequence.h>
-#include <alphabet_mapper.h>
-#include <static_sequence.h>
+#include <libcds/includes/static_bitsequence.h>
+#include <libcds/includes/alphabet_mapper.h>
+#include <libcds/includes/static_sequence.h>
+
using SXSI::TextCollection;
using SXSI::TextCollectionBuilder;
// returns NULLT if the test is true
#define NULLT_IF(x) do { if (x) return NULLT; } while (0)
+#define IS_NIL(x) ((x) < 0)
// Direct calls to sarray library
#define BUFFER_ALLOC (8192 * 2)
#define BUFFER_SIZE (BUFFER_ALLOC / 2)
-static inline int fast_find_open(bp *b,int s)
-{
- int r;
- r = bwd_excess(b,s,0);
- if (r >= -1) return r+1;
- return -1;
-}
-
-static inline int fast_find_close(bp *b,int s)
-{
- return fwd_excess(b,s,-1);
-}
-
-static inline int fast_find_parent_close(bp *b,int s)
-{
- return fwd_excess(b,s,-2);
-}
-
-
-static inline int fast_inspect(bp* Par,treeNode i)
-{
- int j,l;
- j = i >> logD;
- l = i & (D-1);
- return (Par->B[j] >> (D-1-l)) & 1;
-}
-
-static bool fast_isleaf(bp* Par,treeNode x){
- return (fast_inspect(Par, x+1) == CP);
-}
-
-static treeNode fast_first_child(bp *Par, treeNode x)
-{
- x = x+1;
- return (fast_inspect(Par,x) == OP) ? x : NULLT;
-}
-
-inline static treeNode fast_next_sibling(bp* Par,treeNode x)
-{
- treeNode y = fast_find_close(Par,x)+1;
- return (fast_inspect(Par, y) == OP) ? y : NULLT;
-}
-
-inline static bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){
- return (x <= y) && ((x==0) || (y <= fast_find_close(Par,x)));
-}
// tag position -> tree node
static treeNode tagpos2node(int t)
std::vector<std::string> * const TN,
TagIdMap * const tim, uint *empty_texts_bmp,
TagType *tags,
- TextCollection * const TC, bool dis_tc,
+ TextCollectionBuilder * const TCB, bool dis_tc,
TextCollectionBuilder::index_type_t _index_type );
public:
/** SubtreeSize(x): the number of nodes (and attributes) in the subtree of
* node x. */
- int SubtreeSize(treeNode x) { return subtree_size(Par, x); }
+ int SubtreeSize(treeNode x) { return bp_subtree_size(Par, x); }
/** SubtreeTags(x,tag): the number of occurrences of tag within the subtree
* of node x. */
int SubtreeTags(treeNode x, TagType tag){
//int s = x + 2*subtree_size(Par, x) - 1;
- treeNode y = fast_find_close(Par, x);
+ treeNode y = bp_find_close(Par, x);
if (y - x < 10) {
int count = 0;
not a descendant of the first child of x */
bool IsRightDescendant(treeNode x, treeNode y) {
if (x <= Root()) return false;
- treeNode z = fast_find_parent_close(Par, x);
- treeNode c = fast_find_close(Par, x);
+ treeNode z = bp_parent_close(Par, x);
+ treeNode c = bp_find_close(Par, x);
return (y > c && y < z );
}
/** IsFirstChild(x): returns whether node x is the first child of its parent. */
/* OCAML */
bool IsFirstChild(treeNode x) {
- return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));
+ return ((x != NULLT)&&(x==Root() || bp_prev_sibling(Par,x) == (treeNode)-1));
};
/** NumChildren(x): number of children of node x. Constant time with the
/** Parent(x): returns the parent node of node x. */
treeNode Parent(treeNode x) {
- if (x == Root())
- return NULLT;
- else
- return parent(Par, x);
+ return (x == Root()) ? NULLT : bp_parent(Par, x);
};
treeNode BinaryParent(treeNode x){
return NULLT;
else {
treeNode prev = x - 1;
- return (fast_inspect(Par, prev) == OP) ? prev : fast_find_open(Par, prev);
+ return (bp_inspect(Par, prev) == OP) ? prev : bp_find_open(Par, prev);
};
};
/** LastChild(x): returns the last child of node x. */
treeNode LastChild(treeNode x) {
- NULLT_IF(x == NULLT || fast_isleaf(Par,x));
- return fast_find_open(Par, fast_find_close(Par, x)-1);
+ NULLT_IF(x == NULLT || bp_isleaf(Par,x));
+ return bp_find_open(Par, bp_find_close(Par, x)-1);
}
/** PrevSibling(x): returns the previous sibling of node x, assuming it
treeNode PrevSibling(treeNode x)
{
NULLT_IF(x==NULLT);
- return prev_sibling(Par, x);
+ return bp_prev_sibling(Par, x);
}
treeNode SelectDescendant(treeNode x, TagIdSet * tags) {
NULLT_IF (x == NULLT);
treeNode fc = x+1;
- if (fast_inspect(Par, fc) == CP) return NULLT;
+ if (bp_inspect(Par, fc) == CP) return NULLT;
treeNode min = NULLT;
treeNode aux;
NULLT_IF(x <= 0);
- treeNode close = fast_find_close(Par,x);
+ treeNode close = bp_find_close(Par,x);
treeNode min = NULLT;
*/
treeNode FirstChild(treeNode x) {
NULLT_IF(x==NULLT);
- return fast_first_child(Par, x);
+ return bp_first_child(Par, x);
};
treeNode FirstElement(treeNode node){
{
NULLT_IF(node == NULLT);
- treeNode x = fast_first_child(Par, node);
+ treeNode x = bp_first_child(Par, node);
NULLT_IF(x == NULLT);
switch (Tag(x)){
case ATTRIBUTE_TAG_ID:
- x = fast_next_sibling(Par,x);
+ x = bp_next_sibling(Par,x);
if (x == NULLT || Tag(x) != PCDATA_TAG_ID) return x;
case PCDATA_TAG_ID:
x = x+2;
- return (fast_inspect(Par,x)==OP)? x : NULLT;
+ return (bp_inspect(Par,x)==OP)? x : NULLT;
default:
return x;
treeNode NextSibling(treeNode x) {
NULLT_IF (x <= 0);
- return fast_next_sibling(Par, x);
+ return bp_next_sibling(Par, x);
};
/** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT
treeNode NextElement(treeNode x)
{
NULLT_IF(x <= 0);
- x = fast_next_sibling(Par, x);
+ x = bp_next_sibling(Par, x);
NULLT_IF(x == NULLT);
if (Tag(x) == PCDATA_TAG_ID){
int y = x+2;
- return (fast_inspect(Par, y) == OP) ? y : NULLT;
+ return (bp_inspect(Par, y) == OP) ? y : NULLT;
}
else return x;
};
/** TaggedDesc(x,tag): returns the first node tagged tag with larger
* preorder than x and within the subtree of x. Returns NULT if there
* is none. */
+ inline treeNode TaggedNext(treeNode x, TagType tag)
+ {
+ return tagpos2node(Tags->select_next(tag,node2tagpos(x)));
+ }
inline treeNode TaggedDescendant(treeNode x, TagType tag)
{
treeNode y = tagpos2node(s); // transforms the tag position into a node position
- return (fast_is_ancestor(Par,x,y) ? y : NULLT);
+ return (bp_is_ancestor(Par,x,y) ? y : NULLT);
};
inline treeNode TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)
{
- treeNode close = fast_find_close(Par, x);
+ treeNode close = bp_find_close(Par, x);
treeNode s = tagpos2node(Tags->select_next(tag, close));
- if (ancestor == Root() || s == NULLT || s < fast_find_close(Par,ancestor)) return s;
+ if (ancestor == Root() || s == NULLT || s < bp_find_close(Par,ancestor)) return s;
else return NULLT;
};
inline treeNode TaggedFollowingBefore(treeNode x, TagType tag, treeNode ancestor_closing)
{
- treeNode close = fast_find_close(Par, x);
+ treeNode close = bp_find_close(Par, x);
treeNode s = tagpos2node(Tags->select_next(tag, close));
if (ancestor_closing == Root() || s == NULLT || s < ancestor_closing) return s;
else return NULLT;
};
+ inline treeNode NextNodeBefore(treeNode x, treeNode ancestor_closing)
+ {
+ treeNode close = bp_find_close(Par, x);
+ int rank = bp_rank_open(Par, close);
+ treeNode y = bp_select_open(Par, rank+1);
+ return (y < ancestor_closing) ? y : NULLT;
+ };
+
// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.
treeNode TaggedFollowingSibling(treeNode x, TagType tag)
{
NULLT_IF(x==NULLT);
treeNode sibling = x;
TagType ctag;
- while ((sibling = fast_next_sibling(Par, sibling)) != NULLT) {
+ while ((sibling = bp_next_sibling(Par, sibling)) != NULLT) {
ctag = Tag(sibling);
if (ctag == tag) return sibling;
}
treeNode TaggedChild(treeNode x, TagType tag)
{
- NULLT_IF(x==NULLT || fast_isleaf(Par,x));
+ NULLT_IF(x==NULLT || bp_isleaf(Par,x));
treeNode child;
- child = fast_first_child(Par, x);
+ child = bp_first_child(Par, x);
if (Tag(child) == tag)
return child;
projects / SXSI / XMLTree.git / blobdiff