XMLTree.cpp

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