X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=a1eb13c4a188f5d8c83aa6dce1d7fba499ba5737;hb=19534e3089bc0c36bc50e5e522c145e73dcda9cc;hp=fd46677b085db839abc1c75c9dc180a7331c36e8;hpb=b858bc31143609e050e067f1c08a3502be1e13ab;p=SXSI%2FXMLTree.git

diff --git a/XMLTree.cpp b/XMLTree.cpp
index fd46677..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,13 +20,12 @@ static int bits8 (int t ) {
     return 8;
   else if (r <= 16)
     return 16;
-  else 
+  else
     return r;
 }
 
 
 
-
 static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){
 
   if (tag == PCDATA_TAG_ID){
@@ -36,13 +35,11 @@ static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){
 
 }
 
-static bool fast_isleaf(bp* Par,treeNode x){
-  return (fast_inspect(Par,x+1) == CP ? true : false);
-}
+
 
 
 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);
 
@@ -67,11 +64,13 @@ 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)
+		  TextCollection * const TC, bool dis_tc,
+		  TextCollectionBuilder::index_type_t _index_type )
  {
    buffer = 0;
+   print_stack = 0;
     // creates the data structure for the tree topology
     Par = (bp *)umalloc(sizeof(bp));
     STARTTIMER();
@@ -80,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.
@@ -103,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;
 
 
@@ -118,47 +117,41 @@ XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdM
     free(empty_texts_bmp);
     empty_texts_bmp = NULL;
 
-    
+
     disable_tc = dis_tc;
-    stream = NULL;
-    stream_fd = 0;
+    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;
     EBVector = NULL;
-    if (stream != NULL){
-      fclose(stream);
-      stream = NULL;
-      stream_fd = 0;
-    };
 
  }
 
 
-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));
@@ -169,11 +162,10 @@ void XMLTree::print_stats()
          << " *total* " << total_space << endl;
  }
 
-// Save: saves XML tree data structure to file. 
-void XMLTree::Save(int fd, char *filename) 
+// 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");
@@ -186,7 +178,7 @@ void XMLTree::Save(int fd, char *filename)
     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);
@@ -194,22 +186,40 @@ void XMLTree::Save(int fd, char *filename)
     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) {
-        Text->Save(fp, filename);
-    };
- }
 
+      ufwrite(&text_index_type, sizeof(TextCollectionBuilder::index_type_t), 1, fp);
+
+
+      string file(name);
+      switch (text_index_type){
+      case TextCollectionBuilder::index_type_default:
+	file.append(".default");
+	break;
+      case TextCollectionBuilder::index_type_swcsa:
+	file.append(".swcsa");
+	break;
+      case TextCollectionBuilder::index_type_rlcsa:
+	file.append(".rlcsa");
+	break;
+      };
+
+      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, char *filename, bool load_tc,int sample_factor) 
+XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name)
  {
 
     FILE *fp;
@@ -226,7 +236,7 @@ XMLTree *XMLTree::Load(int fd, char *filename, 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();
@@ -235,7 +245,7 @@ XMLTree *XMLTree::Load(int fd, char *filename, 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);
 
@@ -244,10 +254,10 @@ XMLTree *XMLTree::Load(int fd, char *filename, 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);
@@ -256,7 +266,7 @@ XMLTree *XMLTree::Load(int fd, char *filename, 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);
@@ -270,32 +280,46 @@ XMLTree *XMLTree::Load(int fd, char *filename, 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);
-    //XML_Tree->EBVector = static_bitsequence_sdarray::load(fp);
-
-    STOPTIMER(Loading);
-    PRINTTIME("Loading text bitvector struct", Loading);
-    STARTTIMER();
-
-    // Not used  
-    // loads the texts
-    if (!XML_Tree->disable_tc){
-        XML_Tree->Text = TextCollection::Load(fp, filename, TextCollection::index_mode_default, sample_factor);
-    }
-    else XML_Tree->Text = NULL;
-    STOPTIMER(Loading);
-    PRINTTIME("Loading TextCollection", Loading);
-    STARTTIMER(); 
+      XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
+
+      STOPTIMER(Loading);
+      PRINTTIME("Loading text bitvector struct", Loading);
+      STARTTIMER();
+
+      // Not used
+      // loads the texts
+      if (!XML_Tree->disable_tc){
+	ufread(&(XML_Tree->text_index_type),
+	       sizeof(TextCollectionBuilder::index_type_t), 1, fp);
+	string file(name);
+	switch (XML_Tree->text_index_type){
+	case TextCollectionBuilder::index_type_default:
+	  file.append(".default");
+	  break;
+	case TextCollectionBuilder::index_type_swcsa:
+	  file.append(".swcsa");
+	  break;
+	case TextCollectionBuilder::index_type_rlcsa:
+	  file.append(".rlcsa");
+	  break;
+	};
+        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();
     }
     else {
       XML_Tree->EBVector = NULL;
@@ -303,34 +327,34 @@ XMLTree *XMLTree::Load(int fd, char *filename, bool load_tc,int sample_factor)
       XML_Tree->disable_tc = true;
     };
 
-    XML_Tree->stream = NULL;
-    XML_Tree->stream_fd = 0;
-    
+
     return XML_Tree;
  }
 
 
 
 // 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);
@@ -346,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);
@@ -379,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) {
@@ -426,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;
@@ -441,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;
@@ -450,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);
@@ -458,57 +482,57 @@ 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.
-treeNode XMLTree::LastChild(treeNode x)
+   /*treeNode XMLTree::LastChild(treeNode x)
  {
    NULLT_IF(x == NULLT || fast_isleaf(Par,x));
    return find_open(Par, fast_find_close(Par, x)-1);
  }
-
+   */
 // 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;
@@ -517,20 +541,21 @@ treeNode XMLTree::LastChild(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);
  }
-
+*/
 // TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none.
 // 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;
@@ -547,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;
 }
 
 
@@ -581,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));
 
@@ -596,11 +621,11 @@ 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);
  }
 */
-
+/*
 treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)
  {
    NULLT_IF (x ==NULLT || fast_isleaf(Par,x));
@@ -618,12 +643,12 @@ treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)
    return min;
  }
 
-
+*/
 
 // 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);
@@ -637,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
  }
 
 
@@ -645,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 */
@@ -692,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) {
@@ -701,15 +726,15 @@ 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)
  {
 
@@ -723,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) {
@@ -732,15 +757,15 @@ 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;
-   
- }
 
+ }
+*/
 /*
 treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing)
  {
@@ -755,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;
@@ -792,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)
-    //if (EBVector->access(x))
-    return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0
-  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
@@ -835,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);
-    
+
  }
 
 
@@ -861,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);
  }
 
@@ -872,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); }
 
@@ -900,114 +925,105 @@ bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }
 
 
 void XMLTree::Print(int fd,treeNode x, bool no_text){
-  
-  int newfd = dup(fd);
-  stream = fdopen(newfd,"wa");
-  if (stream == 0){
-    perror(NULL);
-    return;
-  };
 
-  if (buffer == 0)
-    buffer = new string();
+  if (buffer == 0) {
+    buffer = new string(BUFFER_ALLOC, 0);
+    buffer->clear();
+    print_stack = new std::vector<string *>();
+    print_stack->reserve(256);
+  };
 
-  FILE* fp = stream;
   treeNode fin = fast_find_close(Par,x);
   treeNode n = x;
   TagType tag = Tag(n);
-  uchar * tagstr;
+
   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)
-  first_idx = first_text;
+    first_idx = first_text;
   else if (first_text == NULLT)
-  first_idx = first_att;
+    first_idx = first_att;
   else
-   first_idx = min(first_att,first_text);
-   
+    first_idx = min(first_att,first_text);
+
    uchar * current_text=NULL;
+
    if (first_idx != NULLT)
-   current_text = GetText(MyText(first_idx));
+     current_text = GetText(MyTextUnsafe(first_idx));
+
    size_t read = 0;
-   std::vector<uchar*> st;
- while (n <= fin){
-   if (fast_inspect(Par,n)){
-     if (tag == PCDATA_TAG_ID  ) {       
-
-       if (no_text)
-	 myfputs("<$/>",fp);
-       else{
-	 read = myfprintf((const char*) current_text, fp);
-	 current_text += (read + 1);
-       };
-       n+=2; // skip closing $
-       tag = Tag(n);
-      
-     }
-     else {
-       myfputc('<',fp);
-       tagstr = (uchar*) GetTagNameByRef(tag);
-       myfputs((const char*) tagstr ,fp);
-       n++;
-       if (fast_inspect(Par,n)) {
-	 st.push_back(tagstr);
+
+   while (n <= fin){
+     if (fast_inspect(Par,n)){
+       if (tag == PCDATA_TAG_ID) {
+
+	 if (no_text)
+	   _dputs("<$/>", fd);
+	 else {
+	   read = _dprintf((const char*) current_text, fd);
+	   current_text += (read + 1);
+	 };
+	 n+=2; // skip closing $
 	 tag = Tag(n);
-	 if (tag == ATTRIBUTE_TAG_ID){
-	   n++;
-	   if (no_text) myfputs("><@@>",fp);
-	   while (fast_inspect(Par,n)){
-	     if (no_text) {
-	       myfputc('<',fp);
-	       myfputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp);
-	       myfputc('>',fp);
-	       myfputs("<$@/></",fp);
-	       myfputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp);
-	       myfputc('>',fp);
-	       n+= 4;
-	     }
-	     else {
-	       myfputc(' ',fp);
-	       myfputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp);
-	       n++;
-	       myfputs("=\"",fp);
-	       read = myfprintf((const char*) current_text,fp);
-	       current_text += (read + 1);
-	       myfputc('"',fp);
-	       n+=3;
-	     }
-	   };
-	   if (no_text) 
-	     myfputs("</@@>",fp);
-	   else myfputc('>',fp);
+
+       } else {
+
+	 _dputc('<',fd);
+	 _dput_str((*TagName)[tag], fd);
+	 n++;
+	 if (fast_inspect(Par,n)) {
+	   print_stack->push_back(&((*TagName)[tag]));
+	   tag = Tag(n);
+	   if (tag == ATTRIBUTE_TAG_ID){
+	     n++;
+	     if (no_text) _dputs("><@@>",fd);
+
+	     while (fast_inspect(Par,n)){
+	       if (no_text) {
+		 _dputc('<', fd);
+		 _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);
+		 _dputc('>', fd);
+		 _dputs("<$@/></", fd);
+		 _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);
+		 _dputc('>', fd);
+		 n+= 4;
+	       } else {
+		 _dputc(' ', fd);
+		 _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);
+		 n++;
+		 _dputs("=\"", fd);
+		 read = _dprintf((const char*) current_text, fd);
+		 current_text += (read + 1);
+		 _dputc('"', fd);
+		 n+=3;
+	       }
+	     };
+	     if (no_text) _dputs("</@@>", fd);
+	     else _dputc('>', fd);
+	     n++;
+	     tag=Tag(n);
+
+	   } else
+	     _dputc('>', fd);
+
+	 } else {// <foo /> tag
+	   _dputs("/>", fd);
 	   n++;
 	   tag=Tag(n);
-	 }
-	 else {
-	   myfputc('>',fp);
 	 };
-       }
-       else {// <foo /> tag
-	 myfputs("/>",fp);
+       };
+     } else do {
+	 _dputs("</", fd);
+	 _dput_str(*(print_stack->back()), fd);
+	 _dputc('>', fd);
+	 print_stack->pop_back();
 	 n++;
-	 tag=Tag(n);	 
-       };     
-     };
-   }
-   else
-     do {
-       myfputs("</",fp);
-       myfputs((const char*)st.back(),fp);
-       myfputc('>', fp);
-       st.pop_back();
-       n++;
-     }while (!fast_inspect(Par,n) && !st.empty());
-   tag=Tag(n);
- };
- myfputc('\n',fp);
- mybufferflush(fp);
- //fflush(fp);
- fclose(fp);
+       } while (!(fast_inspect(Par,n) || print_stack->empty()));
+     tag = Tag(n);
+   };
+   _dputc('\n', fd);
+   //_flush(fd);
 }