X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.h;h=1268cb6b015c369e0bfdc87f7425879d8b88cc47;hb=2134520212940b32a0d0e430df02e71591cc4550;hp=319b9a69e841d6bc8878615aa243539ba2044153;hpb=e421727c5a512154cf2c3ff4cf8390eb88d527d7;p=SXSI%2FXMLTree.git diff --git a/XMLTree.h b/XMLTree.h index 319b9a6..1268cb6 100644 --- a/XMLTree.h +++ b/XMLTree.h @@ -21,16 +21,23 @@ #ifndef XMLTREE_H_ #define XMLTREE_H_ - +#include "TextCollection/TextCollectionBuilder.h" #include #include +#include + +//KIM : OJO +//clash between TextCollection/Tools.h and libcds/includes/basics.h +#undef W +#undef WW +#undef Wminusone + #include "bp.h" -#include "TextCollection/TextCollection.h" +#include +#include +#include using SXSI::TextCollection; -#include "libcds/includes/static_bitsequence.h" -#include "libcds/includes/alphabet_mapper.h" -#include "libcds/includes/static_sequence.h" - +using SXSI::TextCollectionBuilder; // this constant is used to efficiently compute the child operation in the tree @@ -38,6 +45,8 @@ using SXSI::TextCollection; #define NULLT -1 +#define PERM_SAMPLE 10 + // sets bit p in e #define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W))) // cleans bit p in e @@ -54,6 +63,13 @@ typedef struct { } range; +//KIM : OJO +// I know this class implements the working draft that we have but the logics seem flawed here... +// We should have two classes. One XMLTreeBuilder and one XMLTree. +// XMLTreeBuilder would have OpenDocument, NewOpenTag,... and CloseDocument would return an XMLTree +// XMLTree would have only an initialized structure. If find it really ugly to check (!finished) or (!initialized) +// in every function (FirstChild....). + class XMLTree { /** Balanced parentheses representation of the tree */ bp *Par; @@ -68,10 +84,16 @@ class XMLTree { static_bitsequence_rrr02 *EBVector; /** Tag sequence represented with a data structure for rank and select */ - static_sequence_wvtree *Tags; + static_sequence *Tags; + uint * tags_fix; + uint tags_blen, tags_len; /** The texts in the XML document */ + TextCollectionBuilder *TextBuilder; TextCollection *Text; + + /** The texts in the XML document (cached for faster display) */ + vector CachedText; /** Flag indicating whether the whole data structure has been constructed or * not. If the value is true, you cannot add more texts, nodes, etc. */ @@ -86,13 +108,27 @@ class XMLTree { pb *par_aux; TagType *tags_aux; int npar; + int parArraySize; int ntagnames; unsigned int *empty_texts_aux; + + // KIM : OJO + // I added those two. The TagName array should always contains two special tags + // <@> for attributes and <$> for PCDATA. + // <$> can never be in a document (since we handle the text differently) + // but <@> can be returned by the parser. This boolean is needed for the construction + // of the Tag bitmap to know if <@> must be taken into account or not + bool found_attributes; + + // KIM : OJO + // Allows to disable the TextCollection for benchmarkin purposes + bool disable_tc; public: + void print_stats(); /** Data structure constructor */ - XMLTree() {finished = false; initialized = false;}; + XMLTree() {finished = false; initialized = false; Text = 0; TextBuilder = 0; }; /** Data structure destructor */ ~XMLTree(); @@ -117,6 +153,9 @@ public: /** IsChild(x,y): returns whether node x is parent of node y. */ bool IsChild(treeNode x, treeNode y); + + /** IsChild(x,y): returns whether node x is the first child of its parent */ + bool IsFirstChild(treeNode x); /** NumChildren(x): number of children of node x. Constant time with the * data structure of Sadakane. */ @@ -155,8 +194,13 @@ public: * Very fast in BP. */ treeNode FirstChild(treeNode x); + /** LastChild(x): returns the last child of node x. + * Implemented by Kim naively. */ + treeNode LastChild(treeNode x); + /** NextSibling(x): returns the next sibling of node x, assuming it * exists. */ + treeNode NextSibling(treeNode x); /** PrevSibling(x): returns the previous sibling of node x, assuming it @@ -174,6 +218,22 @@ public: * is none. */ treeNode TaggedDesc(treeNode x, TagType tag); + + treeNode TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen, + TagType *desctags, unsigned int dtlen); + + treeNode TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen, + TagType *folltags, unsigned int flen,treeNode root); + + treeNode TaggedDescOnly(treeNode x, TagType *desctags, unsigned int dtlen); + + treeNode TaggedDescOrFollOnly(treeNode x, TagType *folltags, unsigned int flen, + treeNode root); + + treeNode TaggedFollOnly(treeNode x, TagType *folltags, unsigned int flen, + treeNode root); + + /** TaggedPrec(x,tag): returns the first node tagged tag with smaller * preorder than x and not an ancestor of x. Returns NULLT if there * is none. */ @@ -183,7 +243,16 @@ public: * preorder than x and not in the subtree of x. Returns NULLT if there * is none. */ treeNode TaggedFoll(treeNode x, TagType tag); - + + treeNode TaggedFollBelow(treeNode x, TagType tag,treeNode root); + + /** TaggedFollowingSibling(x,tag) */ + treeNode TaggedFollowingSibling(treeNode x, TagType tag); + + /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged + * tag. Return NULLT is there is none. */ + treeNode TaggedAncestor(treeNode x, TagType tag); + /** PrevText(x): returns the document identifier of the text to the left of * node x, or NULLT if x is the root node. */ DocID PrevText(treeNode x); @@ -206,15 +275,19 @@ public: /** ParentNode(d): returns the parent node of document identifier d. */ treeNode ParentNode(DocID d); + treeNode PrevNode(DocID d); - /** OpenDocument(empty_texts,sample_rate_text): initilizes the construction + /** OpenDocument(empty_texts,sample_rate_text,dtc): initilizes the construction * of the data structure for the XML document. Parameter empty_texts * indicates whether we index empty texts in document or not. Parameter * sample_rate_text indicates the sampling rate for the text searching data * structures (small values get faster searching but a bigger space - * requirement). Returns a non-zero value upon success, NULLT in case of + * requirement). dtc disable the use of the TextCollection + * (i.e. everything is considered an empty text *) + * Returns a non-zero value upon success, NULLT in case of * error. */ - int OpenDocument(bool empty_texts, int sample_rate_text); + + int OpenDocument(bool empty_texts, int sample_rate_text, bool dtc); /** CloseDocument(): finishes the construction of the data structure for * the XML document. Tree and tags are represented in the final form, @@ -252,36 +325,124 @@ public: * Returns NULL in case that the tag identifier is not valid.*/ unsigned char *GetTagName(TagType tagid); + + // OJO + /** GetTagName(tagid): returns the tag name of a given tag identifier. + * The result is just a reference and should not be freed by the caller. + */ + const unsigned char *GetTagNameByRef(TagType tagid); + + //OJO + /** RegisterTag adds a new tag to the tag collection this is needed + * if the query contains a tag which is not in the document, we need + * to give this new tag a fresh id and store it somewhere. A logical + * choice is here. + * We might want to use a hashtable instead of an array though. + */ + TagType RegisterTag(unsigned char *tagname); + + bool EmptyText(DocID i) { + return Text->EmptyText(i); + } /** Prefix(s): search for texts prefixed by string s. */ TextCollection::document_result Prefix(uchar const *s) { - Text->Prefix(s); + return Text->Prefix(s); } /** Suffix(s): search for texts having string s as a suffix. */ TextCollection::document_result Suffix(uchar const *s) { - Text->Suffix(s); + return Text->Suffix(s); } /** Equal(s): search for texts equal to string s. */ TextCollection::document_result Equal(uchar const *s) { - Text->Equal(s); + return Text->Equal(s); } /** Contains(s): search for texts containing string s. */ TextCollection::document_result Contains(uchar const *s) { - Text->Contains(s); + return Text->Contains(s); } + /** LessThan(s): returns document identifiers for the texts that + * are lexicographically smaller than string s. */ TextCollection::document_result LessThan(uchar const *s) { - Text->LessThan(s); + return Text->LessThan(s); } - + + /** IsPrefix(x): returns true if there is a text prefixed by string s. */ + bool IsPrefix(uchar const *s) { + return Text->IsPrefix(s); + } + + /** IsSuffix(s): returns true if there is a text having string s as a + * suffix.*/ + bool IsSuffix(uchar const *s) { + return Text->IsSuffix(s); + } + + /** IsEqual(s): returns true if there is a text that equals given + * string s. */ + bool IsEqual(uchar const *s) { + return Text->IsEqual(s); + } + + /** IsContains(s): returns true if there is a text containing string s. */ + bool IsContains(uchar const *s) { + return Text->IsContains(s); + } + + /** IsLessThan(s): returns true if there is at least a text that is + * lexicographically smaller than string s. */ + bool IsLessThan(uchar const *s) { + return Text->IsLessThan(s); + } + + /** Count(s): Global counting */ + unsigned Count(uchar const *s) { + return Text->Count(s); + } + + /** CountPrefix(s): counting version of Prefix(s). */ + unsigned CountPrefix(uchar const *s) { + return Text->CountPrefix(s); + } + + /** CountSuffix(s): counting version of Suffix(s). */ + unsigned CountSuffix(uchar const *s) { + return Text->CountSuffix(s); + } + + /** CountEqual(s): counting version of Equal(s). */ + unsigned CountEqual(uchar const *s) { + return Text->CountEqual(s); + } + + /** CountContains(s): counting version of Contains(s). */ + unsigned CountContains(uchar const *s) { + return Text->CountContains(s); + } + + /** CountLessThan(s): counting version of LessThan(s). */ + unsigned CountLessThan(uchar const *s) { + return CountLessThan(s); + } + /** GetText(d): returns the text corresponding to document with * id d. */ uchar* GetText(DocID d) { - Text->GetText(d); + return Text->GetText(d); + } + + uchar* GetCachedText(DocID d) { + uchar * str = (uchar*) calloc(sizeof(char),(CachedText.at(d).size() + 1)); + strcpy((char*) str,(const char*) CachedText.at(d).c_str()); + return (uchar*) (str); } + TextCollection *getTextCollection() { + return Text; + } /** Save: saves XML tree data structure to file. */ void Save(unsigned char *filename);