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