Added TaggedNext

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@178 3cdefd35-fc62-479d-8e8d-bae585ffb9ca

diff --git a/XMLTree.cpp b/XMLTree.cpp
index bb861a9..4ddec01 100644 (file)
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -268,6 +268,9 @@ int XMLTree::SubtreeTags(treeNode x, TagType tag)
        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
        exit(1);\r
     }\r
+    if (x == Root())\r
+      x = first_child(Par,x);\r
+    \r
 \r
     int s = x + 2*subtree_size(Par, x) - 1;\r
  \r
@@ -368,7 +371,7 @@ TagType XMLTree::Tag(treeNode x)
        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
        exit(1);\r
     }\r
-\r
+    \r
     return Tags->access(node2tagpos(x));\r
  }\r
 \r
@@ -496,6 +499,9 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag)
 \r
     int r, s;\r
     treeNode y;\r
+    if (isleaf(Par,x))\r
+      return NULLT;\r
+\r
     r = (int) Tags->rank(tag, node2tagpos(x));\r
     s = (int) Tags->select(tag, r+1);\r
     if (s == -1) return NULLT; // there is no such node\r
@@ -504,6 +510,28 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag)
     else return y;\r
  }\r
 \r
+// TaggedNext(x,tag): returns the first node tagged tag with larger preorder than x \r
+// Returns NULLT if there is none.\r
+treeNode XMLTree::TaggedNext(treeNode x, TagType tag) \r
+ {\r
+    if (!finished) {\r
+       fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+       exit(1);\r
+    }\r
+\r
+    int r, s;\r
+    treeNode y;\r
+    if (x==NULLT)\r
+      return NULLT;\r
+\r
+    r = (int) Tags->rank(tag, node2tagpos(x));\r
+    s = (int) Tags->select(tag, r+1);\r
+    if (s == -1) return NULLT; // there is no such node\r
+    y = tagpos2node(s); // transforms the tag position into a node position  \r
+    return (y<=x ? NULLT : y);\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::TaggedPrec(treeNode x, TagType tag) \r
@@ -539,9 +567,9 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
     }\r
 \r
     int r, s;\r
-    if (x == Root() || (next_sibling(Par,x) == -1 ))\r
+    if (x ==NULLT || x == Root()|| (next_sibling(Par,x) == -1 ))\r
       return NULLT;\r
-    \r
+\r
     r = (int) Tags->rank(tag, node2tagpos(next_sibling(Par, x))-1);\r
     s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.\r
     if (s==-1) return NULLT;\r

diff --git a/XMLTree.h b/XMLTree.h
index 7c08fcc..a00487a 100644 (file)
--- a/XMLTree.h
+++ b/XMLTree.h
@@ -202,6 +202,10 @@ public:
     * is none. */\r
    treeNode TaggedDesc(treeNode x, TagType tag);\r
 \r
+   /** TaggedNext(x,tag): returns the first node tagged tag with larger \r
+    * preorder than x. Returns NULT if there is none. */\r
+   treeNode TaggedNext(treeNode x, TagType tag);\r
+\r
    /** TaggedPrec(x,tag): returns the first node tagged tag with smaller \r
     * preorder than x and not an ancestor of x. Returns NULLT if there \r
     * is none. */\r