X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=a1eb13c4a188f5d8c83aa6dce1d7fba499ba5737;hb=e2c476850d5598f78c8584530563491a7effd632;hp=119048d338bffd07f5bde85216249ef63b473e88;hpb=44dc45dfa812b495fc4ef7dff7f69a6b89ee5128;p=SXSI%2FXMLTree.git

diff --git a/XMLTree.cpp b/XMLTree.cpp
index 119048d..a1eb13c 100644
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -7,8 +7,8 @@ using std::endl;
 using std::min;
 using std::string;
 
-// functions to convert tag positions to the corresponding tree node and viceversa. 
-// These are implemented in order to be able to change the tree and Tags representations, 
+// functions to convert tag positions to the corresponding tree node and viceversa.
+// These are implemented in order to be able to change the tree and Tags representations,
 // without affecting the code so much.
 // Current implementation corresponds to balanced-parentheses representation for
 // the tree, and storing 2 tags per tree node (opening and closing tags).
@@ -20,7 +20,7 @@ static int bits8 (int t ) {
     return 8;
   else if (r <= 16)
     return 16;
-  else 
+  else
     return r;
 }
 
@@ -39,7 +39,7 @@ static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){
 
 
 inline uint get_field_no_power(uint *A, uint len, uint index) {
-  
+
   register uint i=index*len/W, j=index*len-W*i;
   return (j+len <= W) ? (A[i] << (W-j-len)) >> (W-len) : (A[i] >> j) | (A[i+1] << (WW-j-len)) >> (W-len);
 
@@ -64,7 +64,7 @@ static uint fast_get_field(uint* A,int len, int idx)
 
 
 
-XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdMap * const tim, 
+XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdMap * const tim,
 		  uint *empty_texts_bmp, TagType *tags,
 		  TextCollection * const TC, bool dis_tc,
 		  TextCollectionBuilder::index_type_t _index_type )
@@ -79,19 +79,19 @@ XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdM
     PRINTTIME("Building parenthesis struct", Building);
     STARTTIMER();
 
-   
+
     // creates structure for tags
 
     TagName = (vector<string>*)TN;
     tIdMap = (TagIdMap *) tim;
-    
+
     uint max_tag = TN->size() - 1;
-    
-      
+
+
     static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray();
     alphabet_mapper *am = new alphabet_mapper_none();
     Tags = new static_sequence_bs((uint*)tags,npar,am,bmb);
-    
+
     //cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl;
 
     //Ensures that for small tag numbers, we are on an 8bit boundary.
@@ -102,13 +102,13 @@ XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdM
     tags_fix = new uint[uint_len(tags_blen,tags_len)];
     for(uint i=0;i<(uint)npar;i++)
        set_field(tags_fix,tags_blen,i,tags[i]);
-    delete bmb;    
+    delete bmb;
     free(tags);
     tags = NULL;
 
     STOPTIMER(Building);
     PRINTTIME("Building Tag Structure", Building);
-    
+
     Text = (TextCollection*) TC;
 
 
@@ -117,32 +117,32 @@ XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdM
     free(empty_texts_bmp);
     empty_texts_bmp = NULL;
 
-    
+
     disable_tc = dis_tc;
-    text_index_type = _index_type;    
+    text_index_type = _index_type;
     std::cerr << "Number of distinct tags " << TagName->size() << "\n";
     //std::cerr.flush();
  }
 
 
 // ~XMLTree: frees memory of XML tree.
-XMLTree::~XMLTree() 
- { 
+XMLTree::~XMLTree()
+ {
     int i;
 
     destroyTree(Par);
     free(Par); // frees the memory of struct Par
-   
+
     delete tIdMap;
     tIdMap = NULL;
-    
+
     delete TagName;
     TagName = NULL;
-    
+
     delete Tags;
     Tags = NULL;
 
-    delete Text; 
+    delete Text;
     Text = NULL;
 
     delete EBVector;
@@ -151,7 +151,7 @@ XMLTree::~XMLTree()
  }
 
 
-void XMLTree::print_stats() 
+void XMLTree::print_stats()
  {
     uint total_space = Tags->size()+sizeof(static_sequence*);
     total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len));
@@ -162,11 +162,10 @@ void XMLTree::print_stats()
          << " *total* " << total_space << endl;
  }
 
-// Save: saves XML tree data structure to file. 
-void XMLTree::Save(int fd) 
+// Save: saves XML tree data structure to file.
+void XMLTree::Save(int fd, char * name)
  {
     FILE *fp;
-    char filenameaux[1024];
     int i;
 
     fp = fdopen(fd, "wa");
@@ -179,7 +178,7 @@ void XMLTree::Save(int fd)
     ufwrite(&ntags, sizeof(int), 1, fp);
     for (i = 0; i<ntags;i++)
       fprintf(fp, "%s\n",TagName->at(i).c_str());
-    
+
 
     // stores the tags
     Tags->save(fp);
@@ -187,39 +186,40 @@ void XMLTree::Save(int fd)
     ufwrite(&tags_len,sizeof(uint),1,fp);
     ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp);
 
-    // flags 
+    // flags
     ufwrite(&disable_tc, sizeof(bool),1,fp);
-    
+
     //text positions
     EBVector->save(fp);
-    
-    // stores the texts   
+
+    // stores the texts
     if (!disable_tc) {
 
       ufwrite(&text_index_type, sizeof(TextCollectionBuilder::index_type_t), 1, fp);
-     
-      const char * pref;
+
+
+      string file(name);
       switch (text_index_type){
       case TextCollectionBuilder::index_type_default:
-	pref = "default_";
+	file.append(".default");
 	break;
       case TextCollectionBuilder::index_type_swcsa:
-	pref = "swcsa_";
+	file.append(".swcsa");
 	break;
       case TextCollectionBuilder::index_type_rlcsa:
-	pref = "rlcsa_";
+	file.append(".rlcsa");
 	break;
       };
-      
-      Text->Save(fp, pref);
-	   
+
+      Text->Save(fp, file.c_str());
+
 
     }
  }
 
 // Load: loads XML tree data structure from file. Returns
 // a pointer to the loaded data structure
-XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) 
+XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name)
  {
 
     FILE *fp;
@@ -236,7 +236,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor)
     // Load the tree structure
     XML_Tree->Par = (bp *)umalloc(sizeof(bp));
 
-    loadTree(XML_Tree->Par, fp); 
+    loadTree(XML_Tree->Par, fp);
     STOPTIMER(Loading);
     PRINTTIME("Loading parenthesis struct", Loading);
     STARTTIMER();
@@ -245,7 +245,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor)
     XML_Tree->tIdMap = new std::unordered_map<std::string,int>();
     std::string s;
     int ntags;
-    
+
     // Load the tag names
     ufread(&ntags, sizeof(int), 1, fp);
 
@@ -254,10 +254,10 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor)
 	 throw "Cannot read tag list";
        s = buffer;
        // remove the trailing \n
-       s.erase(s.size()-1);       
-       XML_Tree->TagName->push_back(s);       
+       s.erase(s.size()-1);
+       XML_Tree->TagName->push_back(s);
        XML_Tree->tIdMap->insert(std::make_pair(s,i));
-       
+
     };
     STOPTIMER(Loading);
     PRINTTIME("Loading tag names struct", Loading);
@@ -266,7 +266,7 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor)
     // loads the tag structure
     XML_Tree->Tags = static_sequence::load(fp);
     ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);
-    std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n";    
+    std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n";
     ufread(&XML_Tree->tags_len,sizeof(uint),1,fp);
     XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)];
     ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp);
@@ -280,14 +280,14 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor)
     //XML_Tree->Tags->test(seq,XML_Tree->tags_len);
     //delete [] seq;
     /// End ugly tests
-    
+
     STOPTIMER(Loading);
     std::cerr << (uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/(1024*1024) << " MB for tag sequence" << std::endl;
     PRINTTIME("Loading tag struct", Loading);
     STARTTIMER();
 
     // loads the flags
-    
+
     ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);
     if (load_tc) {
       XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
@@ -295,38 +295,38 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor)
       STOPTIMER(Loading);
       PRINTTIME("Loading text bitvector struct", Loading);
       STARTTIMER();
-      
-      // Not used  
+
+      // Not used
       // loads the texts
       if (!XML_Tree->disable_tc){
 	ufread(&(XML_Tree->text_index_type),
 	       sizeof(TextCollectionBuilder::index_type_t), 1, fp);
-	const char * pref;
-	switch (!XML_Tree->text_index_type){
+	string file(name);
+	switch (XML_Tree->text_index_type){
 	case TextCollectionBuilder::index_type_default:
-	  pref = "default_";
+	  file.append(".default");
 	  break;
 	case TextCollectionBuilder::index_type_swcsa:
-	  pref = "swcsa_";
+	  file.append(".swcsa");
 	  break;
 	case TextCollectionBuilder::index_type_rlcsa:
-	  pref = "rlcsa_";
+	  file.append(".rlcsa");
 	  break;
-	};	
-        XML_Tree->Text = TextCollection::Load(fp, pref, TextCollection::index_mode_default, sample_factor);
+	};
+        XML_Tree->Text = TextCollection::Load(fp, file.c_str(), TextCollection::index_mode_default, sample_factor);
 
       }
       else XML_Tree->Text = NULL;
       STOPTIMER(Loading);
       PRINTTIME("Loading TextCollection", Loading);
-      STARTTIMER(); 
+      STARTTIMER();
     }
     else {
       XML_Tree->EBVector = NULL;
       XML_Tree->Text = NULL;
       XML_Tree->disable_tc = true;
     };
-    
+
 
     return XML_Tree;
  }
@@ -334,27 +334,27 @@ XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor)
 
 
 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.
-/*int XMLTree::SubtreeSize(treeNode x) 
+/*int XMLTree::SubtreeSize(treeNode x)
  {
     return subtree_size(Par, x);
  }
 */
 // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.
 /*
-int XMLTree::SubtreeTags(treeNode x, TagType tag) 
+int XMLTree::SubtreeTags(treeNode x, TagType tag)
  {
     if (x == Root())
       x = fast_first_child(Par,x);
-    
+
 
     int s = x + 2*subtree_size(Par, x) - 1;
- 
+
     return (Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1))+1;
  }
 */
-int XMLTree::SubtreeElements(treeNode x) 
+int XMLTree::SubtreeElements(treeNode x)
  {
-    
+
     int size = subtree_size(Par,x);
     if (x == Root()){
       x = fast_first_child(Par,x);
@@ -370,25 +370,25 @@ int XMLTree::SubtreeElements(treeNode x)
       size -= SubtreeSize(y);
       y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y));
     };
-    return size;    
+    return size;
  }
 
 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation
 // this is just a bit inspection.
-bool XMLTree::IsLeaf(treeNode x) 
+bool XMLTree::IsLeaf(treeNode x)
  {
    NULLT_IF(x==NULLT);
    return fast_isleaf(Par, x);
- } 
+ }
 
 // IsAncestor(x,y): returns whether node x is ancestor of node y.
-bool XMLTree::IsAncestor(treeNode x, treeNode y) 
+bool XMLTree::IsAncestor(treeNode x, treeNode y)
  {
     return fast_is_ancestor(Par, x, y);
  }
 
 // IsChild(x,y): returns whether node x is parent of node y.
-bool XMLTree::IsChild(treeNode x, treeNode y) 
+bool XMLTree::IsChild(treeNode x, treeNode y)
  {
     if (!fast_is_ancestor(Par, x, y)) return false;
     return depth(Par, x) == (depth(Par, y) + 1);
@@ -403,46 +403,46 @@ bool XMLTree::IsChild(treeNode x, treeNode y)
 
 // NumChildren(x): number of children of node x. Constant time with the data structure
 // of Sadakane.
-int XMLTree::NumChildren(treeNode x) 
+int XMLTree::NumChildren(treeNode x)
  {
     return degree(Par, x);
  }
 
 // ChildNumber(x): returns i if node x is the i-th children of its parent.
-int XMLTree::ChildNumber(treeNode x) 
+int XMLTree::ChildNumber(treeNode x)
  {
     return child_rank(Par, x);
  }
 
 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.
-int XMLTree::Depth(treeNode x) 
+int XMLTree::Depth(treeNode x)
  {
     return depth(Par, x);
  }
 
 // Preorder(x): returns the preorder number of node x, just counting the tree
 // nodes (i.e., tags, it disregards the texts in the tree).
-int XMLTree::Preorder(treeNode x) 
+int XMLTree::Preorder(treeNode x)
  {
     return preorder_rank(Par, x);
  }
 
 // Postorder(x): returns the postorder number of node x, just counting the tree
 // nodes (i.e., tags, it disregards the texts in the tree).
-int XMLTree::Postorder(treeNode x) 
+int XMLTree::Postorder(treeNode x)
  {
     return postorder_rank(Par, x);
  }
 /*
 // Tag(x): returns the tag identifier of node x.
-TagType XMLTree::Tag(treeNode x) 
+TagType XMLTree::Tag(treeNode x)
  {
     return fast_get_field(tags_fix,tags_blen,node2tagpos(x));
  }
 */
 // DocIds(x): returns the range of text identifiers that descend from node x.
 // returns {NULLT, NULLT} when there are no texts descending from x.
-range XMLTree::DocIds(treeNode x) 
+range XMLTree::DocIds(treeNode x)
  {
    range r;
    if (x == NULLT) {
@@ -450,8 +450,8 @@ range XMLTree::DocIds(treeNode x)
      r.max = NULLT;
      return r;
    };
-   int min = EBVector->rank1(x-1);                          
-   int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); 
+   int min = EBVector->rank1(x-1);
+   int max = EBVector->rank1(x+2*subtree_size(Par, x)-2);
    if (min==max) { // range is empty, no texts within the subtree of x
      r.min = NULLT;
      r.max = NULLT;
@@ -465,7 +465,7 @@ range XMLTree::DocIds(treeNode x)
 
 // Parent(x): returns the parent node of node x.
 /*
-treeNode XMLTree::Parent(treeNode x) 
+treeNode XMLTree::Parent(treeNode x)
  {
     if (x == Root())
       return NULLT;
@@ -474,7 +474,7 @@ treeNode XMLTree::Parent(treeNode x)
  }*/
 
 // Child(x,i): returns the i-th child of node x, assuming it exists.
-treeNode XMLTree::Child(treeNode x, int i) 
+treeNode XMLTree::Child(treeNode x, int i)
 {
     if (i <= OPTD) return naive_child(Par, x, i);
     else return child(Par, x, i);
@@ -482,46 +482,46 @@ treeNode XMLTree::Child(treeNode x, int i)
 
 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.
 /*
-treeNode XMLTree::FirstChild(treeNode x) 
+treeNode XMLTree::FirstChild(treeNode x)
  {
    NULLT_IF(x==NULLT);
    return fast_first_child(Par, x);
  }
 */
 /*
-treeNode XMLTree::FirstElement(treeNode x) 
+treeNode XMLTree::FirstElement(treeNode x)
  {
    NULLT_IF(x==NULLT);
    x = fast_first_child(Par, x);
    NULLT_IF(x == NULLT);
    switch (Tag(x)){
-  
+
    case PCDATA_TAG_ID:
      x = x+2;
      return (fast_inspect(Par,x)==OP)? x : NULLT;
-     
-   case ATTRIBUTE_TAG_ID:  
+
+   case ATTRIBUTE_TAG_ID:
      x = fast_next_sibling(Par,x);
      if (x != NULLT && Tag(x) == PCDATA_TAG_ID){
        x = x+2;
        return (fast_inspect(Par,x)==OP)? x : NULLT;
-     } 
-     else return x;     
+     }
+     else return x;
    default:
      return x;
    }
  }
 *//*
-treeNode XMLTree::NextElement(treeNode x) 
+treeNode XMLTree::NextElement(treeNode x)
 {
   NULLT_IF(x==NULLT);
   x = fast_next_sibling(Par, x);
-  NULLT_IF(x == NULLT);   
+  NULLT_IF(x == NULLT);
   if (Tag(x) == PCDATA_TAG_ID){
     x = x+2;
      return (fast_inspect(Par,x)==OP)? x : NULLT;
   }
-  else return x;  
+  else return x;
   }*/
 
 // LastChild(x): returns the last child of node x.
@@ -532,7 +532,7 @@ treeNode XMLTree::NextElement(treeNode x)
  }
    */
 // NextSibling(x): returns the next sibling of node x, assuming it exists.
-/*treeNode XMLTree::NextSibling(treeNode x) 
+/*treeNode XMLTree::NextSibling(treeNode x)
  {
    NULLT_IF(x==NULLT || x == Root() );
    x = fast_find_close(Par,x)+1;
@@ -541,7 +541,7 @@ treeNode XMLTree::NextElement(treeNode x)
 */
 
 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.
-/*treeNode XMLTree::PrevSibling(treeNode x) 
+/*treeNode XMLTree::PrevSibling(treeNode x)
  {
    NULLT_IF(x==NULLT);
    return prev_sibling(Par, x);
@@ -551,11 +551,11 @@ treeNode XMLTree::NextElement(treeNode x)
 // Because of the balanced-parentheses representation of the tree, this operation is not supported
 // efficiently, just iterating among the children of node x until finding the desired child.
 /*
-treeNode XMLTree::TaggedChild(treeNode x, TagType tag) 
+treeNode XMLTree::TaggedChild(treeNode x, TagType tag)
  {
-   
+
    NULLT_IF(x==NULLT || fast_isleaf(Par,x));
-   treeNode child;   
+   treeNode child;
    child = fast_first_child(Par, x); // starts at first child of node x
    if (Tag(child) == tag)
      return child;
@@ -572,25 +572,25 @@ treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)
   while (sibling != NULLT) {
     ctag = Tag(sibling);
     if (ctag == tag) // current sibling is labeled with tag of interest
-      return sibling; 
+      return sibling;
     sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling
   }
-  return NULLT; // no such sibling was found   
+  return NULLT; // no such sibling was found
 }
 */
 treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags)
 {
-  
+
   NULLT_IF(x==NULLT || fast_isleaf(Par,x));
   int i;
-  treeNode child = fast_first_child(Par, x);  
+  treeNode child = fast_first_child(Par, x);
   TagType t;
   while (child != NULLT) {
     t = Tag(child);
     if (tags->find(t) != tags->end()) return child;
     child = fast_sibling(Par, child,t);
   }
-  return NULLT;  
+  return NULLT;
 }
 
 
@@ -606,14 +606,14 @@ treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)
      if (tags->find(t) != tags->end()) return sibling;
      sibling = fast_sibling(Par, sibling,t);
    }
-   return NULLT;    
+   return NULLT;
  }
 
 
 // TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within
 // the subtree of x. Returns NULLT if there is none.
 /*
-treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) 
+treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag)
  {
    //NULLT_IF(x==NULLT || fast_isleaf(Par,x));
 
@@ -621,7 +621,7 @@ treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag)
    NULLT_IF (s == -1);
 
    treeNode y = tagpos2node(s); // transforms the tag position into a node position
-   
+
    return (fast_is_ancestor(Par,x,y) ? y : NULLT);
  }
 */
@@ -647,8 +647,8 @@ treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)
 
 // 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::TaggedPreceding(treeNode x, TagType tag) 
- {    
+treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)
+ {
     int r, s;
     treeNode node_s, root;
     r = (int)Tags->rank(tag, node2tagpos(x)-1);
@@ -662,7 +662,7 @@ treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)
        s = (int)Tags->select(tag, r);  // we should use select_prev instead when provided
        node_s = tagpos2node(s);
     }
-    return NULLT; // there is no such node 
+    return NULLT; // there is no such node
  }
 
 
@@ -670,37 +670,37 @@ treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)
 // the subtree of x. Returns NULLT if there is none.
 treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)
  {
-   NULLT_IF (x ==NULLT || x == Root());   
+   NULLT_IF (x ==NULLT || x == Root());
    return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x)));
 
- } 
+ }
 
-// TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x 
+// TaggedFollBelow(x,tag,root): 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::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)
 {
-  // NULLT_IF (x == NULLT || x == Root() || x == ancestor); 
+  // NULLT_IF (x == NULLT || x == Root() || x == ancestor);
 
   //Special optimisation, test for the following sibling first
   treeNode close = fast_find_close(Par, x);
   treeNode s = tagpos2node(Tags->select_next(tag, close));
-  
+
   if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s;
   else return NULLT;
-} 
+}
 */
  /*
 treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing)
 {
 
   NULLT_IF (x == NULLT || x == Root());
-  
-  treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x)));  
+
+  treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x)));
   NULLT_IF (s == NULLT || s >= closing);
-  
+
   return s;
-} 
+}
  */
 /* Here we inline TaggedFoll to find the min globally, and only at the end
    we check if the min is below the context node */
@@ -717,7 +717,7 @@ treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ance
    int i;
    treeNode min = NULLT;
    treeNode aux;
-  
+
 
    TagIdSet::const_iterator tagit;
    for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {
@@ -726,13 +726,13 @@ treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ance
      if (aux == NULLT) continue;
      if ((min == NULLT) || (aux < min)) min = aux;
    };
-     
+
    // found the smallest node in preorder which is after x.
    // if ctx is the root node, just return what we found.
 
    if (ancestor == Root() || min == NULLT || min < fast_find_close(Par, ancestor)) return min;
    else return NULLT;
-   
+
  }
 /*
 treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode ancestor_closing)
@@ -748,7 +748,7 @@ treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode anc
    int i;
    treeNode min = NULLT;
    treeNode aux;
-  
+
 
    TagIdSet::const_iterator tagit;
    for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {
@@ -757,13 +757,13 @@ treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode anc
      if (aux == NULLT) continue;
      if ((min == NULLT) || (aux < min)) min = aux;
    };
-     
+
    // found the smallest node in preorder which is after x.
    // if ctx is the root node, just return what we found.
 
    if (ancestor_closing == Root() || min == NULLT || min < ancestor_closing) return min;
    else return NULLT;
-   
+
  }
 */
 /*
@@ -780,33 +780,33 @@ treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode clo
    for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
 
      aux = tagpos2node(Tags->select_next(*tagit, close));
-     
+
      // The next sibling of x is guaranteed to be below ctx
      // and is the node with lowest preorder which is after ctx.
      // if we find it, we return early;
-     
+
      if (aux == ns ) return ns;
      if (aux == NULLT) continue;
      if ((min == NULLT) || (aux < min)) min = aux;
    };
-     
+
    // found the smallest node in preorder which is after x.
    // if ctx is the root node, just return what we found.
 
    NULLT_IF (min == NULLT || min >= closing);
-   
+
    return min;
-   
+
  }
 */
 
 // 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 (x == NULLT || x == Root())
        return NULLT;
-    
+
     treeNode s = parent(Par, x), r = Root();
     while (s != r) {
       if (Tag(s) == tag) return s;
@@ -817,42 +817,42 @@ treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)
 
 
 
-// MyText(x): returns the document identifier of the text below node x, 
-// or NULLT if x is not a leaf node or the text is empty. Assumes Doc 
+// MyText(x): returns the document identifier of the text below node x,
+// or NULLT if x is not a leaf node or the text is empty. Assumes Doc
 // ids start from 0.
-DocID XMLTree::MyText(treeNode x) 
+DocID XMLTree::MyText(treeNode x)
 {
   TagType tag = Tag(x);
   // seems faster than testing EBVector->access(x);
 
   if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID)
-    return (DocID) (EBVector->rank1(x)-1);  
-  else   
+    return (DocID) (EBVector->rank1(x)-1);
+  else
     return (DocID) NULLT;
-    
+
 }
-// MyText(x): returns the document identifier of the text below node x, 
-// or NULLT if x is not a leaf node or the text is empty. Assumes Doc 
+// MyText(x): returns the document identifier of the text below node x,
+// or NULLT if x is not a leaf node or the text is empty. Assumes Doc
 // ids start from 0.
-DocID XMLTree::MyTextUnsafe(treeNode x) 
+DocID XMLTree::MyTextUnsafe(treeNode x)
 {
   return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0
-  
+
 }
 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of
 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.
-int XMLTree::TextXMLId(DocID d) 
+int XMLTree::TextXMLId(DocID d)
  {
    NULLT_IF(d == NULLT);
      int s = EBVector->select1(d+1);
    return rank_open(Par, s) + d + 1; // +1 because root has preorder 1
-   
+
  }
 
-// NodeXMLId(x): returns the preorder of node x in the tree consisting 
+// NodeXMLId(x): returns the preorder of node x in the tree consisting
 // of all tree nodes and all text nodes. Assumes that the tree root has
 // preorder 0;
-int XMLTree::NodeXMLId(treeNode x) 
+int XMLTree::NodeXMLId(treeNode x)
  {
    NULLT_IF(x == NULLT);
    if (x == Root()) return 1; // root node has preorder 1
@@ -860,21 +860,21 @@ int XMLTree::NodeXMLId(treeNode x)
  }
 
 // ParentNode(d): returns the parent node of document identifier d.
-treeNode XMLTree::ParentNode(DocID d) 
- {    
-   NULLT_IF (d == NULLT);   
-   return (treeNode) EBVector->select1(d+1);     
+treeNode XMLTree::ParentNode(DocID d)
+ {
+   NULLT_IF (d == NULLT);
+   return (treeNode) EBVector->select1(d+1);
  }
 
 // GetTagId: returns the tag identifier corresponding to a given tag name.
 // Returns NULLT in case that the tag name does not exists.
 TagType XMLTree::GetTagId(unsigned char *tagname)
  {
-  
+
    string s = (char *) tagname;
-   TagIdMapIT it = tIdMap->find(s);    
+   TagIdMapIT it = tIdMap->find(s);
    return (TagType) ((it != tIdMap->end()) ? it->second : -1);
-    
+
  }
 
 
@@ -886,7 +886,7 @@ unsigned char *XMLTree::GetTagName(TagType tagid)
     if ( tagid < 0 || tagid >= TagName->size())
       return (unsigned char *) "<INVALID TAG>";
     strcpy((char *)s, (*TagName)[tagid].c_str());
-    
+
     return (s == NULL ? (unsigned char*) "<INVALID TAG>" : s);
  }
 
@@ -897,27 +897,27 @@ const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)
    unsigned char *s;
    if ( tagid < 0 || tagid >= TagName->size())
      return (unsigned char *) "<INVALID TAG>";
-   
+
    return (const unsigned char *) (*TagName)[tagid].c_str();
-   
+
  }
 
 
 
 TagType XMLTree::RegisterTag(unsigned char *tagname)
- {  
+ {
     TagType id = XMLTree::GetTagId(tagname);
     if (id == NULLT) {
-      string s = (char *) tagname;      
-      REGISTER_TAG(TagName,tIdMap,s);      
+      string s = (char *) tagname;
+      REGISTER_TAG(TagName,tIdMap,s);
     };
-    
+
     return id;
  }
 
 
 treeNode XMLTree::Closing(treeNode x) {
-  return fast_find_close(Par,x); 
+  return fast_find_close(Par,x);
 }
 bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }
 
@@ -925,8 +925,8 @@ bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }
 
 
 void XMLTree::Print(int fd,treeNode x, bool no_text){
-  
-  if (buffer == 0) { 
+
+  if (buffer == 0) {
     buffer = new string(BUFFER_ALLOC, 0);
     buffer->clear();
     print_stack = new std::vector<string *>();
@@ -936,30 +936,30 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){
   treeNode fin = fast_find_close(Par,x);
   treeNode n = x;
   TagType tag = Tag(n);
-  
+
   range r = DocIds(x);
   treeNode first_idx;
   treeNode first_text = (tag == PCDATA_TAG_ID ?  x : ParentNode(r.min-1));
   treeNode first_att =  NULLT;
-  
-  if (first_att  == NULLT) 
+
+  if (first_att  == NULLT)
     first_idx = first_text;
   else if (first_text == NULLT)
     first_idx = first_att;
   else
     first_idx = min(first_att,first_text);
-   
+
    uchar * current_text=NULL;
 
    if (first_idx != NULLT)
      current_text = GetText(MyTextUnsafe(first_idx));
-  
+
    size_t read = 0;
 
    while (n <= fin){
      if (fast_inspect(Par,n)){
-       if (tag == PCDATA_TAG_ID) {       
-	 
+       if (tag == PCDATA_TAG_ID) {
+
 	 if (no_text)
 	   _dputs("<$/>", fd);
 	 else {
@@ -968,10 +968,10 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){
 	 };
 	 n+=2; // skip closing $
 	 tag = Tag(n);
-	 
+
        } else {
 
-	 _dputc('<',fd);	 
+	 _dputc('<',fd);
 	 _dput_str((*TagName)[tag], fd);
 	 n++;
 	 if (fast_inspect(Par,n)) {
@@ -1005,15 +1005,15 @@ void XMLTree::Print(int fd,treeNode x, bool no_text){
 	     else _dputc('>', fd);
 	     n++;
 	     tag=Tag(n);
-	   
-	   } else 
+
+	   } else
 	     _dputc('>', fd);
-	   
+
 	 } else {// <foo /> tag
 	   _dputs("/>", fd);
 	   n++;
-	   tag=Tag(n);	 
-	 };     
+	   tag=Tag(n);
+	 };
        };
      } else do {
 	 _dputs("</", fd);