- if (x == Root()) return NULLT;\r
- if (indexing_empty_texts) // faster, no rank needed\r
- return (DocID)x+2*subtree_size(Par, x)-1;\r
- else { // we are not indexing empty texts, rank is needed\r
- int p = x+2*subtree_size(Par, x)-1;\r
- if (EBVector->access(p) == 0) // there is no text to the right of node\r
- return (DocID)NULLT;\r
- else\r
- return (DocID)EBVector->rank1(p)-1; //-1 because document ids start from 0\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
+ \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
+ 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 == Root()) return min;\r
+ // else check whether if is in below the ctx node\r
+\r
+ NULLT_IF (min == NULLT || min >= fast_find_close(Par, ancestor));\r
+ \r
+ return min;\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
+ { \r
+ if (x == NULLT || x == Root())\r
+ return NULLT;\r
+ \r
+ treeNode s = parent(Par, x), r = Root();\r
+ while (s != r) {\r
+ if (Tag(s) == tag) return s;\r
+ s = parent(Par, s);\r