From: kim <kim@3cdefd35-fc62-479d-8e8d-bae585ffb9ca>
Date: Thu, 30 Apr 2009 09:32:20 +0000 (+0000)
Subject: Merge the last bit of Diego's code with the modifications:
X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2FXMLTree.git;a=commitdiff_plain;h=235e3214904e390d2f101c5d5bf7def98745b132

Merge the last bit of Diego's code with the modifications:
- Remove all deprecated function
- Add description of the XML encoding
- Use vector<T> when possible instead of T*
- lot more stuff...


git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@364 3cdefd35-fc62-479d-8e8d-bae585ffb9ca
---

diff --git a/XMLTree.cpp b/XMLTree.cpp
index ffdf5d0..61f6a4d 100644
--- a/XMLTree.cpp
+++ b/XMLTree.cpp
@@ -1,6 +1,7 @@
-#include "XMLTree.h"
+
 #include "basics.h"
 #include <cstring>
+#include "XMLTree.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, 
@@ -11,35 +12,34 @@
 // tag position -> tree node
 inline treeNode tagpos2node(int t) 
  {
-    return (treeNode)t;
+    return (treeNode) t;
  }
 
 // tree node -> tag position
 inline int node2tagpos(treeNode x) 
- {
-    return (int)x;
- }
+{
+  return (int)x;
+}
+
+// returns NULLT if the test is true
+#define NULLT_IF(x)  do { if (x) return NULLT; } while (0)
 
 
-XMLTree::XMLTree(pb *par, uint npar, unsigned char **TN, uint ntagnm, uint *empty_texts_bmp, TagType *tags,
-                 TextCollection *TC, vector<string> CT, bool indexing_empty_t, bool dis_tc)
+XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,
+            TextCollection * const TC, vector<string> * const CT, bool dis_tc)
+
  {
     // creates the data structure for the tree topology
     Par = (bp *)umalloc(sizeof(bp));
-    bp_construct(Par, npar, par, OPT_DEGREE|0);    
-
-
+    bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0);    
+   
     // creates structure for tags
 
-    // 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
-    TagName = TN;
-    ntagnames = ntagnm;
-    uint max_tag = 0;
-    for(uint i=0;i<(uint)npar-1;i++)
-       max_tag = max(max_tag,tags[i]);
-    int ntagsize = 2*ntagnames + 2;
-
+    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);
@@ -56,24 +56,14 @@ XMLTree::XMLTree(pb *par, uint npar, unsigned char **TN, uint ntagnm, uint *empt
     free(tags);
     tags = NULL;
     
-    Text = TC;
-
-    CachedText = CT;
+    Text = (TextCollection*) TC;
 
-    // creates the data structure marking the non-empty texts (just in the case it is necessary)
-    indexing_empty_texts = indexing_empty_t;
-    if (!indexing_empty_t)  {
-       EBVector = new static_bitsequence_rrr02((uint *)empty_texts_bmp,(ulong)npar,(uint)32);
-       free(empty_texts_bmp);
-       empty_texts_bmp = NULL;
-    }
+    CachedText = (vector<string>*) CT;
+    EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32);
+    free(empty_texts_bmp);
+    empty_texts_bmp = NULL;
 
-    TagArray = new TagArrayEntry[ntagnames];
-    for (uint i=0; i<ntagnames; i++) {
-       TagArray[i].first = NULL;
-       TagArray[i].last = NULL;
-    }
- 
+    
     disable_tc = dis_tc;
  }
 
@@ -86,23 +76,22 @@ 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) {
-       delete EBVector;
-       EBVector = NULL;
-    }
-
     delete Tags;
     Tags = NULL;
 
     delete Text; 
     Text = NULL;
 
-    delete TagArray;
+    delete EBVector;
+    EBVector = NULL;
+
+
  }
 
 
@@ -118,177 +107,153 @@ void XMLTree::print_stats()
  }
 
 // Save: saves XML tree data structure to file. 
-void XMLTree::Save(unsigned char *filename) 
+void XMLTree::Save(int fd) 
  {
     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);
-    } 
-    
+
+    fp = fdopen(fd, "wa");
     // first stores the tree topology
     saveTree(Par, fp);
- 
+
     // stores the table with tag names
-    ufwrite(&ntagnames, sizeof(int), 1, fp);
-    for (i=0; i<ntagnames;i++)
-      fprintf(fp, "%s\n",TagName[i]);
-    
-    
-    // stores the flags
-    ufwrite(&indexing_empty_texts, sizeof(bool), 1, fp);
-    bool ignore = true;
-    ufwrite(&ignore, sizeof(bool),1,fp);
-    ufwrite(&ignore, sizeof(bool),1,fp);
-    ufwrite(&disable_tc, sizeof(bool),1,fp);
-    
-    if (!indexing_empty_texts) EBVector->save(fp);
+    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);
-      int st = CachedText.size();
+      int st = CachedText->size();
+
       ufwrite(&st, sizeof(int),1,fp);
-      for (int i = 0; i< CachedText.size(); i++){
-	st = CachedText.at(i).size();
+      for (int i = 0; i< CachedText->size(); i++){
+	st = CachedText->at(i).size();
+
 	ufwrite(&st, sizeof(int),1,fp);
-	ufwrite(CachedText.at(i).c_str(),sizeof(char),1+CachedText.at(i).size(),fp);
+
+	ufwrite(CachedText->at(i).c_str(),sizeof(char),1+CachedText->at(i).size(),fp);
+
       };
+      
+      Text->Save(fp);
     };
-    fclose(fp);
+
 
  }
 
 
 // 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) 
+XMLTree *XMLTree::Load(int fd) 
  {
     FILE *fp;
     char buffer[1024];
     XMLTree *XML_Tree;
     int i;
-    size_t s_tree = 0;
-    long s_text = 0;
-    size_t s_tags = 0;
-
-    // first load the tree topology
-    sprintf(buffer, "%s.srx", filename);
-    fp = fopen(buffer, "r");
-    if (fp == NULL) {
-       printf("Error: cannot open file %s to load the tree structure of XML collection\n", buffer);
-       exit(1);
-    } 
-
-    XML_Tree = new XMLTree();
-
 
-    XML_Tree->Par = (bp *)umalloc(sizeof(bp));
-
-    loadTree(XML_Tree->Par, fp); 
 
-    s_tree += sizeof(bp);
 
+    fp = fdopen(fd, "r");
 
-    // stores the table with tag names
-    ufread(&XML_Tree->ntagnames, sizeof(int), 1, fp);
-
-    s_tree += sizeof(int);
+    XML_Tree = new XMLTree();
 
-    XML_Tree->TagName = (unsigned char **)umalloc(XML_Tree->ntagnames*sizeof(unsigned char *));
+    // Load the tree structure
+    XML_Tree->Par = (bp *)umalloc(sizeof(bp));
 
-    s_tags += sizeof(unsigned char*)*XML_Tree->ntagnames;
+    loadTree(XML_Tree->Par, fp); 
 
+    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<XML_Tree->ntagnames;i++) {
-       char * r = fgets(buffer,1023,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));
+       
+    };
 
-       // strlen is actually the right size, since there is a trailing '\n'
-       int len = strlen((const char*)buffer);
-       XML_Tree->TagName[i] = (unsigned char *)ucalloc(len,sizeof(char));
-       strncpy((char *)XML_Tree->TagName[i], (const char *)buffer,len - 1);
-       s_tags+= len*sizeof(char);
-    }
-
-	
-    // loads the flags
-
-    ufread(&(XML_Tree->indexing_empty_texts), sizeof(bool), 1, fp);
-    bool ignore;
-    ufread(&ignore, sizeof(bool), 1, fp);
-    ufread(&ignore, sizeof(bool), 1, fp);
-    ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);
-
-    s_tree+=sizeof(bool)*4;
-
-    if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
-
-    s_tree+= XML_Tree->EBVector->size();
 
-    // loads the tags
+    // loads the tag structure
     XML_Tree->Tags = static_sequence::load(fp);
     ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);
     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);
-    s_tree+=2*sizeof(uint)+sizeof(uint)*uint_len(XML_Tree->tags_blen,XML_Tree->tags_len);
-    s_tree+= XML_Tree->Tags->size();
-
 
+    // 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;
+      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
+    
 
-    s_text = ftell(fp);
+    // loads the flags
+    
+    ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);
+
+    XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
 
+    // Not used  
+    int sample_rate_text = 64;
     // loads the texts
     if (!XML_Tree->disable_tc){
-      XML_Tree->Text = TextCollection::Load(fp,sample_rate_text);
+      XML_Tree->CachedText = new vector<string>;
       int sst;
       int st;
       ufread(&sst, sizeof(int),1,fp);
+      
       for (int i=0;i<sst;i++){
 	ufread(&st, sizeof(int),1,fp);
 	char* str = (char*) malloc(sizeof(char)*st+1);
 	ufread(str,sizeof(char),st+1,fp);
 	string cppstr = str;
-	XML_Tree->CachedText.push_back(cppstr);
+	XML_Tree->CachedText->push_back(cppstr);
 	free(str);
-      };
 
+      };
+      XML_Tree->Text = TextCollection::Load(fp,sample_rate_text);
     }
     else XML_Tree->Text = NULL;
-
-    s_text = ftell(fp) - s_text;
-
-    fclose(fp);
-
-    XML_Tree->print_stats();
+    
     return XML_Tree;
  }
 
 
 // root(): returns the tree root.
-treeNode XMLTree::Root() 
+inline treeNode XMLTree::Root() 
  {
-    return root_node(Par);
+   return 0; //root_node(Par);
  }
 
 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.
@@ -372,7 +337,7 @@ int XMLTree::Postorder(treeNode x)
 // Tag(x): returns the tag identifier of node x.
 TagType XMLTree::Tag(treeNode x) 
  {
-    return get_field(tags_fix,tags_blen,node2tagpos(x)); //Tags->access(node2tagpos(x));
+    return get_field(tags_fix,tags_blen,node2tagpos(x));
  }
 
 // DocIds(x): returns the range of text identifiers that descend from node x.
@@ -386,23 +351,19 @@ range XMLTree::DocIds(treeNode x)
        return r;
     };
         
-    if (indexing_empty_texts) { // faster, no rank needed
-       r.min = x;
-       r.max = 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;
     }
-    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;
-       }
+    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.
@@ -419,38 +380,51 @@ treeNode XMLTree::Child(treeNode x, int i)
 {
     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) 
  {
-    return first_child(Par, x);
+   NULLT_IF(x==NULLT);
+   return first_child(Par, x);
+ }
+
+treeNode XMLTree::FirstElement(treeNode x) 
+ {
+   NULLT_IF(x==NULLT);
+   treeNode fc = first_child(Par, x);
+   //<$> is 2
+   return ((fc == NULLT || Tag(fc) != PCDATA_TAG_ID) ? fc : next_sibling(Par,fc));
+
  }
 
+treeNode XMLTree::NextElement(treeNode x) 
+{
+   NULLT_IF(x==NULLT);
+   treeNode ns = next_sibling(Par, x);
+   return ((ns == NULLT || Tag(ns) != PCDATA_TAG_ID) ? ns : next_sibling(Par,ns));
+}
+
 // LastChild(x): returns the last child of node x.
 treeNode XMLTree::LastChild(treeNode x)
  {
-    if (x == Root() || isleaf(Par,x) || x == NULLT)
-       return x;
-    else
-//       return find_open(Par,find_close(Par,parent(Par,x))-1);
-       return find_open(Par, find_close(Par, x)-1);
+   NULLT_IF(x==NULLT || x == Root() || isleaf(Par,x));
+   return find_open(Par, find_close(Par, x)-1);
  }
 
 
 // NextSibling(x): returns the next sibling of node x, assuming it exists.
 treeNode XMLTree::NextSibling(treeNode x) 
  {
-    if (x == Root() || x==NULLT)
-      return NULLT;
-    
-    return next_sibling(Par, x);
+   NULLT_IF(x==NULLT || x == Root() );
+   return next_sibling(Par, x);
  }
 
 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.
 treeNode XMLTree::PrevSibling(treeNode x) 
  {
-    return prev_sibling(Par, x);
+   NULLT_IF(x==NULLT || x == Root());
+   return prev_sibling(Par, x);
  }
 
 // TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none.
@@ -458,60 +432,58 @@ treeNode XMLTree::PrevSibling(treeNode x)
 // efficiently, just iterating among the children of node x until finding the desired child.
 treeNode XMLTree::TaggedChild(treeNode x, TagType tag) 
  {
-    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 (get_field(tags_fix,tags_blen,node2tagpos(child)) == tag) // current child is labeled with tag of interest
-          return child; 
-       child = next_sibling(Par, child); // OK, let's try with the next child
-    }
-    return NULLT; // no such child was found  
- }
+   NULLT_IF(x==NULLT || isleaf(Par,x));
 
-
-treeNode XMLTree::SelectChild(treeNode x, TagType *tags, int ntags)
- {
-    int i;
-    treeNode child = first_child(Par, x);
-
-    while (child!=(treeNode)-1) {
-       TagType t = get_field(tags_fix, tags_blen, node2tagpos(child));
-       for (i=0; i<ntags; i++)
-          if (t==tags[i]) return child;
-       child = next_sibling(Par, child);
-    }
-    return NULLT;
+   treeNode child;   
+   child = first_child(Par, x); // starts at first child of node x
+   if (get_field(tags_fix,tags_blen,node2tagpos(child)) == tag)
+     return child;
+   else
+     return TaggedFollSibling(child,tag);
  }
 
-
 // TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.
-treeNode XMLTree::TaggedSibling(treeNode x, TagType tag)
- {
-    treeNode sibling = next_sibling(Par, x);
-   
-    while (sibling!=(treeNode)-1) {
-       if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest
-          return sibling; 
-       sibling = next_sibling(Par, sibling); // OK, let's try with the next sibling
-    }
-    return NULLT; // no such sibling was found   
- }
+treeNode XMLTree::TaggedFollSibling(treeNode x, TagType tag)
+{
+  NULLT_IF(x==NULLT);
+  treeNode sibling = next_sibling(Par, x); 
+  while (sibling != NULLT) {
+    if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest
+      return sibling; 
+    sibling = next_sibling(Par, sibling); // OK, let's try with the next sibling
+  }
+  return NULLT; // no such sibling was found   
+}
 
+treeNode XMLTree::SelectChild(treeNode x, std::unordered_set<int> *tags)
+{
+  
+  NULLT_IF(x==NULLT || isleaf(Par,x));
+  int i;
+  treeNode child = first_child(Par, x);  
+  TagType t = get_field(tags_fix, tags_blen, node2tagpos(child));
+  std::unordered_set<int>::const_iterator tagit = tags->find(t);
+  if (tagit != tags->end()) return child;  
+  return SelectFollSibling(child,tags);
+}
 
-treeNode XMLTree::SelectSibling(treeNode x, TagType *tags, int ntags)
- {
-    int i;
-    treeNode sibling = next_sibling(Par, x);
 
-    while (sibling!=(treeNode)-1) {
-       TagType t = get_field(tags_fix, tags_blen, node2tagpos(sibling));
-       for (i=0; i<ntags; i++)
-          if (t==tags[i]) return sibling;
-       sibling = next_sibling(Par, sibling);
-    }
-    return NULLT;    
+treeNode XMLTree::SelectFollSibling(treeNode x, std::unordered_set<int> *tags)
+{
+
+   NULLT_IF(x==NULLT);
+   int i;
+   TagType t;
+   treeNode sibling = next_sibling(Par, x);
+   std::unordered_set<int>::const_iterator tagit;
+   while (sibling != NULLT) {
+     t = get_field(tags_fix, tags_blen, node2tagpos(sibling));
+     tagit = tags->find(t);
+     if (tagit != tags->end()) return sibling;
+     sibling = next_sibling(Par, sibling);
+   }
+   return NULLT;    
  }
 
 
@@ -519,171 +491,36 @@ treeNode XMLTree::SelectSibling(treeNode x, TagType *tags, int ntags)
 // the subtree of x. Returns NULLT if there is none.
 treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) 
  {
-    treeNode y;
-    if (isleaf(Par,x))
-      return NULLT;
-
-    int s = (int) Tags->select_next(tag,node2tagpos(x));
-    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;
- }
-
-
-treeNode XMLTree::SelectDesc(treeNode x, TagType *tags, int ntags)
- {
-    int i;
-    treeNode min = NULLT;
-    treeNode fc = first_child(Par,x);
-    
-    for (i=0; i<ntags; i++) {
-       treeNode aux = TaggedDesc(x, tags[i]);
-       if (aux == fc) 
-          return fc;
-       else 
-          if ((min == (treeNode)NULLT) || (aux < min)) min = aux;
-    }
-    return min;
- }
-
-
-treeNode XMLTree::TaggedDescOnly(treeNode x,TagType *desctags, unsigned int dtlen)
- {
-    treeNode res, y;
-    if (isleaf(Par,x))
-       return NULLT;
-  
-    res=NULLT;
-    for (unsigned int i = 0; i < dtlen; i ++ ) {
-       y = TaggedDesc(x,desctags[i]);
-       res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;  
-    }
-  
-    return res;
- } 
-
-
-treeNode XMLTree::TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen,
-			      TagType *desctags, unsigned int dtlen) 
- {
-    treeNode fs,y,res;
-    TagType tag;
-
-    if (isleaf(Par,x))
-      return NULLT;
-  
-    res = NULLT;
-    fs = first_child(Par,x);
-    while (fs != NULLT) {
-       tag = get_field(tags_fix,tags_blen,node2tagpos(fs));
-        
-       /* Check for first_child */
-       for (unsigned int i = 0; i < ctlen; i++) {
-          if (childtags[i] == tag)
-	     return fs;
-       }
-    
-       for (unsigned int i = 0; i < dtlen; i++)
-          if (desctags[i] == tag)
-             return fs;  
-    
-       /* check in the descendants */
-       res = NULLT;
-       for (unsigned int i = 0; i < dtlen; i ++ ) {
-          /* maybe inline by hand */
-          y = TaggedDesc(fs,desctags[i]);
-         res = (res==NULLT || (y != NULLT) &&(y < res)) ? y : res;   
-       } 
-       if (res != NULLT)
-          return res;
-    
-       fs = next_sibling(Par,fs);
-    }
-    
-    return res;
-}
+   NULLT_IF(x==NULLT || isleaf(Par,x));
 
+   int s = (int) Tags->select_next(tag,node2tagpos(x));
+   NULLT_IF (s == -1);
 
-treeNode XMLTree::TaggedFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root)
- {
-    treeNode res,y,lim;
-    lim = find_close(Par,root);   
-    res=NULLT;
-    
-    for (unsigned int i = 0; i < ftlen; i ++ ) {
-       y = TaggedFoll(x,folltags[i]);
-       res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;
-    }
-  
-    return res < lim ? res : NULLT;
+   treeNode y = tagpos2node(s); // transforms the tag position into a node position
+   
+   return (is_ancestor(Par,x,y) ? y : NULLT);
  }
 
 
-treeNode XMLTree::TaggedDescOrFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root)
+treeNode XMLTree::SelectDesc(treeNode x, std::unordered_set<int> *tags)
  {
-    treeNode res,y,lim;
-    lim = find_close(Par,root);   
-    res=NULLT;
-  
-    for (unsigned int i = 0; i < ftlen; i++) {
-       int s = (int) Tags->select_next(folltags[i],node2tagpos(x));
-       if (s == -1) 
-          y = NULLT; // there is no such node
-       else {
-          y = tagpos2node(s); 
-	  if (y >= lim)
-	     y = NULLT;
-       }
-       res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;
-    }
-    
-    return res < lim ? res : NULLT;
-}
-
-
-// TaggedNext(x,tag): returns the first node tagged tag with larger preorder than x 
-// Returns NULLT if there is none.
-treeNode XMLTree::TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen,
-			     TagType *folltags, unsigned int flen,treeNode root)
- {
-   treeNode y,old_y,lim,res;
-   TagType tag;
-   if (x == NULLT || x == Root())
-     return NULLT;
-
-   lim = find_close(Par,root);   
-
-   res = NULLT;
-  
-   y = next_sibling(Par,x);
-   while (y != NULLT) {
-     tag = get_field(tags_fix,tags_blen,node2tagpos(y));
-     for(unsigned int i = 0; i < ctlen;i++)
-       if (childtags[i] == tag)
-	 return y;
-     
-     for(unsigned int i = 0; i < flen;i++)
-       if (folltags[i] == tag)
-	 return y;
-
-     res = TaggedBelow(y,NULL,0,folltags,flen);
-     if (res != NULLT)
-       return res;
-     
-     y = next_sibling(Par,y);
-   };
-   //Found nothing in the following sibling of x.
-   res = NULLT;
-   for(unsigned int i = 0; i < flen;i++){
-     y = TaggedFoll(x,folltags[i]);
-     res = (y!= x && (res == NULLT || (y != NULLT && y < res)))? y : res;
+   NULLT_IF (x ==NULLT || isleaf(Par,x));
+   int i;
+   treeNode min = NULLT;
+   treeNode fc = first_child(Par,x);
+   treeNode aux;
+   std::unordered_set<int>::const_iterator tagit;
+   for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
+     aux = TaggedDesc(x, (TagType) *tagit);
+     if (aux == fc) return fc;
+     if (aux == NULLT) continue;
+     if ((min == NULLT) || (aux < min)) min = aux;
    };
-  
-   return res < lim ? res : NULLT;   
+   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) 
@@ -709,60 +546,61 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag)
 // the subtree of x. Returns NULLT if there is none.
 treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
  {
-    if (x ==NULLT || x == Root())
-       return NULLT;
-    
-    int s = (int) Tags->select_next(tag,find_close(Par, x));               
-    if (s==-1) return NULLT;
-    else return tagpos2node(s);
+   NULLT_IF (x ==NULLT || x == Root());
+   
+   return tagpos2node(Tags->select_next(tag,find_close(Par, 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::TaggedFollBelow(treeNode x, TagType tag, treeNode root)
- {
-    if (x == NULLT || x == Root())
-       return NULLT;
-    
-    treeNode s = (treeNode) Tags->select_next(tag, find_close(Par, x));
-    
-    if (root == Root()) 
-      return s;
-    if (s == NULLT || s >= find_close(Par, root)) return NULLT;
-    return s;
- } 
+{
 
+  NULLT_IF (x == NULLT || x == Root());
+  
+  treeNode s = tagpos2node(Tags->select_next(tag, find_close(Par, x)));
+  
+  if (root == Root()) return s;
+  NULLT_IF (s == NULLT || s >= find_close(Par, root));
+  
+  return s;
+} 
 
-treeNode XMLTree::SelectFollBelow(treeNode x, TagType *tags, int ntags, treeNode ctx)
+/* 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::SelectFollBelow(treeNode x, std::unordered_set<int> *tags, treeNode root)
  {
-    int i;
-    treeNode min = NULLT;
-    treeNode fc = first_child(Par, x);
-    
-    for (i=0; i<ntags; i++) {
-       treeNode aux = TaggedFollBelow(x, tags[i], ctx);
-       if (aux == fc)
-          return fc;
-       else
-          if ((min == NULLT) || (aux < min)) min = aux;
-    }
-    return min;    
- }
-
 
+   NULLT_IF(x==NULLT || x==Root());
+   int i;
+   treeNode min = NULLT;
+   treeNode ns = next_sibling(Par, x);
+   treeNode aux;
+   std::unordered_set<int>::const_iterator tagit;
+   for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
 
-// TaggedFollowingSibling(x,tag): returns the first node tagged tag with larger preorder than x and not in
-// the subtree of x. Returns NULLT if there is none.
-treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) 
- {
-    treeNode ns = next_sibling(Par,x);
+     aux = tagpos2node(Tags->select_next(*tagit, find_close(Par, x)));
+     
+     // 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.
 
-    if (x == NULLT || x == Root() || ns == -1)
-      return NULLT;
+   if (root == Root()) return min;
+   // else check whether if is in below the ctx node
 
-    int s = (int) Tags->select_next(tag, node2tagpos(ns)-1);
-    if (s==-1) return NULLT;
-    else return tagpos2node(s);
+   NULLT_IF (min == NULLT || min >= find_close(Par, root));
+   
+   return min;
+   
  }
 
 
@@ -782,64 +620,29 @@ treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)
  }
 
 
-// PrevText(x): returns the document identifier of the text to the left 
-// of node x, or NULLT if x is the root node or the text is empty.
-// Assumes Doc ids start from 0.
-DocID XMLTree::PrevText(treeNode x) 
- {
-    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
-    }
- }
-
-// 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 (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
-    }
- }
 
 // 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 (!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)
+    return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0
+  else 
+    return (DocID) NULLT;
+  
+}
 
 // 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 (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
-    }
+   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 
@@ -847,64 +650,26 @@ int XMLTree::TextXMLId(DocID d)
 // preorder 0;
 int XMLTree::NodeXMLId(treeNode x) 
  {
-    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);
-    }
+   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 (d == NULLT)
-      return NULLT;
-    
-    int s;
-    // OJO : Kim : I added the d+1. before that, else branch was 
-    // EBVector->select1(d)
-    // and gave wrong results (I'm really poking a bear with a stick here).
-    if (indexing_empty_texts) s = d;
-    else s = EBVector->select1(d+1);
-    
-    if (inspect(Par,s) == CP) // is a closing parenthesis
-       return parent(Par, find_open(Par, s));
-    else // is an opening parenthesis
-       return (treeNode)s;
-     
- }
-treeNode XMLTree::PrevNode(DocID d) 
- {    
-    if (d == NULLT)
-      return NULLT;
-    
-    int s;
-    
-    if (indexing_empty_texts) s = d;
-    else s = EBVector->select1(d+1);
-    if (s == -1)
-      return NULLT;
-    
-    if (inspect(Par,s) == CP) // is a closing parenthesis
-      return find_open(Par, s);
-    else // is an opening parenthesis
-      return NULLT;
-    
+   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)
  {
-    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)-1; //ntagnames; //(TagType)NULLT; // tagname does not exists in the table
-    else return i;
+  
+   string s = (char *) tagname;
+   TagIdMapIT it = tIdMap->find(s);    
+   return (TagType) ((it != tIdMap->end()) ? it->second : -1);
+    
  }
 
 
@@ -913,19 +678,23 @@ TagType XMLTree::GetTagId(unsigned char *tagname)
 unsigned char *XMLTree::GetTagName(TagType tagid)
  {
     unsigned char *s;
-		if(tagid==(uint)-1) return NULL;
-    if (tagid >= ntagnames) return NULL; // invalid tag identifier
-    s = (unsigned char *)umalloc((strlen((const char *)TagName[tagid])+1)*sizeof(unsigned char));
-    strcpy((char *)s, (const char *)TagName[tagid]);
-    return s;
+    if ( tagid < 0 || tagid >= TagName->size())
+      return (unsigned char *) "<INVALID TAG>";
+    strcpy((char *)s, TagName->at(tagid).c_str());
+    
+    return (s == NULL ? (unsigned char*) "<INVALID TAG>" : s);
  }
 
 
 const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)
  {
-    if(tagid==(uint)-1) return NULL;
-    if (tagid >= ntagnames) return NULL; // invalid tag identifier
-    return ((const unsigned char*)  TagName[tagid]);
+
+   unsigned char *s;
+   if ( tagid < 0 || tagid >= TagName->size())
+     return (unsigned char *) "<INVALID TAG>";
+   
+   return (const unsigned char *) TagName->at(tagid).c_str();
+   
  }
 
 
@@ -934,13 +703,11 @@ TagType XMLTree::RegisterTag(unsigned char *tagname)
  {  
     TagType id = XMLTree::GetTagId(tagname);
     if (id == NULLT) {
-       id = ntagnames;
-       ntagnames = ntagnames + 1;    
-       TagName = (unsigned char **) urealloc(TagName,ntagnames*(sizeof(unsigned char*)));
-       TagName[id] = (unsigned char *) umalloc(sizeof(unsigned char)*strlen( (const char*) tagname)+1);
-       strcpy((char*)TagName[id], (const char *)tagname);  
-    }
-
+      string s = (char *) tagname;      
+      REGISTER_TAG(TagName,tIdMap,s);
+      
+    };
+    
     return id;
  }
 
diff --git a/XMLTree.h b/XMLTree.h
index ea9b938..8057773 100644
--- a/XMLTree.h
+++ b/XMLTree.h
@@ -21,6 +21,8 @@
 
 #ifndef XMLTREE_H_
 #define XMLTREE_H_
+#include <unordered_set>
+#include <unordered_map>
 #include "TextCollection/TextCollectionBuilder.h"
 #include <stdio.h>
 #include <stdlib.h>
@@ -32,7 +34,7 @@
 #undef Wminusone
 
 #include "bp.h"
-//#include "basics.h"
+
 #include <static_bitsequence.h>
 #include <alphabet_mapper.h>
 #include <static_sequence.h>
@@ -57,27 +59,54 @@ typedef struct {
    int max;
 } range;
 
-typedef struct nd {
-   uint position;
-   struct nd *next;
-} ListNode;
+// Encoding of the XML Document :
+// The following TAGs and IDs are fixed, "" is the tag of the root.
+// a TextNode is represented by a leaf <<$>></<$>> The DocId in the TextCollection
+// of that leaf is kept in a bit sequence.
+// a TextNode below an attribute is likewise represented by a leaf <<@$>><</@$>>
+// An element <e a1="v1" a2="v2" ... an="vn" > ...</e> the representation is:
+// <e><<@>> <<@>a1> <<$@>>DocID(v1)</<$@>></<@>a1> ... </<@>> .... </e>
+// Hence the attributes (if any) are always below the first child of their element,
+// as the children of a fake node <@>.
 
-typedef struct {
-   ListNode *first;
-   ListNode *last;
-} TagArrayEntry;
+
+#define DOCUMENT_OPEN_TAG ""
+#define DOCUMENT_TAG_ID 0
+#define ATTRIBUTE_OPEN_TAG "<@>"
+#define ATTRIBUTE_TAG_ID 1
+#define PCDATA_OPEN_TAG "<$>"
+#define PCDATA_TAG_ID 2
+#define ATTRIBUTE_DATA_OPEN_TAG "<@$>"
+#define ATTRIBUTE_DATA_TAG_ID 3
+#define DOCUMENT_CLOSE_TAG "/"
+#define ATTRIBUTE_CLOSE_TAG "/<@>"
+#define PCDATA_CLOSE_TAG "/<$>"
+#define ATTRIBUTE_DATA_CLOSE_TAG "/<@$>"
+
+
+
+typedef std::unordered_map<string,int> TagIdMap;
+typedef TagIdMap::const_iterator TagIdMapIT;
+
+#define REGISTER_TAG(v,h,t) do { (h)->insert(std::make_pair((t),(v)->size()));\
+    (v)->push_back(t); } while (false)
+
+
+class XMLTreeBuilder;
 
 class XMLTree {
+
+  // Only the builder can access the constructor
+  friend class XMLTreeBuilder;
+
+ private:
    /** Balanced parentheses representation of the tree */
    bp *Par;
  
    /** Mapping from tag identifer to tag name */  
-   unsigned char **TagName;
-   uint ntagnames;
+   vector<string> *TagName;
+   TagIdMap * tIdMap;
   
-   /** boolean flag indicating whether we are indexing empty texts or not */
-   bool indexing_empty_texts; 
-   
    /** Bit vector indicating with a 1 the positions of the non-empty texts. */
    static_bitsequence *EBVector;  
 		      
@@ -90,20 +119,20 @@ class XMLTree {
    TextCollection *Text;
 
    /** The texts in the XML document (cached for faster display) */
-   vector<string> CachedText;
-   
-   TagArrayEntry *TagArray;
+   vector<string> *CachedText;
 
    // Allows to disable the TextCollection for benchmarkin purposes
    bool disable_tc;
    
-public:
+
    /** Data structure constructors */
-   XMLTree() {;};
+   XMLTree(){;};
 
-   XMLTree(pb *par, uint npar, unsigned char **TN, uint ntagnames, uint *empty_texts_bmp, TagType *tags,
-           TextCollection *TC, vector<string> CT, bool indexing_empty_t, bool dis_tc);
- 
+   // non const pointer are freed by this method.
+  XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,
+	   TextCollection * const TC, vector<string> * const CT, bool dis_tc);
+
+public: 
    /** Data structure destructor */
    ~XMLTree();
    
@@ -167,13 +196,15 @@ public:
    /** FirstChild(x): returns the first child of node x, assuming it exists. 
     * Very fast in BP. */
    treeNode FirstChild(treeNode x);
-   
+   treeNode FirstElement(treeNode x);
+
    /** LastChild(x): returns the last child of node x.  */
    treeNode LastChild(treeNode x);
    
    /** NextSibling(x): returns the next sibling of node x, assuming it 
     * exists. */
    treeNode NextSibling(treeNode x);
+   treeNode NextElement(treeNode x);
    
    /** PrevSibling(x): returns the previous sibling of node x, assuming it 
     * exists. */
@@ -185,35 +216,21 @@ public:
     * among the children of node x until finding the desired child. */
    treeNode TaggedChild(treeNode x, TagType tag);
    
-   treeNode SelectChild(treeNode x, TagType *tags, int ntags);
+   treeNode SelectChild(treeNode x, std::unordered_set<int> * tags);
 
-   /** TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or 
+   /** TaggedFollSibling(x,tag): returns the first sibling of node x tagged tag, or 
     *  NULLT if there is none. */
-   treeNode TaggedSibling(treeNode x, TagType tag);
+   treeNode TaggedFollSibling(treeNode x, TagType tag);
    
-   treeNode SelectSibling(treeNode x, TagType *tags, int ntags);
+   treeNode SelectFollSibling(treeNode x, std::unordered_set<int> * tags);
 
    /** TaggedDesc(x,tag): returns the first node tagged tag with larger 
     * preorder than x and within the subtree of x. Returns NULT if there 
     * is none. */
    treeNode TaggedDesc(treeNode x, TagType tag);
 
-   treeNode SelectDesc(treeNode x, TagType *tags, int ntags);
+   treeNode SelectDesc(treeNode x, std::unordered_set<int> * tags);
 
-   treeNode TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen,
-				 TagType *desctags, unsigned int dtlen);
-   
-   treeNode TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen,
-				TagType *folltags, unsigned int flen,treeNode root);
-
-   treeNode TaggedDescOnly(treeNode x, TagType *desctags, unsigned int dtlen);
-   
-   treeNode TaggedDescOrFollOnly(treeNode x, TagType *folltags, unsigned int flen,
-			   treeNode root);
-
-   treeNode TaggedFollOnly(treeNode x, TagType *folltags, unsigned int flen,
-			   treeNode root);
-   
 
    /** TaggedPrec(x,tag): returns the first node tagged tag with smaller 
     * preorder than x and not an ancestor of x. Returns NULLT if there 
@@ -227,7 +244,7 @@ public:
 
    treeNode TaggedFollBelow(treeNode x, TagType tag,treeNode root);     
    
-   treeNode SelectFollBelow(treeNode x, TagType *tags, int ntags, treeNode ctx);
+   treeNode SelectFollBelow(treeNode x, std::unordered_set<int> * tags, treeNode root);
 
    /** TaggedFollowingSibling(x,tag) */
    treeNode TaggedFollowingSibling(treeNode x, TagType tag);
@@ -373,12 +390,13 @@ public:
    /** GetText(d): returns the text corresponding to document with
     * id d. */
    uchar* GetText(DocID d) {
-       return Text->GetText(d);
+     uchar * s = Text->GetText(d);
+     return (s[0] == 1 ? (uchar*)"" : s);
    }
 
    uchar* GetCachedText(DocID d) {
-     uchar * str = (uchar*) calloc(sizeof(char),(CachedText.at(d).size() + 1));
-     strcpy((char*) str,(const char*) CachedText.at(d).c_str());
+     uchar * str = (uchar*) calloc(sizeof(char),(CachedText->at(d).size() + 1));
+     strcpy((char*) str,(const char*) CachedText->at(d).c_str());
      return (uchar*) (str);
    }
    
@@ -387,11 +405,11 @@ public:
    }
    
    /** Save: saves XML tree data structure to file. */
-   void Save(unsigned char *filename);
+   void Save(int fd);
       
    /** Load: loads XML tree data structure from file. sample_rate_text 
     * indicates the sample rate for the text search data structure. */
-   static XMLTree *Load(unsigned char *filename, int sample_rate_text);   
+   static XMLTree *Load(int fd);   
 
    void insertTag(TagType tag, uint position);
    
diff --git a/XMLTreeBuilder.cpp b/XMLTreeBuilder.cpp
index 27bc862..138db9b 100644
--- a/XMLTreeBuilder.cpp
+++ b/XMLTreeBuilder.cpp
@@ -1,43 +1,46 @@
-
-#include "XMLTreeBuilder.h"
 #include "basics.h"
+#include "XMLTreeBuilder.h"
+
+
+XMLTreeBuilder::~XMLTreeBuilder(){
+  
+}
 
 // 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 XMLTreeBuilder::OpenDocument(bool empty_texts, int sample_rate_text, bool dtc)
  {
-    found_attributes = false;
     npar = 0;
     parArraySize = 1;
-    ntagnames = 4;    
     disable_tc = dtc;
     
-    indexing_empty_texts = empty_texts;
-    
+   
     par_aux = (pb *)umalloc(sizeof(pb)*parArraySize);
     
     tags_aux = (TagType *) umalloc(sizeof(TagType));
     
-    TagName = (unsigned char **) umalloc(4*sizeof(unsigned char*));
-    TagName[0] = (unsigned char *) umalloc(4*sizeof(unsigned char));
-    strcpy((char *) TagName[0], "<@>");
-    TagName[1] = (unsigned char *) umalloc(4*sizeof(unsigned char));
-    strcpy((char *) TagName[1], "<$>");
-    TagName[2] = (unsigned char *) umalloc(5*sizeof(unsigned char));
-    strcpy((char *) TagName[2], "/<@>");
-    TagName[3] = (unsigned char *) umalloc(5*sizeof(unsigned char));
-    strcpy((char *) TagName[3], "/<$>");
-
-    if (!indexing_empty_texts) 
-      empty_texts_aux = (unsigned int *)umalloc(sizeof(unsigned int));
-       
+    TagName = new vector<string>();
+    tIdMap = new std::unordered_map<string,int>();
+
+    REGISTER_TAG(TagName,tIdMap,DOCUMENT_OPEN_TAG);
+    REGISTER_TAG(TagName,tIdMap,ATTRIBUTE_OPEN_TAG);
+    REGISTER_TAG(TagName,tIdMap,PCDATA_OPEN_TAG);
+    REGISTER_TAG(TagName,tIdMap,ATTRIBUTE_DATA_OPEN_TAG);
+    REGISTER_TAG(TagName,tIdMap,DOCUMENT_CLOSE_TAG);
+    REGISTER_TAG(TagName,tIdMap,ATTRIBUTE_CLOSE_TAG);
+    REGISTER_TAG(TagName,tIdMap,PCDATA_CLOSE_TAG);
+    REGISTER_TAG(TagName,tIdMap,ATTRIBUTE_DATA_CLOSE_TAG);
+
+
+    CachedText = new vector<string>;
     if (disable_tc)
         TextBuilder = 0;
     else 
-        TextBuilder = new TextCollectionBuilder((unsigned)sample_rate_text);
+      TextBuilder = new TextCollectionBuilder((unsigned)sample_rate_text);
     Text = 0;
-    
+    empty_texts_aux = (unsigned int *)ucalloc(sizeof(unsigned int),1);
+    eta_size = sizeof(unsigned int);
     return 1;  // indicates success in the initialization of the data structure
  }
 
@@ -47,10 +50,10 @@ int XMLTreeBuilder::OpenDocument(bool empty_texts, int sample_rate_text, bool dt
 // the data structure can be queried.
 XMLTree *XMLTreeBuilder::CloseDocument()
  {    
-    // closing parenthesis for the tree root
-    par_aux = (pb *)urealloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));
-    setbit(par_aux, npar, CP);
-    npar++;
+    //closing parenthesis for the tree root
+    //par_aux = (pb *)urealloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));
+    //setbit(par_aux, npar, CP);
+    //npar++;
     
     // makes the text collection static
     if (!disable_tc) {
@@ -60,9 +63,16 @@ XMLTree *XMLTreeBuilder::CloseDocument()
        delete TextBuilder;
        TextBuilder = 0;
     }
-
-    XMLTree *T = new XMLTree(par_aux, npar, TagName, ntagnames, empty_texts_aux, tags_aux, 
-              Text, CachedText, indexing_empty_texts, disable_tc);
+    
+    XMLTree *T = new XMLTree(par_aux,
+			     npar, 
+			     TagName,
+			     tIdMap,
+			     empty_texts_aux,                // freed by the constructor
+			     tags_aux,                       //freed by the constructor
+			     Text,
+			     CachedText,
+			     disable_tc);
     return T; 
  }
 
@@ -70,7 +80,7 @@ XMLTree *XMLTreeBuilder::CloseDocument()
 // 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 XMLTreeBuilder::NewOpenTag(unsigned char *tagname)
+int XMLTreeBuilder::NewOpenTag(string tagname)
  {
     int i;
     
@@ -81,31 +91,22 @@ int XMLTreeBuilder::NewOpenTag(unsigned char *tagname)
     }
     
     setbit(par_aux,npar,OP);  // marks a new opening parenthesis
+    
+    TagIdMapIT tag_id = tIdMap->find(tagname);
+   
+    if (tag_id == tIdMap->end()){
+      REGISTER_TAG(TagName,tIdMap,tagname);
+      i = TagName->size() - 1;
+    }
+    else
+      i = tag_id->second;
 
-    // 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 **)urealloc(TagName, sizeof(char *)*(ntagnames+1));
-       
-       if (!TagName) {
-          fprintf(stderr, "Error: not enough memory\n");
-          return NULLT;
-       }
-       
-       ntagnames++;
-       TagName[i] = (unsigned char *)umalloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1));
-       strcpy((char *)TagName[i], (const char *)tagname);
-    } 
+    if (tagname.compare(PCDATA_OPEN_TAG) == 0 ||
+	tagname.compare(ATTRIBUTE_DATA_OPEN_TAG) == 0){
+    };
+    
     tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1));
-
+    
     tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags
     
     npar++;
@@ -117,7 +118,7 @@ int XMLTreeBuilder::NewOpenTag(unsigned char *tagname)
 // 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 XMLTreeBuilder::NewClosingTag(unsigned char *tagname)
+int XMLTreeBuilder::NewClosingTag(string tagname)
  {
     int i;
     
@@ -128,20 +129,17 @@ int XMLTreeBuilder::NewClosingTag(unsigned char *tagname)
     }
     
     setbit(par_aux,npar,CP);  // marks a new closing parenthesis
+    
+    tagname.insert(0,"/");
 
-    // 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]+1))==0) && (TagName[i][0]=='/')) break;
- 
-    if (i==ntagnames) { // the tag is a new one, then we insert it
-       TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1));
-       
-       ntagnames++;
-       TagName[i] = (unsigned char *)umalloc(sizeof(char)*(strlen((const char *)tagname)+2));
-       TagName[i][0] = '/';
-       strcpy((char *)&(TagName[i][1]), (const char *)tagname);
-    } 
+    TagIdMapIT tag_id = tIdMap->find(tagname);    
+
+    if (tag_id == tIdMap->end()){
+      REGISTER_TAG(TagName,tIdMap,tagname);
+      i = TagName->size() - 1;
+    }
+    else
+      i = tag_id->second;
 
     tags_aux = (TagType *)urealloc(tags_aux, sizeof(TagType)*(npar + 1));
 
@@ -156,41 +154,24 @@ int XMLTreeBuilder::NewClosingTag(unsigned char *tagname)
 // 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 XMLTreeBuilder::NewText(unsigned char *s)
+int XMLTreeBuilder::NewText(string text)
  {
-    if (disable_tc) {
-      XMLTreeBuilder::NewEmptyText();
-      return 1;
-    }
-
-    if (!indexing_empty_texts) {
-       empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));
-              bitset(empty_texts_aux, npar-1);  // marks the non-empty text with a 1 in the bit vector
-    }
-    
-    TextBuilder->InsertText(s);
-    string cpps = (char*) s;
-    CachedText.push_back(cpps); 
-    
-    return 1; // success
+   if (!disable_tc) {
+     if  (text.empty())
+       TextBuilder->InsertText((uchar *)"\001");
+     else
+       TextBuilder->InsertText((uchar *) text.c_str());
+   };
+
+   CachedText->push_back(text); 
+   int n_eta_size = sizeof(uint)*(1+(npar-1)/(8*sizeof(uint)));
+   //see basics.h, recalloc resizes and sets the new area to 0.
+   
+   empty_texts_aux = (uint *)urecalloc(empty_texts_aux,eta_size,n_eta_size);
+   eta_size = n_eta_size;
+   bitset(empty_texts_aux, npar-1);  // marks the non-empty text with a 1 in the bit vector
+
+   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 XMLTreeBuilder::NewEmptyText() 
- {
-    unsigned char c = 0;
-
-    if (!indexing_empty_texts) {
-       empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));
-       
-       bitclean(empty_texts_aux, npar-1);  // marks the empty text with a 0 in the bit vector
-    }
-    else TextBuilder->InsertText(&c); // we insert the empty text just in case we index all the texts
-    
-    return 1; // success    
- }
 
diff --git a/XMLTreeBuilder.h b/XMLTreeBuilder.h
index 38d81ba..336ca2d 100644
--- a/XMLTreeBuilder.h
+++ b/XMLTreeBuilder.h
@@ -21,6 +21,7 @@
 
 #ifndef XMLTREEBUILDER_H_
 #define XMLTREEBUILDER_H_
+#include <unordered_map>
 #include "TextCollection/TextCollectionBuilder.h"
 #include <stdio.h>
 #include <stdlib.h>
@@ -31,8 +32,9 @@
 #undef WW
 #undef Wminusone
 
-#include "bp.h"
+
 #include "XMLTree.h"
+#include "bp.h"
 #include <static_bitsequence.h>
 #include <alphabet_mapper.h>
 #include <static_sequence.h>
@@ -47,6 +49,7 @@ using SXSI::TextCollectionBuilder;
 #define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W)))
 
 
+
 class XMLTreeBuilder {
   
    /** Array containing the balanced parentheses sequence */
@@ -55,9 +58,8 @@ class XMLTreeBuilder {
    int npar;
 
    /** Mapping from tag identifer to tag name */  
-   unsigned char **TagName;
-   int ntagnames;
-
+   vector<string> *TagName;
+   TagIdMap * tIdMap;
    /** Array containing the sequence of tags */
    TagType *tags_aux;
    
@@ -66,19 +68,11 @@ class XMLTreeBuilder {
    TextCollection *Text;
    
    /** The texts in the XML document (cached for faster display) */
-   vector<string> CachedText;
 
-   /** boolean flag indicating whether we are indexing empty texts or not */
-   bool indexing_empty_texts; 
-   unsigned int *empty_texts_aux;
-
-   // The TagName array should always contains two special tags
-   // <@> for attributes and <$> for PCDATA.
-   // <$> can never be in a document (since we handle the text differently)
-   // but <@> can be returned by the parser. This boolean is needed for the construction
-   // of the Tag bitmap to know if <@> must be taken into account or not
-   bool found_attributes;
+   vector<string> *CachedText;
 
+   unsigned int *empty_texts_aux;
+   int eta_size;
    // Allows to disable the TextCollection for benchmarkin purposes
    bool disable_tc;
 
@@ -88,9 +82,8 @@ public:
 
    ~XMLTreeBuilder();
    
-   /** OpenDocument(empty_texts,sample_rate_text,dtc): initilizes the construction
-    * of the data structure for the XML document. Parameter empty_texts 
-    * indicates whether we index empty texts in document or not. Parameter 
+   /** OpenDocument(sample_rate_text,dtc): initilizes the construction
+    * of the data structure for the XML document.  Parameter 
     * sample_rate_text indicates the sampling rate for the text searching data
     * structures (small values get faster searching but a bigger space 
     * requirement). dtc disable the use of the TextCollection
@@ -108,24 +101,23 @@ public:
    /** 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 error. */
-   int NewOpenTag(unsigned char *tagname);
+   int NewOpenTag(string tagname);
    
    /** 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 error. */
-   int NewClosingTag(unsigned char *tagname);
+   int NewClosingTag(string tagname);
  
-   /** NewText(s): indicates the event of finding a new (non-empty) text s in 
+   /** NewText(s): indicates the event of finding a new 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 NewText(unsigned char *s);
-
-   /** 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 NewEmptyText();
+    * Returns a non-zero value upon success, NULLT in case of error. 
+    * If the string is empty, which is legal in attributes, then
+    * the string the sequence '\0x01\0x00' is inserted in the TextCollection
+    * It is ok to do so since a non printable character cannot occur in an XML document
+    */
+   int NewText(string text);
+
+
 };
 #endif
 
diff --git a/basics.h b/basics.h
index 273aa1d..7449c11 100644
--- a/basics.h
+++ b/basics.h
@@ -1,15 +1,21 @@
 #ifndef BASICS_H
 #define BASICS_H
 
+#include <string>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h> // for memset
+#include <sys/types.h>
+#include <unistd.h>
+#include <errno.h>
+
 
 inline void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream)
  {
     size_t res;
     res = fread(ptr,size,nmemb,stream);
     if (res < nmemb)
-       throw "ufread I/O error";
+      throw ("ufread I/O error" );
     return;
  }
 
@@ -30,6 +36,21 @@ inline void *urealloc(void *ptr, size_t size)
        throw std::bad_alloc();
     return dest;
  }
+// realloc and set to 0
+inline void *urecalloc(void *ptr, size_t o_size, size_t n_size)
+ {
+   if (o_size == n_size)
+     return ptr;
+   
+    void *dest = realloc(ptr,n_size);
+    //don't fail if we requested size 0
+    if (dest == NULL && n_size > 0 )
+      throw std::bad_alloc();
+    // Initialize the new area with 0
+    void * n_area_start = &(((char*) dest)[o_size]);
+    memset(n_area_start,0, n_size - o_size);
+    return dest;
+ }
 
 inline void *ucalloc(size_t nmemb, size_t size)
  {