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