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