XMLTree.cpp

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