XMLTree.cpp

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