XMLTree.cpp

   1 #include "basics.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 fast_inspect(Par,x)==OP ? x : NULLT;\r
  34   } else return fast_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                   TextCollection * const TC, 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     Par = (bp *)umalloc(sizeof(bp));\r
  76     STARTTIMER();\r
  77     bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0);\r
  78     STOPTIMER(Building);\r
  79     PRINTTIME("Building parenthesis struct", Building);\r
  80     STARTTIMER();\r
  81 \r
  82 \r
  83     // creates structure for tags\r
  84 \r
  85     TagName = (vector<string>*)TN;\r
  86     tIdMap = (TagIdMap *) tim;\r
  87 \r
  88     uint max_tag = TN->size() - 1;\r
  89 \r
  90 \r
  91     static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray();\r
  92     alphabet_mapper *am = new alphabet_mapper_none();\r
  93     Tags = new static_sequence_bs((uint*)tags,npar,am,bmb);\r
  94 \r
  95     //cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl;\r
  96 \r
  97     //Ensures that for small tag numbers, we are on an 8bit boundary.\r
  98     //Makes tag access way faster with negligeable waste of space.\r
  99     tags_blen = bits8(max_tag);\r
 100     std::cerr << "Tags blen is " << tags_blen << "\n";\r
 101     tags_len = (uint)npar;\r
 102     tags_fix = new uint[uint_len(tags_blen,tags_len)];\r
 103     for(uint i=0;i<(uint)npar;i++)\r
 104        set_field(tags_fix,tags_blen,i,tags[i]);\r
 105     delete bmb;\r
 106     free(tags);\r
 107     tags = NULL;\r
 108 \r
 109     STOPTIMER(Building);\r
 110     PRINTTIME("Building Tag Structure", Building);\r
 111 \r
 112     Text = (TextCollection*) TC;\r
 113 \r
 114 \r
 115     EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32);\r
 116     //EBVector = new static_bitsequence_sdarray(empty_texts_bmp,npar);\r
 117     free(empty_texts_bmp);\r
 118     empty_texts_bmp = NULL;\r
 119 \r
 120 \r
 121     disable_tc = dis_tc;\r
 122     text_index_type = _index_type;\r
 123     std::cerr << "Number of distinct tags " << TagName->size() << "\n";\r
 124     //std::cerr.flush();\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 void XMLTree::print_stats()\r
 155  {\r
 156     uint total_space = Tags->size()+sizeof(static_sequence*);\r
 157     total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len));\r
 158     cout << "Space usage for XMLTree:" << endl\r
 159          << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl\r
 160          << " - tags access array:    " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl\r
 161          << " ... add Diego structures ... " << endl\r
 162          << " *total* " << total_space << endl;\r
 163  }\r
 164 \r
 165 // Save: saves XML tree data structure to file.\r
 166 void XMLTree::Save(int fd, char * name)\r
 167  {\r
 168     FILE *fp;\r
 169     int i;\r
 170 \r
 171     fp = fdopen(fd, "wa");\r
 172     // first stores the tree topology\r
 173     saveTree(Par, fp);\r
 174 \r
 175     // stores the table with tag names\r
 176     int ntags = TagName->size();\r
 177 \r
 178     ufwrite(&ntags, sizeof(int), 1, fp);\r
 179     for (i = 0; i<ntags;i++)\r
 180       fprintf(fp, "%s\n",TagName->at(i).c_str());\r
 181 \r
 182 \r
 183     // stores the tags\r
 184     Tags->save(fp);\r
 185     ufwrite(&tags_blen,sizeof(uint),1,fp);\r
 186     ufwrite(&tags_len,sizeof(uint),1,fp);\r
 187     ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp);\r
 188 \r
 189     // flags\r
 190     ufwrite(&disable_tc, sizeof(bool),1,fp);\r
 191 \r
 192     //text positions\r
 193     EBVector->save(fp);\r
 194 \r
 195     // stores the texts\r
 196     if (!disable_tc) {\r
 197 \r
 198       ufwrite(&text_index_type, sizeof(TextCollectionBuilder::index_type_t), 1, fp);\r
 199 \r
 200 \r
 201       string file(name);\r
 202       switch (text_index_type){\r
 203       case TextCollectionBuilder::index_type_default:\r
 204         file.append(".default");\r
 205         break;\r
 206       case TextCollectionBuilder::index_type_swcsa:\r
 207         file.append(".swcsa");\r
 208         break;\r
 209       case TextCollectionBuilder::index_type_rlcsa:\r
 210         file.append(".rlcsa");\r
 211         break;\r
 212       };\r
 213 \r
 214       Text->Save(fp, file.c_str());\r
 215 \r
 216 \r
 217     }\r
 218  }\r
 219 \r
 220 // Load: loads XML tree data structure from file. Returns\r
 221 // a pointer to the loaded data structure\r
 222 XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name)\r
 223  {\r
 224 \r
 225     FILE *fp;\r
 226     char buffer[1024];\r
 227     XMLTree *XML_Tree;\r
 228     int i;\r
 229 \r
 230     buffer[1023] = '\0';\r
 231 \r
 232     fp = fdopen(fd, "r");\r
 233 \r
 234     XML_Tree = new XMLTree();\r
 235     STARTTIMER();\r
 236     // Load the tree structure\r
 237     XML_Tree->Par = (bp *)umalloc(sizeof(bp));\r
 238 \r
 239     loadTree(XML_Tree->Par, fp);\r
 240     STOPTIMER(Loading);\r
 241     PRINTTIME("Loading parenthesis struct", Loading);\r
 242     STARTTIMER();\r
 243 \r
 244     XML_Tree->TagName = new std::vector<std::string>();\r
 245     XML_Tree->tIdMap = new std::unordered_map<std::string,int>();\r
 246     std::string s;\r
 247     int ntags;\r
 248 \r
 249     // Load the tag names\r
 250     ufread(&ntags, sizeof(int), 1, fp);\r
 251 \r
 252     for (i=0; i<ntags;i++) {\r
 253        if (fgets(buffer,1022,fp) != buffer)\r
 254          throw "Cannot read tag list";\r
 255        s = buffer;\r
 256        // remove the trailing \n\r
 257        s.erase(s.size()-1);\r
 258        XML_Tree->TagName->push_back(s);\r
 259        XML_Tree->tIdMap->insert(std::make_pair(s,i));\r
 260 \r
 261     };\r
 262     STOPTIMER(Loading);\r
 263     PRINTTIME("Loading tag names struct", Loading);\r
 264     STARTTIMER();\r
 265 \r
 266     // loads the tag structure\r
 267     XML_Tree->Tags = static_sequence::load(fp);\r
 268     ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);\r
 269     std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n";\r
 270     ufread(&XML_Tree->tags_len,sizeof(uint),1,fp);\r
 271     XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)];\r
 272     ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp);\r
 273 \r
 274     // TODO ask francisco about this\r
 275     /// FIXME:UGLY tests!\r
 276     //uint * seq = new uint[XML_Tree->tags_len];\r
 277     //for(uint i=0;i<XML_Tree->tags_len;i++)\r
 278     //  seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i);\r
 279     //cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl;\r
 280     //XML_Tree->Tags->test(seq,XML_Tree->tags_len);\r
 281     //delete [] seq;\r
 282     /// End ugly tests\r
 283 \r
 284     STOPTIMER(Loading);\r
 285     std::cerr << (uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/(1024*1024) << " MB for tag sequence" << std::endl;\r
 286     PRINTTIME("Loading tag struct", Loading);\r
 287     STARTTIMER();\r
 288 \r
 289     // loads the flags\r
 290 \r
 291     ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);\r
 292     if (load_tc) {\r
 293       XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);\r
 294 \r
 295       STOPTIMER(Loading);\r
 296       PRINTTIME("Loading text bitvector struct", Loading);\r
 297       STARTTIMER();\r
 298 \r
 299       // Not used\r
 300       // loads the texts\r
 301       if (!XML_Tree->disable_tc){\r
 302         ufread(&(XML_Tree->text_index_type),\r
 303                sizeof(TextCollectionBuilder::index_type_t), 1, fp);\r
 304         string file(name);\r
 305         switch (XML_Tree->text_index_type){\r
 306         case TextCollectionBuilder::index_type_default:\r
 307           file.append(".default");\r
 308           break;\r
 309         case TextCollectionBuilder::index_type_swcsa:\r
 310           file.append(".swcsa");\r
 311           break;\r
 312         case TextCollectionBuilder::index_type_rlcsa:\r
 313           file.append(".rlcsa");\r
 314           break;\r
 315         };\r
 316         XML_Tree->Text = TextCollection::Load(fp, file.c_str(), TextCollection::index_mode_default, sample_factor);\r
 317 \r
 318       }\r
 319       else XML_Tree->Text = NULL;\r
 320       STOPTIMER(Loading);\r
 321       PRINTTIME("Loading TextCollection", Loading);\r
 322       STARTTIMER();\r
 323     }\r
 324     else {\r
 325       XML_Tree->EBVector = NULL;\r
 326       XML_Tree->Text = NULL;\r
 327       XML_Tree->disable_tc = true;\r
 328     };\r
 329 \r
 330 \r
 331     return XML_Tree;\r
 332  }\r
 333 \r
 334 \r
 335 \r
 336 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.\r
 337 /*int XMLTree::SubtreeSize(treeNode x)\r
 338  {\r
 339     return subtree_size(Par, x);\r
 340  }\r
 341 */\r
 342 // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.\r
 343 /*\r
 344 int XMLTree::SubtreeTags(treeNode x, TagType tag)\r
 345  {\r
 346     if (x == Root())\r
 347       x = fast_first_child(Par,x);\r
 348 \r
 349 \r
 350     int s = x + 2*subtree_size(Par, x) - 1;\r
 351 \r
 352     return (Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1))+1;\r
 353  }\r
 354 */\r
 355 int XMLTree::SubtreeElements(treeNode x)\r
 356  {\r
 357 \r
 358     int size = subtree_size(Par,x);\r
 359     if (x == Root()){\r
 360       x = fast_first_child(Par,x);\r
 361       size = size - 1;\r
 362     };\r
 363 \r
 364     int s = x + 2*size - 1;\r
 365     int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1);\r
 366     size = size - ntext;\r
 367     treeNode fin = fast_find_close(Par,x);\r
 368     treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x));\r
 369     while (y != NULLT && y < fin){\r
 370       size -= SubtreeSize(y);\r
 371       y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y));\r
 372     };\r
 373     return size;\r
 374  }\r
 375 \r
 376 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation\r
 377 // this is just a bit inspection.\r
 378 bool XMLTree::IsLeaf(treeNode x)\r
 379  {\r
 380    NULLT_IF(x==NULLT);\r
 381    return fast_isleaf(Par, x);\r
 382  }\r
 383 \r
 384 // IsAncestor(x,y): returns whether node x is ancestor of node y.\r
 385 bool XMLTree::IsAncestor(treeNode x, treeNode y)\r
 386  {\r
 387     return fast_is_ancestor(Par, x, y);\r
 388  }\r
 389 \r
 390 // IsChild(x,y): returns whether node x is parent of node y.\r
 391 bool XMLTree::IsChild(treeNode x, treeNode y)\r
 392  {\r
 393     if (!fast_is_ancestor(Par, x, y)) return false;\r
 394     return depth(Par, x) == (depth(Par, y) + 1);\r
 395  }\r
 396 \r
 397 // IsFirstChild(x): returns whether node x is the first child of its parent.\r
 398 /*bool XMLTree::IsFirstChild(treeNode x)\r
 399  {\r
 400     return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));\r
 401  }\r
 402 */\r
 403 \r
 404 // NumChildren(x): number of children of node x. Constant time with the data structure\r
 405 // of Sadakane.\r
 406 int XMLTree::NumChildren(treeNode x)\r
 407  {\r
 408     return degree(Par, x);\r
 409  }\r
 410 \r
 411 // ChildNumber(x): returns i if node x is the i-th children of its parent.\r
 412 int XMLTree::ChildNumber(treeNode x)\r
 413  {\r
 414     return child_rank(Par, x);\r
 415  }\r
 416 \r
 417 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.\r
 418 int XMLTree::Depth(treeNode x)\r
 419  {\r
 420     return depth(Par, x);\r
 421  }\r
 422 \r
 423 // Preorder(x): returns the preorder number of node x, just counting the tree\r
 424 // nodes (i.e., tags, it disregards the texts in the tree).\r
 425 int XMLTree::Preorder(treeNode x)\r
 426  {\r
 427     return preorder_rank(Par, x);\r
 428  }\r
 429 \r
 430 // Postorder(x): returns the postorder number of node x, just counting the tree\r
 431 // nodes (i.e., tags, it disregards the texts in the tree).\r
 432 int XMLTree::Postorder(treeNode x)\r
 433  {\r
 434     return postorder_rank(Par, x);\r
 435  }\r
 436 /*\r
 437 // Tag(x): returns the tag identifier of node x.\r
 438 TagType XMLTree::Tag(treeNode x)\r
 439  {\r
 440     return fast_get_field(tags_fix,tags_blen,node2tagpos(x));\r
 441  }\r
 442 */\r
 443 // DocIds(x): returns the range of text identifiers that descend from node x.\r
 444 // returns {NULLT, NULLT} when there are no texts descending from x.\r
 445 range XMLTree::DocIds(treeNode x)\r
 446  {\r
 447    range r;\r
 448    if (x == NULLT) {\r
 449      r.min = NULLT;\r
 450      r.max = NULLT;\r
 451      return r;\r
 452    };\r
 453    int min = EBVector->rank1(x-1);\r
 454    int max = EBVector->rank1(x+2*subtree_size(Par, x)-2);\r
 455    if (min==max) { // range is empty, no texts within the subtree of x\r
 456      r.min = NULLT;\r
 457      r.max = NULLT;\r
 458    }\r
 459    else { // the range is non-empty, there are texts within the subtree of x\r
 460      r.min = min+1;\r
 461      r.max = max;\r
 462    }\r
 463    return r;\r
 464  }\r
 465 \r
 466 // Parent(x): returns the parent node of node x.\r
 467 /*\r
 468 treeNode XMLTree::Parent(treeNode x)\r
 469  {\r
 470     if (x == Root())\r
 471       return NULLT;\r
 472     else\r
 473       return  parent(Par, x);;\r
 474  }*/\r
 475 \r
 476 // Child(x,i): returns the i-th child of node x, assuming it exists.\r
 477 treeNode XMLTree::Child(treeNode x, int i)\r
 478 {\r
 479     if (i <= OPTD) return naive_child(Par, x, i);\r
 480     else return child(Par, x, i);\r
 481 }\r
 482 \r
 483 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
 484 /*\r
 485 treeNode XMLTree::FirstChild(treeNode x)\r
 486  {\r
 487    NULLT_IF(x==NULLT);\r
 488    return fast_first_child(Par, x);\r
 489  }\r
 490 */\r
 491 /*\r
 492 treeNode XMLTree::FirstElement(treeNode x)\r
 493  {\r
 494    NULLT_IF(x==NULLT);\r
 495    x = fast_first_child(Par, x);\r
 496    NULLT_IF(x == NULLT);\r
 497    switch (Tag(x)){\r
 498 \r
 499    case PCDATA_TAG_ID:\r
 500      x = x+2;\r
 501      return (fast_inspect(Par,x)==OP)? x : NULLT;\r
 502 \r
 503    case ATTRIBUTE_TAG_ID:\r
 504      x = fast_next_sibling(Par,x);\r
 505      if (x != NULLT && Tag(x) == PCDATA_TAG_ID){\r
 506        x = x+2;\r
 507        return (fast_inspect(Par,x)==OP)? x : NULLT;\r
 508      }\r
 509      else return x;\r
 510    default:\r
 511      return x;\r
 512    }\r
 513  }\r
 514 *//*\r
 515 treeNode XMLTree::NextElement(treeNode x)\r
 516 {\r
 517   NULLT_IF(x==NULLT);\r
 518   x = fast_next_sibling(Par, x);\r
 519   NULLT_IF(x == NULLT);\r
 520   if (Tag(x) == PCDATA_TAG_ID){\r
 521     x = x+2;\r
 522      return (fast_inspect(Par,x)==OP)? x : NULLT;\r
 523   }\r
 524   else return x;\r
 525   }*/\r
 526 \r
 527 // LastChild(x): returns the last child of node x.\r
 528    /*treeNode XMLTree::LastChild(treeNode x)\r
 529  {\r
 530    NULLT_IF(x == NULLT || fast_isleaf(Par,x));\r
 531    return find_open(Par, fast_find_close(Par, x)-1);\r
 532  }\r
 533    */\r
 534 // NextSibling(x): returns the next sibling of node x, assuming it exists.\r
 535 /*treeNode XMLTree::NextSibling(treeNode x)\r
 536  {\r
 537    NULLT_IF(x==NULLT || x == Root() );\r
 538    x = fast_find_close(Par,x)+1;\r
 539    return (fast_inspect(Par,x) == CP ? NULLT : x);\r
 540  }\r
 541 */\r
 542 \r
 543 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
 544 /*treeNode XMLTree::PrevSibling(treeNode x)\r
 545  {\r
 546    NULLT_IF(x==NULLT);\r
 547    return prev_sibling(Par, x);\r
 548  }\r
 549 */\r
 550 // TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none.\r
 551 // Because of the balanced-parentheses representation of the tree, this operation is not supported\r
 552 // efficiently, just iterating among the children of node x until finding the desired child.\r
 553 /*\r
 554 treeNode XMLTree::TaggedChild(treeNode x, TagType tag)\r
 555  {\r
 556 \r
 557    NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
 558    treeNode child;\r
 559    child = fast_first_child(Par, x); // starts at first child of node x\r
 560    if (Tag(child) == tag)\r
 561      return child;\r
 562    else\r
 563      return TaggedFollowingSibling(child,tag);\r
 564  }\r
 565 \r
 566 // TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.\r
 567 treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)\r
 568 {\r
 569   NULLT_IF(x==NULLT);\r
 570   treeNode sibling = fast_next_sibling(Par, x);\r
 571   TagType ctag;\r
 572   while (sibling != NULLT) {\r
 573     ctag = Tag(sibling);\r
 574     if (ctag == tag) // current sibling is labeled with tag of interest\r
 575       return sibling;\r
 576     sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling\r
 577   }\r
 578   return NULLT; // no such sibling was found\r
 579 }\r
 580 */\r
 581 treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags)\r
 582 {\r
 583 \r
 584   NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
 585   int i;\r
 586   treeNode child = fast_first_child(Par, x);\r
 587   TagType t;\r
 588   while (child != NULLT) {\r
 589     t = Tag(child);\r
 590     if (tags->find(t) != tags->end()) return child;\r
 591     child = fast_sibling(Par, child,t);\r
 592   }\r
 593   return NULLT;\r
 594 }\r
 595 \r
 596 \r
 597 treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)\r
 598 {\r
 599 \r
 600    NULLT_IF(x==NULLT);\r
 601    int i;\r
 602    TagType t;\r
 603    treeNode sibling = fast_next_sibling(Par, x);\r
 604    while (sibling != NULLT) {\r
 605      t = Tag(sibling);\r
 606      if (tags->find(t) != tags->end()) return sibling;\r
 607      sibling = fast_sibling(Par, sibling,t);\r
 608    }\r
 609    return NULLT;\r
 610  }\r
 611 \r
 612 \r
 613 // TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within\r
 614 // the subtree of x. Returns NULLT if there is none.\r
 615 /*\r
 616 treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag)\r
 617  {\r
 618    //NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
 619 \r
 620    int s = (int) Tags->select_next(tag,node2tagpos(x));\r
 621    NULLT_IF (s == -1);\r
 622 \r
 623    treeNode y = tagpos2node(s); // transforms the tag position into a node position\r
 624 \r
 625    return (fast_is_ancestor(Par,x,y) ? y : NULLT);\r
 626  }\r
 627 */\r
 628 /*\r
 629 treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)\r
 630  {\r
 631    NULLT_IF (x ==NULLT || fast_isleaf(Par,x));\r
 632    int i;\r
 633    treeNode min = NULLT;\r
 634    treeNode fc = fast_first_child(Par,x);\r
 635    treeNode aux;\r
 636    TagIdSet::const_iterator tagit;\r
 637    for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
 638      aux = TaggedDescendant(x, (TagType) *tagit);\r
 639      if (aux == fc) return fc;\r
 640      if (aux == NULLT) continue;\r
 641      if ((min == NULLT) || (aux < min)) min = aux;\r
 642    };\r
 643    return min;\r
 644  }\r
 645 \r
 646 */\r
 647 \r
 648 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an\r
 649 // ancestor of x. Returns NULLT if there is none.\r
 650 treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)\r
 651  {\r
 652     int r, s;\r
 653     treeNode node_s, root;\r
 654     r = (int)Tags->rank(tag, node2tagpos(x)-1);\r
 655     if (r==0) return NULLT; // there is no such node.\r
 656     s = (int)Tags->select(tag, r);\r
 657     root = root_node(Par);\r
 658     node_s = tagpos2node(s);\r
 659     while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
 660        r--;\r
 661        if (r==0) return NULLT; // there is no such node\r
 662        s = (int)Tags->select(tag, r);  // we should use select_prev instead when provided\r
 663        node_s = tagpos2node(s);\r
 664     }\r
 665     return NULLT; // there is no such node\r
 666  }\r
 667 \r
 668 \r
 669 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in\r
 670 // the subtree of x. Returns NULLT if there is none.\r
 671 treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)\r
 672  {\r
 673    NULLT_IF (x ==NULLT || x == Root());\r
 674    return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x)));\r
 675 \r
 676  }\r
 677 \r
 678 // TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x\r
 679 // and not in the subtree of x. Returns NULLT if there is none.\r
 680 /*\r
 681 treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)\r
 682 {\r
 683   // NULLT_IF (x == NULLT || x == Root() || x == ancestor);\r
 684 \r
 685   //Special optimisation, test for the following sibling first\r
 686   treeNode close = fast_find_close(Par, x);\r
 687   treeNode s = tagpos2node(Tags->select_next(tag, close));\r
 688 \r
 689   if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s;\r
 690   else return NULLT;\r
 691 }\r
 692 */\r
 693  /*\r
 694 treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing)\r
 695 {\r
 696 \r
 697   NULLT_IF (x == NULLT || x == Root());\r
 698 \r
 699   treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x)));\r
 700   NULLT_IF (s == NULLT || s >= closing);\r
 701 \r
 702   return s;\r
 703 }\r
 704  */\r
 705 /* Here we inline TaggedFoll to find the min globally, and only at the end\r
 706    we check if the min is below the context node */\r
 707 treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor)\r
 708  {\r
 709 \r
 710    NULLT_IF(x==NULLT || x==Root());\r
 711 \r
 712    treeNode close = fast_find_close(Par,x);\r
 713    treeNode ns = close+1;\r
 714    if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))\r
 715      return ns;\r
 716 \r
 717    int i;\r
 718    treeNode min = NULLT;\r
 719    treeNode aux;\r
 720 \r
 721 \r
 722    TagIdSet::const_iterator tagit;\r
 723    for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {\r
 724 \r
 725      aux = tagpos2node(Tags->select_next(*tagit, close));\r
 726      if (aux == NULLT) continue;\r
 727      if ((min == NULLT) || (aux < min)) min = aux;\r
 728    };\r
 729 \r
 730    // found the smallest node in preorder which is after x.\r
 731    // if ctx is the root node, just return what we found.\r
 732 \r
 733    if (ancestor == Root() || min == NULLT || min < fast_find_close(Par, ancestor)) return min;\r
 734    else return NULLT;\r
 735 \r
 736  }\r
 737 /*\r
 738 treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode ancestor_closing)\r
 739  {\r
 740 \r
 741    NULLT_IF(x==NULLT || x==Root());\r
 742 \r
 743    treeNode close = fast_find_close(Par,x);\r
 744    treeNode ns = close+1;\r
 745    if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))\r
 746      return ns;\r
 747 \r
 748    int i;\r
 749    treeNode min = NULLT;\r
 750    treeNode aux;\r
 751 \r
 752 \r
 753    TagIdSet::const_iterator tagit;\r
 754    for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {\r
 755 \r
 756      aux = tagpos2node(Tags->select_next(*tagit, close));\r
 757      if (aux == NULLT) continue;\r
 758      if ((min == NULLT) || (aux < min)) min = aux;\r
 759    };\r
 760 \r
 761    // found the smallest node in preorder which is after x.\r
 762    // if ctx is the root node, just return what we found.\r
 763 \r
 764    if (ancestor_closing == Root() || min == NULLT || min < ancestor_closing) return min;\r
 765    else return NULLT;\r
 766 \r
 767  }\r
 768 */\r
 769 /*\r
 770 treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing)\r
 771  {\r
 772 \r
 773    NULLT_IF(x==NULLT || x==Root());\r
 774    int i;\r
 775    treeNode min = NULLT;\r
 776    treeNode ns = fast_next_sibling(Par, x);\r
 777    treeNode close = ns - 1;\r
 778    treeNode aux;\r
 779    TagIdSet::const_iterator tagit;\r
 780    for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
 781 \r
 782      aux = tagpos2node(Tags->select_next(*tagit, close));\r
 783 \r
 784      // The next sibling of x is guaranteed to be below ctx\r
 785      // and is the node with lowest preorder which is after ctx.\r
 786      // if we find it, we return early;\r
 787 \r
 788      if (aux == ns ) return ns;\r
 789      if (aux == NULLT) continue;\r
 790      if ((min == NULLT) || (aux < min)) min = aux;\r
 791    };\r
 792 \r
 793    // found the smallest node in preorder which is after x.\r
 794    // if ctx is the root node, just return what we found.\r
 795 \r
 796    NULLT_IF (min == NULLT || min >= closing);\r
 797 \r
 798    return min;\r
 799 \r
 800  }\r
 801 */\r
 802 \r
 803 // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return\r
 804 // NULLT is there is none.\r
 805 treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)\r
 806  {\r
 807     if (x == NULLT || x == Root())\r
 808        return NULLT;\r
 809 \r
 810     treeNode s = parent(Par, x), r = Root();\r
 811     while (s != r) {\r
 812       if (Tag(s) == tag) return s;\r
 813        s = parent(Par, s);\r
 814     }\r
 815     return NULLT;\r
 816  }\r
 817 \r
 818 \r
 819 \r
 820 // MyText(x): returns the document identifier of the text below node x,\r
 821 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc\r
 822 // ids start from 0.\r
 823 DocID XMLTree::MyText(treeNode x)\r
 824 {\r
 825   TagType tag = Tag(x);\r
 826   // seems faster than testing EBVector->access(x);\r
 827 \r
 828   if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID)\r
 829     return (DocID) (EBVector->rank1(x)-1);\r
 830   else\r
 831     return (DocID) NULLT;\r
 832 \r
 833 }\r
 834 // MyText(x): returns the document identifier of the text below node x,\r
 835 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc\r
 836 // ids start from 0.\r
 837 DocID XMLTree::MyTextUnsafe(treeNode x)\r
 838 {\r
 839   return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0\r
 840 \r
 841 }\r
 842 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of\r
 843 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.\r
 844 int XMLTree::TextXMLId(DocID d)\r
 845  {\r
 846    NULLT_IF(d == NULLT);\r
 847      int s = EBVector->select1(d+1);\r
 848    return rank_open(Par, s) + d + 1; // +1 because root has preorder 1\r
 849 \r
 850  }\r
 851 \r
 852 // NodeXMLId(x): returns the preorder of node x in the tree consisting\r
 853 // of all tree nodes and all text nodes. Assumes that the tree root has\r
 854 // preorder 0;\r
 855 int XMLTree::NodeXMLId(treeNode x)\r
 856  {\r
 857    NULLT_IF(x == NULLT);\r
 858    if (x == Root()) return 1; // root node has preorder 1\r
 859    return rank_open(Par, x) + EBVector->rank1(x-1);\r
 860  }\r
 861 \r
 862 // ParentNode(d): returns the parent node of document identifier d.\r
 863 treeNode XMLTree::ParentNode(DocID d)\r
 864  {\r
 865    NULLT_IF (d == NULLT);\r
 866    return (treeNode) EBVector->select1(d+1);\r
 867  }\r
 868 \r
 869 // GetTagId: returns the tag identifier corresponding to a given tag name.\r
 870 // Returns NULLT in case that the tag name does not exists.\r
 871 TagType XMLTree::GetTagId(unsigned char *tagname)\r
 872  {\r
 873 \r
 874    string s = (char *) tagname;\r
 875    TagIdMapIT it = tIdMap->find(s);\r
 876    return (TagType) ((it != tIdMap->end()) ? it->second : -1);\r
 877 \r
 878  }\r
 879 \r
 880 \r
 881 // GetTagName(tagid): returns the tag name of a given tag identifier.\r
 882 // Returns NULL in case that the tag identifier is not valid.\r
 883 unsigned char *XMLTree::GetTagName(TagType tagid)\r
 884  {\r
 885     unsigned char *s;\r
 886     if ( tagid < 0 || tagid >= TagName->size())\r
 887       return (unsigned char *) "<INVALID TAG>";\r
 888     strcpy((char *)s, (*TagName)[tagid].c_str());\r
 889 \r
 890     return (s == NULL ? (unsigned char*) "<INVALID TAG>" : s);\r
 891  }\r
 892 \r
 893 \r
 894 const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)\r
 895  {\r
 896 \r
 897    unsigned char *s;\r
 898    if ( tagid < 0 || tagid >= TagName->size())\r
 899      return (unsigned char *) "<INVALID TAG>";\r
 900 \r
 901    return (const unsigned char *) (*TagName)[tagid].c_str();\r
 902 \r
 903  }\r
 904 \r
 905 \r
 906 \r
 907 TagType XMLTree::RegisterTag(unsigned char *tagname)\r
 908  {\r
 909     TagType id = XMLTree::GetTagId(tagname);\r
 910     if (id == NULLT) {\r
 911       string s = (char *) tagname;\r
 912       REGISTER_TAG(TagName,tIdMap,s);\r
 913     };\r
 914 \r
 915     return id;\r
 916  }\r
 917 \r
 918 \r
 919 treeNode XMLTree::Closing(treeNode x) {\r
 920   return fast_find_close(Par,x);\r
 921 }\r
 922 bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }\r
 923 \r
 924 //WARNING this uses directly the underlying implementation for plain text\r
 925 \r
 926 \r
 927 void XMLTree::Print(int fd,treeNode x, bool no_text){\r
 928 \r
 929   if (buffer == 0) {\r
 930     buffer = new string(BUFFER_ALLOC, 0);\r
 931     buffer->clear();\r
 932     print_stack = new std::vector<string *>();\r
 933     print_stack->reserve(256);\r
 934   };\r
 935 \r
 936   treeNode fin = fast_find_close(Par,x);\r
 937   treeNode n = x;\r
 938   TagType tag = Tag(n);\r
 939 \r
 940   range r = DocIds(x);\r
 941   treeNode first_idx;\r
 942   treeNode first_text = (tag == PCDATA_TAG_ID ?  x : ParentNode(r.min-1));\r
 943   treeNode first_att =  NULLT;\r
 944 \r
 945   if (first_att  == NULLT)\r
 946     first_idx = first_text;\r
 947   else if (first_text == NULLT)\r
 948     first_idx = first_att;\r
 949   else\r
 950     first_idx = min(first_att,first_text);\r
 951 \r
 952    uchar * current_text=NULL;\r
 953 \r
 954    if (first_idx != NULLT)\r
 955      current_text = GetText(MyTextUnsafe(first_idx));\r
 956 \r
 957    size_t read = 0;\r
 958 \r
 959    while (n <= fin){\r
 960      if (fast_inspect(Par,n)){\r
 961        if (tag == PCDATA_TAG_ID) {\r
 962 \r
 963          if (no_text)\r
 964            _dputs("<$/>", fd);\r
 965          else {\r
 966            read = _dprintf((const char*) current_text, fd);\r
 967            current_text += (read + 1);\r
 968          };\r
 969          n+=2; // skip closing $\r
 970          tag = Tag(n);\r
 971 \r
 972        } else {\r
 973 \r
 974          _dputc('<',fd);\r
 975          _dput_str((*TagName)[tag], fd);\r
 976          n++;\r
 977          if (fast_inspect(Par,n)) {\r
 978            print_stack->push_back(&((*TagName)[tag]));\r
 979            tag = Tag(n);\r
 980            if (tag == ATTRIBUTE_TAG_ID){\r
 981              n++;\r
 982              if (no_text) _dputs("><@@>",fd);\r
 983 \r
 984              while (fast_inspect(Par,n)){\r
 985                if (no_text) {\r
 986                  _dputc('<', fd);\r
 987                  _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);\r
 988                  _dputc('>', fd);\r
 989                  _dputs("<$@/></", fd);\r
 990                  _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);\r
 991                  _dputc('>', fd);\r
 992                  n+= 4;\r
 993                } else {\r
 994                  _dputc(' ', fd);\r
 995                  _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);\r
 996                  n++;\r
 997                  _dputs("=\"", fd);\r
 998                  read = _dprintf((const char*) current_text, fd);\r
 999                  current_text += (read + 1);\r
1000                  _dputc('"', fd);\r
1001                  n+=3;\r
1002                }\r
1003              };\r
1004              if (no_text) _dputs("</@@>", fd);\r
1005              else _dputc('>', fd);\r
1006              n++;\r
1007              tag=Tag(n);\r
1008 \r
1009            } else\r
1010              _dputc('>', fd);\r
1011 \r
1012          } else {// <foo /> tag\r
1013            _dputs("/>", fd);\r
1014            n++;\r
1015            tag=Tag(n);\r
1016          };\r
1017        };\r
1018      } else do {\r
1019          _dputs("</", fd);\r
1020          _dput_str(*(print_stack->back()), fd);\r
1021          _dputc('>', fd);\r
1022          print_stack->pop_back();\r
1023          n++;\r
1024        } while (!(fast_inspect(Par,n) || print_stack->empty()));\r
1025      tag = Tag(n);\r
1026    };\r
1027    _dputc('\n', fd);\r
1028    //_flush(fd);\r
1029 }\r