X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=06aaba0517bf1128628a685fcaa49dc2e9ff6c31;hb=9bb139eb78d143264e4d4dc6b3f9f1be3874ec6e;hp=fe01896d4ca75c93ffdf83121b9d0ba1a42efca0;hpb=add1a8a0b8a7ca05bb099ec38a60f3c52b9dfd71;p=SXSI%2FXMLTree.git

diff --git a/XMLTree.cpp b/XMLTree.cpp
index fe01896..06aaba0 100644
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -1,5 +1,9 @@
+#include "basics.h"
+//#include <cstring>
+#include <stack>
 #include "XMLTree.h"
-#include <cstring>
+#include "timings.h"
+
 // 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.
@@ -7,108 +11,154 @@
 // the tree, and storing 2 tags per tree node (opening and closing tags).
 
 // tag position -> tree node
-inline treeNode tagpos2node(int t) {
-   return (treeNode)t;
+static treeNode tagpos2node(int t) 
+ {
+    return (treeNode) t;
+ }
+
+static int bits8 (int t ) {
+  int r = bits(t);
+  if (r <= 8)
+    return 8;
+  else if (r <= 16)
+    return 16;
+  else 
+    return r;
 }
 
 // tree node -> tag position
-inline int node2tagpos(treeNode x) {
-   return (int)x;
+static int node2tagpos(treeNode x) 
+{
+  return (int)x;
 }
 
-// Save: saves XML tree data structure to file. 
-void XMLTree::Save(unsigned char *filename) 
- {
+static int fast_find_close(bp *b,int s)
+{
+  return fwd_excess(b,s,-1);
+}
 
-    FILE *fp;
-    char filenameaux[1024];
-    int i;
-   
-    sprintf(filenameaux, "%s.srx", filename);
-    fp = fopen(filenameaux, "w");
-    if (fp == NULL) {
-       printf("Error: cannot create file %s to store the tree structure of XML collection\n", filenameaux);
-       exit(1);
-    } 
-    
-    // first stores the tree topology
-    saveTree(Par, fp);
- 
-    // stores the table with tag names
-    fwrite(&ntagnames, sizeof(int), 1, fp);
-    for (i=0; i<ntagnames;i++)
-       fprintf(fp, "%s\n",TagName[i]);
-    
-    // stores the flags
-    fwrite(&indexing_empty_texts, sizeof(bool), 1, fp);
-    fwrite(&initialized, sizeof(bool), 1, fp);
-    fwrite(&finished, sizeof(bool), 1, fp);
-    
-    if (!indexing_empty_texts) EBVector->save(fp);
-    
-    // stores the tags
-    Tags->save(fp);
+static int fast_inspect(bp* Par,treeNode i)
+{
+  int j,l;
+  j = i >> logD;
+  l = i & (D-1);
+  return (Par->B[j] >> (D-1-l)) & 1;
+}
 
-    // stores the texts   
-    Text->Save(fp);
+static treeNode fast_first_child(bp *Par, treeNode x)
+{
+  x = x+1;
+  return (fast_inspect(Par,x) == OP) ? x : NULLT;
+}
 
-    fclose(fp);
+static treeNode fast_next_sibling(bp* Par,treeNode x)
+{
+  x = fwd_excess(Par,x,0);
+  return (fast_inspect(Par,x) == OP) ? x : NULLT;
+}
 
- }
 
+static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){
 
-// Load: loads XML tree data structure from file. Returns
-// a pointer to the loaded data structure
-XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) 
- {
+  if (tag == PCDATA_TAG_ID){
+    x = x+2;
+    return fast_inspect(Par,x)==OP ? x : NULLT;
+  } else return fast_next_sibling(Par,x);
 
-    FILE *fp;
-    char filenameaux[1024];
-    XMLTree *XML_Tree;
-    int i;
-    
-    // first load the tree topology
-    sprintf(filenameaux, "%s.srx", filename);
-    fp = fopen(filenameaux, "r");
-    if (fp == NULL) {
-       printf("Error: cannot open file %s to load the tree structure of XML collection\n", filenameaux);
-       exit(1);
-    } 
+}
 
-    XML_Tree = new XMLTree();
+static bool fast_isleaf(bp* Par,treeNode x){
+  return (fast_inspect(Par,x+1) == CP ? true : false);
+}
 
-    XML_Tree->Par = (bp *)malloc(sizeof(bp));
 
-    loadTree(XML_Tree->Par, fp); 
-    
-    // stores the table with tag names
-    fread(&XML_Tree->ntagnames, sizeof(int), 1, fp);
+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);
 
-    XML_Tree->TagName = (unsigned char **)malloc(XML_Tree->ntagnames*sizeof(unsigned char *));
+}
 
-    for (i=0; i<XML_Tree->ntagnames;i++) {
-       int k = feof(fp);
-       fscanf(fp, "%s\n",filenameaux);
-       XML_Tree->TagName[i] = (unsigned char *)malloc(sizeof(unsigned char)*(strlen((const char *)filenameaux)+1));
-       strcpy((char *)XML_Tree->TagName[i], (const char *)filenameaux);
-    }
-	
-    // loads the flags
-    fread(&(XML_Tree->indexing_empty_texts), sizeof(bool), 1, fp);
-    fread(&(XML_Tree->initialized), sizeof(bool), 1, fp);
-    fread(&(XML_Tree->finished), sizeof(bool), 1, fp);
+static uint fast_get_field(uint* A,int len, int idx)
+{
+  uint f1, f2;
+  switch (len) {
+  case 8:
+    return (uint) (((uchar*)A)[idx]);
+  case 16:
+    f2 = ((unsigned short*)A)[idx];
+    f1 = ((unsigned short*)A)[idx+1];
+    return (f1 << 16) + f2;
+  default:
+    return   get_field_no_power (A,len,idx);
+  };
+
+}
+
+inline bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){
+  if (x > y) 
+    return false;
+  else
+    return (x==0) || (y <= fast_find_close(Par,x));
+}
+
+
+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)
+ {
+    // creates the data structure for the tree topology
+    Par = (bp *)umalloc(sizeof(bp));
+    STARTTIMER();
+    bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0);
+    STOPTIMER(Building);
+    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);
     
-    if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
+    //cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl;
+
+    //Ensures that for small tag numbers, we are on an 8bit boundary.
+    //Makes tag access way faster with negligeable waste of space.
+    tags_blen = bits8(max_tag);
+    std::cerr << "Tags blen is " << tags_blen << "\n";
+    tags_len = (uint)npar;
+    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;    
+    free(tags);
+    tags = NULL;
+
+    STOPTIMER(Building);
+    PRINTTIME("Building Tag Structure", Building);
+    
+    Text = (TextCollection*) TC;
 
-    // loads the tags
-    XML_Tree->Tags = static_sequence::load(fp);
 
-    // loads the texts   
-    XML_Tree->Text->Load(fp,sample_rate_text);
+    EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32);
+    //EBVector = new static_bitsequence_sdarray(empty_texts_bmp,npar);
+    free(empty_texts_bmp);
+    empty_texts_bmp = NULL;
 
-    fclose(fp);
     
-    return XML_Tree;
+    disable_tc = dis_tc;
+    stream = NULL;
+    stream_fd = 0;
+    std::cerr << "Number of distinct tags " << TagName->size() << "\n";
+    //std::cerr.flush();
  }
 
 
@@ -120,123 +170,267 @@ XMLTree::~XMLTree()
     destroyTree(Par);
     free(Par); // frees the memory of struct Par
    
-    for (i=0; i<ntagnames;i++) 
-       free(TagName[i]);
+    delete tIdMap;
+    tIdMap = NULL;
+    
+    delete TagName;
+    TagName = NULL;
     
-    free(TagName);
-
-    if (!indexing_empty_texts) {
-       //EBVector->~static_bitsequence_rrr02();
-       delete EBVector;
-       EBVector = NULL;
-    }
-
-    //Tags->~static_sequence_wvtree();
     delete Tags;
     Tags = NULL;
 
-    //Text->~TextCollection();
-    delete Text;
+    delete Text; 
     Text = NULL;
 
-    initialized = false;
-    finished = false;
+    delete EBVector;
+    EBVector = NULL;
+    if (stream != NULL){
+      fclose(stream);
+      stream = NULL;
+      stream_fd = 0;
+    };
+
+ }
+
+
+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));
+    cout << "Space usage for XMLTree:" << endl
+         << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl
+         << " - tags access array:    " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl
+         << " ... add Diego structures ... " << endl
+         << " *total* " << total_space << endl;
+ }
+
+// Save: saves XML tree data structure to file. 
+void XMLTree::Save(int fd) 
+ {
+    FILE *fp;
+    char filenameaux[1024];
+    int i;
+
+    fp = fdopen(fd, "wa");
+    // first stores the tree topology
+    saveTree(Par, fp);
+
+    // stores the table with tag names
+    int ntags = TagName->size();
+
+    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);
+    ufwrite(&tags_blen,sizeof(uint),1,fp);
+    ufwrite(&tags_len,sizeof(uint),1,fp);
+    ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp);
+
+    // flags 
+    ufwrite(&disable_tc, sizeof(bool),1,fp);
+    
+    //text positions
+    EBVector->save(fp);
+    
+    // stores the texts   
+    if (!disable_tc) {
+      Text->Save(fp);
+    };
+
+
  }
 
-// root(): returns the tree root.
-treeNode XMLTree::Root() 
+
+// 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) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
+    FILE *fp;
+    char buffer[1024];
+    XMLTree *XML_Tree;
+    int i;
+
+
+
+    fp = fdopen(fd, "r");
+
+    XML_Tree = new XMLTree();
+    STARTTIMER();
+    // Load the tree structure
+    XML_Tree->Par = (bp *)umalloc(sizeof(bp));
+
+    loadTree(XML_Tree->Par, fp); 
+    STOPTIMER(Loading);
+    PRINTTIME("Loading parenthesis struct", Loading);
+    STARTTIMER();
+
+    XML_Tree->TagName = new vector<string>();
+    XML_Tree->tIdMap = new std::unordered_map<string,int>();
+    
+    string s;
+    int ntags;
+    
+    // Load the tag names
+    ufread(&ntags, sizeof(int), 1, fp);
+
+    for (i=0; i<ntags;i++) {
+      char * r = fgets(buffer,1023,fp);
+       if (r==NULL)
+	 throw "Cannot read tag list";
+       s = (const char*) buffer;
+       // remove the trailing \n
+       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);
+    STARTTIMER();
+
+    // 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";    
+    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);
+
+    // TODO ask francisco about this
+    /// FIXME:UGLY tests!
+    //uint * seq = new uint[XML_Tree->tags_len];
+    //for(uint i=0;i<XML_Tree->tags_len;i++)
+    //  seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i);
+    //cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl;
+    //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,sample_factor);
+    }
+    else XML_Tree->Text = NULL;
+    STOPTIMER(Loading);
+    PRINTTIME("Loading TextCollection", Loading);
+    STARTTIMER(); 
     }
-    return root_node(Par);
+    else {
+      XML_Tree->EBVector = NULL;
+      XML_Tree->Text = NULL;
+      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) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
     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) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
+    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);
  }
+int XMLTree::SubtreeElements(treeNode x) 
+ {
+    
+    int size = subtree_size(Par,x);
+    if (x == Root()){
+      x = fast_first_child(Par,x);
+      size = size - 1;
+    };
+
+    int s = x + 2*size - 1;
+    int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1);
+    size = size - ntext;
+    treeNode fin = fast_find_close(Par,x);
+    treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x));
+    while (y != NULLT && y < fin){
+      size -= SubtreeSize(y);
+      y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y));
+    };
+    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) 
  {
-    return isleaf(Par, 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) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    return is_ancestor(Par, x, 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) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    if (!is_ancestor(Par, x, y)) return false;
+    if (!fast_is_ancestor(Par, x, y)) return false;
     return depth(Par, x) == (depth(Par, y) + 1);
  }
 
+// IsFirstChild(x): returns whether node x is the first child of its parent.
+bool XMLTree::IsFirstChild(treeNode x)
+ {
+    return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));
+ }
+
+
 // NumChildren(x): number of children of node x. Constant time with the data structure
 // of Sadakane.
 int XMLTree::NumChildren(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
     return degree(Par, x);
  }
 
 // ChildNumber(x): returns i if node x is the i-th children of its parent.
 int XMLTree::ChildNumber(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
     return child_rank(Par, x);
  }
 
 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.
 int XMLTree::Depth(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
     return depth(Par, x);
  }
 
@@ -244,11 +438,6 @@ int XMLTree::Depth(treeNode x)
 // nodes (i.e., tags, it disregards the texts in the tree).
 int XMLTree::Preorder(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
     return preorder_rank(Par, x);
  }
 
@@ -256,166 +445,237 @@ int XMLTree::Preorder(treeNode x)
 // nodes (i.e., tags, it disregards the texts in the tree).
 int XMLTree::Postorder(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
     return postorder_rank(Par, x);
  }
-
+/*
 // Tag(x): returns the tag identifier of node x.
 TagType XMLTree::Tag(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    return Tags->access(node2tagpos(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) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    range r;
-    if (indexing_empty_texts) { // faster, no rank needed
-       r.min = x;
-       r.max = x+2*subtree_size(Par, x)-2;
-    }
-    else { // we are not indexing empty texts, we need rank
-       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;
-       }
-       else { // the range is non-empty, there are texts within the subtree of x
-          r.min = min+1;
-          r.max = max;
-       }
-    }
-    return r;
+   range r;
+   if (x == NULLT) {
+     r.min = NULLT;
+     r.max = NULLT;
+     return r;
+   };
+   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;
+   }
+   else { // the range is non-empty, there are texts within the subtree of x
+     r.min = min+1;
+     r.max = max;
+   }
+   return r;
  }
 
 // Parent(x): returns the parent node of node x.
+
 treeNode XMLTree::Parent(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
     if (x == Root())
       return NULLT;
     else
-      return parent(Par, x);
+      return  parent(Par, x);;
  }
 
 // Child(x,i): returns the i-th child of node x, assuming it exists.
 treeNode XMLTree::Child(treeNode x, int i) 
 {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
     if (i <= OPTD) return naive_child(Par, x, i);
     else return child(Par, x, i);
- }
+}
 
 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.
+
 treeNode XMLTree::FirstChild(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
+   NULLT_IF(x==NULLT);
+   return fast_first_child(Par, 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:  
+     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;     
+   default:
+     return x;
+   }
+ }
+
+treeNode XMLTree::NextElement(treeNode x) 
+{
+  NULLT_IF(x==NULLT);
+  x = fast_next_sibling(Par, x);
+  NULLT_IF(x == NULLT);   
+  if (Tag(x) == PCDATA_TAG_ID){
+    x = x+2;
+     return (fast_inspect(Par,x)==OP)? x : NULLT;
+  }
+  else return x;  
+}
+value XMLTree::CamlFirstElement(value x)
+{
+  return Val_int(FirstElement(Int_val(x)));
+}
+value XMLTree::CamlNextElement(value x)
+{
+  return Val_int(NextElement(Int_val(x)));
+}
+
+extern "C" value caml_cpp_fast_first_element(value xmltree, value node){
+  return XMLTREE(xmltree)->CamlFirstElement(node);
+}
 
-    return first_child(Par, x);
+extern "C" value caml_cpp_fast_next_element(value xmltree, value node){
+  return XMLTREE(xmltree)->CamlNextElement(node);
+}
+
+// LastChild(x): returns the last child of node 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) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-    if (x == Root())
-      return NULLT;
- 
-    return next_sibling(Par, x);
+   NULLT_IF(x==NULLT || x == Root() );
+   x = fast_find_close(Par,x)+1;
+   return (fast_inspect(Par,x) == CP ? NULLT : x);
  }
 
+
 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.
 treeNode XMLTree::PrevSibling(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    return prev_sibling(Par, x);
+   NULLT_IF(x==NULLT);
+   return prev_sibling(Par, x);
  }
 
-// TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or NULLT if there is none.
+// 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, int i, TagType tag) 
+treeNode XMLTree::TaggedChild(treeNode x, TagType tag) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    treeNode child;
    
-    child = first_child(Par, x); // starts at first child of node x
-    if (child==(treeNode)-1) return NULLT; // node x is a leaf, there is no such child
-    while (child!=(treeNode)-1) {
-       if (Tags->access(node2tagpos(child)) == tag) { // current child is labeled with tag of interest
-          i--;
-          if (i==0) return child; // we have seen i children of x tagged tag, this is the one we are looking for
-       }
-       child = next_sibling(Par, x); // OK, let's try with the next child
-    }
-    return NULLT; // no such child was found  
+   NULLT_IF(x==NULLT || fast_isleaf(Par,x));
+   treeNode child;   
+   child = fast_first_child(Par, x); // starts at first child of node x
+   if (Tag(child) == tag)
+     return child;
+   else
+     return TaggedFollowingSibling(child,tag);
  }
 
-// TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within
+// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.
+treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)
+{
+  NULLT_IF(x==NULLT);
+  treeNode sibling = fast_next_sibling(Par, x);
+  TagType ctag;
+  while (sibling != NULLT) {
+    ctag = Tag(sibling);
+    if (ctag == tag) // current sibling is labeled with tag of interest
+      return sibling; 
+    sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling
+  }
+  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);  
+  TagType t;
+  while (child != NULLT) {
+    t = Tag(child);
+    if (tags->find(t) != tags->end()) return child;
+    child = fast_sibling(Par, child,t);
+  }
+  return NULLT;  
+}
+
+
+treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)
+{
+
+   NULLT_IF(x==NULLT);
+   int i;
+   TagType t;
+   treeNode sibling = fast_next_sibling(Par, x);
+   while (sibling != NULLT) {
+     t = Tag(sibling);
+     if (tags->find(t) != tags->end()) return sibling;
+     sibling = fast_sibling(Par, sibling,t);
+   }
+   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::TaggedDesc(treeNode x, TagType tag) 
+treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
+   //NULLT_IF(x==NULLT || fast_isleaf(Par,x));
 
-    int r, s;
-    treeNode y;
-    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
-    if (!is_ancestor(Par, x, y)) return NULLT; // the next node tagged tag (in preorder) is not within the subtree of x.
-    else return y;
+   int s = (int) Tags->select_next(tag,node2tagpos(x));
+   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));
+   int i;
+   treeNode min = NULLT;
+   treeNode fc = fast_first_child(Par,x);
+   treeNode aux;
+   TagIdSet::const_iterator tagit;
+   for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
+     aux = TaggedDescendant(x, (TagType) *tagit);
+     if (aux == fc) return fc;
+     if (aux == NULLT) continue;
+     if ((min == NULLT) || (aux < min)) min = aux;
+   };
+   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::TaggedPrec(treeNode x, TagType tag) 
- {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-    
+treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) 
+ {    
     int r, s;
     treeNode node_s, root;
     r = (int)Tags->rank(tag, node2tagpos(x)-1);
@@ -423,7 +683,7 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag)
     s = (int)Tags->select(tag, r);
     root = root_node(Par);
     node_s = tagpos2node(s);
-    while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x
+    while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x
        r--;
        if (r==0) return NULLT; // there is no such node
        s = (int)Tags->select(tag, r);  // we should use select_prev instead when provided
@@ -432,100 +692,179 @@ 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::TaggedFollowing(treeNode x, TagType tag)
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
+   NULLT_IF (x ==NULLT || x == Root());   
+   return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x)));
 
-    int r, s;
-    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;
-    else return tagpos2node(s);
- }
+ } 
+
+// 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); 
+
+  //Special optimisation, test for the following sibling first
+  treeNode close = fast_find_close(Par, x);
+  /*
+   treeNode ns = close+1;
+  if (fast_inspect(Par,ns) == OP) {
+    TagType tagns = Tag(ns);
+    //    cout << GetTagNameByRef(tagns) << endl;
+    //cout.flush();
+    if (tagns == PCDATA_TAG_ID){
+      close = ns+1;
+      ns = ns+2;
+      if (fast_inspect(Par,ns) != OP)
+	goto after;
+      tagns = Tag(ns);      
+    };
+    if (tagns == tag)
+      return ns;
+  };
+ after:
+  */
+  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)
+{
 
-// 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.
-DocID XMLTree::PrevText(treeNode x) 
+  NULLT_IF (x == NULLT || x == Root());
+  
+  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 */
+treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor)
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
 
-    if (x == Root()) return NULLT;
-    if (indexing_empty_texts)  // faster, no rank needed
-       return (DocID)x-1;
-    else { // we are not indexing empty texts, rank is needed
-       if (EBVector->access(x-1) == 0) 
-          return (DocID)NULLT;  // there is no text to the left of node (text is empty)
-       else
-          return (DocID)EBVector->rank1(x-1)-1;  //-1 because document ids start from 0
-    }
- }
+   NULLT_IF(x==NULLT || x==Root());
+
+   treeNode close = fast_find_close(Par,x);
+   treeNode ns = close+1;
+   if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))
+     return ns;
+
+   int i;
+   treeNode min = NULLT;
+   treeNode aux;
+  
+
+   TagIdSet::const_iterator tagit;
+   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 == 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.
 
-// NextText(x): returns the document identifier of the text to the right
-// of node x, or NULLT if x is the root node. Assumes Doc ids start from 0.
-DocID XMLTree::NextText(treeNode x) 
+   if (ancestor == Root()) return min;
+   // else check whether if is in below the ctx node
+
+   NULLT_IF (min == NULLT || min >= fast_find_close(Par, ancestor));
+   
+   return min;
+   
+ }
+treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing)
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
 
-    if (x == Root()) return NULLT;
-    if (indexing_empty_texts)  // faster, no rank needed
-       return (DocID)x+2*subtree_size(Par, x)-1;
-    else { // we are not indexing empty texts, rank is needed
-       int p = x+2*subtree_size(Par, x)-1;
-       if (EBVector->access(p) == 0) // there is no text to the right of node
-          return (DocID)NULLT;
-       else
-          return (DocID)EBVector->rank1(p)-1; //-1 because document ids start from 0
+   NULLT_IF(x==NULLT || x==Root());
+   int i;
+   treeNode min = NULLT;
+   treeNode ns = fast_next_sibling(Par, x);
+   treeNode close = ns - 1;
+   treeNode aux;
+   TagIdSet::const_iterator tagit;
+   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;
+       s = parent(Par, s);
     }
+    return 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 
 // ids start from 0.
 DocID XMLTree::MyText(treeNode x) 
- {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    if (!IsLeaf(x)) return NULLT;
-    if (indexing_empty_texts) // faster, no rank needed
-       return (DocID)x;
-    else { // we are not indexing empty texts, rank is needed
-       if (EBVector->access(x) == 0)  // there is no text below node x
-          return (DocID)NULLT;
-       else
-          return (DocID)EBVector->rank1(x)-1; //-1 because document ids start from 0
-    } 
- }
-
+{
+  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) 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 
+// ids start from 0.
+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) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    if (indexing_empty_texts) 
-       return d + rank_open(Par, d)+1; // +1 because root has preorder 1
-    else { // slower, needs rank and select
-       int s = EBVector->select1(d+1);
-       return rank_open(Par, s) + d + 1; // +1 because root has preorder 1
-    }
+   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 
@@ -533,364 +872,183 @@ int XMLTree::TextXMLId(DocID d)
 // preorder 0;
 int XMLTree::NodeXMLId(treeNode x) 
  {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    if (indexing_empty_texts)
-       return x - 1 + rank_open(Par, x);
-    else {
-       if (x == Root()) return 1; // root node has preorder 1
-       else
-          return rank_open(Par, x) + EBVector->rank1(x-1);
-    }
+   NULLT_IF(x == NULLT);
+   if (x == Root()) return 1; // root node has preorder 1
+   return rank_open(Par, x) + EBVector->rank1(x-1);
  }
 
 // ParentNode(d): returns the parent node of document identifier d.
 treeNode XMLTree::ParentNode(DocID d) 
- {
-    if (!finished) {
-       fprintf(stderr, "Error: data structure has not been constructed properly\n");
-       exit(1);
-    }
-
-    int s;
-    if (indexing_empty_texts) s = d;
-    else s = EBVector->select1(d);
-    
-    if (inspect(Par,s) == CP) // is a closing parenthesis
-       return parent(Par, find_open(Par, s));
-    else // is an opening parenthesis
-       return (treeNode)s;
-     
+ {    
+   NULLT_IF (d == NULLT);   
+   return (treeNode) EBVector->select1(d+1);     
  }
 
-
-// OpenDocument(empty_texts): it starts the construction of the data structure for
-// the XML document. Parameter empty_texts indicates whether we index empty texts
-// in document or not. Returns a non-zero value upon success, NULLT in case of error.
-int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text)
- {
-    initialized = true;
-    finished = false;
-    found_attributes = false;
-    npar = 0;
-    parArraySize = 1;
-    ntagnames = 2;    
- 
-    indexing_empty_texts = empty_texts;
-    
-    par_aux = (pb *)malloc(sizeof(pb)*parArraySize);
-    if (!par_aux) {
-       fprintf(stderr, "Error: not enough memory\n");
-       return NULLT;
-    }
-    
-    tags_aux = (TagType *) malloc(sizeof(TagType));
-    if (!tags_aux) {
-       fprintf(stderr, "Error: not enough memory\n");
-       return NULLT;
-    }
-    
-    TagName = (unsigned char **) malloc(2*sizeof(unsigned char*));
-    if (!TagName){
-       fprintf(stderr, "Error: not enough memory\n");
-       return NULLT;
-    }
-
-    TagName[0] = (unsigned char *) malloc(4*sizeof(unsigned char));
-    strcpy((char *) TagName[0], "<@>");
-
-    if (!TagName[0]){
-      fprintf(stderr, "Error: not enough memory\n");
-      return NULLT;
-    }
-
-    TagName[1] = (unsigned char *) malloc(4*sizeof(unsigned char));
-    if (!TagName[1]){
-      fprintf(stderr, "Error: not enough memory\n");
-      return NULLT;
-    }
-
-    strcpy((char *) TagName[1], "<$>");
-
-
-    if (!indexing_empty_texts) {
-       empty_texts_aux = (unsigned int *)malloc(sizeof(unsigned int));
-       if (!empty_texts_aux) {
-          fprintf(stderr, "Error: not enough memory\n");
-          return NULLT;
-       }
-    }
-    
-    Text = TextCollection::InitTextCollection((unsigned)sample_rate_text);
-    
-    return 1;  // indicates success in the initialization of the data structure
- }
-
-// CloseDocument(): it finishes the construction of the data structure for the XML
-// document. Tree and tags are represented in the final form, dynamic data 
-// structures are made static, and the flag "finished" is set to true. After that, 
-// the data structure can be queried.
-int XMLTree::CloseDocument()
+// 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)
  {
-    if (!initialized) {  // data structure has not been initialized properly
-       fprintf(stderr, "Error: data structure has not been initialized properly (by calling method OpenDocument)\n");
-       return NULLT;
-    }
-    
-    // closing parenthesis for the tree root
-    par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));
-    if (!par_aux) {
-       fprintf(stderr, "Error: not enough memory\n");
-       return NULLT;    
-    }
-    
-    // creates the data structure for the tree topology
-    Par = (bp *)malloc(sizeof(bp));
-    bp_construct(Par, npar, par_aux, OPT_DEGREE|0);    
-    // creates structure for tags
-    static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20);
-    static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb);
-    static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb);
-
-
-    // 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
-    int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2;
-
-    Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,ntagsize, bmb, ssb);
-    
-    delete bmb;
-    delete pmb;
-    delete ssb;
-    // makes the text collection static
-    Text->MakeStatic();
+  
+   string s = (char *) tagname;
+   TagIdMapIT it = tIdMap->find(s);    
+   return (TagType) ((it != tIdMap->end()) ? it->second : -1);
     
-    // creates the data structure marking the non-empty texts (just in the case it is necessary)
-    if (!indexing_empty_texts) 
-       EBVector = new static_bitsequence_rrr02((uint *)empty_texts_aux,(ulong)npar,(uint)32);
-
-    finished = true;
-
-    return 1; // indicates success in the inicialization
  }
 
 
-// NewOpenTag(tagname): indicates the event of finding a new opening tag in the document.
-// Tag name is given. Returns a non-zero value upon success, and returns NULLT
-// in case of failing when trying to insert the new tag.
-int XMLTree::NewOpenTag(unsigned char *tagname)
+// GetTagName(tagid): returns the tag name of a given tag identifier.
+// Returns NULL in case that the tag identifier is not valid.
+unsigned char *XMLTree::GetTagName(TagType tagid)
  {
-    int i;
-
-    if (!initialized) {  // data structure has not been initialized properly
-       fprintf(stderr, "Error: you cannot insert a new opening tag without first calling method OpenDocument first\n");
-       return NULLT;
-    }
-    
-    // inserts a new opening parentheses in the bit sequence
-    if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis
-       par_aux = (pb *)realloc(par_aux, sizeof(pb)*2*parArraySize);
-       parArraySize *= 2;
-    }
-    
-    if (!par_aux) {
-       fprintf(stderr, "Error: not enough memory\n");
-       return NULLT;    
-    }
-
-    setbit(par_aux,npar,OP);  // marks a new opening 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;
- 
-
-    // NewOpenTag("<@>") was called
-    if (i==0) 
-      found_attributes=true;
-
-    if (i==ntagnames) { // the tag is a new one, then we insert it
-       TagName = (unsigned char **)realloc(TagName, sizeof(char *)*(ntagnames+1));
-       
-       if (!TagName) {
-          fprintf(stderr, "Error: not enough memory\n");
-          return NULLT;
-       }
-       
-       ntagnames++;
-       TagName[i] = (unsigned char *)malloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1));
-       strcpy((char *)TagName[i], (const char *)tagname);
-    } 
-    tags_aux = (TagType *) realloc(tags_aux, sizeof(TagType)*(npar + 1));
-    if (!tags_aux) {
-       fprintf(stderr, "Error: not enough memory\n");
-       return NULLT;
-    }
-
-    tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags
-    
-    npar++;
-
-    return 1;
+    unsigned char *s;
+    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);
  }
 
 
-// NewClosingTag(tagname): indicates the event of finding a new closing tag in the document.
-// Tag name is given. Returns a non-zero value upon success, and returns NULLT
-// in case of failing when trying to insert the new tag.
-int XMLTree::NewClosingTag(unsigned char *tagname)
+const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)
  {
-    int i;
-
-    if (!initialized) {  // data structure has not been initialized properly
-       fprintf(stderr, "Error: you cannot insert a new closing tag without first calling method OpenDocument first\n");
-       return NULLT;
-    }
-    
-    // inserts a new closing parentheses in the bit sequence
-    if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis
-       par_aux = (pb *)realloc(par_aux, sizeof(pb)*2*parArraySize);
-       parArraySize *= 2;
-    }
-    
-    if (!par_aux) {
-       fprintf(stderr, "Error: not enough memory\n");
-       return NULLT;    
-    }
-    setbit(par_aux,npar,CP);  // marks a new closing opening 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 (i==ntagnames) { // the tag is a new one, then we insert it
-       TagName = (unsigned char **)realloc(TagName, sizeof(char *)*(ntagnames+1));
-       
-       if (!TagName) {
-          fprintf(stderr, "Error: not enough memory\n");
-          return NULLT;
-       }
-       
-       ntagnames++;
-       TagName[i] = (unsigned char *)malloc(sizeof(char)*(strlen((const char *)tagname)+2));
-       TagName[i][0] = '/';
-       strcpy((char *)&(TagName[i][1]), (const char *)tagname);
-    } 
-
-    tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1));
-
-    if (!tags_aux) {
-       fprintf(stderr, "Error: not enough memory\n");
-       return NULLT;
-    }
 
-    tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags
-    
-    npar++;
-
-    return 1; // success
-    
+   unsigned char *s;
+   if ( tagid < 0 || tagid >= TagName->size())
+     return (unsigned char *) "<INVALID TAG>";
+   
+   return (const unsigned char *) (*TagName)[tagid].c_str();
+   
  }
 
 
-// NewText(s): indicates the event of finding a new (non-empty) text s in the document.
-// The new text is inserted within the text collection. Returns a non-zero value upon
-// success, NULLT in case of error.
-int XMLTree::NewText(unsigned char *s)
- {
-    if (!initialized) {  // data structure has not been initialized properly
-       fprintf(stderr, "Error: you cannot insert a new text without first calling method OpenDocument first\n");
-       return NULLT;
-    }
 
-    if (!indexing_empty_texts) {
-       empty_texts_aux = (unsigned int *)realloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));
-       if (!empty_texts_aux) {
-          fprintf(stderr, "Error: not enough memory\n");
-          return NULLT;
-       }
-       
-       bitset(empty_texts_aux, npar-1);  // marks the non-empty text with a 1 in the bit vector
-    }
-    
-    Text->InsertText(s);
-    
-    return 1; // success
- }
-
-// NewEmptyText(): indicates the event of finding a new empty text in the document.
-// In case of indexing empty and non-empty texts, we insert the empty texts into the
-// text collection. In case of indexing only non-empty texts, it just indicates an
-// empty text in the bit vector of empty texts. Returns a non-zero value upon
-// success, NULLT in case of error.
-int XMLTree::NewEmptyText() 
- {
-    unsigned char c = 0;
-    if (!initialized) {  // data structure has not been initialized properly
-       fprintf(stderr, "Error: you cannot insert a new empty text without first calling method OpenDocument first\n");
-       return NULLT;
-    }
-
-    if (!indexing_empty_texts) {
-       empty_texts_aux = (unsigned int *)realloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));
-       if (!empty_texts_aux) {
-          fprintf(stderr, "Error: not enough memory\n");
-          return NULLT;
-       }
-       
-       bitclean(empty_texts_aux, npar-1);  // marks the empty text with a 0 in the bit vector
-    }
-    else Text->InsertText(&c); // we insert the empty text just in case we index all the texts
+TagType XMLTree::RegisterTag(unsigned char *tagname)
+ {  
+    TagType id = XMLTree::GetTagId(tagname);
+    if (id == NULLT) {
+      string s = (char *) tagname;      
+      REGISTER_TAG(TagName,tIdMap,s);      
+    };
     
-    return 1; // success    
+    return id;
  }
 
 
-// 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)
- {
-    int i;
-    // 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
-    else return i;
- }
+treeNode XMLTree::Closing(treeNode x) {
+  return fast_find_close(Par,x); 
+}
+bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }
 
+//WARNING this uses directly the underlying implementation for plain text
 
-// GetTagName(tagid): returns the tag name of a given tag identifier.
-// Returns NULL in case that the tag identifier is not valid.
-unsigned char *XMLTree::GetTagName(TagType tagid)
- {
-    unsigned char *s;
-
-    if (tagid >= ntagnames) return NULL; // invalid tag identifier
-    s = (unsigned char *)malloc((strlen((const char *)TagName[tagid])+1)*sizeof(unsigned char));
-    strcpy((char *)s, (const char *)TagName[tagid]);
-    return s;
- }
 
 
-TagType XMLTree::RegisterTag(unsigned char *tagname)
-{
-  if (!finished)
-    return NULLT;
+void XMLTree::Print(int fd,treeNode x, bool no_text){
   
-
-  TagType id = XMLTree::GetTagId(tagname);
-  if (id == NULLT){
-    id = ntagnames;
-    ntagnames = ntagnames + 1;    
-    TagName = (unsigned char **) realloc(TagName,ntagnames*(sizeof(unsigned char*)));
-    strcpy((char*)TagName[id], (const char *)tagname);  
-  };
-
-  return id;
+  int newfd = dup(fd);
+  stream = fdopen(newfd,"wa");
+
+
+  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 : TaggedDescendant(x,PCDATA_TAG_ID));
+  treeNode first_att =  NULLT;//TaggedDesc(x,ATTRIBUTE_DATA_TAG_ID);
+  
+  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(MyText(first_idx));
+   int read = 0;
+
+ std::stack<uchar*> st;
+ while (n <= fin){
+   if (fast_inspect(Par,n)){
+     if (tag == PCDATA_TAG_ID  ) {       
+       //       myfputs((const char*) (GetText(MyTextUnsafe(n))),fp);
+       if (no_text)
+	 myfputs("<$/>",fp);
+       else{
+       read = fprintf(fp,"%s",(const char*) current_text);
+       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(tagstr);
+	 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 = fprintf(fp,"%s",(const char*) current_text);
+	       current_text += (read + 1);
+	       //myfputs((const char*) GetText(MyTextUnsafe(n)),fp);
+	       myfputc('"',fp);
+	       n+=3;
+	     }
+	   };
+	   if (no_text) 
+	     myfputs("</@@>",fp);
+	   else myfputc('>',fp);
+	   n++;
+	   tag=Tag(n);
+	 }
+	 else {
+	   myfputc('>',fp);
+	 };
+       }
+       else {// <foo /> tag
+	 myfputs("/>",fp);
+	 n++;
+	 tag=Tag(n);	 
+       };     
+     };
+   }
+   else
+     do {
+       myfputs("</",fp);
+       myfputs((const char*)st.top(),fp);
+       myfputc('>', fp);
+       st.pop();
+       n++;
+     }while (!fast_inspect(Par,n) && !st.empty());
+   tag=Tag(n);
+ };
+ myfputc('\n',fp);
+ mybufferflush(fp);
+ fflush(fp);
+ fclose(fp);
 }