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