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 \r
  30 #undef W\r
  31 #undef WW\r
  32 #undef Wminusone\r
  33 \r
  34 #include "bp.h"\r
  35 //#include "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 typedef struct nd {\r
  61    uint position;\r
  62    struct nd *next;\r
  63 } ListNode;\r
  64 \r
  65 typedef struct {\r
  66    ListNode *first;\r
  67    ListNode *last;\r
  68 } TagArrayEntry;\r
  69 \r
  70 class XMLTree {\r
  71    /** Balanced parentheses representation of the tree */\r
  72    bp *Par;\r
  73  \r
  74    /** Mapping from tag identifer to tag name */  \r
  75    unsigned char **TagName;\r
  76    uint ntagnames;\r
  77   \r
  78    /** boolean flag indicating whether we are indexing empty texts or not */\r
  79    bool indexing_empty_texts; \r
  80    \r
  81    /** Bit vector indicating with a 1 the positions of the non-empty texts. */\r
  82    static_bitsequence *EBVector;  \r
  83                       \r
  84    /** Tag sequence represented with a data structure for rank and select */\r
  85    static_sequence *Tags;\r
  86    uint * tags_fix;\r
  87    uint tags_blen, tags_len;\r
  88 \r
  89    /** The texts in the XML document */\r
  90    TextCollection *Text;\r
  91 \r
  92    /** The texts in the XML document (cached for faster display) */\r
  93    vector<string> CachedText;\r
  94    \r
  95    TagArrayEntry *TagArray;\r
  96 \r
  97    // Allows to disable the TextCollection for benchmarkin purposes\r
  98    bool disable_tc;\r
  99    \r
 100 public:\r
 101    /** Data structure constructors */\r
 102    XMLTree() {;};\r
 103 \r
 104    XMLTree(pb *par, uint npar, unsigned char **TN, uint ntagnames, uint *empty_texts_bmp, TagType *tags,\r
 105            TextCollection *TC, vector<string> CT, bool indexing_empty_t, bool dis_tc);\r
 106  \r
 107    /** Data structure destructor */\r
 108    ~XMLTree();\r
 109    \r
 110    /** root(): returns the tree root. */\r
 111    treeNode Root();\r
 112    \r
 113    /** SubtreeSize(x): the number of nodes (and attributes) in the subtree of \r
 114     * node x. */\r
 115    int SubtreeSize(treeNode x);\r
 116    \r
 117    /** SubtreeTags(x,tag): the number of occurrences of tag within the subtree \r
 118     * of node x. */\r
 119    int SubtreeTags(treeNode x, TagType tag);\r
 120    \r
 121    /** IsLeaf(x): returns whether node x is leaf or not. In the succinct \r
 122     * representation this is just a bit inspection. */\r
 123    bool IsLeaf(treeNode x);\r
 124     \r
 125    /** IsAncestor(x,y): returns whether node x is ancestor of node y. */\r
 126    bool IsAncestor(treeNode x, treeNode y);\r
 127   \r
 128    /** IsChild(x,y): returns whether node x is parent of node y. */\r
 129    bool IsChild(treeNode x, treeNode y);\r
 130 \r
 131    /** IsFirstChild(x): returns whether node x is the first child of its parent. */\r
 132    bool IsFirstChild(treeNode x);\r
 133 \r
 134    /** NumChildren(x): number of children of node x. Constant time with the \r
 135     * data structure of Sadakane. */\r
 136    int NumChildren(treeNode x);\r
 137    \r
 138    /** ChildNumber(x): returns i if node x is the i-th children of its \r
 139     * parent. */\r
 140    inline int ChildNumber(treeNode x);\r
 141 \r
 142    /** Depth(x): depth of node x, a simple binary rank on the parentheses \r
 143     * sequence. */\r
 144    int Depth(treeNode x);\r
 145    \r
 146    /** Preorder(x): returns the preorder number of node x, just regarding tree \r
 147     * nodes (and not texts). */ \r
 148    int Preorder(treeNode x);\r
 149    \r
 150    /** Postorder(x): returns the postorder number of node x, just regarding \r
 151     * tree nodes (and not texts). */\r
 152    int Postorder(treeNode x);\r
 153    \r
 154    /** Tag(x): returns the tag identifier of node x. */\r
 155    TagType Tag(treeNode x);\r
 156    \r
 157    /** DocIds(x): returns the range (i.e., a pair of integers) of document \r
 158     * identifiers that descend from node x. */\r
 159    range DocIds(treeNode x);\r
 160    \r
 161    /** Parent(x): returns the parent node of node x. */\r
 162    treeNode Parent(treeNode x);\r
 163    \r
 164    /** Child(x,i): returns the i-th child of node x, assuming it exists. */   \r
 165    treeNode Child(treeNode x, int i);\r
 166    \r
 167    /** FirstChild(x): returns the first child of node x, assuming it exists. \r
 168     * Very fast in BP. */\r
 169    treeNode FirstChild(treeNode x);\r
 170    \r
 171    /** LastChild(x): returns the last child of node x.  */\r
 172    treeNode LastChild(treeNode x);\r
 173    \r
 174    /** NextSibling(x): returns the next sibling of node x, assuming it \r
 175     * exists. */\r
 176    treeNode NextSibling(treeNode x);\r
 177    \r
 178    /** PrevSibling(x): returns the previous sibling of node x, assuming it \r
 179     * exists. */\r
 180    treeNode PrevSibling(treeNode x);\r
 181    \r
 182    /** TaggedChild(x,tag): returns the first child of node x tagged tag, or \r
 183     * NULLT if there is none. Because of the balanced-parentheses representation \r
 184     * of the tree, this operation is not supported efficiently, just iterating \r
 185     * among the children of node x until finding the desired child. */\r
 186    treeNode TaggedChild(treeNode x, TagType tag);\r
 187    \r
 188    treeNode SelectChild(treeNode x, TagType *tags, int ntags);\r
 189 \r
 190    /** TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or \r
 191     *  NULLT if there is none. */\r
 192    treeNode TaggedSibling(treeNode x, TagType tag);\r
 193    \r
 194    treeNode SelectSibling(treeNode x, TagType *tags, int ntags);\r
 195 \r
 196    /** TaggedDesc(x,tag): returns the first node tagged tag with larger \r
 197     * preorder than x and within the subtree of x. Returns NULT if there \r
 198     * is none. */\r
 199    treeNode TaggedDesc(treeNode x, TagType tag);\r
 200 \r
 201    treeNode SelectDesc(treeNode x, TagType *tags, int ntags);\r
 202 \r
 203    treeNode TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen,\r
 204                                  TagType *desctags, unsigned int dtlen);\r
 205    \r
 206    treeNode TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen,\r
 207                                 TagType *folltags, unsigned int flen,treeNode root);\r
 208 \r
 209    treeNode TaggedDescOnly(treeNode x, TagType *desctags, unsigned int dtlen);\r
 210    \r
 211    treeNode TaggedDescOrFollOnly(treeNode x, TagType *folltags, unsigned int flen,\r
 212                            treeNode root);\r
 213 \r
 214    treeNode TaggedFollOnly(treeNode x, TagType *folltags, unsigned int flen,\r
 215                            treeNode root);\r
 216    \r
 217 \r
 218    /** TaggedPrec(x,tag): returns the first node tagged tag with smaller \r
 219     * preorder than x and not an ancestor of x. Returns NULLT if there \r
 220     * is none. */\r
 221    treeNode TaggedPrec(treeNode x, TagType tag);\r
 222   \r
 223    /** TaggedFoll(x,tag): returns the first node tagged tag with larger \r
 224     * preorder than x and not in the subtree of x. Returns NULLT if there \r
 225     * is none. */\r
 226    treeNode TaggedFoll(treeNode x, TagType tag);\r
 227 \r
 228    treeNode TaggedFollBelow(treeNode x, TagType tag,treeNode root);     \r
 229    \r
 230    treeNode SelectFollBelow(treeNode x, TagType *tags, int ntags, treeNode ctx);\r
 231 \r
 232    /** TaggedFollowingSibling(x,tag) */\r
 233    treeNode TaggedFollowingSibling(treeNode x, TagType tag);\r
 234 \r
 235    /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged \r
 236      * tag. Return NULLT is there is none. */\r
 237    treeNode TaggedAncestor(treeNode x, TagType tag);\r
 238  \r
 239    /** PrevText(x): returns the document identifier of the text to the left of \r
 240     * node x, or NULLT if x is the root node. */\r
 241    DocID PrevText(treeNode x);\r
 242    \r
 243    /** NextText(x): returns the document identifier of the text to the right of \r
 244     * node x, or NULLT if x is the root node. */\r
 245    DocID NextText(treeNode x);\r
 246    \r
 247    /** MyText(x): returns the document identifier of the text below node x, or \r
 248     * NULLT if x is not a leaf node. */\r
 249    DocID MyText(treeNode x);\r
 250    \r
 251    /** TextXMLId(d): returns the preorder of document with identifier d in the \r
 252     * tree consisting of all tree nodes and all text nodes. */\r
 253    int TextXMLId(DocID d);\r
 254    \r
 255    /** NodeXMLId(x): returns the preorder of node x in the tree consisting of \r
 256     * all tree nodes and all text nodes. */\r
 257    int NodeXMLId(treeNode x);\r
 258    \r
 259    /** ParentNode(d): returns the parent node of document identifier d. */\r
 260    treeNode ParentNode(DocID d);\r
 261    \r
 262    treeNode PrevNode(DocID d);\r
 263 \r
 264    /** GetTagId(tagname): returns the tag identifier corresponding to a given \r
 265     * tag name. Returns NULLT in case that the tag name does not exists. */\r
 266    TagType GetTagId(unsigned char *tagname);\r
 267 \r
 268    /** GetTagName(tagid): returns the tag name of a given tag identifier. \r
 269     * Returns NULL in case that the tag identifier is not valid.*/\r
 270    unsigned char *GetTagName(TagType tagid);\r
 271 \r
 272    /** GetTagName(tagid): returns the tag name of a given tag identifier.     \r
 273     *  The result is just a reference and should not be freed by the caller.\r
 274     */\r
 275    const unsigned char *GetTagNameByRef(TagType tagid);\r
 276 \r
 277    /** RegisterTag adds a new tag to the tag collection this is needed\r
 278     * if the query contains a tag which is not in the document, we need\r
 279     * to give this new tag a fresh id and store it somewhere. A logical\r
 280     * choice is here.\r
 281     * We might want to use a hashtable instead of an array though.\r
 282     */\r
 283    TagType RegisterTag(unsigned char *tagname);\r
 284 \r
 285    bool EmptyText(DocID i) {\r
 286        return Text->EmptyText(i);\r
 287    }\r
 288 \r
 289    /** Prefix(s): search for texts prefixed by string s. */\r
 290    TextCollection::document_result Prefix(uchar const *s) {\r
 291       return Text->Prefix(s);\r
 292    }\r
 293 \r
 294    /** Suffix(s): search for texts having string s as a suffix. */\r
 295    TextCollection::document_result Suffix(uchar const *s) {\r
 296       return Text->Suffix(s);\r
 297    }\r
 298 \r
 299    /** Equal(s): search for texts equal to string s. */\r
 300    TextCollection::document_result Equal(uchar const *s) {\r
 301       return Text->Equal(s);\r
 302    }\r
 303 \r
 304    /** Contains(s): search for texts containing string s.  */\r
 305    TextCollection::document_result Contains(uchar const *s) {\r
 306       return Text->Contains(s);\r
 307    }\r
 308 \r
 309    /** LessThan(s): returns document identifiers for the texts that\r
 310     * are lexicographically smaller than string s. */\r
 311    TextCollection::document_result LessThan(uchar const *s) {\r
 312       return Text->LessThan(s);\r
 313    }\r
 314    \r
 315    /** IsPrefix(x): returns true if there is a text prefixed by string s. */\r
 316    bool IsPrefix(uchar const *s) {\r
 317       return Text->IsPrefix(s);\r
 318    }          \r
 319    \r
 320    /** IsSuffix(s): returns true if there is a text having string s as a \r
 321     * suffix.*/\r
 322    bool IsSuffix(uchar const *s) {\r
 323       return Text->IsSuffix(s);\r
 324    }\r
 325    \r
 326    /** IsEqual(s): returns true if there is a text that equals given \r
 327     * string s. */\r
 328    bool IsEqual(uchar const *s) {\r
 329       return Text->IsEqual(s);\r
 330    }\r
 331    \r
 332    /** IsContains(s): returns true if there is a text containing string s. */\r
 333    bool IsContains(uchar const *s) {\r
 334       return Text->IsContains(s);\r
 335    }\r
 336    \r
 337    /** IsLessThan(s): returns true if there is at least a text that is \r
 338     * lexicographically smaller than string s. */\r
 339    bool IsLessThan(uchar const *s) {\r
 340       return Text->IsLessThan(s);\r
 341    }\r
 342    \r
 343    /** Count(s): Global counting  */\r
 344    unsigned Count(uchar const *s) {\r
 345       return Text->Count(s);\r
 346    }\r
 347 \r
 348    /** CountPrefix(s): counting version of Prefix(s). */\r
 349    unsigned CountPrefix(uchar const *s) {\r
 350       return Text->CountPrefix(s);\r
 351    }\r
 352    \r
 353    /** CountSuffix(s): counting version of Suffix(s). */\r
 354    unsigned CountSuffix(uchar const *s) {\r
 355       return Text->CountSuffix(s);\r
 356    }\r
 357    \r
 358    /** CountEqual(s): counting version of Equal(s). */\r
 359    unsigned CountEqual(uchar const *s) {\r
 360       return Text->CountEqual(s);\r
 361    }\r
 362    \r
 363    /** CountContains(s): counting version of Contains(s). */\r
 364    unsigned CountContains(uchar const *s) {\r
 365       return Text->CountContains(s);\r
 366    }\r
 367    \r
 368    /** CountLessThan(s): counting version of LessThan(s). */\r
 369    unsigned CountLessThan(uchar const *s) {\r
 370       return Text->CountLessThan(s);\r
 371    }\r
 372    \r
 373    /** GetText(d): returns the text corresponding to document with\r
 374     * id d. */\r
 375    uchar* GetText(DocID d) {\r
 376        return Text->GetText(d);\r
 377    }\r
 378 \r
 379    uchar* GetCachedText(DocID d) {\r
 380      uchar * str = (uchar*) calloc(sizeof(char),(CachedText.at(d).size() + 1));\r
 381      strcpy((char*) str,(const char*) CachedText.at(d).c_str());\r
 382      return (uchar*) (str);\r
 383    }\r
 384    \r
 385    TextCollection *getTextCollection() {\r
 386       return Text;\r
 387    }\r
 388    \r
 389    /** Save: saves XML tree data structure to file. */\r
 390    void Save(unsigned char *filename);\r
 391       \r
 392    /** Load: loads XML tree data structure from file. sample_rate_text \r
 393     * indicates the sample rate for the text search data structure. */\r
 394    static XMLTree *Load(unsigned char *filename, int sample_rate_text);   \r
 395 \r
 396    void insertTag(TagType tag, uint position);\r
 397    \r
 398    void print_stats();\r
 399 };\r
 400 #endif\r
 401 \r