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