XMLTree.cpp

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