#include "basics.h"\r
#include <cstring>\r
#include <sstream>\r
+#include <stack>\r
#include "XMLTree.h"\r
#include <sys/time.h>\r
#include <time.h>\r
+#include <sys/types.h>\r
#include <sys/stat.h> \r
#include <unistd.h>\r
\r
return (int)x;\r
}\r
\r
-// returns NULLT if the test is true\r
-#define NULLT_IF(x) do { if (x) return NULLT; } while (0)\r
+int fast_find_close(bp *b,int s)\r
+{\r
+ return fwd_excess(b,s,-1);\r
+}\r
+\r
+inline int fast_inspect(bp* Par,treeNode i)\r
+{\r
+ int j,l;\r
+ j = i >> logD;\r
+ l = i & (D-1);\r
+ return (Par->B[j] >> (D-1-l)) & 1;\r
+}\r
+\r
+inline treeNode fast_first_child(bp *Par, treeNode x)\r
+{\r
+ x = x+1;\r
+ return (fast_inspect(Par,x) == CP) ? NULLT : x;\r
+}\r
+\r
+inline treeNode fast_next_sibling(bp* Par,treeNode x)\r
+{\r
+ x = fast_find_close(Par,x)+1;\r
+ return (fast_inspect(Par,x) == CP) ? NULLT : x;\r
+}\r
+\r
+\r
+inline treeNode fast_sibling(bp* Par,treeNode x,TagType tag){\r
+\r
+ if (tag == PCDATA_TAG_ID){\r
+ x = x+2;\r
+ return fast_inspect(Par,x)==OP ? x : NULLT;\r
+ } else return fast_next_sibling(Par,x);\r
\r
+}\r
+\r
+inline bool fast_isleaf(bp* Par,treeNode x){\r
+ return (fast_inspect(Par,x+1) == CP ? true : false);\r
+}\r
+\r
+inline uint fast_get_field(uint* A,int len, int idx)\r
+{\r
+ switch(len){\r
+ case 8:\r
+ return (uint) (((uchar*)A)[idx]);\r
+ // Other 8-alligned values need to take care of the endianess of the arch.\r
+ default: \r
+ return get_field (A,len,idx);\r
+ };\r
+\r
+}\r
+\r
+inline bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){\r
+\r
+ if (x > y) \r
+ return false;\r
+ else\r
+ return (y <= fast_find_close(Par,x));\r
+}\r
\r
-XMLTree::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
+XMLTree::XMLTree( pb * const par, uint npar, vector<string> * const TN, TagIdMap * const tim, \r
+ uint *empty_texts_bmp, TagType *tags,\r
+ TextCollection * const TC, bool dis_tc)\r
{\r
// creates the data structure for the tree topology\r
Par = (bp *)umalloc(sizeof(bp));\r
tIdMap = (TagIdMap *) tim;\r
\r
uint max_tag = TN->size() - 1;\r
+ \r
\r
static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray();\r
alphabet_mapper *am = new alphabet_mapper_none();\r
\r
cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl;\r
\r
- tags_blen = bits(max_tag);\r
+ //Ensures that for small tag numbers, we are on an 8bit boundary.\r
+ //Makes tag access way faster with negligeable waste of space.\r
+ tags_blen = max(bits(max_tag),8);\r
+ std::cerr << "Tags blen is " << tags_blen << "\n";\r
tags_len = (uint)npar;\r
tags_fix = new uint[uint_len(tags_blen,tags_len)];\r
for(uint i=0;i<(uint)npar;i++)\r
\r
\r
EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32);\r
+ //EBVector = new static_bitsequence_sdarray(empty_texts_bmp,npar);\r
free(empty_texts_bmp);\r
empty_texts_bmp = NULL;\r
\r
\r
disable_tc = dis_tc;\r
+ stream = NULL;\r
+ stream_fd = 0;\r
}\r
\r
\r
\r
delete EBVector;\r
EBVector = NULL;\r
-\r
+ if (stream != NULL){\r
+ fclose(stream);\r
+ stream = NULL;\r
+ stream_fd = 0;\r
+ };\r
\r
}\r
\r
\r
// Load: loads XML tree data structure from file. Returns\r
// a pointer to the loaded data structure\r
-XMLTree *XMLTree::Load(int fd) \r
+XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor) \r
{\r
FILE *fp;\r
char buffer[1024];\r
// loads the tag structure\r
XML_Tree->Tags = static_sequence::load(fp);\r
ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);\r
+ std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n"; \r
ufread(&XML_Tree->tags_len,sizeof(uint),1,fp);\r
XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)];\r
ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp);\r
// loads the flags\r
\r
ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);\r
-\r
+ if (load_tc) {\r
XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);\r
-\r
+ //XML_Tree->EBVector = static_bitsequence_sdarray::load(fp);\r
\r
STOPTIMER(Loading);\r
PRINTTIME("Loading text bitvector struct", Loading);\r
STARTTIMER();\r
\r
// Not used \r
- int sample_rate_text = 64;\r
// loads the texts\r
if (!XML_Tree->disable_tc){\r
- XML_Tree->Text = TextCollection::Load(fp,sample_rate_text);\r
+ XML_Tree->Text = TextCollection::Load(fp,sample_factor);\r
}\r
else XML_Tree->Text = NULL;\r
STOPTIMER(Loading);\r
PRINTTIME("Loading TextCollection", Loading);\r
- STARTTIMER();\r
+ STARTTIMER(); \r
+ }\r
+ else {\r
+ XML_Tree->EBVector = NULL;\r
+ XML_Tree->Text = NULL;\r
+ XML_Tree->disable_tc = true;\r
+ };\r
\r
+ XML_Tree->stream = NULL;\r
+ XML_Tree->stream_fd = 0;\r
+ \r
return XML_Tree;\r
}\r
\r
int XMLTree::SubtreeTags(treeNode x, TagType tag) \r
{\r
if (x == Root())\r
- x = first_child(Par,x);\r
+ x = fast_first_child(Par,x);\r
\r
\r
int s = x + 2*subtree_size(Par, x) - 1;\r
\r
return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1);\r
}\r
+int XMLTree::SubtreeElements(treeNode x) \r
+ {\r
+ \r
+ int size = subtree_size(Par,x);\r
+ if (x == Root()){\r
+ x = fast_first_child(Par,x);\r
+ size = size - 1;\r
+ };\r
+\r
+ int s = x + 2*size - 1;\r
+ int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1);\r
+ size = size - ntext;\r
+ treeNode fin = fast_find_close(Par,x);\r
+ treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x));\r
+ while (y != NULLT && y < fin){\r
+ size -= SubtreeSize(y);\r
+ y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y));\r
+ };\r
+ return size; \r
+ }\r
\r
// IsLeaf(x): returns whether node x is leaf or not. In the succinct representation\r
// this is just a bit inspection.\r
bool XMLTree::IsLeaf(treeNode x) \r
{\r
- return isleaf(Par, x);\r
+ NULLT_IF(x==NULLT);\r
+ return fast_isleaf(Par, x);\r
} \r
\r
// IsAncestor(x,y): returns whether node x is ancestor of node y.\r
bool XMLTree::IsAncestor(treeNode x, treeNode y) \r
{\r
- return is_ancestor(Par, x, y);\r
+ return fast_is_ancestor(Par, x, y);\r
}\r
\r
// IsChild(x,y): returns whether node x is parent of node y.\r
bool XMLTree::IsChild(treeNode x, treeNode y) \r
{\r
- if (!is_ancestor(Par, x, y)) return false;\r
+ if (!fast_is_ancestor(Par, x, y)) return false;\r
return depth(Par, x) == (depth(Par, y) + 1);\r
}\r
\r
{\r
return postorder_rank(Par, x);\r
}\r
-\r
+/*\r
// Tag(x): returns the tag identifier of node x.\r
TagType XMLTree::Tag(treeNode x) \r
{\r
- return get_field(tags_fix,tags_blen,node2tagpos(x));\r
+ return fast_get_field(tags_fix,tags_blen,node2tagpos(x));\r
}\r
-\r
+*/\r
// DocIds(x): returns the range of text identifiers that descend from node x.\r
// returns {NULLT, NULLT} when there are no texts descending from x.\r
range XMLTree::DocIds(treeNode x) \r
{\r
- range r;\r
- if (x == NULLT) {\r
- r.min = NULLT;\r
- r.max = NULLT;\r
- return r;\r
- };\r
- \r
- \r
- int min = EBVector->rank1(x-1); \r
- int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); \r
- if (min==max) { // range is empty, no texts within the subtree of x\r
- r.min = NULLT;\r
- r.max = NULLT;\r
- }\r
- else { // the range is non-empty, there are texts within the subtree of x\r
- r.min = min+1;\r
- r.max = max;\r
- }\r
- return r;\r
-\r
+ range r;\r
+ if (x == NULLT) {\r
+ r.min = NULLT;\r
+ r.max = NULLT;\r
+ return r;\r
+ };\r
+ int min = EBVector->rank1(x-1); \r
+ int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); \r
+ if (min==max) { // range is empty, no texts within the subtree of x\r
+ r.min = NULLT;\r
+ r.max = NULLT;\r
+ }\r
+ else { // the range is non-empty, there are texts within the subtree of x\r
+ r.min = min+1;\r
+ r.max = max;\r
+ }\r
+ return r;\r
}\r
\r
// Parent(x): returns the parent node of node x.\r
+\r
treeNode XMLTree::Parent(treeNode x) \r
{\r
if (x == Root())\r
return NULLT;\r
else\r
- return parent(Par, x);\r
+ return parent(Par, x);;\r
}\r
\r
// Child(x,i): returns the i-th child of node x, assuming it exists.\r
}\r
\r
// FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
+\r
treeNode XMLTree::FirstChild(treeNode x) \r
{\r
NULLT_IF(x==NULLT);\r
- return first_child(Par, x);\r
+ return fast_first_child(Par, x);\r
}\r
\r
treeNode XMLTree::FirstElement(treeNode x) \r
{\r
NULLT_IF(x==NULLT);\r
- treeNode fc = first_child(Par, x);\r
- NULLT_IF(fc == NULLT);\r
- TagType tag = Tag(fc);\r
- if (tag != PCDATA_TAG_ID && tag != ATTRIBUTE_TAG_ID) \r
- return fc;\r
- else return next_sibling(Par,fc);\r
-\r
+ x = fast_first_child(Par, x);\r
+ NULLT_IF(x == NULLT);\r
+ TagType tag = Tag(x);\r
+ if (tag == PCDATA_TAG_ID){\r
+ x = x+2;\r
+ return (fast_inspect(Par,x)==OP)? x : NULLT;\r
+ } \r
+ else if (tag == ATTRIBUTE_TAG_ID){\r
+ x = fast_next_sibling(Par,x);\r
+ if (x != NULLT && Tag(x) == PCDATA_TAG_ID){\r
+ x = x+2;\r
+ return (fast_inspect(Par,x)==OP)? x : NULLT;\r
+ } \r
+ else return x; \r
+ }else return x;\r
}\r
\r
treeNode XMLTree::NextElement(treeNode x) \r
{\r
- NULLT_IF(x==NULLT);\r
- treeNode ns = next_sibling(Par, x);\r
- NULLT_IF(ns == NULLT);\r
- TagType tag = Tag(ns);\r
- if (tag != PCDATA_TAG_ID && tag != ATTRIBUTE_TAG_ID) \r
- return ns;\r
- else return next_sibling(Par,ns);\r
+ NULLT_IF(x==NULLT);\r
+ x = fast_next_sibling(Par, x);\r
+ NULLT_IF(x == NULLT); \r
+ if (Tag(x) == PCDATA_TAG_ID){\r
+ x = x+2;\r
+ return (fast_inspect(Par,x)==OP)? x : NULLT;\r
+ }\r
+ else return x; \r
}\r
\r
// LastChild(x): returns the last child of node x.\r
treeNode XMLTree::LastChild(treeNode x)\r
{\r
- NULLT_IF(x==NULLT || x == Root() || isleaf(Par,x));\r
- return find_open(Par, find_close(Par, x)-1);\r
+ NULLT_IF(NULLT || x == Root() || fast_isleaf(Par,x));\r
+ return find_open(Par, fast_find_close(Par, x)-1);\r
}\r
\r
-\r
// NextSibling(x): returns the next sibling of node x, assuming it exists.\r
treeNode XMLTree::NextSibling(treeNode x) \r
{\r
NULLT_IF(x==NULLT || x == Root() );\r
- return next_sibling(Par, x);\r
+ x = fast_find_close(Par,x)+1;\r
+ return (fast_inspect(Par,x) == CP ? NULLT : x);\r
}\r
\r
+\r
// PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
treeNode XMLTree::PrevSibling(treeNode x) \r
{\r
treeNode XMLTree::TaggedChild(treeNode x, TagType tag) \r
{\r
\r
- NULLT_IF(x==NULLT || isleaf(Par,x));\r
-\r
+ NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
treeNode child; \r
- child = first_child(Par, x); // starts at first child of node x\r
- if (get_field(tags_fix,tags_blen,node2tagpos(child)) == tag)\r
+ child = fast_first_child(Par, x); // starts at first child of node x\r
+ if (Tag(child) == tag)\r
return child;\r
else\r
- return TaggedFollSibling(child,tag);\r
+ return TaggedFollowingSibling(child,tag);\r
}\r
\r
// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.\r
-treeNode XMLTree::TaggedFollSibling(treeNode x, TagType tag)\r
+treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)\r
{\r
NULLT_IF(x==NULLT);\r
- treeNode sibling = next_sibling(Par, x); \r
+ treeNode sibling = fast_next_sibling(Par, x);\r
+ TagType ctag;\r
while (sibling != NULLT) {\r
- if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest\r
+ ctag = Tag(sibling);\r
+ if (ctag == tag) // current sibling is labeled with tag of interest\r
return sibling; \r
- sibling = next_sibling(Par, sibling); // OK, let's try with the next sibling\r
+ sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling\r
}\r
return NULLT; // no such sibling was found \r
}\r
\r
-treeNode XMLTree::SelectChild(treeNode x, std::unordered_set<int> *tags)\r
+treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags)\r
{\r
\r
- NULLT_IF(x==NULLT || isleaf(Par,x));\r
+ NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
int i;\r
- treeNode child = first_child(Par, x); \r
- TagType t = get_field(tags_fix, tags_blen, node2tagpos(child));\r
- std::unordered_set<int>::const_iterator tagit = tags->find(t);\r
- if (tagit != tags->end()) return child; \r
- return SelectFollSibling(child,tags);\r
+ treeNode child = fast_first_child(Par, x); \r
+ TagType t;\r
+ while (child != NULLT) {\r
+ t = Tag(child);\r
+ if (tags->find(t) != tags->end()) return child;\r
+ child = fast_sibling(Par, child,t);\r
+ }\r
+ return NULLT; \r
}\r
\r
\r
-treeNode XMLTree::SelectFollSibling(treeNode x, std::unordered_set<int> *tags)\r
+treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)\r
{\r
\r
NULLT_IF(x==NULLT);\r
int i;\r
TagType t;\r
- treeNode sibling = next_sibling(Par, x);\r
- std::unordered_set<int>::const_iterator tagit;\r
+ treeNode sibling = fast_next_sibling(Par, x);\r
while (sibling != NULLT) {\r
- t = get_field(tags_fix, tags_blen, node2tagpos(sibling));\r
- tagit = tags->find(t);\r
- if (tagit != tags->end()) return sibling;\r
- sibling = next_sibling(Par, sibling);\r
+ t = Tag(sibling);\r
+ if (tags->find(t) != tags->end()) return sibling;\r
+ sibling = fast_sibling(Par, sibling,t);\r
}\r
return NULLT; \r
}\r
\r
\r
-// TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within\r
+// TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within\r
// the subtree of x. Returns NULLT if there is none.\r
-treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) \r
+treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) \r
{\r
- NULLT_IF(x==NULLT || isleaf(Par,x));\r
+ NULLT_IF(x==NULLT || fast_isleaf(Par,x));\r
\r
int s = (int) Tags->select_next(tag,node2tagpos(x));\r
NULLT_IF (s == -1);\r
\r
treeNode y = tagpos2node(s); // transforms the tag position into a node position\r
\r
- return (is_ancestor(Par,x,y) ? y : NULLT);\r
+ return (fast_is_ancestor(Par,x,y) ? y : NULLT);\r
}\r
\r
\r
-treeNode XMLTree::SelectDesc(treeNode x, std::unordered_set<int> *tags)\r
+treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)\r
{\r
- NULLT_IF (x ==NULLT || isleaf(Par,x));\r
+ NULLT_IF (x ==NULLT || fast_isleaf(Par,x));\r
int i;\r
treeNode min = NULLT;\r
- treeNode fc = first_child(Par,x);\r
+ treeNode fc = fast_first_child(Par,x);\r
treeNode aux;\r
- std::unordered_set<int>::const_iterator tagit;\r
+ TagIdSet::const_iterator tagit;\r
for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
- aux = TaggedDesc(x, (TagType) *tagit);\r
+ aux = TaggedDescendant(x, (TagType) *tagit);\r
if (aux == fc) return fc;\r
if (aux == NULLT) continue;\r
if ((min == NULLT) || (aux < min)) min = aux;\r
\r
// TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an\r
// ancestor of x. Returns NULLT if there is none.\r
-treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) \r
+treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) \r
{ \r
int r, s;\r
treeNode node_s, root;\r
s = (int)Tags->select(tag, r);\r
root = root_node(Par);\r
node_s = tagpos2node(s);\r
- while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
+ while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x\r
r--;\r
if (r==0) return NULLT; // there is no such node\r
s = (int)Tags->select(tag, r); // we should use select_prev instead when provided\r
\r
// TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in\r
// the subtree of x. Returns NULLT if there is none.\r
-treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)\r
+treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)\r
{\r
- NULLT_IF (x ==NULLT || x == Root());\r
- \r
- return tagpos2node(Tags->select_next(tag,find_close(Par, x)));\r
+ NULLT_IF (x ==NULLT || x == Root()); \r
+ return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x)));\r
\r
} \r
\r
// TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x \r
// and not in the subtree of x. Returns NULLT if there is none.\r
-treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root)\r
+treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)\r
+{\r
+ NULLT_IF (x == NULLT || x == Root() || x == ancestor); \r
+ treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x)));\r
+ \r
+ if (ancestor == Root()) return s;\r
+ NULLT_IF (s == NULLT || s >= fast_find_close(Par, ancestor));\r
+ \r
+ return s;\r
+} \r
+\r
+treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing)\r
{\r
\r
NULLT_IF (x == NULLT || x == Root());\r
\r
- treeNode s = tagpos2node(Tags->select_next(tag, find_close(Par, x)));\r
- \r
- if (root == Root()) return s;\r
- NULLT_IF (s == NULLT || s >= find_close(Par, root));\r
+ treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x))); \r
+ NULLT_IF (s == NULLT || s >= closing);\r
\r
return s;\r
} \r
\r
/* Here we inline TaggedFoll to find the min globally, and only at the end\r
we check if the min is below the context node */\r
-treeNode XMLTree::SelectFollBelow(treeNode x, std::unordered_set<int> *tags, treeNode root)\r
+treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor)\r
{\r
\r
NULLT_IF(x==NULLT || x==Root());\r
int i;\r
treeNode min = NULLT;\r
- treeNode ns = next_sibling(Par, x);\r
+ treeNode ns = fast_next_sibling(Par, x);\r
+ treeNode close = ns - 1;\r
treeNode aux;\r
- std::unordered_set<int>::const_iterator tagit;\r
+ TagIdSet::const_iterator tagit;\r
for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
\r
- aux = tagpos2node(Tags->select_next(*tagit, find_close(Par, x)));\r
+ aux = tagpos2node(Tags->select_next(*tagit, close));\r
\r
// The next sibling of x is guaranteed to be below ctx\r
// and is the node with lowest preorder which is after ctx.\r
// found the smallest node in preorder which is after x.\r
// if ctx is the root node, just return what we found.\r
\r
- if (root == Root()) return min;\r
+ if (ancestor == Root()) return min;\r
// else check whether if is in below the ctx node\r
\r
- NULLT_IF (min == NULLT || min >= find_close(Par, root));\r
+ NULLT_IF (min == NULLT || min >= fast_find_close(Par, ancestor));\r
+ \r
+ return min;\r
+ \r
+ }\r
+treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing)\r
+ {\r
+\r
+ NULLT_IF(x==NULLT || x==Root());\r
+ int i;\r
+ treeNode min = NULLT;\r
+ treeNode ns = fast_next_sibling(Par, x);\r
+ treeNode close = ns - 1;\r
+ treeNode aux;\r
+ TagIdSet::const_iterator tagit;\r
+ for (tagit = tags->begin(); tagit != tags->end(); tagit++) {\r
+\r
+ aux = tagpos2node(Tags->select_next(*tagit, close));\r
+ \r
+ // The next sibling of x is guaranteed to be below ctx\r
+ // and is the node with lowest preorder which is after ctx.\r
+ // if we find it, we return early;\r
+ \r
+ if (aux == ns ) return ns;\r
+ if (aux == NULLT) continue;\r
+ if ((min == NULLT) || (aux < min)) min = aux;\r
+ };\r
+ \r
+ // found the smallest node in preorder which is after x.\r
+ // if ctx is the root node, just return what we found.\r
+\r
+ NULLT_IF (min == NULLT || min >= closing);\r
\r
return min;\r
\r
\r
treeNode s = parent(Par, x), r = Root();\r
while (s != r) {\r
- if (get_field(tags_fix,tags_blen,node2tagpos(s)) /*Tags->access(node2tagpos(s))*/ == tag) return s;\r
+ if (Tag(s) == tag) return s;\r
s = parent(Par, s);\r
}\r
return NULLT;\r
// seems faster than testing EBVector->access(x);\r
\r
if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID)\r
+ //if (EBVector->access(x))\r
return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0\r
else \r
return (DocID) NULLT;\r
\r
}\r
-\r
+// MyText(x): returns the document identifier of the text below node x, \r
+// or NULLT if x is not a leaf node or the text is empty. Assumes Doc \r
+// ids start from 0.\r
+DocID XMLTree::MyTextUnsafe(treeNode x) \r
+{\r
+ return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0\r
+}\r
// TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of\r
// all tree nodes and all text nodes. Assumes that the tree root has preorder 1.\r
int XMLTree::TextXMLId(DocID d) \r
unsigned char *s;\r
if ( tagid < 0 || tagid >= TagName->size())\r
return (unsigned char *) "<INVALID TAG>";\r
- strcpy((char *)s, TagName->at(tagid).c_str());\r
+ strcpy((char *)s, (*TagName)[tagid].c_str());\r
\r
return (s == NULL ? (unsigned char*) "<INVALID TAG>" : s);\r
}\r
if ( tagid < 0 || tagid >= TagName->size())\r
return (unsigned char *) "<INVALID TAG>";\r
\r
- return (const unsigned char *) TagName->at(tagid).c_str();\r
+ return (const unsigned char *) (*TagName)[tagid].c_str();\r
\r
}\r
\r
TagType id = XMLTree::GetTagId(tagname);\r
if (id == NULLT) {\r
string s = (char *) tagname; \r
- REGISTER_TAG(TagName,tIdMap,s);\r
- \r
+ REGISTER_TAG(TagName,tIdMap,s); \r
};\r
\r
return id;\r
\r
\r
treeNode XMLTree::Closing(treeNode x) {\r
- return find_close(Par,x); \r
+ return fast_find_close(Par,x); \r
+}\r
+bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }\r
+\r
+//WARNING this uses directly the underlying implementation for plain text\r
+\r
+void XMLTree::Print(int fd,treeNode x){\r
+ \r
+ int newfd = dup(fd);\r
+ stream = fdopen(newfd,"wa");\r
+ /* if (stream_fd != fd){\r
+ if (stream != NULL)\r
+ fclose(stream);\r
+ int newfd = dup(fd);\r
+ stream = fdopen(newfd,"wa");\r
+ stream_fd = fd;\r
+ };\r
+ */\r
+\r
+ FILE* fp = stream;\r
+ treeNode fin = fast_find_close(Par,x);\r
+ treeNode n = x;\r
+ TagType tag = Tag(n);\r
+ uchar * tagstr;\r
+ range r = DocIds(x);\r
+ treeNode first_idx;\r
+ treeNode first_text = (tag == PCDATA_TAG_ID ? x : TaggedDescendant(x,PCDATA_TAG_ID));\r
+ treeNode first_att = NULLT;//TaggedDesc(x,ATTRIBUTE_DATA_TAG_ID);\r
+ \r
+ if (first_att == NULLT)\r
+ first_idx = first_text;\r
+ else if (first_text == NULLT)\r
+ first_idx = first_att;\r
+ else\r
+ first_idx = min(first_att,first_text);\r
+ \r
+ uchar * current_text=NULL;\r
+ if (first_idx != NULLT)\r
+ current_text = GetText(MyText(first_idx));\r
+ int read = 0;\r
+\r
+ std::stack<uchar*> st;\r
+ while (n <= fin){\r
+ if (fast_inspect(Par,n)){\r
+ if (tag == PCDATA_TAG_ID) { \r
+ // fputs((const char*) (GetText(MyTextUnsafe(n))),fp);\r
+ \r
+ read = fprintf(fp,"%s",(const char*) current_text);\r
+ current_text += (read + 1);\r
+\r
+ n+=2; // skip closing $\r
+ tag = Tag(n);\r
+ }\r
+ else {\r
+\r
+ fputc('<',fp);\r
+ tagstr = (uchar*) GetTagNameByRef(tag);\r
+ fputs((const char*) tagstr ,fp);\r
+ n++;\r
+ if (fast_inspect(Par,n)) {\r
+ st.push(tagstr);\r
+ tag = Tag(n);\r
+ if (tag == ATTRIBUTE_TAG_ID){\r
+ n++;\r
+ while (fast_inspect(Par,n)){\r
+ fputc(' ',fp);\r
+ fputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp);\r
+ fputs("=\"",fp);\r
+ n++;\r
+ read = fprintf(fp,"%s",(const char*) current_text);\r
+ current_text += (read + 1);\r
+ //fputs((const char*) GetText(MyTextUnsafe(n)),fp);\r
+ fputc('"',fp);\r
+ n+=3; //close @$ @@ \r
+ };\r
+ fputc('>',fp);\r
+ n++;\r
+ tag=Tag(n);\r
+ }\r
+ else {\r
+ fputc('>',fp);\r
+ };\r
+ }\r
+ else {// <foo /> tag\r
+ fputs("/>",fp);\r
+ n++;\r
+ tag=Tag(n); \r
+ }; \r
+ };\r
+ }\r
+ else\r
+ do {\r
+ fputs("</",fp);\r
+ fputs((const char*)st.top(),fp);\r
+ fputc('>', fp);\r
+ st.pop();\r
+ n++;\r
+ }while (!fast_inspect(Par,n) && !st.empty());\r
+ tag=Tag(n);\r
+ };\r
+ fputc('\n',fp);\r
+ fflush(fp);\r
+ fclose(fp);\r
}\r
-bool XMLTree::IsOpen(treeNode x) { return inspect(Par,x); }\r
-\r
/******************************************************************************\r
* Copyright (C) 2008 by Diego Arroyuelo *\r
* Interface for the in-memory XQuery/XPath engine *\r
#undef Wminusone\r
\r
#include "bp.h"\r
-\r
+#include <libcds/includes/basics.h>\r
#include <static_bitsequence.h>\r
#include <alphabet_mapper.h>\r
#include <static_sequence.h>\r
#define ATTRIBUTE_DATA_CLOSE_TAG "/<@$>"\r
\r
\r
-\r
+typedef std::unordered_set<int> TagIdSet;\r
typedef std::unordered_map<string,int> TagIdMap;\r
typedef TagIdMap::const_iterator TagIdMapIT;\r
\r
(v)->push_back(t); } while (false)\r
\r
\r
+// returns NULLT if the test is true\r
+#define NULLT_IF(x) do { if (x) return NULLT; } while (0)\r
+\r
+\r
class XMLTreeBuilder;\r
\r
class XMLTree {\r
// Allows to disable the TextCollection for benchmarkin purposes\r
bool disable_tc;\r
\r
+ FILE* stream;\r
+ int stream_fd;\r
\r
/** Data structure constructors */\r
XMLTree(){;};\r
\r
/** root(): returns the tree root. */\r
treeNode Root();\r
- \r
+\r
+ /** Size() : Number of parenthesis */\r
+ unsigned int Size(){\r
+ return tags_len/2;\r
+ }\r
+\r
/** SubtreeSize(x): the number of nodes (and attributes) in the subtree of \r
* node x. */\r
int SubtreeSize(treeNode x);\r
- \r
+ \r
/** SubtreeTags(x,tag): the number of occurrences of tag within the subtree \r
* of node x. */\r
int SubtreeTags(treeNode x, TagType tag);\r
\r
+ /** SubtreeElements(x) of element nodes in the subtree of x\r
+ */\r
+ int SubtreeElements(treeNode x);\r
+\r
/** IsLeaf(x): returns whether node x is leaf or not. In the succinct \r
* representation this is just a bit inspection. */\r
+\r
bool IsLeaf(treeNode x);\r
- \r
+\r
/** IsAncestor(x,y): returns whether node x is ancestor of node y. */\r
+\r
bool IsAncestor(treeNode x, treeNode y);\r
\r
/** IsChild(x,y): returns whether node x is parent of node y. */\r
bool IsChild(treeNode x, treeNode y);\r
\r
/** IsFirstChild(x): returns whether node x is the first child of its parent. */\r
+ /* OCAML */\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
- \r
+\r
/** ChildNumber(x): returns i if node x is the i-th children of its \r
* parent. */\r
- inline int ChildNumber(treeNode x);\r
+ int ChildNumber(treeNode x);\r
\r
/** Depth(x): depth of node x, a simple binary rank on the parentheses \r
* sequence. */\r
/** Postorder(x): returns the postorder number of node x, just regarding \r
* tree nodes (and not texts). */\r
int Postorder(treeNode x);\r
- \r
+ \r
/** Tag(x): returns the tag identifier of node x. */\r
- TagType Tag(treeNode x);\r
- \r
+ TagType Tag(treeNode x) {\r
+ if (tags_blen == 8)\r
+ return (TagType) (((uchar*)tags_fix)[(int) x]);\r
+ else\r
+ return (TagType) get_field(tags_fix,tags_blen, (int) x);\r
+ }\r
+\r
/** DocIds(x): returns the range (i.e., a pair of integers) of document \r
* identifiers that descend from node x. */\r
range DocIds(treeNode x);\r
- \r
+\r
/** Parent(x): returns the parent node of node x. */\r
treeNode Parent(treeNode x);\r
+ /* Assumes x is neither 0 nor -1 */\r
\r
/** Child(x,i): returns the i-th child of node x, assuming it exists. */ \r
treeNode Child(treeNode x, int i);\r
- \r
- /** FirstChild(x): returns the first child of node x, assuming it exists. \r
- * Very fast in BP. */\r
+\r
+ /** FirstChild(x): returns the first child of node x, or NULLT if the node is a leaf\r
+ */\r
treeNode FirstChild(treeNode x);\r
+\r
+ /** FirstElement(x): returns the first non text, non attribute child of node x, or NULLT\r
+ * if none.\r
+ */\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
+ /** NextSibling(x): returns the next sibling of node x, or NULLT if none \r
* exists. */\r
+\r
treeNode NextSibling(treeNode x);\r
+\r
+ /** NextElement(x): returns the first non text, non attribute sibling of node x, or NULLT\r
+ * if none.\r
+ */\r
treeNode NextElement(treeNode x);\r
\r
/** PrevSibling(x): returns the previous sibling of node x, assuming it \r
* exists. */\r
+\r
treeNode PrevSibling(treeNode x);\r
\r
/** TaggedChild(x,tag): returns the first child of node x tagged tag, or \r
* among the children of node x until finding the desired child. */\r
treeNode TaggedChild(treeNode x, TagType tag);\r
\r
- treeNode SelectChild(treeNode x, std::unordered_set<int> * tags);\r
+ treeNode SelectChild(treeNode x, TagIdSet * tags);\r
\r
- /** TaggedFollSibling(x,tag): returns the first sibling of node x tagged tag, or \r
+ /** TaggedFollowingSibling(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
+ treeNode TaggedFollowingSibling(treeNode x, TagType tag);\r
\r
- treeNode SelectFollSibling(treeNode x, std::unordered_set<int> * tags);\r
+ treeNode SelectFollowingSibling(treeNode x, TagIdSet * 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
+ treeNode TaggedDescendant(treeNode x, TagType tag);\r
\r
+ treeNode SelectDescendant(treeNode x, TagIdSet * tags);\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
- treeNode TaggedPrec(treeNode x, TagType tag);\r
+ treeNode TaggedPreceding(treeNode x, TagType tag);\r
\r
/** TaggedFoll(x,tag): returns the first node tagged tag with larger \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
+ treeNode TaggedFollowing(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
+ treeNode TaggedFollowingBelow(treeNode x, TagType tag,treeNode ancestor); \r
\r
- /** TaggedFollowingSibling(x,tag) */\r
- treeNode TaggedFollowingSibling(treeNode x, TagType tag);\r
+ treeNode SelectFollowingBelow(treeNode x, TagIdSet * tags, treeNode ancestor);\r
+\r
+ treeNode TaggedFollowingBefore(treeNode x, TagType tag,treeNode closing);\r
+\r
+ treeNode SelectFollowingBefore(treeNode x, TagIdSet * tags, treeNode closing);\r
\r
/** TaggedAncestor(x, tag): returns the closest ancestor of x tagged \r
* tag. Return NULLT is there is none. */\r
/** MyText(x): returns the document identifier of the text below node x, or \r
* NULLT if x is not a leaf node. */\r
DocID MyText(treeNode x);\r
- \r
+ DocID MyTextUnsafe(treeNode x);\r
+\r
/** TextXMLId(d): returns the preorder of document with identifier d in the \r
* tree consisting of all tree nodes and all text nodes. */\r
int TextXMLId(DocID d);\r
}\r
\r
/** Equal(s): search for texts equal to string s. */\r
- TextCollection::document_result Equal(uchar const *s) {\r
+ TextCollection::document_result Equals(uchar const *s) {\r
return Text->Equal(s);\r
}\r
\r
/** GetText(d): returns the text corresponding to document with\r
* id d. */\r
uchar* GetText(DocID d) {\r
- uchar * s = Text->GetText(d);\r
- return (s[0] == 1 ? (uchar*)"" : s);\r
+ \r
+ uchar * s = Text->GetText(d);\r
+ return (s[0] == 1 ? (uchar*)"" : s);\r
}\r
\r
/** GetText(i, j): returns the texts corresponding to documents with\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
+ static XMLTree *Load(int fd,bool load_tc, int sample_factor); \r
\r
void insertTag(TagType tag, uint position);\r
\r
void print_stats();\r
\r
+ \r
+ /** Parenthesis functions */\r
treeNode Closing(treeNode x);\r
+\r
bool IsOpen(treeNode x);\r
\r
+\r
+ /** Print procedure */\r
+ void Print(int fd,treeNode x);\r
+\r
};\r
#endif\r
\r
projects / SXSI / XMLTree.git / commitdiff