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