XMLTree.cpp

   1 #include "XMLTree.h"\r
   2 #include <cstring>\r
   3 \r
   4 // functions to convert tag positions to the corresponding tree node and viceversa. \r
   5 // These are implemented in order to be able to change the tree and Tags representations, \r
   6 // without affecting the code so much.\r
   7 // Current implementation corresponds to balanced-parentheses representation for\r
   8 // the tree, and storing 2 tags per tree node (opening and closing tags).\r
   9 \r
  10 // tag position -> tree node\r
  11 inline treeNode tagpos2node(int t) {\r
  12    return (treeNode)t;\r
  13 }\r
  14 \r
  15 // tree node -> tag position\r
  16 inline int node2tagpos(treeNode x) {\r
  17    return (int)x;\r
  18 }\r
  19 \r
  20 \r
  21 //KIM OJO to prevent suprious "unused result" warnings\r
  22 \r
  23 inline void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream){\r
  24   size_t res;\r
  25   res = fread(ptr,size,nmemb,stream);\r
  26   if (res < nmemb)\r
  27     throw "ufread I/O error";\r
  28 \r
  29   return;\r
  30 }\r
  31 \r
  32 inline void ufwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream){\r
  33   size_t res;\r
  34   res = fwrite(ptr,size,nmemb,stream);\r
  35   if (res < nmemb)\r
  36     throw "ufwrite I/O error";\r
  37   return;\r
  38 }\r
  39 \r
  40 // OJO to fail cleanly while doing a realloc\r
  41 // if we can't realloc we are pretty much screwed anyway but\r
  42 // it makes the code clearer to not have a bunch of if (!ptr) { printf("..."); exit(1); };\r
  43 inline void * urealloc(void *ptr, size_t size){\r
  44 \r
  45   void * dest = realloc(ptr,size);\r
  46   //don't fail if we requested size 0\r
  47   if (dest == NULL && size > 0 )\r
  48     throw std::bad_alloc();\r
  49   return dest;\r
  50 \r
  51 }\r
  52 \r
  53 inline void * ucalloc(size_t nmemb, size_t size){\r
  54 \r
  55   void * dest = calloc(nmemb,size);\r
  56   //don't fail if we requested size 0\r
  57   if (dest == NULL && nmemb > 0 && size > 0 )\r
  58     throw std::bad_alloc();\r
  59   return dest;\r
  60 \r
  61 }\r
  62 \r
  63 inline void * umalloc(size_t size){\r
  64   void * dest = malloc(size);\r
  65   if (dest == NULL && size > 0)\r
  66     throw std::bad_alloc();\r
  67   return dest;\r
  68 }\r
  69 \r
  70 // Save: saves XML tree data structure to file. \r
  71 void XMLTree::Save(unsigned char *filename) \r
  72  {\r
  73 \r
  74     FILE *fp;\r
  75     char filenameaux[1024];\r
  76     int i;\r
  77    \r
  78     sprintf(filenameaux, "%s.srx", filename);\r
  79     fp = fopen(filenameaux, "w");\r
  80     if (fp == NULL) {\r
  81        printf("Error: cannot create file %s to store the tree structure of XML collection\n", filenameaux);\r
  82        exit(1);\r
  83     } \r
  84     \r
  85     // first stores the tree topology\r
  86     saveTree(Par, fp);\r
  87  \r
  88     // stores the table with tag names\r
  89     ufwrite(&ntagnames, sizeof(int), 1, fp);\r
  90     for (i=0; i<ntagnames;i++)\r
  91       fprintf(fp, "%s\n",TagName[i]);\r
  92     \r
  93     \r
  94     // stores the flags\r
  95     ufwrite(&indexing_empty_texts, sizeof(bool), 1, fp);\r
  96     ufwrite(&initialized, sizeof(bool), 1, fp);\r
  97     ufwrite(&finished, sizeof(bool), 1, fp);\r
  98     ufwrite(&disable_tc, sizeof(bool),1,fp);\r
  99     \r
 100     if (!indexing_empty_texts) EBVector->save(fp);\r
 101     \r
 102     // stores the tags\r
 103     Tags->save(fp);\r
 104 \r
 105     // stores the texts   \r
 106     if (!disable_tc) {\r
 107       Text->Save(fp);\r
 108       int st = CachedText.size();\r
 109       ufwrite(&st, sizeof(int),1,fp);\r
 110       for (int i = 0; i< CachedText.size(); i++){\r
 111         st = CachedText.at(i).size();\r
 112         ufwrite(&st, sizeof(int),1,fp);\r
 113         ufwrite(CachedText.at(i).c_str(),sizeof(char),1+CachedText.at(i).size(),fp);\r
 114       };\r
 115     };\r
 116     fclose(fp);\r
 117 \r
 118  }\r
 119 \r
 120 \r
 121 // Load: loads XML tree data structure from file. Returns\r
 122 // a pointer to the loaded data structure\r
 123 XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) \r
 124  {\r
 125 \r
 126     FILE *fp;\r
 127     char buffer[1024];\r
 128     XMLTree *XML_Tree;\r
 129     int i;\r
 130     size_t s_tree = 0;\r
 131     long s_text = 0;\r
 132     size_t s_tags = 0;\r
 133 \r
 134     // first load the tree topology\r
 135     sprintf(buffer, "%s.srx", filename);\r
 136     fp = fopen(buffer, "r");\r
 137     if (fp == NULL) {\r
 138        printf("Error: cannot open file %s to load the tree structure of XML collection\n", buffer);\r
 139        exit(1);\r
 140     } \r
 141 \r
 142     XML_Tree = new XMLTree();\r
 143 \r
 144     XML_Tree->Par = (bp *)umalloc(sizeof(bp));\r
 145 \r
 146     loadTree(XML_Tree->Par, fp); \r
 147 \r
 148     s_tree += sizeof(bp);\r
 149 \r
 150     // stores the table with tag names\r
 151     ufread(&XML_Tree->ntagnames, sizeof(int), 1, fp);\r
 152     \r
 153     s_tree += sizeof(int);\r
 154 \r
 155     XML_Tree->TagName = (unsigned char **)umalloc(XML_Tree->ntagnames*sizeof(unsigned char *));\r
 156     \r
 157     s_tags += sizeof(unsigned char*)*XML_Tree->ntagnames;\r
 158 \r
 159 \r
 160     for (i=0; i<XML_Tree->ntagnames;i++) {\r
 161       \r
 162       // OJO Kim is it needed ?\r
 163       int k = feof(fp);\r
 164 \r
 165       \r
 166        // fscanf chokes on "\n" which is the case for the root element\r
 167        char * r = fgets(buffer,1023,fp);\r
 168        //       int r = fscanf(fp, "%s\n",buffer);\r
 169        if (r==NULL)\r
 170          throw "Cannot read tag list";\r
 171 \r
 172        // strlen is actually the right size, since there is a trailing '\n'\r
 173        int len = strlen((const char*)buffer);\r
 174        XML_Tree->TagName[i] = (unsigned char *)ucalloc(len,sizeof(char));\r
 175        strncpy((char *)XML_Tree->TagName[i], (const char *)buffer,len - 1);\r
 176        s_tags+= len*sizeof(char);\r
 177     }\r
 178         \r
 179     // loads the flags\r
 180 \r
 181     ufread(&(XML_Tree->indexing_empty_texts), sizeof(bool), 1, fp);\r
 182     ufread(&(XML_Tree->initialized), sizeof(bool), 1, fp);\r
 183     ufread(&(XML_Tree->finished), sizeof(bool), 1, fp);\r
 184     ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);\r
 185     \r
 186     s_tree+=sizeof(bool)*4;\r
 187 \r
 188     if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);\r
 189     \r
 190     s_tree+= XML_Tree->EBVector->size();\r
 191     \r
 192     // loads the tags\r
 193     XML_Tree->Tags = static_sequence::load(fp);\r
 194     s_tree+= XML_Tree->Tags->size();\r
 195 \r
 196     s_text = ftell(fp);\r
 197 \r
 198     // loads the texts\r
 199     if (!XML_Tree->disable_tc){\r
 200       XML_Tree->Text = TextCollection::InitTextCollection(sample_rate_text);\r
 201       XML_Tree->Text->Load(fp,sample_rate_text);\r
 202       int sst;\r
 203       int st;\r
 204       ufread(&sst, sizeof(int),1,fp);\r
 205       for (int i=0;i<sst;i++){\r
 206         ufread(&st, sizeof(int),1,fp);\r
 207         char* str = (char*) malloc(sizeof(char)*st+1);\r
 208         ufread(str,sizeof(char),st+1,fp);\r
 209         string cppstr = str;\r
 210         XML_Tree->CachedText.push_back(cppstr);\r
 211         free(str);\r
 212       };\r
 213 \r
 214     }\r
 215     else {\r
 216       XML_Tree->Text = NULL;\r
 217     }\r
 218     s_text = ftell(fp) - s_text;\r
 219 \r
 220     \r
 221 \r
 222 \r
 223     fclose(fp);\r
 224 \r
 225     std::cerr << "Tree part is " << s_tree/1024 << " Kbytes,\n"\r
 226               << "with node->tagid part " << XML_Tree->Tags->size()/1024 << "Kbytes \n"\r
 227               << "size of Tag part : " << XML_Tree->Tags->length () << " elements\n"\r
 228               << "sizof(unsigned int)* " <<  XML_Tree->Tags->length () << " = " << \r
 229       sizeof(unsigned int) * XML_Tree->Tags->length () / 1024 << " Kbytes\n"\r
 230               << "Tag part is " << s_tags/1024 << " Kbytes,\n"\r
 231               << "Text collection is " << s_text/1024 << " Kbytes \n";\r
 232     return XML_Tree;\r
 233  }\r
 234 \r
 235 \r
 236 // ~XMLTree: frees memory of XML tree.\r
 237 XMLTree::~XMLTree() \r
 238  { \r
 239     int i;\r
 240 \r
 241     destroyTree(Par);\r
 242     free(Par); // frees the memory of struct Par\r
 243    \r
 244     for (i=0; i<ntagnames;i++) \r
 245        free(TagName[i]);\r
 246     \r
 247     free(TagName);\r
 248 \r
 249     if (!indexing_empty_texts) {\r
 250        //EBVector->~static_bitsequence_rrr02();\r
 251        delete EBVector;\r
 252        EBVector = NULL;\r
 253     }\r
 254 \r
 255     //Tags->~static_sequence_wvtree();\r
 256     delete Tags;\r
 257     Tags = NULL;\r
 258 \r
 259     //Text->~TextCollection();\r
 260     delete Text;\r
 261     Text = NULL;\r
 262 \r
 263     initialized = false;\r
 264     finished = false;\r
 265  }\r
 266 \r
 267 // root(): returns the tree root.\r
 268 treeNode XMLTree::Root() \r
 269  {\r
 270     if (!finished) {\r
 271        fprintf(stderr, "Root() : Error: data structure has not been constructed properly\n");\r
 272        exit(1);\r
 273     }\r
 274     return root_node(Par);\r
 275  }\r
 276 \r
 277 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.\r
 278 int XMLTree::SubtreeSize(treeNode x) \r
 279  {\r
 280     if (!finished) {\r
 281        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 282        exit(1);\r
 283     }\r
 284     return subtree_size(Par, x);\r
 285  }\r
 286 \r
 287 // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.\r
 288 int XMLTree::SubtreeTags(treeNode x, TagType tag) \r
 289  {\r
 290     if (!finished) {\r
 291        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 292        exit(1);\r
 293     }\r
 294     if (x == Root())\r
 295       x = first_child(Par,x);\r
 296     \r
 297 \r
 298     int s = x + 2*subtree_size(Par, x) - 1;\r
 299  \r
 300     return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1);\r
 301  }\r
 302 \r
 303 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation\r
 304 // this is just a bit inspection.\r
 305 bool XMLTree::IsLeaf(treeNode x) \r
 306  {\r
 307     return isleaf(Par, x);\r
 308  } \r
 309 \r
 310 // IsAncestor(x,y): returns whether node x is ancestor of node y.\r
 311 bool XMLTree::IsAncestor(treeNode x, treeNode y) \r
 312  {\r
 313     if (!finished) {\r
 314        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 315        exit(1);\r
 316     }\r
 317 \r
 318     return is_ancestor(Par, x, y);\r
 319  }\r
 320 \r
 321 // IsChild(x,y): returns whether node x is parent of node y.\r
 322 bool XMLTree::IsChild(treeNode x, treeNode y) \r
 323  {\r
 324     if (!finished) {\r
 325        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 326        exit(1);\r
 327     }\r
 328 \r
 329     if (!is_ancestor(Par, x, y)) return false;\r
 330     return depth(Par, x) == (depth(Par, y) + 1);\r
 331  }\r
 332 \r
 333 // NumChildren(x): number of children of node x. Constant time with the data structure\r
 334 // of Sadakane.\r
 335 int XMLTree::NumChildren(treeNode x) \r
 336  {\r
 337     if (!finished) {\r
 338        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 339        exit(1);\r
 340     }\r
 341 \r
 342     return degree(Par, x);\r
 343  }\r
 344 \r
 345 // ChildNumber(x): returns i if node x is the i-th children of its parent.\r
 346 int XMLTree::ChildNumber(treeNode x) \r
 347  {\r
 348     if (!finished) {\r
 349        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 350        exit(1);\r
 351     }\r
 352 \r
 353     return child_rank(Par, x);\r
 354  }\r
 355 \r
 356 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.\r
 357 int XMLTree::Depth(treeNode x) \r
 358  {\r
 359     if (!finished) {\r
 360        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 361        exit(1);\r
 362     }\r
 363 \r
 364     return depth(Par, x);\r
 365  }\r
 366 \r
 367 // Preorder(x): returns the preorder number of node x, just counting the tree\r
 368 // nodes (i.e., tags, it disregards the texts in the tree).\r
 369 int XMLTree::Preorder(treeNode x) \r
 370  {\r
 371     if (!finished) {\r
 372        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 373        exit(1);\r
 374     }\r
 375 \r
 376     return preorder_rank(Par, x);\r
 377  }\r
 378 \r
 379 // Postorder(x): returns the postorder number of node x, just counting the tree\r
 380 // nodes (i.e., tags, it disregards the texts in the tree).\r
 381 int XMLTree::Postorder(treeNode x) \r
 382  {\r
 383     if (!finished) {\r
 384        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 385        exit(1);\r
 386     }\r
 387     return postorder_rank(Par, x);\r
 388  }\r
 389 \r
 390 // Tag(x): returns the tag identifier of node x.\r
 391 TagType XMLTree::Tag(treeNode x) \r
 392  {\r
 393     if (!finished) {\r
 394        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 395        exit(1);\r
 396     }\r
 397     \r
 398     return Tags->access(node2tagpos(x));\r
 399  }\r
 400 \r
 401 // DocIds(x): returns the range of text identifiers that descend from node x.\r
 402 // returns {NULLT, NULLT} when there are no texts descending from x.\r
 403 range XMLTree::DocIds(treeNode x) \r
 404  {\r
 405     if (!finished) {\r
 406        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 407        exit(1);\r
 408     }\r
 409 \r
 410     range r;\r
 411     if (indexing_empty_texts) { // faster, no rank needed\r
 412        r.min = x;\r
 413        r.max = x+2*subtree_size(Par, x)-2;\r
 414     }\r
 415     else { // we are not indexing empty texts, we need rank\r
 416        int min = EBVector->rank1(x-1);                          \r
 417        int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); \r
 418        if (min==max) { // range is empty, no texts within the subtree of x\r
 419           r.min = NULLT;\r
 420           r.max = NULLT;\r
 421        }\r
 422        else { // the range is non-empty, there are texts within the subtree of x\r
 423           r.min = min+1;\r
 424           r.max = max;\r
 425        }\r
 426     }\r
 427     return r;\r
 428  }\r
 429 \r
 430 // Parent(x): returns the parent node of node x.\r
 431 treeNode XMLTree::Parent(treeNode x) \r
 432  {\r
 433     if (!finished) {\r
 434        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 435        exit(1);\r
 436     }\r
 437     if (x == Root())\r
 438       return NULLT;\r
 439     else\r
 440       return parent(Par, x);\r
 441  }\r
 442 \r
 443 // Child(x,i): returns the i-th child of node x, assuming it exists.\r
 444 treeNode XMLTree::Child(treeNode x, int i) \r
 445 {\r
 446     if (!finished) {\r
 447        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 448        exit(1);\r
 449     }\r
 450 \r
 451     if (i <= OPTD) return naive_child(Par, x, i);\r
 452     else return child(Par, x, i);\r
 453  }\r
 454 \r
 455 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
 456 treeNode XMLTree::FirstChild(treeNode x) \r
 457  {\r
 458     if (!finished) {\r
 459        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 460        exit(1);\r
 461     }\r
 462 \r
 463     return first_child(Par, x);\r
 464  }\r
 465 \r
 466 // NextSibling(x): returns the next sibling of node x, assuming it exists.\r
 467 treeNode XMLTree::NextSibling(treeNode x) \r
 468  {\r
 469     if (!finished) {\r
 470        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 471        exit(1);\r
 472     }\r
 473     if (x == Root())\r
 474       return NULLT;\r
 475  \r
 476     return next_sibling(Par, x);\r
 477  }\r
 478 \r
 479 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
 480 treeNode XMLTree::PrevSibling(treeNode x) \r
 481  {\r
 482     if (!finished) {\r
 483        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 484        exit(1);\r
 485     }\r
 486 \r
 487     return prev_sibling(Par, x);\r
 488  }\r
 489 \r
 490 // TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or NULLT if there is none.\r
 491 // Because of the balanced-parentheses representation of the tree, this operation is not supported\r
 492 // efficiently, just iterating among the children of node x until finding the desired child.\r
 493 treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag) \r
 494  {\r
 495     if (!finished) {\r
 496        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 497        exit(1);\r
 498     }\r
 499 \r
 500     treeNode child;\r
 501    \r
 502     child = first_child(Par, x); // starts at first child of node x\r
 503     if (child==(treeNode)-1) return NULLT; // node x is a leaf, there is no such child\r
 504     while (child!=(treeNode)-1) {\r
 505        if (Tags->access(node2tagpos(child)) == tag) { // current child is labeled with tag of interest\r
 506           i--;\r
 507           if (i==0) return child; // we have seen i children of x tagged tag, this is the one we are looking for\r
 508        }\r
 509        child = next_sibling(Par, x); // OK, let's try with the next child\r
 510     }\r
 511     return NULLT; // no such child was found  \r
 512  }\r
 513 \r
 514 // TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within\r
 515 // the subtree of x. Returns NULLT if there is none.\r
 516 treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) \r
 517  {\r
 518     if (!finished) {\r
 519        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 520        exit(1);\r
 521     }\r
 522 \r
 523     int r, s;\r
 524     treeNode y;\r
 525     if (isleaf(Par,x))\r
 526       return NULLT;\r
 527 \r
 528     r = (int) Tags->rank(tag, node2tagpos(x));\r
 529     s = (int) Tags->select(tag, r+1);\r
 530     if (s == -1) return NULLT; // there is no such node\r
 531     y = tagpos2node(s); // transforms the tag position into a node position\r
 532     if (!is_ancestor(Par, x, y)) return NULLT; // the next node tagged tag (in preorder) is not within the subtree of x.\r
 533     else return y;\r
 534  }\r
 535 \r
 536 // TaggedNext(x,tag): returns the first node tagged tag with larger preorder than x \r
 537 // Returns NULLT if there is none.\r
 538 treeNode XMLTree::TaggedNext(treeNode x, TagType tag) \r
 539  {\r
 540     if (!finished) {\r
 541        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 542        exit(1);\r
 543     }\r
 544 \r
 545     int r, s;\r
 546     treeNode y;\r
 547     if (x==NULLT)\r
 548       return NULLT;\r
 549 \r
 550     r = (int) Tags->rank(tag, node2tagpos(x));\r
 551     s = (int) Tags->select(tag, r+1);\r
 552     if (s == -1) return NULLT; // there is no such node\r
 553     y = tagpos2node(s); // transforms the tag position into a node position  \r
 554     return (y<=x ? NULLT : y);\r
 555  }\r
 556 \r
 557 \r
 558 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an\r
 559 // ancestor of x. Returns NULLT if there is none.\r
 560 treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) \r
 561  {\r
 562     if (!finished) {\r
 563        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 564        exit(1);\r
 565     }\r
 566     \r
 567     int r, s;\r
 568     treeNode node_s, root;\r
 569     r = (int)Tags->rank(tag, node2tagpos(x)-1);\r
 570     if (r==0) return NULLT; // there is no such node.\r
 571     s = (int)Tags->select(tag, r);\r
 572     root = root_node(Par);\r
 573     node_s = tagpos2node(s);\r
 574     while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
 575        r--;\r
 576        if (r==0) return NULLT; // there is no such node\r
 577        s = (int)Tags->select(tag, r);  // we should use select_prev instead when provided\r
 578        node_s = tagpos2node(s);\r
 579     }\r
 580     return NULLT; // there is no such node \r
 581  }\r
 582 \r
 583 \r
 584 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in\r
 585 // the subtree of x. Returns NULLT if there is none.\r
 586 treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)\r
 587  {\r
 588     if (!finished) {\r
 589        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 590        exit(1);\r
 591     }\r
 592 \r
 593     int r, s;\r
 594     if (x ==NULLT || x == Root())\r
 595        return NULLT;\r
 596                    \r
 597     r = (int) Tags->rank(tag, find_close(Par, x));\r
 598     s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.\r
 599     if (s==-1) return NULLT;\r
 600     else return tagpos2node(s);\r
 601  } \r
 602 \r
 603 \r
 604 // TaggedFollowingSibling(x,tag): returns the first node tagged tag with larger preorder than x and not in\r
 605 // the subtree of x. Returns NULLT if there is none.\r
 606 treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) \r
 607  {\r
 608     if (!finished) {\r
 609        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 610        exit(1);\r
 611     }\r
 612 \r
 613     int r, s;\r
 614     treeNode ns = next_sibling(Par,x);\r
 615 \r
 616     if (x == NULLT || x == Root() || ns == -1)\r
 617       return NULLT;\r
 618 \r
 619     r = (int) Tags->rank(tag, node2tagpos(ns)-1);\r
 620     s = (int) Tags->select(tag, r+1);  // select returns -1 in case that there is no r+1-th tag.\r
 621     if (s==-1) return NULLT;\r
 622     else return tagpos2node(s);\r
 623  }\r
 624 \r
 625 \r
 626 // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return\r
 627 // NULLT is there is none.\r
 628 treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)\r
 629  {\r
 630     if (!finished) {\r
 631        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 632        exit(1);\r
 633     }\r
 634     \r
 635     if (x == NULLT || x == Root())\r
 636        return NULLT;\r
 637     \r
 638     treeNode s = parent(Par, x), r = Root();\r
 639     while (s != r) {\r
 640        if (Tags->access(node2tagpos(s)) == tag) return s;\r
 641        s = parent(Par, s);\r
 642     }\r
 643     return NULLT;\r
 644  }\r
 645 \r
 646 \r
 647 // PrevText(x): returns the document identifier of the text to the left \r
 648 // of node x, or NULLT if x is the root node or the text is empty.\r
 649 // Assumes Doc ids start from 0.\r
 650 DocID XMLTree::PrevText(treeNode x) \r
 651  {\r
 652     if (!finished) {\r
 653        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 654        exit(1);\r
 655     }\r
 656 \r
 657     if (x == Root()) return NULLT;\r
 658     if (indexing_empty_texts)  // faster, no rank needed\r
 659        return (DocID)x-1;\r
 660     else { // we are not indexing empty texts, rank is needed\r
 661        if (EBVector->access(x-1) == 0) \r
 662           return (DocID)NULLT;  // there is no text to the left of node (text is empty)\r
 663        else\r
 664           return (DocID)EBVector->rank1(x-1)-1;  //-1 because document ids start from 0\r
 665     }\r
 666  }\r
 667 \r
 668 // NextText(x): returns the document identifier of the text to the right\r
 669 // of node x, or NULLT if x is the root node. Assumes Doc ids start from 0.\r
 670 DocID XMLTree::NextText(treeNode x) \r
 671  {\r
 672     if (!finished) {\r
 673        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 674        exit(1);\r
 675     }\r
 676 \r
 677     if (x == Root()) return NULLT;\r
 678     if (indexing_empty_texts)  // faster, no rank needed\r
 679        return (DocID)x+2*subtree_size(Par, x)-1;\r
 680     else { // we are not indexing empty texts, rank is needed\r
 681        int p = x+2*subtree_size(Par, x)-1;\r
 682        if (EBVector->access(p) == 0) // there is no text to the right of node\r
 683           return (DocID)NULLT;\r
 684        else\r
 685           return (DocID)EBVector->rank1(p)-1; //-1 because document ids start from 0\r
 686     }\r
 687  }\r
 688 \r
 689 // MyText(x): returns the document identifier of the text below node x, \r
 690 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc \r
 691 // ids start from 0.\r
 692 DocID XMLTree::MyText(treeNode x) \r
 693  {\r
 694     if (!finished) {\r
 695        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 696        exit(1);\r
 697     }\r
 698 \r
 699     if (!IsLeaf(x)) return NULLT;\r
 700     if (indexing_empty_texts) // faster, no rank needed\r
 701        return (DocID)x;\r
 702     else { // we are not indexing empty texts, rank is needed\r
 703        if (EBVector->access(x) == 0)  // there is no text below node x\r
 704           return (DocID)NULLT;\r
 705        else\r
 706           return (DocID)EBVector->rank1(x)-1; //-1 because document ids start from 0\r
 707     } \r
 708  }\r
 709 \r
 710 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of\r
 711 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.\r
 712 int XMLTree::TextXMLId(DocID d) \r
 713  {\r
 714     if (!finished) {\r
 715        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 716        exit(1);\r
 717     }\r
 718 \r
 719     if (indexing_empty_texts) \r
 720        return d + rank_open(Par, d)+1; // +1 because root has preorder 1\r
 721     else { // slower, needs rank and select\r
 722        int s = EBVector->select1(d+1);\r
 723        return rank_open(Par, s) + d + 1; // +1 because root has preorder 1\r
 724     }\r
 725  }\r
 726 \r
 727 // NodeXMLId(x): returns the preorder of node x in the tree consisting \r
 728 // of all tree nodes and all text nodes. Assumes that the tree root has\r
 729 // preorder 0;\r
 730 int XMLTree::NodeXMLId(treeNode x) \r
 731  {\r
 732     if (!finished) {\r
 733        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 734        exit(1);\r
 735     }\r
 736 \r
 737     if (indexing_empty_texts)\r
 738        return x - 1 + rank_open(Par, x);\r
 739     else {\r
 740        if (x == Root()) return 1; // root node has preorder 1\r
 741        else\r
 742           return rank_open(Par, x) + EBVector->rank1(x-1);\r
 743     }\r
 744  }\r
 745 \r
 746 // ParentNode(d): returns the parent node of document identifier d.\r
 747 treeNode XMLTree::ParentNode(DocID d) \r
 748  {\r
 749     if (!finished) {\r
 750        fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
 751        exit(1);\r
 752     }\r
 753     \r
 754     if (d == NULLT)\r
 755       return NULLT;\r
 756     \r
 757     int s;\r
 758     // OJO : Kim : I added the d+1. before that, else branch was \r
 759     // EBVector->select1(d)\r
 760     // and gave wrong results (I'm really poking a bear with a stick here).\r
 761     if (indexing_empty_texts) s = d;\r
 762     else s = EBVector->select1(d+1);\r
 763     \r
 764     if (inspect(Par,s) == CP) // is a closing parenthesis\r
 765        return parent(Par, find_open(Par, s));\r
 766     else // is an opening parenthesis\r
 767        return (treeNode)s;\r
 768      \r
 769  }\r
 770 \r
 771 \r
 772 // OpenDocument(empty_texts): it starts the construction of the data structure for\r
 773 // the XML document. Parameter empty_texts indicates whether we index empty texts\r
 774 // in document or not. Returns a non-zero value upon success, NULLT in case of error.\r
 775 int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc)\r
 776  {\r
 777     initialized = true;\r
 778     finished = false;\r
 779     found_attributes = false;\r
 780     npar = 0;\r
 781     parArraySize = 1;\r
 782     ntagnames = 4;    \r
 783     disable_tc = dtc;\r
 784     \r
 785     indexing_empty_texts = empty_texts;\r
 786     \r
 787     par_aux = (pb *)umalloc(sizeof(pb)*parArraySize);\r
 788     \r
 789     tags_aux = (TagType *) umalloc(sizeof(TagType));\r
 790     \r
 791     TagName = (unsigned char **) umalloc(4*sizeof(unsigned char*));\r
 792 \r
 793     TagName[0] = (unsigned char *) umalloc(4*sizeof(unsigned char));\r
 794 \r
 795     strcpy((char *) TagName[0], "<@>");\r
 796 \r
 797     TagName[1] = (unsigned char *) umalloc(4*sizeof(unsigned char));\r
 798 \r
 799     strcpy((char *) TagName[1], "<$>");\r
 800     \r
 801     //OJO need to put these in the table too.\r
 802     TagName[2] = (unsigned char *) umalloc(5*sizeof(unsigned char));\r
 803 \r
 804     strcpy((char *) TagName[2], "/<@>");\r
 805 \r
 806     TagName[3] = (unsigned char *) umalloc(5*sizeof(unsigned char));\r
 807 \r
 808     strcpy((char *) TagName[3], "/<$>");\r
 809 \r
 810 \r
 811     if (!indexing_empty_texts) \r
 812       empty_texts_aux = (unsigned int *)umalloc(sizeof(unsigned int));\r
 813        \r
 814     \r
 815     \r
 816     Text = TextCollection::InitTextCollection((unsigned)sample_rate_text);\r
 817     \r
 818     return 1;  // indicates success in the initialization of the data structure\r
 819  }\r
 820 \r
 821 // CloseDocument(): it finishes the construction of the data structure for the XML\r
 822 // document. Tree and tags are represented in the final form, dynamic data \r
 823 // structures are made static, and the flag "finished" is set to true. After that, \r
 824 // the data structure can be queried.\r
 825 int XMLTree::CloseDocument()\r
 826  {\r
 827     if (!initialized) {  // data structure has not been initialized properly\r
 828        fprintf(stderr, "Error: data structure has not been initialized properly (by calling method OpenDocument)\n");\r
 829        return NULLT;\r
 830     }\r
 831     \r
 832     // closing parenthesis for the tree root\r
 833     par_aux = (pb *)urealloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));\r
 834     \r
 835     // creates the data structure for the tree topology\r
 836     Par = (bp *)umalloc(sizeof(bp));\r
 837     bp_construct(Par, npar, par_aux, OPT_DEGREE|0);    \r
 838     // creates structure for tags\r
 839     static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20);\r
 840     static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb);\r
 841     static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb);\r
 842 \r
 843 \r
 844     // If we found an attribute then "<@>" is present in the tree\r
 845     // if we didn't then it is not. "<$>" is never present in the tree\r
 846     int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2;\r
 847 \r
 848     Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,ntagsize, bmb, ssb);\r
 849     \r
 850     delete bmb;\r
 851     delete pmb;\r
 852     delete ssb;\r
 853     // makes the text collection static\r
 854     if (!disable_tc)\r
 855       Text->MakeStatic();\r
 856     \r
 857     // creates the data structure marking the non-empty texts (just in the case it is necessary)\r
 858     if (!indexing_empty_texts)  {\r
 859        EBVector = new static_bitsequence_rrr02((uint *)empty_texts_aux,(ulong)npar,(uint)32);\r
 860        free (empty_texts_aux);\r
 861        empty_texts_aux = NULL;\r
 862     }\r
 863    \r
 864     // OJO was leaked before, found by valgrind\r
 865     free(tags_aux);\r
 866 \r
 867     tags_aux = NULL;\r
 868 \r
 869     finished = true;\r
 870 \r
 871     return 1; // indicates success in the inicialization\r
 872  }\r
 873 \r
 874 \r
 875 // NewOpenTag(tagname): indicates the event of finding a new opening tag in the document.\r
 876 // Tag name is given. Returns a non-zero value upon success, and returns NULLT\r
 877 // in case of failing when trying to insert the new tag.\r
 878 int XMLTree::NewOpenTag(unsigned char *tagname)\r
 879  {\r
 880     int i;\r
 881 \r
 882     if (!initialized) {  // data structure has not been initialized properly\r
 883        fprintf(stderr, "Error: you cannot insert a new opening tag without first calling method OpenDocument first\n");\r
 884        return NULLT;\r
 885     }\r
 886     \r
 887     // inserts a new opening parentheses in the bit sequence\r
 888     if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis\r
 889        par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize);\r
 890        parArraySize *= 2;\r
 891     }\r
 892     \r
 893     setbit(par_aux,npar,OP);  // marks a new opening parenthesis\r
 894 \r
 895     // transforms the tagname into a tag identifier. If the tag is new, we insert\r
 896     // it in the table.\r
 897     for (i=0; i<ntagnames; i++)\r
 898       if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break;\r
 899  \r
 900 \r
 901     // NewOpenTag("<@>") was called\r
 902     if (i==0) \r
 903       found_attributes=true;\r
 904 \r
 905     if (i==ntagnames) { // the tag is a new one, then we insert it\r
 906        TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1));\r
 907        \r
 908        if (!TagName) {\r
 909           fprintf(stderr, "Error: not enough memory\n");\r
 910           return NULLT;\r
 911        }\r
 912        \r
 913        ntagnames++;\r
 914        TagName[i] = (unsigned char *)umalloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1));\r
 915        strcpy((char *)TagName[i], (const char *)tagname);\r
 916     } \r
 917     tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1));\r
 918 \r
 919     tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags\r
 920     \r
 921     npar++;\r
 922     \r
 923     return 1;\r
 924     \r
 925  }\r
 926 \r
 927 \r
 928 // NewClosingTag(tagname): indicates the event of finding a new closing tag in the document.\r
 929 // Tag name is given. Returns a non-zero value upon success, and returns NULLT\r
 930 // in case of failing when trying to insert the new tag.\r
 931 int XMLTree::NewClosingTag(unsigned char *tagname)\r
 932  {\r
 933     int i;\r
 934 \r
 935     if (!initialized) {  // data structure has not been initialized properly\r
 936        fprintf(stderr, "Error: you cannot insert a new closing tag without first calling method OpenDocument first\n");\r
 937        return NULLT;\r
 938     }\r
 939     \r
 940     // inserts a new closing parentheses in the bit sequence\r
 941     if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis\r
 942        par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize);\r
 943        parArraySize *= 2;\r
 944     }\r
 945     \r
 946     setbit(par_aux,npar,CP);  // marks a new closing parenthesis\r
 947 \r
 948     // transforms the tagname into a tag identifier. If the tag is new, we insert\r
 949     // it in the table.\r
 950     for (i=0; i<ntagnames; i++)\r
 951        if ((strcmp((const char *)tagname,(const char *)(TagName[i]+1))==0) && (TagName[i][0]=='/')) break;\r
 952  \r
 953     if (i==ntagnames) { // the tag is a new one, then we insert it\r
 954        TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1));\r
 955        \r
 956        ntagnames++;\r
 957        TagName[i] = (unsigned char *)umalloc(sizeof(char)*(strlen((const char *)tagname)+2));\r
 958        TagName[i][0] = '/';\r
 959        strcpy((char *)&(TagName[i][1]), (const char *)tagname);\r
 960     } \r
 961 \r
 962     tags_aux = (TagType *)urealloc(tags_aux, sizeof(TagType)*(npar + 1));\r
 963 \r
 964     tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags\r
 965     \r
 966     npar++;\r
 967 \r
 968     return 1; // success\r
 969     \r
 970  }\r
 971 \r
 972 \r
 973 // NewText(s): indicates the event of finding a new (non-empty) text s in the document.\r
 974 // The new text is inserted within the text collection. Returns a non-zero value upon\r
 975 // success, NULLT in case of error.\r
 976 int XMLTree::NewText(unsigned char *s)\r
 977  {\r
 978     if (!initialized) {  // data structure has not been initialized properly\r
 979        fprintf(stderr, "Error: you cannot insert a new text without first calling method OpenDocument first\n");\r
 980        return NULLT;\r
 981     }\r
 982 \r
 983     if (disable_tc) {\r
 984       XMLTree::NewEmptyText();\r
 985       return 1;\r
 986     };\r
 987 \r
 988     if (!indexing_empty_texts) {\r
 989        empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));\r
 990               bitset(empty_texts_aux, npar-1);  // marks the non-empty text with a 1 in the bit vector\r
 991     }\r
 992     \r
 993     Text->InsertText(s);\r
 994     string cpps = (char*) s;\r
 995     CachedText.push_back(cpps); \r
 996     \r
 997     return 1; // success\r
 998  }\r
 999 \r
1000 // NewEmptyText(): indicates the event of finding a new empty text in the document.\r
1001 // In case of indexing empty and non-empty texts, we insert the empty texts into the\r
1002 // text collection. In case of indexing only non-empty texts, it just indicates an\r
1003 // empty text in the bit vector of empty texts. Returns a non-zero value upon\r
1004 // success, NULLT in case of error.\r
1005 int XMLTree::NewEmptyText() \r
1006  {\r
1007     unsigned char c = 0;\r
1008     if (!initialized) {  // data structure has not been initialized properly\r
1009        fprintf(stderr, "Error: you cannot insert a new empty text without first calling method OpenDocument first\n");\r
1010        return NULLT;\r
1011     }\r
1012 \r
1013     if (!indexing_empty_texts) {\r
1014        empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));\r
1015        \r
1016        bitclean(empty_texts_aux, npar-1);  // marks the empty text with a 0 in the bit vector\r
1017     }\r
1018     else Text->InsertText(&c); // we insert the empty text just in case we index all the texts\r
1019     \r
1020     return 1; // success    \r
1021  }\r
1022 \r
1023 \r
1024 // GetTagId: returns the tag identifier corresponding to a given tag name.\r
1025 // Returns NULLT in case that the tag name does not exists.\r
1026 TagType XMLTree::GetTagId(unsigned char *tagname)\r
1027  {\r
1028     int i;\r
1029     // this should be changed for more efficient processing\r
1030     for (i=0; i<ntagnames; i++)\r
1031        if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break; \r
1032     if (i==ntagnames) return (TagType)NULLT; // tagname does not exists in the table\r
1033     else return i;\r
1034  }\r
1035 \r
1036 \r
1037 // GetTagName(tagid): returns the tag name of a given tag identifier.\r
1038 // Returns NULL in case that the tag identifier is not valid.\r
1039 unsigned char *XMLTree::GetTagName(TagType tagid)\r
1040  {\r
1041     unsigned char *s;\r
1042 \r
1043     if (tagid >= ntagnames) return NULL; // invalid tag identifier\r
1044     s = (unsigned char *)umalloc((strlen((const char *)TagName[tagid])+1)*sizeof(unsigned char));\r
1045     strcpy((char *)s, (const char *)TagName[tagid]);\r
1046     return s;\r
1047  }\r
1048 \r
1049 \r
1050 //KIM : OJO need the two following methods\r
1051 \r
1052 const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)\r
1053  {\r
1054     if (tagid >= ntagnames) return NULL; // invalid tag identifier\r
1055     return ((const unsigned char*)  TagName[tagid]);\r
1056  }\r
1057 \r
1058 \r
1059 \r
1060 TagType XMLTree::RegisterTag(unsigned char *tagname)\r
1061 {\r
1062   if (!finished)\r
1063     return NULLT;\r
1064   \r
1065   TagType id = XMLTree::GetTagId(tagname);\r
1066   if (id == NULLT){\r
1067     id = ntagnames;\r
1068     ntagnames = ntagnames + 1;    \r
1069     TagName = (unsigned char **) urealloc(TagName,ntagnames*(sizeof(unsigned char*)));\r
1070     TagName[id] = (unsigned char *) umalloc(sizeof(unsigned char)*strlen( (const char*) tagname)+1);\r
1071     strcpy((char*)TagName[id], (const char *)tagname);  \r
1072   };\r
1073 \r
1074   return id;\r
1075 }\r