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