X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=61f6a4d30b0223a246f2656838f40cc1240c7546;hb=235e3214904e390d2f101c5d5bf7def98745b132;hp=ffdf5d03a11c565eaf369cc6900189e1a37ca14d;hpb=aa6692a9fd2badf8e8e686b92075f041dc03bbef;p=SXSI%2FXMLTree.git

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;
  }