XMLTree.cpp

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