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