XMLTree.h

   1 /******************************************************************************
   2  *   Copyright (C) 2008 by Diego Arroyuelo                                    *
   3  *   Interface for the in-memory XQuery/XPath engine                          *
   4  *                                                                            *
   5  *   This program is free software; you can redistribute it and/or modify     *
   6  *   it under the terms of the GNU Lesser General Public License as published *
   7  *   by the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                      *
   9  *                                                                            *
  10  *   This program is distributed in the hope that it will be useful,          *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
  13  *   GNU Lesser General Public License for more details.                      *
  14  *                                                                            *
  15  *   You should have received a copy of the GNU Lesser General Public License *
  16  *   along with this program; if not, write to the                            *
  17  *   Free Software Foundation, Inc.,                                          *
  18  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.                *
  19  ******************************************************************************/
  20
  21 #ifndef XMLTREE_H_
  22 #define XMLTREE_H_
  23
  24
  25 #include <unordered_set>
  26 #include <unordered_map>
  27 #include <sstream>
  28 #include <TextCollection/TextCollectionBuilder.h>
  29
  30 #undef W
  31 #undef WW
  32 #undef Wminusone
  33
  34 #include <bp/bp.h>
  35 #include <bp/bp-darray.h>
  36 #include <libcds/includes/basics.h>
  37 #include <libcds/includes/static_bitsequence.h>
  38 #include <libcds/includes/alphabet_mapper.h>
  39 #include <libcds/includes/static_sequence.h>
  40
  41 using SXSI::TextCollection;
  42 using SXSI::TextCollectionBuilder;
  43
  44
  45 // this constant is used to efficiently compute the child operation in the tree
  46 #define OPTD 10
  47
  48 #define NULLT -1
  49
  50 #define PERM_SAMPLE 10
  51
  52
  53 typedef int treeNode;
  54 typedef int TagType;
  55 typedef int DocID;
  56
  57 typedef struct {
  58    int min;
  59    int max;
  60 } range;
  61
  62 // Encoding of the XML Document :
  63 // The following TAGs and IDs are fixed, "" is the tag of the root.
  64 // a TextNode is represented by a leaf <<$>></<$>> The DocId in the TextCollection
  65 // of that leaf is kept in a bit sequence.
  66 // a TextNode below an attribute is likewise represented by a leaf <<@$>><</@$>>
  67 // An element <e a1="v1" a2="v2" ... an="vn" > ...</e> the representation is:
  68 // <e><<@>> <<@>a1> <<$@>>DocID(v1)</<$@>></<@>a1> ... </<@>> .... </e>
  69 // Hence the attributes (if any) are always below the first child of their element,
  70 // as the children of a fake node <@>.
  71
  72
  73 #define DOCUMENT_OPEN_TAG ""
  74 #define DOCUMENT_TAG_ID 0
  75 #define ATTRIBUTE_OPEN_TAG "<@>"
  76 #define ATTRIBUTE_TAG_ID 1
  77 #define PCDATA_OPEN_TAG "<$>"
  78 #define PCDATA_TAG_ID 2
  79 #define ATTRIBUTE_DATA_OPEN_TAG "<@$>"
  80 #define ATTRIBUTE_DATA_TAG_ID 3
  81 #define CLOSING_TAG   "</>"
  82 #define CLOSING_TAG_ID 4
  83 #define DOCUMENT_CLOSE_TAG "/"
  84 #define ATTRIBUTE_CLOSE_TAG "/<@>"
  85 #define PCDATA_CLOSE_TAG "/<$>"
  86 #define ATTRIBUTE_DATA_CLOSE_TAG "/<@$>"
  87
  88
  89 typedef std::unordered_set<int> TagIdSet;
  90 typedef std::unordered_map<std::string,int> TagIdMap;
  91 typedef TagIdMap::const_iterator TagIdMapIT;
  92
  93 #define REGISTER_TAG(v,h,t) do { (h)->insert(std::make_pair((t),(v)->size()));\
  94     (v)->push_back(t); } while (false)
  95
  96 // returns NULLT if the test is true
  97 #define NULLT_IF(x)  do { if (x) return NULLT; } while (0)
  98 #define IS_NIL(x) ((x) < 0)
  99
 100 // Direct calls to sarray library
 101
 102 #define BUFFER_ALLOC (8192 * 2)
 103 #define BUFFER_SIZE (BUFFER_ALLOC / 2)
 104
 105 // tag position -> tree node
 106 static treeNode tagpos2node(int t)
 107  {
 108     return (treeNode) t;
 109  }
 110 // tree node -> tag position
 111 static int node2tagpos(treeNode x)
 112 {
 113   return (int)x;
 114 }
 115
 116
 117 class XMLTreeBuilder;
 118
 119 class XMLTree {
 120
 121   // Only the builder can access the constructor
 122   friend class XMLTreeBuilder;
 123
 124  private:
 125    /** Balanced parentheses representation of the tree */
 126    bp *Par;
 127
 128    /** Mapping from tag identifer to tag name */
 129    std::vector<std::string> *TagName;
 130    TagIdMap * tIdMap;
 131
 132    /** Bit vector indicating with a 1 the positions of the non-empty texts. */
 133    static_bitsequence *EBVector;
 134
 135    /** Tag sequence represented with a data structure for rank and select */
 136    static_sequence *Tags;
 137    uint * tags_fix;
 138    uint tags_blen, tags_len;
 139
 140    /** The texts in the XML document */
 141    TextCollection *Text;
 142
 143    // Allows to disable the TextCollection for benchmarkin purposes
 144    bool disable_tc;
 145    SXSI::TextCollectionBuilder::index_type_t text_index_type;
 146
 147    std::string *buffer;
 148    std::vector<std::string *> *print_stack;
 149
 150
 151    void _real_flush(int fd, size_t size) {
 152      if (size == 0) return;
 153      size_t written;
 154      while (1) {
 155        written = write(fd, buffer->data(), size);
 156                    if ((written < 0) && (errno == EAGAIN || errno == EINTR))
 157                      continue;
 158                    break;
 159      };
 160      buffer->clear();
 161
 162    }
 163
 164    void _flush(int fd){
 165            size_t size = buffer->size();
 166            if (size < BUFFER_SIZE) return;
 167            _real_flush(fd, size);
 168    }
 169
 170    void _dput_str(std::string s, int fd){
 171            buffer->append(s);
 172            _flush(fd);
 173    }
 174
 175    void _dputs(const char* s, int fd){
 176      buffer->append(s);
 177      _flush(fd);
 178    }
 179
 180    void _dputc(const char c, int fd){
 181      buffer->push_back(c);
 182    }
 183
 184    size_t _dprintf(const char* s, int fd){
 185      if (s == NULL) return 0;
 186      size_t i;
 187      char c;
 188      for (i = 0; (c = s[i]); i++) {
 189              switch (c) {
 190              case '"':
 191                      _dputs("&quot;", fd);
 192                      break;
 193              case '&':
 194                      _dputs("&amp;", fd);
 195                      break;
 196              case '\'':
 197                      _dputs("&apos;", fd);
 198                      break;
 199              case '<':
 200                      _dputs("&lt;", fd);
 201                      break;
 202              case '>':
 203                      _dputs("&gt;", fd);
 204                      break;
 205              default:
 206                      _dputc(c, fd);
 207
 208              };
 209      };
 210      return i;
 211    }
 212
 213    void PrintNode(treeNode n, int fd);
 214    /** Data structure constructors */
 215    XMLTree(){ buffer = 0;};
 216
 217    // non const pointer are freed by this method.
 218    XMLTree( pb * const par,
 219             uint npar,
 220             std::vector<std::string> * const TN,
 221             TagIdMap * const tim, uint *empty_texts_bmp,
 222             TagType *tags,
 223             TextCollectionBuilder * const TCB, bool dis_tc,
 224             TextCollectionBuilder::index_type_t _index_type );
 225
 226 public:
 227    /** Data structure destructor */
 228    ~XMLTree();
 229
 230    /** root(): returns the tree root. */
 231    treeNode Root() { return 0; }
 232
 233    /** Size() :  Number of parenthesis */
 234    unsigned int Size(){
 235      return tags_len/2;
 236    }
 237
 238
 239    /** NumTags() : Number of distinct tags */
 240    unsigned int NumTags() {
 241            return TagName->size();
 242    }
 243
 244    int TagsBinaryLength(){ return tags_blen; };
 245    unsigned int TagStructLength(){ return uint_len(tags_blen,tags_len); };
 246    unsigned int * TagStruct() { return tags_fix; };
 247
 248
 249    /** SubtreeSize(x): the number of nodes (and attributes) in the subtree of
 250     * node x. */
 251    int SubtreeSize(treeNode x) { return bp_subtree_size(Par, x); }
 252
 253    /** SubtreeTags(x,tag): the number of occurrences of tag within the subtree
 254     * of node x. */
 255    int SubtreeTags(treeNode x, TagType tag){
 256            //int s = x + 2*subtree_size(Par, x) - 1;
 257            treeNode y = bp_find_close(Par, x);
 258
 259            if (y - x < 10) {
 260                    int count = 0;
 261                    for(int i = x; i < y; i++)
 262                            count += (Tag(i) == tag);
 263                    return count;
 264            }
 265            else
 266                    return (Tags->rank(tag, y) - Tags->rank(tag, x));
 267    };
 268
 269    /** SubtreeElements(x) of element nodes in the subtree of x
 270     */
 271    int SubtreeElements(treeNode x);
 272
 273    /** IsLeaf(x): returns whether node x is leaf or not. In the succinct
 274     * representation this is just a bit inspection. */
 275
 276    bool IsLeaf(treeNode x);
 277
 278    /** IsAncestor(x,y): returns whether node x is ancestor of node y. */
 279
 280    bool IsAncestor(treeNode x, treeNode y);
 281
 282
 283    /** IsRigthDescendant returns true if y is a descendant of x and y is
 284        not a descendant of the first child of x */
 285    bool IsRightDescendant(treeNode x, treeNode y) {
 286      if (x <= Root()) return false;
 287      treeNode z = bp_parent_close(Par, x);
 288      treeNode c = bp_find_close(Par, x);
 289      return (y > c && y < z );
 290    }
 291
 292
 293    /** IsChild(x,y): returns whether node x is parent of node y. */
 294    bool IsChild(treeNode x, treeNode y);
 295
 296    /** IsFirstChild(x): returns whether node x is the first child of its parent. */
 297    /* OCAML */
 298    bool IsFirstChild(treeNode x) {
 299            return ((x != NULLT)&&(x==Root() || bp_prev_sibling(Par,x) == (treeNode)-1));
 300    };
 301
 302    /** NumChildren(x): number of children of node x. Constant time with the
 303     * data structure of Sadakane. */
 304    int NumChildren(treeNode x);
 305
 306    /** ChildNumber(x): returns i if node x is the i-th children of its
 307     * parent. */
 308    int ChildNumber(treeNode x);
 309
 310    /** Depth(x): depth of node x, a simple binary rank on the parentheses
 311     * sequence. */
 312    int Depth(treeNode x);
 313
 314    /** Preorder(x): returns the preorder number of node x, just regarding tree
 315     * nodes (and not texts). */
 316    int Preorder(treeNode x);
 317
 318    /** Postorder(x): returns the postorder number of node x, just regarding
 319     * tree nodes (and not texts). */
 320    int Postorder(treeNode x);
 321
 322
 323    /** DocIds(x): returns the range (i.e., a pair of integers) of document
 324     * identifiers that descend from node x. */
 325    range DocIds(treeNode x);
 326
 327    /** Parent(x): returns the parent node of node x. */
 328    treeNode Parent(treeNode x) {
 329      return (x == Root()) ? NULLT : bp_parent(Par, x);
 330    };
 331
 332    treeNode BinaryParent(treeNode x){
 333      if (x <= Root())
 334        return NULLT;
 335      else {
 336        treeNode prev = x - 1;
 337        return (bp_inspect(Par, prev) == OP) ? prev : bp_find_open(Par, prev);
 338      };
 339    };
 340
 341    /* Assumes x is neither 0 nor -1 */
 342
 343    /** Child(x,i): returns the i-th child of node x, assuming it exists. */
 344    treeNode Child(treeNode x, int i);
 345
 346
 347
 348    /** LastChild(x): returns the last child of node x.  */
 349    treeNode LastChild(treeNode x) {
 350            NULLT_IF(x == NULLT || bp_isleaf(Par,x));
 351            return bp_find_open(Par, bp_find_close(Par, x)-1);
 352    }
 353
 354    /** PrevSibling(x): returns the previous sibling of node x, assuming it
 355     * exists. */
 356
 357    treeNode PrevSibling(treeNode x)
 358    {
 359            NULLT_IF(x==NULLT);
 360            return bp_prev_sibling(Par, x);
 361    }
 362
 363
 364    /** TaggedChild(x,tag): returns the first child of node x tagged tag, or
 365     * NULLT if there is none. Because of the balanced-parentheses representation
 366     * of the tree, this operation is not supported efficiently, just iterating
 367     * among the children of node x until finding the desired child. */
 368
 369
 370    treeNode SelectChild(treeNode x, TagIdSet * tags);
 371
 372    /** TaggedFollowingSibling(x,tag): returns the first sibling of node x tagged tag, or
 373     *  NULLT if there is none. */
 374
 375    treeNode SelectFollowingSibling(treeNode x, TagIdSet * tags);
 376
 377
 378
 379
 380    treeNode SelectDescendant(treeNode x, TagIdSet * tags) {
 381    NULLT_IF (x == NULLT);
 382    treeNode fc = x+1;
 383    if (bp_inspect(Par, fc) == CP) return NULLT;
 384    treeNode min = NULLT;
 385    treeNode aux;
 386
 387    TagIdSet::const_iterator tagit;
 388    for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {
 389            aux = TaggedDescendant(x, (TagType) *tagit);
 390            if (((unsigned int) aux) < ((unsigned int) min)) min = aux;
 391    };
 392    return min;
 393  }
 394
 395    /** TaggedPrec(x,tag): returns the first node tagged tag with smaller
 396     * preorder than x and not an ancestor of x. Returns NULLT if there
 397     * is none. */
 398    treeNode TaggedPreceding(treeNode x, TagType tag);
 399
 400    /** TaggedFoll(x,tag): returns the first node tagged tag with larger
 401     * preorder than x and not in the subtree of x. Returns NULLT if there
 402     * is none. */
 403    treeNode TaggedFollowing(treeNode x, TagType tag);
 404
 405
 406
 407    treeNode SelectFollowingBelow(treeNode x, TagIdSet * tags, treeNode ancestor);
 408
 409    //   treeNode TaggedFollowingBefore(treeNode x, TagType tag,treeNode closing);
 410
 411    treeNode SelectFollowingBefore(treeNode x, TagIdSet * tags, treeNode ancestor_closing)
 412  {
 413
 414    NULLT_IF(x <= 0);
 415
 416    treeNode close = bp_find_close(Par,x);
 417
 418
 419    treeNode min = NULLT;
 420    treeNode aux;
 421
 422
 423    TagIdSet::const_iterator tagit;
 424    for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {
 425
 426            aux = tagpos2node(Tags->select_next(*tagit, close));
 427
 428            if (((unsigned int) aux) < ((unsigned int) min)) min = aux;
 429    };
 430
 431
 432    return (min < ancestor_closing) ? min : NULLT;
 433
 434  }
 435
 436    /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged
 437      * tag. Return NULLT is there is none. */
 438    treeNode TaggedAncestor(treeNode x, TagType tag);
 439
 440    /** PrevText(x): returns the document identifier of the text to the left of
 441     * node x, or NULLT if x is the root node. */
 442    DocID PrevText(treeNode x);
 443
 444    /** NextText(x): returns the document identifier of the text to the right of
 445     * node x, or NULLT if x is the root node. */
 446    DocID NextText(treeNode x);
 447
 448    /** MyText(x): returns the document identifier of the text below node x, or
 449     * NULLT if x is not a leaf node. */
 450    DocID MyText(treeNode x);
 451    DocID MyTextUnsafe(treeNode x);
 452
 453    /** TextXMLId(d): returns the preorder of document with identifier d in the
 454     * tree consisting of all tree nodes and all text nodes. */
 455    int TextXMLId(DocID d);
 456
 457    /** NodeXMLId(x): returns the preorder of node x in the tree consisting of
 458     * all tree nodes and all text nodes. */
 459    int NodeXMLId(treeNode x);
 460
 461    /** ParentNode(d): returns the parent node of document identifier d. */
 462    treeNode ParentNode(DocID d);
 463
 464    treeNode PrevNode(DocID d);
 465
 466    /** GetTagId(tagname): returns the tag identifier corresponding to a given
 467     * tag name. Returns NULLT in case that the tag name does not exists. */
 468    TagType GetTagId(unsigned char *tagname);
 469
 470    /** GetTagName(tagid): returns the tag name of a given tag identifier.
 471     * Returns NULL in case that the tag identifier is not valid.*/
 472    unsigned char *GetTagName(TagType tagid);
 473
 474    /** GetTagName(tagid): returns the tag name of a given tag identifier.
 475     *  The result is just a reference and should not be freed by the caller.
 476     */
 477    const unsigned char *GetTagNameByRef(TagType tagid);
 478
 479    /** RegisterTag adds a new tag to the tag collection this is needed
 480     * if the query contains a tag which is not in the document, we need
 481     * to give this new tag a fresh id and store it somewhere. A logical
 482     * choice is here.
 483     * We might want to use a hashtable instead of an array though.
 484     */
 485    TagType RegisterTag(unsigned char *tagname);
 486
 487    bool EmptyText(DocID i) {
 488        return Text->EmptyText(i);
 489    }
 490
 491    /** Prefix(s): search for texts prefixed by string s. */
 492    TextCollection::document_result Prefix(uchar const *s) {
 493       return Text->Prefix(s);
 494    }
 495
 496    /** Suffix(s): search for texts having string s as a suffix. */
 497    TextCollection::document_result Suffix(uchar const *s) {
 498       return Text->Suffix(s);
 499    }
 500
 501    /** Equal(s): search for texts equal to string s. */
 502    TextCollection::document_result Equals(uchar const *s) {
 503       return Text->Equal(s);
 504    }
 505
 506    /** Contains(s): search for texts containing string s.  */
 507    TextCollection::document_result Contains(uchar const *s) {
 508       return Text->Contains(s);
 509    }
 510
 511    /** LessThan(s): returns document identifiers for the texts that
 512     * are lexicographically smaller than string s. */
 513    TextCollection::document_result LessThan(uchar const *s) {
 514       return Text->LessThan(s);
 515    }
 516
 517    /** IsPrefix(x): returns true if there is a text prefixed by string s. */
 518    bool IsPrefix(uchar const *s) {
 519       return Text->IsPrefix(s);
 520    }
 521
 522    /** IsSuffix(s): returns true if there is a text having string s as a
 523     * suffix.*/
 524    bool IsSuffix(uchar const *s) {
 525       return Text->IsSuffix(s);
 526    }
 527
 528    /** IsEqual(s): returns true if there is a text that equals given
 529     * string s. */
 530    bool IsEqual(uchar const *s) {
 531       return Text->IsEqual(s);
 532    }
 533
 534    /** IsContains(s): returns true if there is a text containing string s. */
 535    bool IsContains(uchar const *s) {
 536       return Text->IsContains(s);
 537    }
 538
 539    /** IsLessThan(s): returns true if there is at least a text that is
 540     * lexicographically smaller than string s. */
 541    bool IsLessThan(uchar const *s) {
 542       return Text->IsLessThan(s);
 543    }
 544
 545    /** Count(s): Global counting  */
 546    unsigned Count(uchar const *s) {
 547       return Text->Count(s);
 548    }
 549
 550    /** CountPrefix(s): counting version of Prefix(s). */
 551    unsigned CountPrefix(uchar const *s) {
 552       return Text->CountPrefix(s);
 553    }
 554
 555    /** CountSuffix(s): counting version of Suffix(s). */
 556    unsigned CountSuffix(uchar const *s) {
 557       return Text->CountSuffix(s);
 558    }
 559
 560    /** CountEqual(s): counting version of Equal(s). */
 561    unsigned CountEqual(uchar const *s) {
 562       return Text->CountEqual(s);
 563    }
 564
 565    /** CountContains(s): counting version of Contains(s). */
 566    unsigned CountContains(uchar const *s) {
 567       return Text->CountContains(s);
 568    }
 569
 570    /** CountLessThan(s): counting version of LessThan(s). */
 571    unsigned CountLessThan(uchar const *s) {
 572       return Text->CountLessThan(s);
 573    }
 574
 575    /** GetText(d): returns the text corresponding to document with
 576     * id d. */
 577    uchar* GetText(DocID d) {
 578
 579        uchar * s = Text->GetText(d);
 580        return (s[0] == 1 ? (s+1) : s);
 581    }
 582
 583    /** GetText(i, j): returns the texts corresponding to documents with
 584     * ids i, i+1, ..., j. Texts are separated by '\0' character.  */
 585    //   uchar* GetText(DocID i, DocID j) {
 586    //  uchar * s = Text->GetText(i, j);
 587    // return (s[0] == 1 ? (uchar*)"" : s);
 588    //}
 589
 590    TextCollection *getTextCollection() {
 591       return Text;
 592    }
 593
 594    /** Save: saves XML tree data structure to file. */
 595    void Save(int fd, char* name );
 596
 597    /** Load: loads XML tree data structure from file. sample_rate_text
 598     * indicates the sample rate for the text search data structure. */
 599    static XMLTree *Load(int fd, bool load_tc, int sample_factor, char * name);
 600
 601    void insertTag(TagType tag, uint position);
 602
 603    void print_stats();
 604
 605
 606    /** Parenthesis functions */
 607    treeNode Closing(treeNode x);
 608
 609    bool IsOpen(treeNode x);
 610
 611
 612    /** Print procedure */
 613    void Print(int fd,treeNode x, bool no_text);
 614    void Print(int fd,treeNode x) { Print(fd,x,false); }
 615    void Flush(int fd){ if (buffer) _real_flush(fd, buffer->size()); }
 616
 617   // The following are inlined here for speed
 618   /** Tag(x): returns the tag identifier of node x. */
 619
 620    inline TagType Tag(treeNode x) const throw () {
 621           if (tags_blen == 8)
 622                   return  (TagType) (((uchar*)tags_fix)[(int) x]);
 623           else
 624                   return get_field(tags_fix, tags_blen, x);
 625                   /*
 626                   {
 627           size_t idxlen = x * tags_blen;
 628           size_t j = idxlen % W;
 629           size_t i = idxlen / W;
 630           size_t offset = W - tags_blen;
 631           size_t offset2 = offset - j;
 632           size_t w = tags_fix[i];
 633           return (offset2 >= 0)
 634                   ? ( w << offset2 ) >> offset
 635                   : ( w >> j) | (tags_fix[i+1] << (W+offset2)) >> offset;
 636                   }; */
 637
 638   }
 639
 640      /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf
 641     */
 642    treeNode FirstChild(treeNode x) {
 643            NULLT_IF(x==NULLT);
 644            return bp_first_child(Par, x);
 645    };
 646
 647
 648    /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT
 649     *    if none.
 650     */
 651    treeNode FirstElement(treeNode node){
 652      {
 653        NULLT_IF(node == NULLT);
 654        treeNode x = bp_first_child(Par, node);
 655        NULLT_IF(x == NULLT);
 656        switch (Tag(x)){
 657
 658        case ATTRIBUTE_TAG_ID:
 659                x = bp_next_sibling(Par,x);
 660                if (x == NULLT || Tag(x) != PCDATA_TAG_ID) return x;
 661
 662        case PCDATA_TAG_ID:
 663                x = x+2;
 664                return (bp_inspect(Par,x)==OP)? x : NULLT;
 665
 666        default:
 667                return x;
 668        }
 669      }
 670    };
 671
 672   /** NextSibling(x): returns the next sibling of node x, or NULLT if none
 673    * exists. */
 674
 675   treeNode NextSibling(treeNode x) {
 676     NULLT_IF (x <= 0);
 677     return bp_next_sibling(Par, x);
 678   };
 679
 680    /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT
 681     *    if none.
 682     */
 683   treeNode NextElement(treeNode x)
 684   {
 685     NULLT_IF(x <= 0);
 686     x = bp_next_sibling(Par, x);
 687     NULLT_IF(x == NULLT);
 688     if (Tag(x) == PCDATA_TAG_ID){
 689       int y = x+2;
 690       return (bp_inspect(Par, y) == OP) ? y : NULLT;
 691     }
 692     else return x;
 693   };
 694      /** TaggedDesc(x,tag): returns the first node tagged tag with larger
 695     * preorder than x and within the subtree of x. Returns NULT if there
 696     * is none. */
 697   inline treeNode TaggedNext(treeNode x, TagType tag)
 698   {
 699     return tagpos2node(Tags->select_next(tag,node2tagpos(x)));
 700   }
 701   inline treeNode TaggedDescendant(treeNode x, TagType tag)
 702   {
 703
 704           int s = (int) Tags->select_next(tag,node2tagpos(x));
 705           NULLT_IF (s == -1);
 706
 707           treeNode y = tagpos2node(s); // transforms the tag position into a node position
 708
 709           return (bp_is_ancestor(Par,x,y) ? y : NULLT);
 710   };
 711
 712   inline treeNode TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)
 713   {
 714           treeNode close = bp_find_close(Par, x);
 715           treeNode s = tagpos2node(Tags->select_next(tag, close));
 716
 717           if (ancestor == Root() || s == NULLT || s < bp_find_close(Par,ancestor)) return s;
 718           else return NULLT;
 719   };
 720
 721   inline treeNode TaggedFollowingBefore(treeNode x, TagType tag, treeNode ancestor_closing)
 722   {
 723           treeNode close = bp_find_close(Par, x);
 724           treeNode s = tagpos2node(Tags->select_next(tag, close));
 725
 726           if (ancestor_closing == Root() || s == NULLT || s < ancestor_closing) return s;
 727           else return NULLT;
 728   };
 729
 730   inline treeNode NextNodeBefore(treeNode x, treeNode ancestor_closing)
 731   {
 732     treeNode close = bp_find_close(Par, x);
 733     int rank = bp_rank_open(Par, close);
 734     treeNode y = bp_select_open(Par, rank+1);
 735     return (y < ancestor_closing) ? y : NULLT;
 736   };
 737
 738 // TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.
 739 treeNode TaggedFollowingSibling(treeNode x, TagType tag)
 740 {
 741   NULLT_IF(x==NULLT);
 742   treeNode sibling = x;
 743   TagType ctag;
 744   while ((sibling = bp_next_sibling(Par, sibling)) != NULLT) {
 745     ctag = Tag(sibling);
 746     if (ctag == tag) return sibling;
 747   }
 748   return NULLT;
 749 };
 750
 751 treeNode TaggedChild(treeNode x, TagType tag)
 752 {
 753
 754    NULLT_IF(x==NULLT || bp_isleaf(Par,x));
 755    treeNode child;
 756    child = bp_first_child(Par, x);
 757
 758 if (Tag(child) == tag)
 759      return child;
 760    else
 761      return TaggedFollowingSibling(child, tag);
 762 };
 763
 764
 765 };
 766
 767
 768 #endif
 769