XMLTree.h

   1 \r
   2 /******************************************************************************\r
   3  *   Copyright (C) 2008 by Diego Arroyuelo                                    *\r
   4  *   Interface for the in-memory XQuery/XPath engine                          *\r
   5  *                                                                            *\r
   6  *   This program is free software; you can redistribute it and/or modify     *\r
   7  *   it under the terms of the GNU Lesser General Public License as published *\r
   8  *   by the Free Software Foundation; either version 2 of the License, or     *\r
   9  *   (at your option) any later version.                                      *\r
  10  *                                                                            *\r
  11  *   This program is distributed in the hope that it will be useful,          *\r
  12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of           *\r
  13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *\r
  14  *   GNU Lesser General Public License for more details.                      *\r
  15  *                                                                            *\r
  16  *   You should have received a copy of the GNU Lesser General Public License *\r
  17  *   along with this program; if not, write to the                            *\r
  18  *   Free Software Foundation, Inc.,                                          *\r
  19  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.                *\r
  20  ******************************************************************************/ \r
  21 \r
  22 #ifndef XMLTREE_H_\r
  23 #define XMLTREE_H_\r
  24 #include "TextCollection/TextCollectionBuilder.h"\r
  25 #include <stdio.h>\r
  26 #include <stdlib.h>\r
  27 #include <cstring>\r
  28 \r
  29 //KIM : OJO\r
  30 //clash between TextCollection/Tools.h and libcds/includes/basics.h\r
  31 #undef W\r
  32 #undef WW\r
  33 #undef Wminusone\r
  34 \r
  35 #include "bp.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         // sets bit p in e\r
  51 #define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W)))\r
  52         // cleans bit p in e\r
  53 #define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W)))\r
  54 \r
  55 \r
  56 typedef int treeNode;\r
  57 typedef int TagType; \r
  58 typedef int DocID;  \r
  59 \r
  60 typedef struct {\r
  61    int min;\r
  62    int max;\r
  63 } range;\r
  64 \r
  65 \r
  66 //KIM : OJO\r
  67 // I know this class implements the working draft that we have but the logics seem flawed here...\r
  68 // We should have two classes. One XMLTreeBuilder and one XMLTree.\r
  69 // XMLTreeBuilder would have OpenDocument, NewOpenTag,... and CloseDocument would return an XMLTree\r
  70 // XMLTree would have only an initialized structure. If find it really ugly to check (!finished) or (!initialized)\r
  71 // in every function (FirstChild....).\r
  72 \r
  73 class XMLTree {\r
  74    /** Balanced parentheses representation of the tree */\r
  75    bp *Par;\r
  76  \r
  77    /** Mapping from tag identifer to tag name */  \r
  78    unsigned char **TagName;\r
  79   \r
  80    /** boolean flag indicating whether we are indexing empty texts or not */\r
  81    bool indexing_empty_texts; \r
  82    \r
  83    /** Bit vector indicating with a 1 the positions of the non-empty texts. */\r
  84    static_bitsequence_rrr02 *EBVector;  \r
  85                       \r
  86    /** Tag sequence represented with a data structure for rank and select */\r
  87    static_sequence *Tags;\r
  88          uint * tags_fix;\r
  89          uint tags_blen, tags_len;\r
  90 \r
  91    /** The texts in the XML document */\r
  92    TextCollectionBuilder *TextBuilder;\r
  93    TextCollection *Text;\r
  94 \r
  95    /** The texts in the XML document (cached for faster display) */\r
  96    vector<string> CachedText;\r
  97    \r
  98    /** Flag indicating whether the whole data structure has been constructed or \r
  99     * not. If the value is true, you cannot add more texts, nodes, etc. */\r
 100    bool finished;\r
 101 \r
 102    /** Flag indicating whether the construction of the data structure has been\r
 103     * initialized or not (by calling method OpenDocument()). If this is true,\r
 104     * you cannot insert new tags or texts. */\r
 105    bool initialized;\r
 106    \r
 107    /* the following components are used for construction purposes */\r
 108    pb *par_aux;\r
 109    TagType *tags_aux;\r
 110    int npar;\r
 111    int parArraySize;\r
 112    int ntagnames;\r
 113    unsigned int *empty_texts_aux;\r
 114 \r
 115    // KIM : OJO\r
 116    // I added those two. The TagName array should always contains two special tags\r
 117    // <@> for attributes and <$> for PCDATA.\r
 118    // <$> can never be in a document (since we handle the text differently)\r
 119    // but <@> can be returned by the parser. This boolean is needed for the construction\r
 120    // of the Tag bitmap to know if <@> must be taken into account or not\r
 121    bool found_attributes;\r
 122 \r
 123    // KIM : OJO\r
 124    // Allows to disable the TextCollection for benchmarkin purposes\r
 125    bool disable_tc;\r
 126    \r
 127 public:\r
 128          void print_stats();\r
 129 \r
 130    /** Data structure constructor */\r
 131    XMLTree() {finished = false; initialized = false; Text = 0; TextBuilder = 0; }; \r
 132  \r
 133    /** Data structure destructor */\r
 134    ~XMLTree();\r
 135    \r
 136    /** root(): returns the tree root. */\r
 137    treeNode Root();\r
 138    \r
 139    /** SubtreeSize(x): the number of nodes (and attributes) in the subtree of \r
 140     * node x. */\r
 141    int SubtreeSize(treeNode x);\r
 142    \r
 143    /** SubtreeTags(x,tag): the number of occurrences of tag within the subtree \r
 144     * of node x. */\r
 145    int SubtreeTags(treeNode x, TagType tag);\r
 146    \r
 147    /** IsLeaf(x): returns whether node x is leaf or not. In the succinct \r
 148     * representation this is just a bit inspection. */\r
 149    bool IsLeaf(treeNode x);\r
 150     \r
 151    /** IsAncestor(x,y): returns whether node x is ancestor of node y. */\r
 152    bool IsAncestor(treeNode x, treeNode y);\r
 153   \r
 154    /** IsChild(x,y): returns whether node x is parent of node y. */\r
 155    bool IsChild(treeNode x, treeNode y);\r
 156 \r
 157    /** IsChild(x,y): returns whether node x is the first child of its parent */\r
 158    bool IsFirstChild(treeNode x);\r
 159    \r
 160    /** NumChildren(x): number of children of node x. Constant time with the \r
 161     * data structure of Sadakane. */\r
 162    int NumChildren(treeNode x);\r
 163    \r
 164    /** ChildNumber(x): returns i if node x is the i-th children of its \r
 165     * parent. */\r
 166    inline int ChildNumber(treeNode x);\r
 167 \r
 168    /** Depth(x): depth of node x, a simple binary rank on the parentheses \r
 169     * sequence. */\r
 170    int Depth(treeNode x);\r
 171    \r
 172    /** Preorder(x): returns the preorder number of node x, just regarding tree \r
 173     * nodes (and not texts). */ \r
 174    int Preorder(treeNode x);\r
 175    \r
 176    /** Postorder(x): returns the postorder number of node x, just regarding \r
 177     * tree nodes (and not texts). */\r
 178    int Postorder(treeNode x);\r
 179    \r
 180    /** Tag(x): returns the tag identifier of node x. */\r
 181    TagType Tag(treeNode x);\r
 182    \r
 183    /** DocIds(x): returns the range (i.e., a pair of integers) of document \r
 184     * identifiers that descend from node x. */\r
 185    range DocIds(treeNode x);\r
 186    \r
 187    /** Parent(x): returns the parent node of node x. */\r
 188    treeNode Parent(treeNode x);\r
 189    \r
 190    /** Child(x,i): returns the i-th child of node x, assuming it exists. */   \r
 191    treeNode Child(treeNode x, int i);\r
 192    \r
 193    /** FirstChild(x): returns the first child of node x, assuming it exists. \r
 194     * Very fast in BP. */\r
 195    treeNode FirstChild(treeNode x);\r
 196    \r
 197    /** LastChild(x): returns the last child of node x. \r
 198     * Implemented by Kim naively. */\r
 199    treeNode LastChild(treeNode x);\r
 200 \r
 201    /** NextSibling(x): returns the next sibling of node x, assuming it \r
 202     * exists. */\r
 203 \r
 204    treeNode NextSibling(treeNode x);\r
 205    \r
 206    /** PrevSibling(x): returns the previous sibling of node x, assuming it \r
 207     * exists. */\r
 208    treeNode PrevSibling(treeNode x);\r
 209    \r
 210    /** TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or \r
 211     * NULLT if there is none. Because of the balanced-parentheses representation \r
 212     * of the tree, this operation is not supported efficiently, just iterating \r
 213     * among the children of node x until finding the desired child. */\r
 214    treeNode TaggedChild(treeNode x, int i, TagType tag);\r
 215    \r
 216    /** TaggedDesc(x,tag): returns the first node tagged tag with larger \r
 217     * preorder than x and within the subtree of x. Returns NULT if there \r
 218     * is none. */\r
 219    treeNode TaggedDesc(treeNode x, TagType tag);\r
 220 \r
 221 \r
 222    treeNode TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen,\r
 223                                  TagType *desctags, unsigned int dtlen);\r
 224    \r
 225    treeNode TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen,\r
 226                                 TagType *folltags, unsigned int flen,treeNode root);\r
 227 \r
 228    treeNode TaggedDescOnly(treeNode x, TagType *desctags, unsigned int dtlen);\r
 229    \r
 230    treeNode TaggedDescOrFollOnly(treeNode x, TagType *folltags, unsigned int flen,\r
 231                            treeNode root);\r
 232 \r
 233    treeNode TaggedFollOnly(treeNode x, TagType *folltags, unsigned int flen,\r
 234                            treeNode root);\r
 235    \r
 236 \r
 237    /** TaggedPrec(x,tag): returns the first node tagged tag with smaller \r
 238     * preorder than x and not an ancestor of x. Returns NULLT if there \r
 239     * is none. */\r
 240    treeNode TaggedPrec(treeNode x, TagType tag);\r
 241   \r
 242    /** TaggedFoll(x,tag): returns the first node tagged tag with larger \r
 243     * preorder than x and not in the subtree of x. Returns NULLT if there \r
 244     * is none. */\r
 245    treeNode TaggedFoll(treeNode x, TagType tag);\r
 246 \r
 247    treeNode TaggedFollBelow(treeNode x, TagType tag,treeNode root);     \r
 248   \r
 249    /** TaggedFollowingSibling(x,tag) */\r
 250    treeNode TaggedFollowingSibling(treeNode x, TagType tag);\r
 251 \r
 252    /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged \r
 253      * tag. Return NULLT is there is none. */\r
 254    treeNode TaggedAncestor(treeNode x, TagType tag);\r
 255  \r
 256    /** PrevText(x): returns the document identifier of the text to the left of \r
 257     * node x, or NULLT if x is the root node. */\r
 258    DocID PrevText(treeNode x);\r
 259    \r
 260    /** NextText(x): returns the document identifier of the text to the right of \r
 261     * node x, or NULLT if x is the root node. */\r
 262    DocID NextText(treeNode x);\r
 263    \r
 264    /** MyText(x): returns the document identifier of the text below node x, or \r
 265     * NULLT if x is not a leaf node. */\r
 266    DocID MyText(treeNode x);\r
 267    \r
 268    /** TextXMLId(d): returns the preorder of document with identifier d in the \r
 269     * tree consisting of all tree nodes and all text nodes. */\r
 270    int TextXMLId(DocID d);\r
 271    \r
 272    /** NodeXMLId(x): returns the preorder of node x in the tree consisting of \r
 273     * all tree nodes and all text nodes. */\r
 274    int NodeXMLId(treeNode x);\r
 275    \r
 276    /** ParentNode(d): returns the parent node of document identifier d. */\r
 277    treeNode ParentNode(DocID d);\r
 278    treeNode PrevNode(DocID d);\r
 279 \r
 280    /** OpenDocument(empty_texts,sample_rate_text,dtc): initilizes the construction\r
 281     * of the data structure for the XML document. Parameter empty_texts \r
 282     * indicates whether we index empty texts in document or not. Parameter \r
 283     * sample_rate_text indicates the sampling rate for the text searching data\r
 284     * structures (small values get faster searching but a bigger space \r
 285     * requirement). dtc disable the use of the TextCollection\r
 286     * (i.e. everything is considered an empty text *)\r
 287     * Returns a non-zero value upon success, NULLT in case of \r
 288     * error. */\r
 289 \r
 290    int OpenDocument(bool empty_texts, int sample_rate_text, bool dtc);\r
 291 \r
 292    /** CloseDocument(): finishes the construction of the data structure for \r
 293     * the XML document. Tree and tags are represented in the final form, \r
 294     * dynamic data structures are made static, and the flag "finished" is set \r
 295     * to true. After that, the data structure can be queried. */\r
 296    int CloseDocument();\r
 297 \r
 298    /** NewOpenTag(tagname): indicates the event of finding a new opening tag \r
 299     * in the document. Tag name is given. Returns a non-zero value upon \r
 300     * success, and returns NULLT in case of error. */\r
 301    int NewOpenTag(unsigned char *tagname);\r
 302    \r
 303    /** NewClosingTag(tagname): indicates the event of finding a new closing tag\r
 304     *  in the document. Tag name is given. Returns a non-zero value upon \r
 305     *  success, and returns NULLT in case of error. */\r
 306    int NewClosingTag(unsigned char *tagname);\r
 307  \r
 308    /** NewText(s): indicates the event of finding a new (non-empty) text s in \r
 309     * the document. The new text is inserted within the text collection. \r
 310     * Returns a non-zero value upon success, NULLT in case of error. */\r
 311    int NewText(unsigned char *s);\r
 312 \r
 313    /** NewEmptyText(): indicates the event of finding a new empty text in the \r
 314     * document. In case of indexing empty and non-empty texts, we insert the \r
 315     * empty texts into the text collection. In case of indexing only non-empty\r
 316     * texts, it just indicates an empty text in the bit vector of empty texts. \r
 317     * Returns a non-zero value upon success, NULLT in case of error. */\r
 318    int NewEmptyText();\r
 319 \r
 320    /** GetTagId(tagname): returns the tag identifier corresponding to a given \r
 321     * tag name. Returns NULLT in case that the tag name does not exists. */\r
 322    TagType GetTagId(unsigned char *tagname);\r
 323 \r
 324    /** GetTagName(tagid): returns the tag name of a given tag identifier. \r
 325     * Returns NULL in case that the tag identifier is not valid.*/\r
 326    unsigned char *GetTagName(TagType tagid);\r
 327 \r
 328 \r
 329    // OJO\r
 330    /** GetTagName(tagid): returns the tag name of a given tag identifier.     \r
 331     *  The result is just a reference and should not be freed by the caller.\r
 332     */\r
 333    const unsigned char *GetTagNameByRef(TagType tagid);\r
 334 \r
 335    //OJO\r
 336    /** RegisterTag adds a new tag to the tag collection this is needed\r
 337     * if the query contains a tag which is not in the document, we need\r
 338     * to give this new tag a fresh id and store it somewhere. A logical\r
 339     * choice is here.\r
 340     * We might want to use a hashtable instead of an array though.\r
 341     */\r
 342    TagType RegisterTag(unsigned char *tagname);\r
 343 \r
 344    bool EmptyText(DocID i) {\r
 345        return Text->EmptyText(i);\r
 346    }\r
 347    /** Prefix(s): search for texts prefixed by string s. */\r
 348    TextCollection::document_result Prefix(uchar const *s) {\r
 349       return Text->Prefix(s);\r
 350    }\r
 351 \r
 352    /** Suffix(s): search for texts having string s as a suffix. */\r
 353    TextCollection::document_result Suffix(uchar const *s) {\r
 354       return Text->Suffix(s);\r
 355    }\r
 356 \r
 357    /** Equal(s): search for texts equal to string s. */\r
 358    TextCollection::document_result Equal(uchar const *s) {\r
 359       return Text->Equal(s);\r
 360    }\r
 361 \r
 362    /** Contains(s): search for texts containing string s.  */\r
 363    TextCollection::document_result Contains(uchar const *s) {\r
 364       return Text->Contains(s);\r
 365    }\r
 366 \r
 367    /** LessThan(s): returns document identifiers for the texts that\r
 368     * are lexicographically smaller than string s. */\r
 369    TextCollection::document_result LessThan(uchar const *s) {\r
 370       return Text->LessThan(s);\r
 371    }\r
 372    \r
 373    /** IsPrefix(x): returns true if there is a text prefixed by string s. */\r
 374    bool IsPrefix(uchar const *s) {\r
 375       return Text->IsPrefix(s);\r
 376    }          \r
 377    \r
 378    /** IsSuffix(s): returns true if there is a text having string s as a \r
 379     * suffix.*/\r
 380    bool IsSuffix(uchar const *s) {\r
 381       return Text->IsSuffix(s);\r
 382    }\r
 383    \r
 384    /** IsEqual(s): returns true if there is a text that equals given \r
 385     * string s. */\r
 386    bool IsEqual(uchar const *s) {\r
 387       return Text->IsEqual(s);\r
 388    }\r
 389    \r
 390    /** IsContains(s): returns true if there is a text containing string s. */\r
 391    bool IsContains(uchar const *s) {\r
 392       return Text->IsContains(s);\r
 393    }\r
 394    \r
 395    /** IsLessThan(s): returns true if there is at least a text that is \r
 396     * lexicographically smaller than string s. */\r
 397    bool IsLessThan(uchar const *s) {\r
 398       return Text->IsLessThan(s);\r
 399    }\r
 400    \r
 401    /** Count(s): Global counting  */\r
 402    unsigned Count(uchar const *s) {\r
 403       return Text->Count(s);\r
 404    }\r
 405 \r
 406    /** CountPrefix(s): counting version of Prefix(s). */\r
 407    unsigned CountPrefix(uchar const *s) {\r
 408       return Text->CountPrefix(s);\r
 409    }\r
 410    \r
 411    /** CountSuffix(s): counting version of Suffix(s). */\r
 412    unsigned CountSuffix(uchar const *s) {\r
 413       return Text->CountSuffix(s);\r
 414    }\r
 415    \r
 416    /** CountEqual(s): counting version of Equal(s). */\r
 417    unsigned CountEqual(uchar const *s) {\r
 418       return Text->CountEqual(s);\r
 419    }\r
 420    \r
 421    /** CountContains(s): counting version of Contains(s). */\r
 422    unsigned CountContains(uchar const *s) {\r
 423       return Text->CountContains(s);\r
 424    }\r
 425    \r
 426    /** CountLessThan(s): counting version of LessThan(s). */\r
 427    unsigned CountLessThan(uchar const *s) {\r
 428       return CountLessThan(s);\r
 429    }\r
 430    \r
 431    /** GetText(d): returns the text corresponding to document with\r
 432     * id d. */\r
 433    uchar* GetText(DocID d) {\r
 434        return Text->GetText(d);\r
 435    }\r
 436 \r
 437    uchar* GetCachedText(DocID d) {\r
 438      uchar * str = (uchar*) calloc(sizeof(char),(CachedText.at(d).size() + 1));\r
 439      strcpy((char*) str,(const char*) CachedText.at(d).c_str());\r
 440      return (uchar*) (str);\r
 441    }\r
 442    \r
 443    TextCollection *getTextCollection() {\r
 444       return Text;\r
 445    }\r
 446    /** Save: saves XML tree data structure to file. */\r
 447    void Save(unsigned char *filename);\r
 448       \r
 449    /** Load: loads XML tree data structure from file. sample_rate_text \r
 450     * indicates the sample rate for the text search data structure. */\r
 451    static XMLTree *Load(unsigned char *filename, int sample_rate_text);   \r
 452 };\r
 453 #endif\r