From 3c8f8af6704ca98b36b503878058aa0619806dad Mon Sep 17 00:00:00 2001
From: darroyue <darroyue@3cdefd35-fc62-479d-8e8d-bae585ffb9ca>
Date: Fri, 27 Feb 2009 22:04:58 +0000
Subject: [PATCH] Diego: added method TaggedAncestor, renamed former method
 TaggedFoll to TaggedFollowingSibling, added new method TaggedFoll, fixed the
 bug when inserting closing tags

git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@190 3cdefd35-fc62-479d-8e8d-bae585ffb9ca
---
 XMLTree.cpp | 56 +++++++++++++++++++++++++++++++++++++++++++++++------
 XMLTree.h   |  9 ++++++++-
 2 files changed, 58 insertions(+), 7 deletions(-)

diff --git a/XMLTree.cpp b/XMLTree.cpp
index cdfe952..a37263a 100644
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -581,9 +581,30 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag)
     return NULLT; // there is no such node 
  }
 
+
 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in
 // the subtree of x. Returns NULLT if there is none.
-treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) 
+treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
+ {
+    if (!finished) {
+       fprintf(stderr, "Error: data structure has not been constructed properly\n");
+       exit(1);
+    }
+
+    int r, s;
+    if (x ==NULLT || x == Root())
+       return NULLT;
+                   
+    r = (int) Tags->rank(tag, find_close(Par, x));
+    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;
+    else return tagpos2node(s);
+ } 
+
+
+// TaggedFollowingSibling(x,tag): returns the first node tagged tag with larger preorder than x and not in
+// the subtree of x. Returns NULLT if there is none.
+treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) 
  {
     if (!finished) {
        fprintf(stderr, "Error: data structure has not been constructed properly\n");
@@ -591,15 +612,39 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
     }
 
     int r, s;
-    if (x ==NULLT || x == Root()|| (next_sibling(Par,x) == -1 ))
+    treeNode ns = next_sibling(Par,x);
+
+    if (x == NULLT || x == Root() || ns == -1)
       return NULLT;
 
-    r = (int) Tags->rank(tag, node2tagpos(next_sibling(Par, x))-1);
+    r = (int) Tags->rank(tag, node2tagpos(ns)-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;
     else return tagpos2node(s);
  }
 
+
+// TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return
+// NULLT is there is none.
+treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)
+ {
+    if (!finished) {
+       fprintf(stderr, "Error: data structure has not been constructed properly\n");
+       exit(1);
+    }
+    
+    if (x == NULLT || x == Root())
+       return NULLT;
+    
+    treeNode s = parent(Par, x), r = Root();
+    while (s != r) {
+       if (Tags->access(node2tagpos(s)) == tag) return s;
+       s = parent(Par, s);
+    }
+    return NULLT;
+ }
+
+
 // PrevText(x): returns the document identifier of the text to the left 
 // of node x, or NULLT if x is the root node or the text is empty.
 // Assumes Doc ids start from 0.
@@ -890,17 +935,16 @@ int XMLTree::NewClosingTag(unsigned char *tagname)
        parArraySize *= 2;
     }
     
-    setbit(par_aux,npar,CP);  // marks a new closing opening parenthesis
+    setbit(par_aux,npar,CP);  // marks a new closing parenthesis
 
     // transforms the tagname into a tag identifier. If the tag is new, we insert
     // it in the table.
     for (i=0; i<ntagnames; i++)
-       if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break;
+       if ((strcmp((const char *)tagname,(const char *)(TagName[i]+1))==0) && (TagName[i][0]=='/')) break;
  
     if (i==ntagnames) { // the tag is a new one, then we insert it
        TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1));
        
-       
        ntagnames++;
        TagName[i] = (unsigned char *)umalloc(sizeof(char)*(strlen((const char *)tagname)+2));
        TagName[i][0] = '/';
diff --git a/XMLTree.h b/XMLTree.h
index 67ffd6e..d446ab1 100644
--- a/XMLTree.h
+++ b/XMLTree.h
@@ -217,7 +217,14 @@ public:
     * preorder than x and not in the subtree of x. Returns NULLT if there 
     * is none. */
    treeNode TaggedFoll(treeNode x, TagType tag);
-   
+  
+   /** TaggedFollowingSibling(x,tag) */
+   treeNode TaggedFollowingSibling(treeNode x, TagType tag);
+
+   /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged 
+     * tag. Return NULLT is there is none. */
+   treeNode TaggedAncestor(treeNode x, TagType tag);
+ 
    /** PrevText(x): returns the document identifier of the text to the left of 
     * node x, or NULLT if x is the root node. */
    DocID PrevText(treeNode x);
-- 
2.17.1