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