* 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 <stdlib.h>\r
#include <cstring>\r
\r
-//KIM : OJO\r
-//clash between TextCollection/Tools.h and libcds/includes/basics.h\r
+\r
#undef W\r
#undef WW\r
#undef Wminusone\r
\r
#include "bp.h"\r
+//#include "basics.h"\r
#include <static_bitsequence.h>\r
#include <alphabet_mapper.h>\r
#include <static_sequence.h>\r
\r
#define PERM_SAMPLE 10\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
-\r
\r
typedef int treeNode;\r
typedef int TagType; \r
int max;\r
} range;\r
\r
+typedef struct nd {\r
+ uint position;\r
+ struct nd *next;\r
+} ListNode;\r
\r
-//KIM : OJO\r
-// I know this class implements the working draft that we have but the logics seem flawed here...\r
-// We should have two classes. One XMLTreeBuilder and one XMLTree.\r
-// XMLTreeBuilder would have OpenDocument, NewOpenTag,... and CloseDocument would return an XMLTree\r
-// XMLTree would have only an initialized structure. If find it really ugly to check (!finished) or (!initialized)\r
-// in every function (FirstChild....).\r
+typedef struct {\r
+ ListNode *first;\r
+ ListNode *last;\r
+} TagArrayEntry;\r
\r
class XMLTree {\r
/** Balanced parentheses representation of the tree */\r
\r
/** Mapping from tag identifer to tag name */ \r
unsigned char **TagName;\r
+ uint ntagnames;\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 *Tags;\r
- uint * tags_fix;\r
- uint tags_blen, tags_len;\r
+ uint * tags_fix;\r
+ uint tags_blen, tags_len;\r
\r
/** The texts in the XML document */\r
- TextCollectionBuilder *TextBuilder;\r
TextCollection *Text;\r
\r
/** The texts in the XML document (cached for faster display) */\r
vector<string> CachedText;\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
-\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 parArraySize;\r
- int ntagnames;\r
- unsigned int *empty_texts_aux;\r
-\r
- // KIM : OJO\r
- // I added those two. The TagName array should always contains two special tags\r
- // <@> for attributes and <$> for PCDATA.\r
- // <$> can never be in a document (since we handle the text differently)\r
- // but <@> can be returned by the parser. This boolean is needed for the construction\r
- // of the Tag bitmap to know if <@> must be taken into account or not\r
- bool found_attributes;\r
-\r
- // KIM : OJO\r
+ TagArrayEntry *TagArray;\r
+\r
// Allows to disable the TextCollection for benchmarkin purposes\r
bool disable_tc;\r
\r
public:\r
- void print_stats();\r
+ /** Data structure constructors */\r
+ XMLTree() {;};\r
\r
- /** Data structure constructor */\r
- XMLTree() {finished = false; initialized = false; Text = 0; TextBuilder = 0; }; \r
+ XMLTree(pb *par, uint npar, unsigned char **TN, uint ntagnames, uint *empty_texts_bmp, TagType *tags,\r
+ TextCollection *TC, vector<string> CT, bool indexing_empty_t, bool dis_tc);\r
\r
/** Data structure destructor */\r
~XMLTree();\r
/** IsChild(x,y): returns whether node x is parent of node y. */\r
bool IsChild(treeNode x, treeNode y);\r
\r
- /** IsChild(x,y): returns whether node x is the first child of its parent */\r
+ /** IsFirstChild(x): returns whether node x is the first child of its parent. */\r
bool IsFirstChild(treeNode x);\r
- \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
* Very fast in BP. */\r
treeNode FirstChild(treeNode x);\r
\r
- /** LastChild(x): returns the last child of node x. \r
- * Implemented by Kim naively. */\r
+ /** LastChild(x): returns the last child of node x. */\r
treeNode LastChild(treeNode x);\r
-\r
+ \r
/** NextSibling(x): returns the next sibling of node x, assuming it \r
* exists. */\r
-\r
treeNode NextSibling(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, TagType *tags, int ntags);\r
+\r
+ /** TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or \r
+ * NULLT if there is none. */\r
+ treeNode TaggedSibling(treeNode x, TagType tag);\r
+ \r
+ treeNode SelectSibling(treeNode x, TagType *tags, int ntags);\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, TagType *tags, int ntags);\r
\r
treeNode TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen,\r
TagType *desctags, unsigned int dtlen);\r
treeNode TaggedFoll(treeNode x, TagType tag);\r
\r
treeNode TaggedFollBelow(treeNode x, TagType tag,treeNode root); \r
- \r
+ \r
+ treeNode SelectFollBelow(treeNode x, TagType *tags, int ntags, treeNode ctx);\r
+\r
/** TaggedFollowingSibling(x,tag) */\r
treeNode TaggedFollowingSibling(treeNode x, TagType tag);\r
\r
\r
/** ParentNode(d): returns the parent node of document identifier d. */\r
treeNode ParentNode(DocID d);\r
+ \r
treeNode PrevNode(DocID d);\r
\r
- /** OpenDocument(empty_texts,sample_rate_text,dtc): 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). dtc disable the use of the TextCollection\r
- * (i.e. everything is considered an empty text *)\r
- * Returns a non-zero value upon success, NULLT in case of \r
- * error. */\r
-\r
- int OpenDocument(bool empty_texts, int sample_rate_text, bool dtc);\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
/** 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
TagType GetTagId(unsigned char *tagname);\r
* Returns NULL in case that the tag identifier is not valid.*/\r
unsigned char *GetTagName(TagType tagid);\r
\r
-\r
- // OJO\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
- //OJO\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
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
/** CountLessThan(s): counting version of LessThan(s). */\r
unsigned CountLessThan(uchar const *s) {\r
- return CountLessThan(s);\r
+ return Text->CountLessThan(s);\r
}\r
\r
/** GetText(d): returns the text corresponding to document with\r
TextCollection *getTextCollection() {\r
return Text;\r
}\r
+ \r
/** Save: saves XML tree data structure to file. */\r
void Save(unsigned char *filename);\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(unsigned char *filename, int sample_rate_text); \r
+\r
+ void insertTag(TagType tag, uint position);\r
+ \r
+ void print_stats();\r
};\r
#endif\r
+\r
projects / SXSI / XMLTree.git / blobdiff