X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=8dcdaec6904f8e017e064e912fa129ced60a8b57;hb=c1865639eb1a804ff9363035a2a656b64fd98b9e;hp=6fee8f4673d8a825a107e310d7e34c0de1d0ab79;hpb=82b89c86269e04916a4aef964977ee738d8f2927;p=SXSI%2FXMLTree.git

diff --git a/XMLTree.cpp b/XMLTree.cpp
index 6fee8f4..8dcdaec 100644
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -427,6 +427,14 @@ range XMLTree::DocIds(treeNode x)
     }
 
     range r;
+    if (x == NULLT)
+      {
+	r.min = NULLT;
+	r.max = NULLT;
+	return r;
+      };
+        
+      
     if (indexing_empty_texts) { // faster, no rank needed
        r.min = x;
        r.max = x+2*subtree_size(Par, x)-2;
@@ -489,9 +497,9 @@ treeNode XMLTree::NextSibling(treeNode x)
        fprintf(stderr, "Error: data structure has not been constructed properly\n");
        exit(1);
     }
-    if (x == Root())
+    if (x == Root() || x==NULLT)
       return NULLT;
- 
+    
     return next_sibling(Par, x);
  }
 
@@ -552,25 +560,151 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag)
     else return y;
  }
 
+treeNode XMLTree::TaggedDescOnly(treeNode x,TagType *desctags, unsigned int dtlen)
+{
+
+  treeNode res,y;
+  if (isleaf(Par,x))
+    return NULLT;
+  
+  res=NULLT;
+  for (unsigned int i = 0; i < dtlen; i ++ )
+    {
+      y = TaggedDesc(x,desctags[i]);
+      res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;
+      
+    };
+  
+  return res;
+  
+}
+
+
+treeNode XMLTree::TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen,
+			      TagType *desctags, unsigned int dtlen)
+{
+  treeNode fs,y,res;
+  TagType tag;
+
+  if (isleaf(Par,x))
+    return NULLT;
+  
+  res = NULLT;
+  fs = first_child(Par,x);
+  while (fs != NULLT) {
+    tag = get_field(tags_fix,tags_blen,node2tagpos(fs));
+        
+    /* Check for first_child */
+    for (unsigned int i = 0; i < ctlen; i++) {
+      if (childtags[i] == tag)
+	return fs;
+    };
+    
+    for (unsigned int i = 0; i < dtlen; i++)
+      if (desctags[i] == tag)
+	return fs;  
+    
+    /* check in the descendants */
+    res = NULLT;
+    for (unsigned int i = 0; i < dtlen; i ++ ){
+      /* maybe inline by hand */
+      y = TaggedDesc(fs,desctags[i]);
+      res = (res==NULLT || (y != NULLT) &&(y < res)) ? y : res;   
+    };
+    if (res != NULLT)
+      return res;
+    
+    fs = next_sibling(Par,fs);
+  };
+  return res;
+    
+}
+treeNode XMLTree::TaggedFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root)
+{
+
+  treeNode res,y,lim;
+  lim = find_close(Par,root);   
+  res=NULLT;
+  for (unsigned int i = 0; i < ftlen; i ++ )
+    {
+      y = TaggedFoll(x,folltags[i]);
+      res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;
+      
+    };
+  
+  return res < lim ? res : NULLT;
+  
+}
+
+treeNode XMLTree::TaggedDescOrFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root)
+{
+
+  treeNode res,y,lim;
+  int r,s;
+  lim = find_close(Par,root);   
+  res=NULLT;
+  for (unsigned int i = 0; i < ftlen; i ++ )
+    {
+
+      r = (int) Tags->rank(folltags[i], node2tagpos(x));
+      s = (int) Tags->select(folltags[i], r+1);
+      if (s == -1) 
+	y = NULLT; // there is no such node
+      else {
+	y = tagpos2node(s); 
+	if (y >= lim)
+	  y = NULLT;
+      };
+      res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;
+      
+    };
+  
+  return res < lim ? res : NULLT;
+  
+}
+
+
 // 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) 
+treeNode XMLTree::TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen,
+			     TagType *folltags, unsigned int flen,treeNode root)
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
+   treeNode y,old_y,lim,res;
+   TagType tag;
+   if (x == NULLT || x == Root())
+     return NULLT;
 
-    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);
+   lim = find_close(Par,root);   
+
+   res = NULLT;
+  
+   y = next_sibling(Par,x);
+   while (y != NULLT) {
+     tag = get_field(tags_fix,tags_blen,node2tagpos(y));
+     for(unsigned int i = 0; i < ctlen;i++)
+       if (childtags[i] == tag)
+	 return y;
+     
+     for(unsigned int i = 0; i < flen;i++)
+       if (folltags[i] == tag)
+	 return y;
+
+     res = TaggedBelow(y,NULL,0,folltags,flen);
+     if (res != NULLT)
+       return res;
+     
+     y = next_sibling(Par,y);
+   };
+   //Found nothing in the following sibling of x.
+   res = NULLT;
+   for(unsigned int i = 0; i < flen;i++){
+     y = TaggedFoll(x,folltags[i]);
+     res = (y!= x && (res == NULLT || (y != NULLT && y < res)))? y : res;
+   };
+  
+   return res < lim ? res : NULLT;
+   
  }
 
 
@@ -619,6 +753,24 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
     else return tagpos2node(s);
  } 
 
+// 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::TaggedFollBelow(treeNode x, TagType tag, treeNode root)
+ {
+
+    int r, s;
+    int lim = node2tagpos(find_close(Par,root));
+    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 || s >= lim) 
+      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.
@@ -786,6 +938,29 @@ treeNode XMLTree::ParentNode(DocID d)
        return (treeNode)s;
      
  }
+treeNode XMLTree::PrevNode(DocID d) 
+ {
+    if (!finished) {
+       fprintf(stderr, "Error: data structure has not been constructed properly\n");
+       exit(1);
+    }
+    
+    if (d == NULLT)
+      return NULLT;
+    
+    int s;
+    
+    if (indexing_empty_texts) s = d;
+    else s = EBVector->select1(d+1);
+    if (s == -1)
+      return NULLT;
+    
+    if (inspect(Par,s) == CP) // is a closing parenthesis
+      return find_open(Par, s);
+    else // is an opening parenthesis
+      return NULLT;
+    
+ }
 
 
 // OpenDocument(empty_texts): it starts the construction of the data structure for
@@ -862,18 +1037,21 @@ int XMLTree::CloseDocument()
 
     // If we found an attribute then "<@>" is present in the tree
     // if we didn't then it is not. "<$>" is never present in the tree
+		uint max_tag = 0;
+		for(uint i=0;i<(uint)npar-1;i++)
+			max_tag = max(max_tag,tags_aux[i]);
+		max_tag++;
     int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2;
+		tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1));
+		tags_aux[npar++] = max_tag;
 
 		static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20);
 		alphabet_mapper *am = new alphabet_mapper_none();
-		wt_coder * wc = new wt_coder_huff((uint*)tags_aux,npar-1,am);
-		Tags = new static_sequence_wvtree((uint*)tags_aux,npar-1,wc ,bmb, am);
+		wt_coder * wc = new wt_coder_huff((uint*)tags_aux,npar,am);
+		Tags = new static_sequence_wvtree((uint*)tags_aux,npar,wc ,bmb, am);
     //Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,ntagsize, bmb, ssb);
-		uint max_tag = 0;
-		for(uint i=0;i<(uint)npar-1;i++)
-			max_tag = max(max_tag,tags_aux[i]);
 		tags_blen = bits(max_tag);
-		tags_len = (uint)npar-1;
+		tags_len = (uint)npar;
 		tags_fix = new uint[uint_len(tags_blen,tags_len)];
 		for(uint i=0;i<(uint)npar-1;i++)
 			set_field(tags_fix,tags_blen,i,tags_aux[i]);
@@ -1061,7 +1239,7 @@ TagType XMLTree::GetTagId(unsigned char *tagname)
     // this should be changed for more efficient processing
     for (i=0; i<ntagnames; i++)
        if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break; 
-    if (i==ntagnames) return (TagType)NULLT; // tagname does not exists in the table
+    if (i==ntagnames) return ntagnames; //(TagType)NULLT; // tagname does not exists in the table
     else return i;
  }