* along with this program; if not, write to the *\r
* Free Software Foundation, Inc., *\r
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *\r
- ******************************************************************************/ \r
+ ******************************************************************************/\r
\r
+#ifndef XMLTREE_H_\r
+#define XMLTREE_H_\r
+#include <unordered_set>\r
+#include <unordered_map>\r
+#include "TextCollection/TextCollectionBuilder.h"\r
#include <stdio.h>\r
#include <stdlib.h>\r
+#include <cstring>\r
+\r
+\r
+#undef W\r
+#undef WW\r
+#undef Wminusone\r
+\r
#include "bp.h"\r
-#include "libcds/includes/static_bitsequence.h"\r
-#include "libcds/includes/alphabet_mapper.h"\r
-#include "libcds/includes/static_sequence.h"\r
\r
-//#include "TextCollection/TextCollection.h"\r
-//using SXSI::TextCollection;\r
+#include <static_bitsequence.h>\r
+#include <alphabet_mapper.h>\r
+#include <static_sequence.h>\r
+using SXSI::TextCollection;\r
+using SXSI::TextCollectionBuilder;\r
+using SXSI::TextStorage;\r
\r
// this constant is used to efficiently compute the child operation in the tree\r
#define OPTD 10\r
\r
#define NULLT -1\r
\r
- // sets bit p in e\r
-#define bitset(e,p) ((e)[(p)/W] |= (1<<((p)%W)))\r
- // cleans bit p in e\r
-#define bitclean(e,p) ((e)[(p)/W] &= ~(1<<((p)%W)))\r
+#define PERM_SAMPLE 10\r
\r
\r
typedef int treeNode;\r
int max;\r
} range;\r
\r
+// Encoding of the XML Document :\r
+// The following TAGs and IDs are fixed, "" is the tag of the root.\r
+// a TextNode is represented by a leaf <<$>></<$>> The DocId in the TextCollection\r
+// of that leaf is kept in a bit sequence.\r
+// a TextNode below an attribute is likewise represented by a leaf <<@$>><</@$>>\r
+// An element <e a1="v1" a2="v2" ... an="vn" > ...</e> the representation is:\r
+// <e><<@>> <<@>a1> <<$@>>DocID(v1)</<$@>></<@>a1> ... </<@>> .... </e>\r
+// Hence the attributes (if any) are always below the first child of their element,\r
+// as the children of a fake node <@>.\r
+\r
+\r
+#define DOCUMENT_OPEN_TAG ""\r
+#define DOCUMENT_TAG_ID 0\r
+#define ATTRIBUTE_OPEN_TAG "<@>"\r
+#define ATTRIBUTE_TAG_ID 1\r
+#define PCDATA_OPEN_TAG "<$>"\r
+#define PCDATA_TAG_ID 2\r
+#define ATTRIBUTE_DATA_OPEN_TAG "<@$>"\r
+#define ATTRIBUTE_DATA_TAG_ID 3\r
+#define DOCUMENT_CLOSE_TAG "/"\r
+#define ATTRIBUTE_CLOSE_TAG "/<@>"\r
+#define PCDATA_CLOSE_TAG "/<$>"\r
+#define ATTRIBUTE_DATA_CLOSE_TAG "/<@$>"\r
+\r
+\r
+\r
+typedef std::unordered_map<string,int> TagIdMap;\r
+typedef TagIdMap::const_iterator TagIdMapIT;\r
+\r
+#define REGISTER_TAG(v,h,t) do { (h)->insert(std::make_pair((t),(v)->size()));\\r
+ (v)->push_back(t); } while (false)\r
+\r
+\r
+class XMLTreeBuilder;\r
\r
class XMLTree {\r
+\r
+ // Only the builder can access the constructor\r
+ friend class XMLTreeBuilder;\r
+\r
+ private:\r
/** Balanced parentheses representation of the tree */\r
bp *Par;\r
\r
/** Mapping from tag identifer to tag name */ \r
- unsigned char **TagName;\r
+ vector<string> *TagName;\r
+ TagIdMap * tIdMap;\r
\r
- /** boolean flag indicating whether we are indexing empty texts or not */\r
- bool indexing_empty_texts; \r
- \r
/** Bit vector indicating with a 1 the positions of the non-empty texts. */\r
- static_bitsequence_rrr02 *EBVector; \r
+ static_bitsequence *EBVector; \r
\r
/** Tag sequence represented with a data structure for rank and select */\r
- static_sequence_wvtree *Tags;\r
+ static_sequence *Tags;\r
+ uint * tags_fix;\r
+ uint tags_blen, tags_len;\r
\r
/** The texts in the XML document */\r
- //TextCollection *Text;\r
- \r
- /** Flag indicating whether the whole data structure has been constructed or \r
- * not. If the value is true, you cannot add more texts, nodes, etc. */\r
- bool finished;\r
+ TextCollection *Text;\r
\r
- /** Flag indicating whether the construction of the data structure has been\r
- * initialized or not (by calling method OpenDocument()). If this is true,\r
- * you cannot insert new tags or texts. */\r
- bool initialized;\r
- \r
- /* the following components are used for construction purposes */\r
- pb *par_aux;\r
- TagType *tags_aux;\r
- int npar;\r
- int ntagnames;\r
- unsigned int *empty_texts_aux;\r
+ // Allows to disable the TextCollection for benchmarkin purposes\r
+ bool disable_tc;\r
\r
-public:\r
\r
- /** Data structure constructor */\r
- XMLTree() {finished = false; initialized = false;}; \r
- \r
+ /** Data structure constructors */\r
+ XMLTree(){;};\r
+\r
+ // non const pointer are freed by this method.\r
+ XMLTree( pb * const par, uint npar, vector<string> * const TN, TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,\r
+ TextCollection * const TC, bool dis_tc);\r
+\r
+public: \r
/** Data structure destructor */\r
~XMLTree();\r
\r
\r
/** IsChild(x,y): returns whether node x is parent of node y. */\r
bool IsChild(treeNode x, treeNode y);\r
- \r
+\r
+ /** IsFirstChild(x): returns whether node x is the first child of its parent. */\r
+ bool IsFirstChild(treeNode x);\r
+\r
/** NumChildren(x): number of children of node x. Constant time with the \r
* data structure of Sadakane. */\r
int NumChildren(treeNode x);\r
/** FirstChild(x): returns the first child of node x, assuming it exists. \r
* Very fast in BP. */\r
treeNode FirstChild(treeNode x);\r
+ treeNode FirstElement(treeNode x);\r
+\r
+ /** LastChild(x): returns the last child of node x. */\r
+ treeNode LastChild(treeNode x);\r
\r
/** NextSibling(x): returns the next sibling of node x, assuming it \r
* exists. */\r
treeNode NextSibling(treeNode x);\r
+ treeNode NextElement(treeNode x);\r
\r
/** PrevSibling(x): returns the previous sibling of node x, assuming it \r
* exists. */\r
treeNode PrevSibling(treeNode x);\r
\r
- /** TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or \r
+ /** TaggedChild(x,tag): returns the first child of node x tagged tag, or \r
* NULLT if there is none. Because of the balanced-parentheses representation \r
* of the tree, this operation is not supported efficiently, just iterating \r
* among the children of node x until finding the desired child. */\r
- treeNode TaggedChild(treeNode x, int i, TagType tag);\r
+ treeNode TaggedChild(treeNode x, TagType tag);\r
+ \r
+ treeNode SelectChild(treeNode x, std::unordered_set<int> * tags);\r
+\r
+ /** TaggedFollSibling(x,tag): returns the first sibling of node x tagged tag, or \r
+ * NULLT if there is none. */\r
+ treeNode TaggedFollSibling(treeNode x, TagType tag);\r
\r
+ treeNode SelectFollSibling(treeNode x, std::unordered_set<int> * tags);\r
+\r
/** TaggedDesc(x,tag): returns the first node tagged tag with larger \r
* preorder than x and within the subtree of x. Returns NULT if there \r
* is none. */\r
treeNode TaggedDesc(treeNode x, TagType tag);\r
\r
+ treeNode SelectDesc(treeNode x, std::unordered_set<int> * tags);\r
+\r
+\r
/** TaggedPrec(x,tag): returns the first node tagged tag with smaller \r
* preorder than x and not an ancestor of x. Returns NULLT if there \r
* is none. */\r
* preorder than x and not in the subtree of x. Returns NULLT if there \r
* is none. */\r
treeNode TaggedFoll(treeNode x, TagType tag);\r
+\r
+ treeNode TaggedFollBelow(treeNode x, TagType tag,treeNode root); \r
\r
+ treeNode SelectFollBelow(treeNode x, std::unordered_set<int> * tags, treeNode root);\r
+\r
+ /** TaggedFollowingSibling(x,tag) */\r
+ treeNode TaggedFollowingSibling(treeNode x, TagType tag);\r
+\r
+ /** TaggedAncestor(x, tag): returns the closest ancestor of x tagged \r
+ * tag. Return NULLT is there is none. */\r
+ treeNode TaggedAncestor(treeNode x, TagType tag);\r
+ \r
/** PrevText(x): returns the document identifier of the text to the left of \r
* node x, or NULLT if x is the root node. */\r
DocID PrevText(treeNode x);\r
\r
/** ParentNode(d): returns the parent node of document identifier d. */\r
treeNode ParentNode(DocID d);\r
-\r
- /** OpenDocument(empty_texts,sample_rate_text): initilizes the construction\r
- * of the data structure for the XML document. Parameter empty_texts \r
- * indicates whether we index empty texts in document or not. Parameter \r
- * sample_rate_text indicates the sampling rate for the text searching data\r
- * structures (small values get faster searching but a bigger space \r
- * requirement). Returns a non-zero value upon success, NULLT in case of \r
- * error. */\r
- int OpenDocument(bool empty_texts, int sample_rate_text);\r
-\r
- /** CloseDocument(): finishes the construction of the data structure for \r
- * the XML document. Tree and tags are represented in the final form, \r
- * dynamic data structures are made static, and the flag "finished" is set \r
- * to true. After that, the data structure can be queried. */\r
- int CloseDocument();\r
-\r
- /** NewOpenTag(tagname): indicates the event of finding a new opening tag \r
- * in the document. Tag name is given. Returns a non-zero value upon \r
- * success, and returns NULLT in case of error. */\r
- int NewOpenTag(unsigned char *tagname);\r
- \r
- /** NewClosingTag(tagname): indicates the event of finding a new closing tag\r
- * in the document. Tag name is given. Returns a non-zero value upon \r
- * success, and returns NULLT in case of error. */\r
- int NewClosingTag(unsigned char *tagname);\r
- \r
- /** NewText(s): indicates the event of finding a new (non-empty) text s in \r
- * the document. The new text is inserted within the text collection. \r
- * Returns a non-zero value upon success, NULLT in case of error. */\r
- int NewText(unsigned char *s);\r
-\r
- /** NewEmptyText(): indicates the event of finding a new empty text in the \r
- * document. In case of indexing empty and non-empty texts, we insert the \r
- * empty texts into the text collection. In case of indexing only non-empty\r
- * texts, it just indicates an empty text in the bit vector of empty texts. \r
- * Returns a non-zero value upon success, NULLT in case of error. */\r
- int NewEmptyText();\r
+ \r
+ treeNode PrevNode(DocID d);\r
\r
/** GetTagId(tagname): returns the tag identifier corresponding to a given \r
* tag name. Returns NULLT in case that the tag name does not exists. */\r
* Returns NULL in case that the tag identifier is not valid.*/\r
unsigned char *GetTagName(TagType tagid);\r
\r
- /** saveXMLTree: saves XML tree data structure to file. Every component of \r
- * the collection is stored in different files (same name, different file \r
- * extensions). */\r
- void Save(unsigned char *filename);\r
+ /** GetTagName(tagid): returns the tag name of a given tag identifier. \r
+ * The result is just a reference and should not be freed by the caller.\r
+ */\r
+ const unsigned char *GetTagNameByRef(TagType tagid);\r
+\r
+ /** RegisterTag adds a new tag to the tag collection this is needed\r
+ * if the query contains a tag which is not in the document, we need\r
+ * to give this new tag a fresh id and store it somewhere. A logical\r
+ * choice is here.\r
+ * We might want to use a hashtable instead of an array though.\r
+ */\r
+ TagType RegisterTag(unsigned char *tagname);\r
+\r
+ bool EmptyText(DocID i) {\r
+ return Text->EmptyText(i);\r
+ }\r
+\r
+ /** Prefix(s): search for texts prefixed by string s. */\r
+ TextCollection::document_result Prefix(uchar const *s) {\r
+ return Text->Prefix(s);\r
+ }\r
+\r
+ /** Suffix(s): search for texts having string s as a suffix. */\r
+ TextCollection::document_result Suffix(uchar const *s) {\r
+ return Text->Suffix(s);\r
+ }\r
+\r
+ /** Equal(s): search for texts equal to string s. */\r
+ TextCollection::document_result Equal(uchar const *s) {\r
+ return Text->Equal(s);\r
+ }\r
+\r
+ /** Contains(s): search for texts containing string s. */\r
+ TextCollection::document_result Contains(uchar const *s) {\r
+ return Text->Contains(s);\r
+ }\r
+\r
+ /** LessThan(s): returns document identifiers for the texts that\r
+ * are lexicographically smaller than string s. */\r
+ TextCollection::document_result LessThan(uchar const *s) {\r
+ return Text->LessThan(s);\r
+ }\r
+\r
+ /** KMismatches (s): returns document identifiers for the texts that\r
+ * contain occurrence of string s with at most K mismatches. */\r
+ TextCollection::document_result KMismatches(uchar const *s, unsigned K) {\r
+ return Text->KMismatches(s, K);\r
+ }\r
+\r
+ /** KErrors (s): returns document identifiers for the texts that\r
+ * contain occurrence of string s with at most K errors. \r
+ * The accepted "errors" are insertions, deletions and mutations of chars.\r
+ */\r
+ TextCollection::document_result KErrors(uchar const *s, unsigned K) {\r
+ return Text->KErrors(s, K);\r
+ }\r
+ \r
+ /** IsPrefix(x): returns true if there is a text prefixed by string s. */\r
+ bool IsPrefix(uchar const *s) {\r
+ return Text->IsPrefix(s);\r
+ } \r
+ \r
+ /** IsSuffix(s): returns true if there is a text having string s as a \r
+ * suffix.*/\r
+ bool IsSuffix(uchar const *s) {\r
+ return Text->IsSuffix(s);\r
+ }\r
+ \r
+ /** IsEqual(s): returns true if there is a text that equals given \r
+ * string s. */\r
+ bool IsEqual(uchar const *s) {\r
+ return Text->IsEqual(s);\r
+ }\r
+ \r
+ /** IsContains(s): returns true if there is a text containing string s. */\r
+ bool IsContains(uchar const *s) {\r
+ return Text->IsContains(s);\r
+ }\r
+ \r
+ /** IsLessThan(s): returns true if there is at least a text that is \r
+ * lexicographically smaller than string s. */\r
+ bool IsLessThan(uchar const *s) {\r
+ return Text->IsLessThan(s);\r
+ }\r
+ \r
+ /** Count(s): Global counting */\r
+ unsigned Count(uchar const *s) {\r
+ return Text->Count(s);\r
+ }\r
+\r
+ /** CountPrefix(s): counting version of Prefix(s). */\r
+ unsigned CountPrefix(uchar const *s) {\r
+ return Text->CountPrefix(s);\r
+ }\r
+ \r
+ /** CountSuffix(s): counting version of Suffix(s). */\r
+ unsigned CountSuffix(uchar const *s) {\r
+ return Text->CountSuffix(s);\r
+ }\r
+ \r
+ /** CountEqual(s): counting version of Equal(s). */\r
+ unsigned CountEqual(uchar const *s) {\r
+ return Text->CountEqual(s);\r
+ }\r
+ \r
+ /** CountContains(s): counting version of Contains(s). */\r
+ unsigned CountContains(uchar const *s) {\r
+ return Text->CountContains(s);\r
+ }\r
+ \r
+ /** CountLessThan(s): counting version of LessThan(s). */\r
+ unsigned CountLessThan(uchar const *s) {\r
+ return Text->CountLessThan(s);\r
+ }\r
+ \r
+ /** GetText(d): returns the text corresponding to document with\r
+ * id d. \r
+ *\r
+ * Implementation of GetText() may or may NOT \r
+ * require you to free() the pointer that is returned.\r
+ * Call DeleteText() for each pointer returned by GetText()\r
+ * to avoid possible memory leaks.\r
+ */\r
+ uchar* GetText(DocID d) const {\r
+ return Text->GetText(d);\r
+ }\r
+\r
+ /**\r
+ * Free the pointer returned by GetText().\r
+ */\r
+ void DeleteText(uchar *text) const {\r
+ Text->DeleteText(text);\r
+ }\r
+\r
+ /** GetText(i, j): returns the texts corresponding to documents with\r
+ * ids i, i+1, ..., j. Texts are separated by '\0' character. \r
+ *\r
+ * Call DeleteText() for each pointer returned by GetText()\r
+ * to avoid possible memory leaks.\r
+ */\r
+ uchar* GetText(DocID i, DocID j) const {\r
+ return Text->GetText(i, j);\r
+ }\r
+\r
+\r
+ TextCollection *getTextCollection() {\r
+ return Text;\r
+ }\r
+ \r
+ /** Save: saves XML tree data structure to file. */\r
+ void Save(int fd);\r
\r
- /** load: loads XML tree data structure from file. */\r
- static XMLTree *Load(unsigned char *filename, int sample_rate_text); \r
-};\r
+ /** Load: loads XML tree data structure from file. sample_rate_text \r
+ * indicates the sample rate for the text search data structure. */\r
+ static XMLTree *Load(int fd); \r
\r
+ void insertTag(TagType tag, uint position);\r
+ \r
+ void print_stats();\r
+};\r
+#endif\r
\r
projects / SXSI / XMLTree.git / blobdiff