XMLTree.cpp

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