XMLTree.h

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