XMLTree.cpp

   1 #include "basics.h"\r
   2 #include <cstring>\r
   3 #include <sstream>\r
   4 #include "XMLTree.h"\r
   5 #include <sys/time.h>\r
   6 #include <time.h>\r
   7 #include <sys/stat.h> \r
   8 #include <unistd.h>\r
   9 \r
  10 static double tLoading = 0;\r
  11 \r
  12 static unsigned int cLoading = 0;\r
  13 static struct timeval tmpv1;\r
  14 static struct timeval tmpv2;\r
  15 static string mem1;\r
  16 static string mem2;\r
  17 \r
  18 void read_procmem(string& memstr) {\r
  19   std::string buf;\r
  20   pid_t pid = getpid();\r
  21   std::stringstream path;\r
  22   path <<  "/proc/" << pid << "/status";\r
  23   std::ifstream infile;\r
  24   infile.open (path.str().c_str(), std::ifstream::in);\r
  25   while (infile.good()){\r
  26     getline(infile,buf);\r
  27     if (infile.eof()) {\r
  28       memstr = "Could not read memory";\r
  29       return;\r
  30     };\r
  31     int idx = buf.find("VmRSS");\r
  32     if (idx == 0){\r
  33       memstr = buf;\r
  34       return;\r
  35     };\r
  36   };\r
  37   memstr = "Could not read memory";\r
  38   return;\r
  39 \r
  40 }\r
  41 \r
  42 #define STARTTIMER()   do {                                             \\r
  43   gettimeofday(&tmpv1,NULL);                                            \\r
  44   read_procmem(mem1);                                                   \\r
  45   } while (0)                                                           \\r
  46 \r
  47 #define STOPTIMER(x)   do {                                             \\r
  48     read_procmem(mem2);                                                 \\r
  49     gettimeofday(&tmpv2,NULL);                                          \\r
  50     (t##x) = ((tmpv2.tv_sec  - tmpv1.tv_sec) * 1000000.0 +              \\r
  51                        (tmpv2.tv_usec  - tmpv1.tv_usec))/1000.0;        \\r
  52     (c##x)= (c##x)+1;                                                   \\r
  53   } while (0)\r
  54 \r
  55 #define PRINTTIME(s,x) do {                                             \\r
  56     std::cerr << (s) << " : " << (t##x) << "ms" << std::endl;           \\r
  57     std::cerr << "Mem use before: " << mem1 << std::endl;               \\r
  58     std::cerr << "Mem use after: " << mem2 << std::endl;                \\r
  59     std::cerr.flush();                                                  \\r
  60   } while (0)                                                           \\r
  61 \r
  62 \r
  63 // functions to convert tag positions to the corresponding tree node and viceversa. \r
  64 // These are implemented in order to be able to change the tree and Tags representations, \r
  65 // without affecting the code so much.\r
  66 // Current implementation corresponds to balanced-parentheses representation for\r
  67 // the tree, and storing 2 tags per tree node (opening and closing tags).\r
  68 \r
  69 // tag position -> tree node\r
  70 inline treeNode tagpos2node(int t) \r
  71  {\r
  72     return (treeNode) t;\r
  73  }\r
  74 \r
  75 // tree node -> tag position\r
  76 inline int node2tagpos(treeNode x) \r
  77 {\r
  78   return (int)x;\r
  79 }\r
  80 \r
  81 // returns NULLT if the test is true\r
  82 #define NULLT_IF(x)  do { if (x) return NULLT; } while (0)\r
  83 \r
  84 \r
  85 XMLTree::XMLTree( pb * const par, uint npar,  vector<string> * const TN,  TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,\r
  86             TextCollection * const TC, bool dis_tc)\r
  87 \r
  88  {\r
  89     // creates the data structure for the tree topology\r
  90     Par = (bp *)umalloc(sizeof(bp));\r
  91     bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0);    \r
  92    \r
  93     // creates structure for tags\r
  94 \r
  95     TagName = (vector<string>*)TN;\r
  96     tIdMap = (TagIdMap *) tim;\r
  97     \r
  98     uint max_tag = TN->size() - 1;\r
  99       \r
 100     static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray();\r
 101     alphabet_mapper *am = new alphabet_mapper_none();\r
 102     Tags = new static_sequence_bs((uint*)tags,npar,am,bmb);\r
 103     \r
 104     cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl;\r
 105 \r
 106     tags_blen = bits(max_tag);\r
 107     tags_len = (uint)npar;\r
 108     tags_fix = new uint[uint_len(tags_blen,tags_len)];\r
 109     for(uint i=0;i<(uint)npar;i++)\r
 110        set_field(tags_fix,tags_blen,i,tags[i]);\r
 111 \r
 112     delete bmb;    \r
 113     free(tags);\r
 114     tags = NULL;\r
 115     \r
 116     Text = (TextCollection*) TC;\r
 117 \r
 118 \r
 119     EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32);\r
 120     free(empty_texts_bmp);\r
 121     empty_texts_bmp = NULL;\r
 122 \r
 123     \r
 124     disable_tc = dis_tc;\r
 125  }\r
 126 \r
 127 \r
 128 // ~XMLTree: frees memory of XML tree.\r
 129 XMLTree::~XMLTree() \r
 130  { \r
 131     int i;\r
 132 \r
 133     destroyTree(Par);\r
 134     free(Par); // frees the memory of struct Par\r
 135    \r
 136     delete tIdMap;\r
 137     tIdMap = NULL;\r
 138     \r
 139     delete TagName;\r
 140     TagName = NULL;\r
 141     \r
 142     delete Tags;\r
 143     Tags = NULL;\r
 144 \r
 145     delete Text; \r
 146     Text = NULL;\r
 147 \r
 148     delete EBVector;\r
 149     EBVector = NULL;\r
 150 \r
 151 \r
 152  }\r
 153 \r
 154 \r
 155 void XMLTree::print_stats() \r
 156  {\r
 157     uint total_space = Tags->size()+sizeof(static_sequence*);\r
 158     total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len));\r
 159     cout << "Space usage for XMLTree:" << endl\r
 160          << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl\r
 161          << " - tags access array:    " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl\r
 162          << " ... add Diego structures ... " << endl\r
 163          << " *total* " << total_space << endl;\r
 164  }\r
 165 \r
 166 // Save: saves XML tree data structure to file. \r
 167 void XMLTree::Save(int fd) \r
 168  {\r
 169     FILE *fp;\r
 170     char filenameaux[1024];\r
 171     int i;\r
 172 \r
 173     fp = fdopen(fd, "wa");\r
 174     // first stores the tree topology\r
 175     saveTree(Par, fp);\r
 176 \r
 177     // stores the table with tag names\r
 178     int ntags = TagName->size();\r
 179 \r
 180     ufwrite(&ntags, sizeof(int), 1, fp);\r
 181     for (i = 0; i<ntags;i++)\r
 182       fprintf(fp, "%s\n",TagName->at(i).c_str());\r
 183     \r
 184 \r
 185     // stores the tags\r
 186     Tags->save(fp);\r
 187     ufwrite(&tags_blen,sizeof(uint),1,fp);\r
 188     ufwrite(&tags_len,sizeof(uint),1,fp);\r
 189     ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp);\r
 190 \r
 191     // flags \r
 192     ufwrite(&disable_tc, sizeof(bool),1,fp);\r
 193     \r
 194     //text positions\r
 195     EBVector->save(fp);\r
 196     \r
 197     // stores the texts   \r
 198     if (!disable_tc) {\r
 199       Text->Save(fp);\r
 200     };\r
 201 \r
 202 \r
 203  }\r
 204 \r
 205 \r
 206 // Load: loads XML tree data structure from file. Returns\r
 207 // a pointer to the loaded data structure\r
 208 XMLTree *XMLTree::Load(int fd) \r
 209  {\r
 210     FILE *fp;\r
 211     char buffer[1024];\r
 212     XMLTree *XML_Tree;\r
 213     int i;\r
 214 \r
 215 \r
 216 \r
 217     fp = fdopen(fd, "r");\r
 218 \r
 219     XML_Tree = new XMLTree();\r
 220     STARTTIMER();\r
 221     // Load the tree structure\r
 222     XML_Tree->Par = (bp *)umalloc(sizeof(bp));\r
 223 \r
 224     loadTree(XML_Tree->Par, fp); \r
 225     STOPTIMER(Loading);\r
 226     PRINTTIME("Loading parenthesis struct", Loading);\r
 227     STARTTIMER();\r
 228 \r
 229     XML_Tree->TagName = new vector<string>();\r
 230     XML_Tree->tIdMap = new std::unordered_map<string,int>();\r
 231     \r
 232     string s;\r
 233     int ntags;\r
 234     \r
 235     // Load the tag names\r
 236     ufread(&ntags, sizeof(int), 1, fp);\r
 237 \r
 238     for (i=0; i<ntags;i++) {\r
 239       char * r = fgets(buffer,1023,fp);\r
 240        if (r==NULL)\r
 241          throw "Cannot read tag list";\r
 242        s = (const char*) buffer;\r
 243        // remove the trailing \n\r
 244        s.erase(s.size()-1);       \r
 245        XML_Tree->TagName->push_back(s);\r
 246        XML_Tree->tIdMap->insert(std::make_pair(s,i));\r
 247        \r
 248     };\r
 249     STOPTIMER(Loading);\r
 250     PRINTTIME("Loading tag names struct", Loading);\r
 251     STARTTIMER();\r
 252 \r
 253     // loads the tag structure\r
 254     XML_Tree->Tags = static_sequence::load(fp);\r
 255     ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);\r
 256     ufread(&XML_Tree->tags_len,sizeof(uint),1,fp);\r
 257     XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)];\r
 258     ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp);\r
 259 \r
 260     // TODO ask francisco about this\r
 261     /// FIXME:UGLY tests!\r
 262     uint * seq = new uint[XML_Tree->tags_len];\r
 263     for(uint i=0;i<XML_Tree->tags_len;i++)\r
 264       seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i);\r
 265     //cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl;\r
 266     XML_Tree->Tags->test(seq,XML_Tree->tags_len);\r
 267     delete [] seq;\r
 268     /// End ugly tests\r
 269     \r
 270     STOPTIMER(Loading);\r
 271     PRINTTIME("Loading tag struct", Loading);\r
 272     STARTTIMER();\r
 273 \r
 274     // loads the flags\r
 275     \r
 276     ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);\r
 277 \r
 278     XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);\r
 279 \r
 280 \r
 281     STOPTIMER(Loading);\r
 282     PRINTTIME("Loading text bitvector struct", Loading);\r
 283     STARTTIMER();\r
 284 \r
 285     // Not used  \r
 286     int sample_rate_text = 64;\r
 287     // loads the texts\r
 288     if (!XML_Tree->disable_tc){\r
 289       XML_Tree->Text = TextCollection::Load(fp,sample_rate_text);\r
 290     }\r
 291     else XML_Tree->Text = NULL;\r
 292     STOPTIMER(Loading);\r
 293     PRINTTIME("Loading TextCollection", Loading);\r
 294     STARTTIMER();\r
 295 \r
 296     return XML_Tree;\r
 297  }\r
 298 \r
 299 \r
 300 // root(): returns the tree root.\r
 301 inline treeNode XMLTree::Root() \r
 302  {\r
 303    return 0; //root_node(Par);\r
 304  }\r
 305 \r
 306 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.\r
 307 int XMLTree::SubtreeSize(treeNode x) \r
 308  {\r
 309     return subtree_size(Par, x);\r
 310  }\r
 311 \r
 312 // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.\r
 313 int XMLTree::SubtreeTags(treeNode x, TagType tag) \r
 314  {\r
 315     if (x == Root())\r
 316       x = first_child(Par,x);\r
 317     \r
 318 \r
 319     int s = x + 2*subtree_size(Par, x) - 1;\r
 320  \r
 321     return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1);\r
 322  }\r
 323 \r
 324 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation\r
 325 // this is just a bit inspection.\r
 326 bool XMLTree::IsLeaf(treeNode x) \r
 327  {\r
 328     return isleaf(Par, x);\r
 329  } \r
 330 \r
 331 // IsAncestor(x,y): returns whether node x is ancestor of node y.\r
 332 bool XMLTree::IsAncestor(treeNode x, treeNode y) \r
 333  {\r
 334     return is_ancestor(Par, x, y);\r
 335  }\r
 336 \r
 337 // IsChild(x,y): returns whether node x is parent of node y.\r
 338 bool XMLTree::IsChild(treeNode x, treeNode y) \r
 339  {\r
 340     if (!is_ancestor(Par, x, y)) return false;\r
 341     return depth(Par, x) == (depth(Par, y) + 1);\r
 342  }\r
 343 \r
 344 // IsFirstChild(x): returns whether node x is the first child of its parent.\r
 345 bool XMLTree::IsFirstChild(treeNode x)\r
 346  {\r
 347     return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));\r
 348  }\r
 349 \r
 350 \r
 351 // NumChildren(x): number of children of node x. Constant time with the data structure\r
 352 // of Sadakane.\r
 353 int XMLTree::NumChildren(treeNode x) \r
 354  {\r
 355     return degree(Par, x);\r
 356  }\r
 357 \r
 358 // ChildNumber(x): returns i if node x is the i-th children of its parent.\r
 359 int XMLTree::ChildNumber(treeNode x) \r
 360  {\r
 361     return child_rank(Par, x);\r
 362  }\r
 363 \r
 364 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.\r
 365 int XMLTree::Depth(treeNode x) \r
 366  {\r
 367     return depth(Par, x);\r
 368  }\r
 369 \r
 370 // Preorder(x): returns the preorder number of node x, just counting the tree\r
 371 // nodes (i.e., tags, it disregards the texts in the tree).\r
 372 int XMLTree::Preorder(treeNode x) \r
 373  {\r
 374     return preorder_rank(Par, x);\r
 375  }\r
 376 \r
 377 // Postorder(x): returns the postorder number of node x, just counting the tree\r
 378 // nodes (i.e., tags, it disregards the texts in the tree).\r
 379 int XMLTree::Postorder(treeNode x) \r
 380  {\r
 381     return postorder_rank(Par, x);\r
 382  }\r
 383 \r
 384 // Tag(x): returns the tag identifier of node x.\r
 385 TagType XMLTree::Tag(treeNode x) \r
 386  {\r
 387     return get_field(tags_fix,tags_blen,node2tagpos(x));\r
 388  }\r
 389 \r
 390 // DocIds(x): returns the range of text identifiers that descend from node x.\r
 391 // returns {NULLT, NULLT} when there are no texts descending from x.\r
 392 range XMLTree::DocIds(treeNode x) \r
 393  {\r
 394     range r;\r
 395     if (x == NULLT) {\r
 396        r.min = NULLT;\r
 397        r.max = NULLT;\r
 398        return r;\r
 399     };\r
 400         \r
 401     \r
 402     int min = EBVector->rank1(x-1);                          \r
 403     int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); \r
 404     if (min==max) { // range is empty, no texts within the subtree of x\r
 405       r.min = NULLT;\r
 406       r.max = NULLT;\r
 407     }\r
 408     else { // the range is non-empty, there are texts within the subtree of x\r
 409       r.min = min+1;\r
 410       r.max = max;\r
 411     }\r
 412     return r;\r
 413 \r
 414  }\r
 415 \r
 416 // Parent(x): returns the parent node of node x.\r
 417 treeNode XMLTree::Parent(treeNode x) \r
 418  {\r
 419     if (x == Root())\r
 420       return NULLT;\r
 421     else\r
 422       return parent(Par, x);\r
 423  }\r
 424 \r
 425 // Child(x,i): returns the i-th child of node x, assuming it exists.\r
 426 treeNode XMLTree::Child(treeNode x, int i) \r
 427 {\r
 428     if (i <= OPTD) return naive_child(Par, x, i);\r
 429     else return child(Par, x, i);\r
 430 }\r
 431 \r
 432 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
 433 treeNode XMLTree::FirstChild(treeNode x) \r
 434  {\r
 435    NULLT_IF(x==NULLT);\r
 436    return first_child(Par, x);\r
 437  }\r
 438 \r
 439 treeNode XMLTree::FirstElement(treeNode x) \r
 440  {\r
 441    NULLT_IF(x==NULLT);\r
 442    treeNode fc = first_child(Par, x);\r
 443    //<$> is 2\r
 444    return ((fc == NULLT || Tag(fc) != PCDATA_TAG_ID) ? fc : next_sibling(Par,fc));\r
 445 \r
 446  }\r
 447 \r
 448 treeNode XMLTree::NextElement(treeNode x) \r
 449 {\r
 450    NULLT_IF(x==NULLT);\r
 451    treeNode ns = next_sibling(Par, x);\r
 452    return ((ns == NULLT || Tag(ns) != PCDATA_TAG_ID) ? ns : next_sibling(Par,ns));\r
 453 }\r
 454 \r
 455 // LastChild(x): returns the last child of node x.\r
 456 treeNode XMLTree::LastChild(treeNode x)\r
 457  {\r
 458    NULLT_IF(x==NULLT || x == Root() || isleaf(Par,x));\r
 459    return find_open(Par, find_close(Par, x)-1);\r
 460  }\r
 461 \r
 462 \r
 463 // NextSibling(x): returns the next sibling of node x, assuming it exists.\r
 464 treeNode XMLTree::NextSibling(treeNode x) \r
 465  {\r
 466    NULLT_IF(x==NULLT || x == Root() );\r
 467    return next_sibling(Par, x);\r
 468  }\r
 469 \r
 470 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
 471 treeNode XMLTree::PrevSibling(treeNode x) \r
 472  {\r
 473    NULLT_IF(x==NULLT || x == Root());\r
 474    return prev_sibling(Par, x);\r
 475  }\r
 476 \r
 477 // TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none.\r
 478 // Because of the balanced-parentheses representation of the tree, this operation is not supported\r
 479 // efficiently, just iterating among the children of node x until finding the desired child.\r
 480 treeNode XMLTree::TaggedChild(treeNode x, TagType tag) \r
 481  {\r
 482    \r
 483    NULLT_IF(x==NULLT || isleaf(Par,x));\r
 484 \r
 485    treeNode child;   \r
 486    child = first_child(Par, x); // starts at first child of node x\r
 487    if (get_field(tags_fix,tags_blen,node2tagpos(child)) == tag)\r
 488      return child;\r
 489    else\r
 490      return TaggedFollSibling(child,tag);\r
 491  }\r
 492 \r
 493 // TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.\r
 494 treeNode XMLTree::TaggedFollSibling(treeNode x, TagType tag)\r
 495 {\r
 496   NULLT_IF(x==NULLT);\r
 497   treeNode sibling = next_sibling(Par, x); \r
 498   while (sibling != NULLT) {\r
 499     if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest\r
 500       return sibling; \r
 501     sibling = next_sibling(Par, sibling); // OK, let's try with the next sibling\r
 502   }\r
 503   return NULLT; // no such sibling was found   \r
 504 }\r
 505 \r
 506 treeNode XMLTree::SelectChild(treeNode x, std::unordered_set<int> *tags)\r
 507 {\r
 508   \r
 509   NULLT_IF(x==NULLT || isleaf(Par,x));\r
 510   int i;\r
 511   treeNode child = first_child(Par, x);  \r
 512   TagType t = get_field(tags_fix, tags_blen, node2tagpos(child));\r
 513   std::unordered_set<int>::const_iterator tagit = tags->find(t);\r
 514   if (tagit != tags->end()) return child;  \r
 515   return SelectFollSibling(child,tags);\r
 516 }\r
 517 \r
 518 \r
 519 treeNode XMLTree::SelectFollSibling(treeNode x, std::unordered_set<int> *tags)\r
 520 {\r
 521 \r
 522    NULLT_IF(x==NULLT);\r
 523    int i;\r
 524    TagType t;\r
 525    treeNode sibling = next_sibling(Par, x);\r
 526    std::unordered_set<int>::const_iterator tagit;\r
 527    while (sibling != NULLT) {\r
 528      t = get_field(tags_fix, tags_blen, node2tagpos(sibling));\r
 529      tagit = tags->find(t);\r
 530      if (tagit != tags->end()) return sibling;\r
 531      sibling = next_sibling(Par, sibling);\r
 532    }\r
 533    return NULLT;    \r
 534  }\r
 535 \r
 536 \r
 537 // TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within\r
 538 // the subtree of x. Returns NULLT if there is none.\r
 539 treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) \r
 540  {\r
 541    NULLT_IF(x==NULLT || isleaf(Par,x));\r
 542 \r
 543    int s = (int) Tags->select_next(tag,node2tagpos(x));\r
 544    NULLT_IF (s == -1);\r
 545 \r
 546    treeNode y = tagpos2node(s); // transforms the tag position into a node position\r
 547    \r
 548    return (is_ancestor(Par,x,y) ? y : NULLT);\r
 549  }\r
 550 \r
 551 \r
 552 treeNode XMLTree::SelectDesc(treeNode x, std::unordered_set<int> *tags)\r
 553  {\r
 554    NULLT_IF (x ==NULLT || isleaf(Par,x));\r
 555    int i;\r
 556    treeNode min = NULLT;\r
 557    treeNode fc = first_child(Par,x);\r
 558    treeNode aux;\r
 559    std::unordered_set<int>::const_iterator tagit;\r
 560    for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
 561      aux = TaggedDesc(x, (TagType) *tagit);\r
 562      if (aux == fc) return fc;\r
 563      if (aux == NULLT) continue;\r
 564      if ((min == NULLT) || (aux < min)) min = aux;\r
 565    };\r
 566    return min;\r
 567  }\r
 568 \r
 569 \r
 570 \r
 571 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an\r
 572 // ancestor of x. Returns NULLT if there is none.\r
 573 treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) \r
 574  {    \r
 575     int r, s;\r
 576     treeNode node_s, root;\r
 577     r = (int)Tags->rank(tag, node2tagpos(x)-1);\r
 578     if (r==0) return NULLT; // there is no such node.\r
 579     s = (int)Tags->select(tag, r);\r
 580     root = root_node(Par);\r
 581     node_s = tagpos2node(s);\r
 582     while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
 583        r--;\r
 584        if (r==0) return NULLT; // there is no such node\r
 585        s = (int)Tags->select(tag, r);  // we should use select_prev instead when provided\r
 586        node_s = tagpos2node(s);\r
 587     }\r
 588     return NULLT; // there is no such node \r
 589  }\r
 590 \r
 591 \r
 592 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in\r
 593 // the subtree of x. Returns NULLT if there is none.\r
 594 treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)\r
 595  {\r
 596    NULLT_IF (x ==NULLT || x == Root());\r
 597    \r
 598    return tagpos2node(Tags->select_next(tag,find_close(Par, x)));\r
 599 \r
 600  } \r
 601 \r
 602 // TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x \r
 603 // and not in the subtree of x. Returns NULLT if there is none.\r
 604 treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root)\r
 605 {\r
 606 \r
 607   NULLT_IF (x == NULLT || x == Root());\r
 608   \r
 609   treeNode s = tagpos2node(Tags->select_next(tag, find_close(Par, x)));\r
 610   \r
 611   if (root == Root()) return s;\r
 612   NULLT_IF (s == NULLT || s >= find_close(Par, root));\r
 613   \r
 614   return s;\r
 615 } \r
 616 \r
 617 /* Here we inline TaggedFoll to find the min globally, and only at the end\r
 618    we check if the min is below the context node */\r
 619 treeNode XMLTree::SelectFollBelow(treeNode x, std::unordered_set<int> *tags, treeNode root)\r
 620  {\r
 621 \r
 622    NULLT_IF(x==NULLT || x==Root());\r
 623    int i;\r
 624    treeNode min = NULLT;\r
 625    treeNode ns = next_sibling(Par, x);\r
 626    treeNode aux;\r
 627    std::unordered_set<int>::const_iterator tagit;\r
 628    for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
 629 \r
 630      aux = tagpos2node(Tags->select_next(*tagit, find_close(Par, x)));\r
 631      \r
 632      // The next sibling of x is guaranteed to be below ctx\r
 633      // and is the node with lowest preorder which is after ctx.\r
 634      // if we find it, we return early;\r
 635      \r
 636      if (aux == ns ) return ns;\r
 637      if (aux == NULLT) continue;\r
 638      if ((min == NULLT) || (aux < min)) min = aux;\r
 639    };\r
 640      \r
 641    // found the smallest node in preorder which is after x.\r
 642    // if ctx is the root node, just return what we found.\r
 643 \r
 644    if (root == Root()) return min;\r
 645    // else check whether if is in below the ctx node\r
 646 \r
 647    NULLT_IF (min == NULLT || min >= find_close(Par, root));\r
 648    \r
 649    return min;\r
 650    \r
 651  }\r
 652 \r
 653 \r
 654 // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return\r
 655 // NULLT is there is none.\r
 656 treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)\r
 657  {    \r
 658     if (x == NULLT || x == Root())\r
 659        return NULLT;\r
 660     \r
 661     treeNode s = parent(Par, x), r = Root();\r
 662     while (s != r) {\r
 663        if (get_field(tags_fix,tags_blen,node2tagpos(s)) /*Tags->access(node2tagpos(s))*/ == tag) return s;\r
 664        s = parent(Par, s);\r
 665     }\r
 666     return NULLT;\r
 667  }\r
 668 \r
 669 \r
 670 \r
 671 // MyText(x): returns the document identifier of the text below node x, \r
 672 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc \r
 673 // ids start from 0.\r
 674 DocID XMLTree::MyText(treeNode x) \r
 675 {\r
 676   TagType tag = Tag(x);\r
 677   // seems faster than testing EBVector->access(x);\r
 678 \r
 679   if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID)\r
 680     return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0\r
 681   else \r
 682     return (DocID) NULLT;\r
 683   \r
 684 }\r
 685 \r
 686 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of\r
 687 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.\r
 688 int XMLTree::TextXMLId(DocID d) \r
 689  {\r
 690    NULLT_IF(d == NULLT);\r
 691      int s = EBVector->select1(d+1);\r
 692    return rank_open(Par, s) + d + 1; // +1 because root has preorder 1\r
 693    \r
 694  }\r
 695 \r
 696 // NodeXMLId(x): returns the preorder of node x in the tree consisting \r
 697 // of all tree nodes and all text nodes. Assumes that the tree root has\r
 698 // preorder 0;\r
 699 int XMLTree::NodeXMLId(treeNode x) \r
 700  {\r
 701    NULLT_IF(x == NULLT);\r
 702    if (x == Root()) return 1; // root node has preorder 1\r
 703    return rank_open(Par, x) + EBVector->rank1(x-1);\r
 704  }\r
 705 \r
 706 // ParentNode(d): returns the parent node of document identifier d.\r
 707 treeNode XMLTree::ParentNode(DocID d) \r
 708  {    \r
 709    NULLT_IF (d == NULLT);   \r
 710    return (treeNode) EBVector->select1(d+1);     \r
 711  }\r
 712 \r
 713 // GetTagId: returns the tag identifier corresponding to a given tag name.\r
 714 // Returns NULLT in case that the tag name does not exists.\r
 715 TagType XMLTree::GetTagId(unsigned char *tagname)\r
 716  {\r
 717   \r
 718    string s = (char *) tagname;\r
 719    TagIdMapIT it = tIdMap->find(s);    \r
 720    return (TagType) ((it != tIdMap->end()) ? it->second : -1);\r
 721     \r
 722  }\r
 723 \r
 724 \r
 725 // GetTagName(tagid): returns the tag name of a given tag identifier.\r
 726 // Returns NULL in case that the tag identifier is not valid.\r
 727 unsigned char *XMLTree::GetTagName(TagType tagid)\r
 728  {\r
 729     unsigned char *s;\r
 730     if ( tagid < 0 || tagid >= TagName->size())\r
 731       return (unsigned char *) "<INVALID TAG>";\r
 732     strcpy((char *)s, TagName->at(tagid).c_str());\r
 733     \r
 734     return (s == NULL ? (unsigned char*) "<INVALID TAG>" : s);\r
 735  }\r
 736 \r
 737 \r
 738 const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)\r
 739  {\r
 740 \r
 741    unsigned char *s;\r
 742    if ( tagid < 0 || tagid >= TagName->size())\r
 743      return (unsigned char *) "<INVALID TAG>";\r
 744    \r
 745    return (const unsigned char *) TagName->at(tagid).c_str();\r
 746    \r
 747  }\r
 748 \r
 749 \r
 750 \r
 751 TagType XMLTree::RegisterTag(unsigned char *tagname)\r
 752  {  \r
 753     TagType id = XMLTree::GetTagId(tagname);\r
 754     if (id == NULLT) {\r
 755       string s = (char *) tagname;      \r
 756       REGISTER_TAG(TagName,tIdMap,s);\r
 757       \r
 758     };\r
 759     \r
 760     return id;\r
 761  }\r
 762 \r
 763 \r