\r
if (tag == PCDATA_TAG_ID){\r
x = x+2;\r
- return fast_inspect(Par,x)==OP ? x : NULLT;\r
- } else return fast_next_sibling(Par,x);\r
+ return bp_inspect(Par,x)==OP ? x : NULLT;\r
+ } else return bp_next_sibling(Par,x);\r
\r
}\r
\r
{\r
buffer = 0;\r
print_stack = 0;\r
- // creates the data structure for the tree topology\r
- Par = (bp *)umalloc(sizeof(bp));\r
- STARTTIMER();\r
- bp_construct(Par, npar, (pb*) par, OPT_FAST_PREORDER_SELECT | OPT_DEGREE|0);\r
- STOPTIMER(Building);\r
- PRINTTIME("Building parenthesis struct", Building);\r
- STARTTIMER();\r
+ // creates the data structure for the tree topology\r
+ STARTTIMER();\r
+ Par = bp_construct(npar, (pb*) par, OPT_FAST_PREORDER_SELECT | OPT_DEGREE|0);\r
+ STOPTIMER(Building);\r
+ PRINTTIME("Building parenthesis struct", Building);\r
+ STARTTIMER();\r
\r
\r
// creates structure for tags\r
{\r
int i;\r
\r
- destroyTree(Par);\r
- free(Par); // frees the memory of struct Par\r
+ bp_delete(Par);\r
+ Par = NULL;\r
\r
delete tIdMap;\r
tIdMap = NULL;\r
XML_Tree = new XMLTree();\r
STARTTIMER();\r
// Load the tree structure\r
- XML_Tree->Par = (bp *)umalloc(sizeof(bp));\r
-\r
- loadTree(XML_Tree->Par, fp);\r
+ XML_Tree->Par = loadTree(fp);\r
STOPTIMER(Loading);\r
PRINTTIME("Loading parenthesis struct", Loading);\r
STARTTIMER();\r
\r
\r
\r
-// SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.\r
-/*int XMLTree::SubtreeSize(treeNode x)\r
- {\r
- return subtree_size(Par, x);\r
- }\r
-*/\r
-// SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.\r
-/*\r
-int XMLTree::SubtreeTags(treeNode x, TagType tag)\r
- {\r
- if (x == Root())\r
- x = fast_first_child(Par,x);\r
-\r
\r
- int s = x + 2*subtree_size(Par, x) - 1;\r
-\r
- return (Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1))+1;\r
- }\r
-*/\r
int XMLTree::SubtreeElements(treeNode x)\r
{\r
\r
- int size = subtree_size(Par,x);\r
+ int size = bp_subtree_size(Par, x);\r
if (x == Root()){\r
- x = fast_first_child(Par,x);\r
+ x = bp_first_child(Par,x);\r
size = size - 1;\r
};\r
\r
int s = x + 2*size - 1;\r
int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1);\r
size = size - ntext;\r
- treeNode fin = fast_find_close(Par,x);\r
+ treeNode fin = bp_find_close(Par,x);\r
treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x));\r
while (y != NULLT && y < fin){\r
size -= SubtreeSize(y);\r
- y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y));\r
+ y = Tags->select_next(ATTRIBUTE_TAG_ID, node2tagpos(y));\r
};\r
return size;\r
}\r
bool XMLTree::IsLeaf(treeNode x)\r
{\r
NULLT_IF(x==NULLT);\r
- return fast_isleaf(Par, x);\r
+ return bp_isleaf(Par, x);\r
}\r
\r
// IsAncestor(x,y): returns whether node x is ancestor of node y.\r
bool XMLTree::IsAncestor(treeNode x, treeNode y)\r
{\r
- return fast_is_ancestor(Par, x, y);\r
+ return bp_is_ancestor(Par, x, y);\r
}\r
\r
// IsChild(x,y): returns whether node x is parent of node y.\r
bool XMLTree::IsChild(treeNode x, treeNode y)\r
{\r
- if (!fast_is_ancestor(Par, x, y)) return false;\r
- return depth(Par, x) == (depth(Par, y) + 1);\r
+ if (!bp_is_ancestor(Par, x, y)) return false;\r
+ return bp_depth(Par, x) == (bp_depth(Par, y) + 1);\r
}\r
\r
-// IsFirstChild(x): returns whether node x is the first child of its parent.\r
-/*bool XMLTree::IsFirstChild(treeNode x)\r
- {\r
- return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));\r
- }\r
-*/\r
\r
// NumChildren(x): number of children of node x. Constant time with the data structure\r
// of Sadakane.\r
int XMLTree::NumChildren(treeNode x)\r
{\r
- return degree(Par, x);\r
+ return bp_degree(Par, x);\r
}\r
\r
// ChildNumber(x): returns i if node x is the i-th children of its parent.\r
int XMLTree::ChildNumber(treeNode x)\r
{\r
- return child_rank(Par, x);\r
+ return bp_child_rank(Par, x);\r
}\r
\r
// Depth(x): depth of node x, a simple binary rank on the parentheses sequence.\r
int XMLTree::Depth(treeNode x)\r
{\r
- return depth(Par, x);\r
+ return bp_depth(Par, x);\r
}\r
\r
// Preorder(x): returns the preorder number of node x, just counting the tree\r
// nodes (i.e., tags, it disregards the texts in the tree).\r
int XMLTree::Preorder(treeNode x)\r
{\r
- return preorder_rank(Par, x);\r
+ return bp_preorder_rank(Par, x);\r
}\r
\r
// Postorder(x): returns the postorder number of node x, just counting the tree\r
// nodes (i.e., tags, it disregards the texts in the tree).\r
int XMLTree::Postorder(treeNode x)\r
{\r
- return postorder_rank(Par, x);\r
+ return bp_postorder_rank(Par, x);\r
}\r
-/*\r
-// Tag(x): returns the tag identifier of node x.\r
-TagType XMLTree::Tag(treeNode x)\r
- {\r
- return fast_get_field(tags_fix,tags_blen,node2tagpos(x));\r
- }\r
-*/\r
+\r
// DocIds(x): returns the range of text identifiers that descend from node x.\r
// returns {NULLT, NULLT} when there are no texts descending from x.\r
range XMLTree::DocIds(treeNode x)\r
return r;\r
};\r
int min = EBVector->rank1(x-1);\r
- int max = EBVector->rank1(x+2*subtree_size(Par, x)-2);\r
+ int max = EBVector->rank1(x+2*bp_subtree_size(Par, x)-2);\r
if (min==max) { // range is empty, no texts within the subtree of x\r
r.min = NULLT;\r
r.max = NULLT;\r
return r;\r
}\r
\r
-// Parent(x): returns the parent node of node x.\r
-/*\r
-treeNode XMLTree::Parent(treeNode x)\r
- {\r
- if (x == Root())\r
- return NULLT;\r
- else\r
- return parent(Par, x);;\r
- }*/\r
\r
// Child(x,i): returns the i-th child of node x, assuming it exists.\r
treeNode XMLTree::Child(treeNode x, int i)\r
{\r
- if (i <= OPTD) return naive_child(Par, x, i);\r
- else return child(Par, x, i);\r
+ if (i <= OPTD) return bp_naive_child(Par, x, i);\r
+ else return bp_child(Par, x, i);\r
}\r
\r
-// FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
-/*\r
-treeNode XMLTree::FirstChild(treeNode x)\r
- {\r
- NULLT_IF(x==NULLT);\r
- return fast_first_child(Par, x);\r
- }\r
-*/\r
-/*\r
-treeNode XMLTree::FirstElement(treeNode x)\r
- {\r
- NULLT_IF(x==NULLT);\r
- x = fast_first_child(Par, x);\r
- NULLT_IF(x == NULLT);\r
- switch (Tag(x)){\r
-\r
- case PCDATA_TAG_ID:\r
- x = x+2;\r
- return (fast_inspect(Par,x)==OP)? x : NULLT;\r
-\r
- case ATTRIBUTE_TAG_ID:\r
- x = fast_next_sibling(Par,x);\r
- if (x != NULLT && Tag(x) == PCDATA_TAG_ID){\r
- x = x+2;\r
- return (fast_inspect(Par,x)==OP)? x : NULLT;\r
- }\r
- else return x;\r
- default:\r
- return x;\r
- }\r
- }\r
-*//*\r
-treeNode XMLTree::NextElement(treeNode x)\r
-{\r
- NULLT_IF(x==NULLT);\r
- x = fast_next_sibling(Par, x);\r
- NULLT_IF(x == NULLT);\r
- if (Tag(x) == PCDATA_TAG_ID){\r
- x = x+2;\r
- return (fast_inspect(Par,x)==OP)? x : NULLT;\r
- }\r
- else return x;\r
- }*/\r
-\r
-// LastChild(x): returns the last child of node x.\r
- /*treeNode XMLTree::LastChild(treeNode x)\r
- {\r
- NULLT_IF(x == NULLT || fast_isleaf(Par,x));\r
- return find_open(Par, fast_find_close(Par, x)-1);\r
- }\r
- */\r
-// NextSibling(x): returns the next sibling of node x, assuming it exists.\r
-/*treeNode XMLTree::NextSibling(treeNode x)\r
- {\r
- NULLT_IF(x==NULLT || x == Root() );\r
- x = fast_find_close(Par,x)+1;\r
- return (fast_inspect(Par,x) == CP ? NULLT : x);\r
- }\r
-*/\r
-\r
-// PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
-/*treeNode XMLTree::PrevSibling(treeNode x)\r
- {\r
- NULLT_IF(x==NULLT);\r
- return prev_sibling(Par, x);\r
- }\r
-*/\r
-// TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none.\r
-// Because of the balanced-parentheses representation of the tree, this operation is not supported\r
-// efficiently, just iterating among the children of node x until finding the desired child.\r
-/*\r
-treeNode XMLTree::TaggedChild(treeNode x, TagType tag)\r
- {\r
\r
- NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
- treeNode child;\r
- child = fast_first_child(Par, x); // starts at first child of node x\r
- if (Tag(child) == tag)\r
- return child;\r
- else\r
- return TaggedFollowingSibling(child,tag);\r
- }\r
-\r
-// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.\r
-treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)\r
-{\r
- NULLT_IF(x==NULLT);\r
- treeNode sibling = fast_next_sibling(Par, x);\r
- TagType ctag;\r
- while (sibling != NULLT) {\r
- ctag = Tag(sibling);\r
- if (ctag == tag) // current sibling is labeled with tag of interest\r
- return sibling;\r
- sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling\r
- }\r
- return NULLT; // no such sibling was found\r
-}\r
-*/\r
treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags)\r
{\r
\r
- NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
+ NULLT_IF(x==NULLT || bp_isleaf(Par,x));\r
int i;\r
- treeNode child = fast_first_child(Par, x);\r
+ treeNode child = bp_first_child(Par, x);\r
TagType t;\r
while (child != NULLT) {\r
t = Tag(child);\r
NULLT_IF(x==NULLT);\r
int i;\r
TagType t;\r
- treeNode sibling = fast_next_sibling(Par, x);\r
+ treeNode sibling = bp_next_sibling(Par, x);\r
while (sibling != NULLT) {\r
t = Tag(sibling);\r
if (tags->find(t) != tags->end()) return sibling;\r
}\r
\r
\r
-// TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within\r
-// the subtree of x. Returns NULLT if there is none.\r
-/*\r
-treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag)\r
- {\r
- //NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
-\r
- int s = (int) Tags->select_next(tag,node2tagpos(x));\r
- NULLT_IF (s == -1);\r
-\r
- treeNode y = tagpos2node(s); // transforms the tag position into a node position\r
-\r
- return (fast_is_ancestor(Par,x,y) ? y : NULLT);\r
- }\r
-*/\r
-/*\r
-treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)\r
- {\r
- NULLT_IF (x ==NULLT || fast_isleaf(Par,x));\r
- int i;\r
- treeNode min = NULLT;\r
- treeNode fc = fast_first_child(Par,x);\r
- treeNode aux;\r
- TagIdSet::const_iterator tagit;\r
- for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
- aux = TaggedDescendant(x, (TagType) *tagit);\r
- if (aux == fc) return fc;\r
- if (aux == NULLT) continue;\r
- if ((min == NULLT) || (aux < min)) min = aux;\r
- };\r
- return min;\r
- }\r
-\r
-*/\r
-\r
// TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an\r
// ancestor of x. Returns NULLT if there is none.\r
treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)\r
r = (int)Tags->rank(tag, node2tagpos(x)-1);\r
if (r==0) return NULLT; // there is no such node.\r
s = (int)Tags->select(tag, r);\r
- root = root_node(Par);\r
+ root = bp_root_node(Par);\r
node_s = tagpos2node(s);\r
- while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
+ while (bp_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
r--;\r
if (r==0) return NULLT; // there is no such node\r
s = (int)Tags->select(tag, r); // we should use select_prev instead when provided\r
treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)\r
{\r
NULLT_IF (x ==NULLT || x == Root());\r
- return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x)));\r
+ return tagpos2node(Tags->select_next(tag, bp_find_close(Par, x)));\r
\r
}\r
\r
-// TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x\r
-// and not in the subtree of x. Returns NULLT if there is none.\r
-/*\r
-treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)\r
-{\r
- // NULLT_IF (x == NULLT || x == Root() || x == ancestor);\r
-\r
- //Special optimisation, test for the following sibling first\r
- treeNode close = fast_find_close(Par, x);\r
- treeNode s = tagpos2node(Tags->select_next(tag, close));\r
-\r
- if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s;\r
- else return NULLT;\r
-}\r
-*/\r
- /*\r
-treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing)\r
-{\r
-\r
- NULLT_IF (x == NULLT || x == Root());\r
-\r
- treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x)));\r
- NULLT_IF (s == NULLT || s >= closing);\r
\r
- return s;\r
-}\r
- */\r
/* Here we inline TaggedFoll to find the min globally, and only at the end\r
we check if the min is below the context node */\r
treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor)\r
\r
NULLT_IF(x==NULLT || x==Root());\r
\r
- treeNode close = fast_find_close(Par,x);\r
+ treeNode close = bp_find_close(Par,x);\r
treeNode ns = close+1;\r
- if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))\r
+ if ( (bp_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))\r
return ns;\r
\r
int i;\r
// found the smallest node in preorder which is after x.\r
// if ctx is the root node, just return what we found.\r
\r
- if (ancestor == Root() || min == NULLT || min < fast_find_close(Par, ancestor)) return min;\r
+ if (ancestor == Root() || min == NULLT || min < bp_find_close(Par, ancestor)) return min;\r
else return NULLT;\r
\r
}\r
-/*\r
-treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode ancestor_closing)\r
- {\r
-\r
- NULLT_IF(x==NULLT || x==Root());\r
-\r
- treeNode close = fast_find_close(Par,x);\r
- treeNode ns = close+1;\r
- if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))\r
- return ns;\r
-\r
- int i;\r
- treeNode min = NULLT;\r
- treeNode aux;\r
-\r
-\r
- TagIdSet::const_iterator tagit;\r
- for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {\r
-\r
- aux = tagpos2node(Tags->select_next(*tagit, close));\r
- if (aux == NULLT) continue;\r
- if ((min == NULLT) || (aux < min)) min = aux;\r
- };\r
-\r
- // found the smallest node in preorder which is after x.\r
- // if ctx is the root node, just return what we found.\r
-\r
- if (ancestor_closing == Root() || min == NULLT || min < ancestor_closing) return min;\r
- else return NULLT;\r
-\r
- }\r
-*/\r
-/*\r
-treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing)\r
- {\r
-\r
- NULLT_IF(x==NULLT || x==Root());\r
- int i;\r
- treeNode min = NULLT;\r
- treeNode ns = fast_next_sibling(Par, x);\r
- treeNode close = ns - 1;\r
- treeNode aux;\r
- TagIdSet::const_iterator tagit;\r
- for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
-\r
- aux = tagpos2node(Tags->select_next(*tagit, close));\r
-\r
- // The next sibling of x is guaranteed to be below ctx\r
- // and is the node with lowest preorder which is after ctx.\r
- // if we find it, we return early;\r
-\r
- if (aux == ns ) return ns;\r
- if (aux == NULLT) continue;\r
- if ((min == NULLT) || (aux < min)) min = aux;\r
- };\r
-\r
- // found the smallest node in preorder which is after x.\r
- // if ctx is the root node, just return what we found.\r
-\r
- NULLT_IF (min == NULLT || min >= closing);\r
-\r
- return min;\r
-\r
- }\r
-*/\r
-\r
// TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return\r
// NULLT is there is none.\r
treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)\r
if (x == NULLT || x == Root())\r
return NULLT;\r
\r
- treeNode s = parent(Par, x), r = Root();\r
+ treeNode s = bp_parent(Par, x), r = Root();\r
while (s != r) {\r
if (Tag(s) == tag) return s;\r
- s = parent(Par, s);\r
+ s = bp_parent(Par, s);\r
}\r
return NULLT;\r
}\r
{\r
NULLT_IF(d == NULLT);\r
int s = EBVector->select1(d+1);\r
- return rank_open(Par, s) + d + 1; // +1 because root has preorder 1\r
+ return bp_rank_open(Par, s) + d + 1; // +1 because root has preorder 1\r
\r
}\r
\r
{\r
NULLT_IF(x == NULLT);\r
if (x == Root()) return 1; // root node has preorder 1\r
- return rank_open(Par, x) + EBVector->rank1(x-1);\r
+ return bp_rank_open(Par, x) + EBVector->rank1(x-1);\r
}\r
\r
// ParentNode(d): returns the parent node of document identifier d.\r
\r
\r
treeNode XMLTree::Closing(treeNode x) {\r
- return fast_find_close(Par,x);\r
+ return bp_find_close(Par,x);\r
}\r
-bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }\r
+bool XMLTree::IsOpen(treeNode x) { return bp_inspect(Par,x); }\r
\r
//WARNING this uses directly the underlying implementation for plain text\r
\r
print_stack->reserve(256);\r
};\r
\r
- treeNode fin = fast_find_close(Par,x);\r
+ treeNode fin = bp_find_close(Par,x);\r
treeNode n = x;\r
TagType tag = Tag(n);\r
\r
size_t read = 0;\r
\r
while (n <= fin){\r
- if (fast_inspect(Par,n)){\r
+ if (bp_inspect(Par,n)){\r
if (tag == PCDATA_TAG_ID) {\r
\r
if (no_text)\r
_dputc('<',fd);\r
_dput_str((*TagName)[tag], fd);\r
n++;\r
- if (fast_inspect(Par,n)) {\r
+ if (bp_inspect(Par,n)) {\r
print_stack->push_back(&((*TagName)[tag]));\r
tag = Tag(n);\r
if (tag == ATTRIBUTE_TAG_ID){\r
n++;\r
if (no_text) _dputs("><@@>",fd);\r
\r
- while (fast_inspect(Par,n)){\r
+ while (bp_inspect(Par,n)){\r
if (no_text) {\r
_dputc('<', fd);\r
_dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);\r
_dputc('>', fd);\r
print_stack->pop_back();\r
n++;\r
- } while (!(fast_inspect(Par,n) || print_stack->empty()));\r
+ } while (!(bp_inspect(Par,n) || print_stack->empty()));\r
tag = Tag(n);\r
};\r
_dputc('\n', fd);\r
projects / SXSI / XMLTree.git / blobdiff