X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.h;h=8671baeba3abb37b4cef85bf522ce4f0f3536840;hb=45de465016fdd58a01d69012691772ef1b8d335c;hp=1eddbb0f1b0792298b72585545d652a0ba681f9b;hpb=f21a49f63aa3813e0b0b972bf81dc752b2a37153;p=SXSI%2FXMLTree.git diff --git a/XMLTree.h b/XMLTree.h index 1eddbb0..8671bae 100644 --- a/XMLTree.h +++ b/XMLTree.h @@ -95,9 +95,47 @@ typedef TagIdMap::const_iterator TagIdMapIT; // returns NULLT if the test is true #define NULLT_IF(x) do { if (x) return NULLT; } while (0) - - - +// Direct calls to sarray library + +static inline int fast_find_close(bp *b,int s) +{ + return fwd_excess(b,s,-1); +} + +static 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 treeNode fast_first_child(bp *Par, treeNode x) +{ + x = x+1; + return (fast_inspect(Par,x) == OP) ? x : NULLT; +} + +static treeNode fast_next_sibling(bp* Par,treeNode x) +{ + x = fast_find_close(Par,x)+1; + return (fast_inspect(Par,x) == OP) ? x : NULLT; +} + +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) + { + return (treeNode) t; + } +// tree node -> tag position +static int node2tagpos(treeNode x) +{ + return (int)x; +} class XMLTreeBuilder; @@ -211,7 +249,9 @@ public: /** IsFirstChild(x): returns whether node x is the first child of its parent. */ /* OCAML */ - bool IsFirstChild(treeNode x); + bool IsFirstChild(treeNode x) { + return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1)); + }; /** NumChildren(x): number of children of node x. Constant time with the * data structure of Sadakane. */ @@ -233,46 +273,29 @@ public: * tree nodes (and not texts). */ int Postorder(treeNode x); - /** Tag(x): returns the tag identifier of node x. */ - TagType Tag(treeNode x) { - if (tags_blen == 8) - return (TagType) (((uchar*)tags_fix)[(int) x]); - else - return (TagType) get_field(tags_fix,tags_blen, (int) x); - } /** DocIds(x): returns the range (i.e., a pair of integers) of document * identifiers that descend from node x. */ range DocIds(treeNode x); /** Parent(x): returns the parent node of node x. */ - treeNode Parent(treeNode x); + treeNode Parent(treeNode x) { + if (x == Root()) + return NULLT; + else + return parent(Par, x); + }; /* Assumes x is neither 0 nor -1 */ /** Child(x,i): returns the i-th child of node x, assuming it exists. */ treeNode Child(treeNode x, int i); - /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf - */ - treeNode FirstChild(treeNode x); - /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT - * if none. - */ - treeNode FirstElement(treeNode x); /** LastChild(x): returns the last child of node x. */ treeNode LastChild(treeNode x); - /** NextSibling(x): returns the next sibling of node x, or NULLT if none - * exists. */ - treeNode NextSibling(treeNode x); - - /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT - * if none. - */ - treeNode NextElement(treeNode x); /** PrevSibling(x): returns the previous sibling of node x, assuming it * exists. */ @@ -293,12 +316,10 @@ public: treeNode SelectFollowingSibling(treeNode x, TagIdSet * tags); - /** 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. */ - treeNode TaggedDescendant(treeNode x, TagType tag); - treeNode SelectDescendant(treeNode x, TagIdSet * tags); + + + treeNode SelectDescendant(treeNode x, TagIdSet * tags); /** TaggedPrec(x,tag): returns the first node tagged tag with smaller * preorder than x and not an ancestor of x. Returns NULLT if there @@ -310,7 +331,7 @@ public: * is none. */ treeNode TaggedFollowing(treeNode x, TagType tag); - treeNode TaggedFollowingBelow(treeNode x, TagType tag,treeNode ancestor); + treeNode SelectFollowingBelow(treeNode x, TagIdSet * tags, treeNode ancestor); @@ -498,6 +519,96 @@ public: void Print(int fd,treeNode x, bool no_text); void Print(int fd,treeNode x) { Print(fd,x,false); } + // The following are inlined here for speed + /** Tag(x): returns the tag identifier of node x. */ + + TagType Tag(treeNode x) { + if (tags_blen == 8) + return (TagType) (((uchar*)tags_fix)[(int) x]); + else + return (TagType) get_field(tags_fix,tags_blen, (int) x); + } + + /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf + */ + treeNode FirstChild(treeNode x) { + NULLT_IF(x==NULLT); + return fast_first_child(Par, x); + }; + + + /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT + * if none. + */ + treeNode FirstElement(treeNode x){ + { + NULLT_IF(x==NULLT); + x = fast_first_child(Par, x); + NULLT_IF(x == NULLT); + switch (Tag(x)){ + + case PCDATA_TAG_ID: + x = x+2; + return (fast_inspect(Par,x)==OP)? x : NULLT; + + case ATTRIBUTE_TAG_ID: + x = fast_next_sibling(Par,x); + if (x != NULLT && Tag(x) == PCDATA_TAG_ID){ + x = x+2; + return (fast_inspect(Par,x)==OP)? x : NULLT; + } + else return x; + default: + return x; + } + } + }; + + /** NextSibling(x): returns the next sibling of node x, or NULLT if none + * exists. */ + + treeNode NextSibling(treeNode x) { + NULLT_IF (x <= 0); + return fast_next_sibling(Par, x); + }; + + /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT + * if none. + */ + treeNode NextElement(treeNode x) + { + NULLT_IF(x <= 0); + x = fast_next_sibling(Par, x); + NULLT_IF(x == NULLT); + if (Tag(x) == PCDATA_TAG_ID){ + x = x+2; + return (fast_inspect(Par,x)==OP)? x : 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. */ + treeNode TaggedDescendant(treeNode x, TagType tag) + { + + int s = (int) Tags->select_next(tag,node2tagpos(x)); + NULLT_IF (s == -1); + + treeNode y = tagpos2node(s); // transforms the tag position into a node position + + return (fast_is_ancestor(Par,x,y) ? y : NULLT); + }; + + treeNode TaggedFollowingBelow(treeNode x, TagType tag,treeNode ancestor) + { + treeNode close = fast_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; + else return NULLT; + }; + };