From dd9992dcd5366f37820c24ed7cddf24ecbc0d549 Mon Sep 17 00:00:00 2001
From: kim <kim@3cdefd35-fc62-479d-8e8d-bae585ffb9ca>
Date: Mon, 16 Feb 2009 00:06:58 +0000
Subject: [PATCH] Added TaggedNext

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@178 3cdefd35-fc62-479d-8e8d-bae585ffb9ca
---
 XMLTree.cpp | 34 +++++++++++++++++++++++++++++++---
 XMLTree.h   |  4 ++++
 2 files changed, 35 insertions(+), 3 deletions(-)

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