X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.h;h=1cab2aacf36da23962fd39ecc22591ce868d2266;hb=00d137d79d67d8a79c8ff7ab6623a00a3783df5f;hp=3b07aaf775799844bafd4d9f1b15fbc5bc59881b;hpb=e38bc834442d5369a523ba47d74865e48995ace4;p=SXSI%2FXMLTree.git diff --git a/XMLTree.h b/XMLTree.h index 3b07aaf..1cab2aa 100644 --- a/XMLTree.h +++ b/XMLTree.h @@ -25,17 +25,18 @@ #include #include #include -#include "TextCollection/TextCollectionBuilder.h" +#include #undef W #undef WW #undef Wminusone -#include "bp.h" +#include #include -#include -#include -#include +#include +#include +#include + using SXSI::TextCollection; using SXSI::TextCollectionBuilder; @@ -98,52 +99,6 @@ typedef TagIdMap::const_iterator TagIdMapIT; #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) @@ -291,13 +246,13 @@ 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; @@ -327,8 +282,8 @@ public: 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 ); } @@ -339,7 +294,7 @@ public: /** 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 @@ -369,10 +324,7 @@ public: /** 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){ @@ -380,7 +332,7 @@ public: 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); }; }; @@ -393,8 +345,8 @@ public: /** 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 @@ -403,7 +355,7 @@ public: treeNode PrevSibling(treeNode x) { NULLT_IF(x==NULLT); - return prev_sibling(Par, x); + return bp_prev_sibling(Par, x); } @@ -426,7 +378,7 @@ public: 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; @@ -459,7 +411,7 @@ public: NULLT_IF(x <= 0); - treeNode close = fast_find_close(Par,x); + treeNode close = bp_find_close(Par,x); treeNode min = NULLT; @@ -687,7 +639,7 @@ public: */ treeNode FirstChild(treeNode x) { NULLT_IF(x==NULLT); - return fast_first_child(Par, x); + return bp_first_child(Par, x); }; @@ -697,17 +649,17 @@ public: 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; @@ -720,7 +672,7 @@ public: 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 @@ -729,11 +681,11 @@ public: 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; }; @@ -752,21 +704,21 @@ public: 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; @@ -775,9 +727,9 @@ public: inline treeNode NextNodeBefore(treeNode x, treeNode ancestor_closing) { - treeNode close = fast_find_close(Par, x); - int rank = rank_open(Par, close); - treeNode y = select_open(Par, rank+1); + 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; }; @@ -787,7 +739,7 @@ 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; } @@ -797,9 +749,9 @@ treeNode TaggedFollowingSibling(treeNode x, TagType tag) 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;