6 // functions to convert tag positions to the corresponding tree node and viceversa.
\r
7 // These are implemented in order to be able to change the tree and Tags representations,
\r
8 // without affecting the code so much.
\r
9 // Current implementation corresponds to balanced-parentheses representation for
\r
10 // the tree, and storing 2 tags per tree node (opening and closing tags).
\r
12 // tag position -> tree node
\r
13 inline treeNode tagpos2node(int t)
\r
15 return (treeNode) t;
\r
18 // tree node -> tag position
\r
19 inline int node2tagpos(treeNode x)
\r
24 // returns NULLT if the test is true
\r
25 #define NULLT_IF(x) do { if (x) return NULLT; } while (0)
\r
28 XMLTree::XMLTree( pb * const par, uint npar, vector<string> * const TN, TagIdMap * const tim, uint *empty_texts_bmp, TagType *tags,
\r
29 TextCollection * const TC, vector<string> * const CT, bool dis_tc)
\r
32 // creates the data structure for the tree topology
\r
33 Par = (bp *)umalloc(sizeof(bp));
\r
34 bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0);
\r
36 // creates structure for tags
\r
38 TagName = (vector<string>*)TN;
\r
39 tIdMap = (TagIdMap *) tim;
\r
41 uint max_tag = TN->size() - 1;
\r
43 static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray();
\r
44 alphabet_mapper *am = new alphabet_mapper_none();
\r
45 Tags = new static_sequence_bs((uint*)tags,npar,am,bmb);
\r
47 cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl;
\r
49 tags_blen = bits(max_tag);
\r
50 tags_len = (uint)npar;
\r
51 tags_fix = new uint[uint_len(tags_blen,tags_len)];
\r
52 for(uint i=0;i<(uint)npar;i++)
\r
53 set_field(tags_fix,tags_blen,i,tags[i]);
\r
59 Text = (TextCollection*) TC;
\r
61 CachedText = (vector<string>*) CT;
\r
62 EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32);
\r
63 free(empty_texts_bmp);
\r
64 empty_texts_bmp = NULL;
\r
67 disable_tc = dis_tc;
\r
71 // ~XMLTree: frees memory of XML tree.
\r
72 XMLTree::~XMLTree()
\r
77 free(Par); // frees the memory of struct Par
\r
98 void XMLTree::print_stats()
\r
100 uint total_space = Tags->size()+sizeof(static_sequence*);
\r
101 total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len));
\r
102 cout << "Space usage for XMLTree:" << endl
\r
103 << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl
\r
104 << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl
\r
105 << " ... add Diego structures ... " << endl
\r
106 << " *total* " << total_space << endl;
\r
109 // Save: saves XML tree data structure to file.
\r
110 void XMLTree::Save(int fd)
\r
113 char filenameaux[1024];
\r
116 fp = fdopen(fd, "wa");
\r
117 // first stores the tree topology
\r
120 // stores the table with tag names
\r
121 int ntags = TagName->size();
\r
123 ufwrite(&ntags, sizeof(int), 1, fp);
\r
124 for (i = 0; i<ntags;i++)
\r
125 fprintf(fp, "%s\n",TagName->at(i).c_str());
\r
130 ufwrite(&tags_blen,sizeof(uint),1,fp);
\r
131 ufwrite(&tags_len,sizeof(uint),1,fp);
\r
132 ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp);
\r
135 ufwrite(&disable_tc, sizeof(bool),1,fp);
\r
138 EBVector->save(fp);
\r
140 // stores the texts
\r
142 int st = CachedText->size();
\r
144 ufwrite(&st, sizeof(int),1,fp);
\r
145 for (int i = 0; i< CachedText->size(); i++){
\r
146 st = CachedText->at(i).size();
\r
148 ufwrite(&st, sizeof(int),1,fp);
\r
150 ufwrite(CachedText->at(i).c_str(),sizeof(char),1+CachedText->at(i).size(),fp);
\r
161 // Load: loads XML tree data structure from file. Returns
\r
162 // a pointer to the loaded data structure
\r
163 XMLTree *XMLTree::Load(int fd)
\r
172 fp = fdopen(fd, "r");
\r
174 XML_Tree = new XMLTree();
\r
176 // Load the tree structure
\r
177 XML_Tree->Par = (bp *)umalloc(sizeof(bp));
\r
179 loadTree(XML_Tree->Par, fp);
\r
181 XML_Tree->TagName = new vector<string>();
\r
182 XML_Tree->tIdMap = new std::unordered_map<string,int>();
\r
187 // Load the tag names
\r
188 ufread(&ntags, sizeof(int), 1, fp);
\r
190 for (i=0; i<ntags;i++) {
\r
191 char * r = fgets(buffer,1023,fp);
\r
193 throw "Cannot read tag list";
\r
194 s = (const char*) buffer;
\r
195 // remove the trailing \n
\r
196 s.erase(s.size()-1);
\r
197 XML_Tree->TagName->push_back(s);
\r
198 XML_Tree->tIdMap->insert(std::make_pair(s,i));
\r
203 // loads the tag structure
\r
204 XML_Tree->Tags = static_sequence::load(fp);
\r
205 ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);
\r
206 ufread(&XML_Tree->tags_len,sizeof(uint),1,fp);
\r
207 XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)];
\r
208 ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp);
\r
210 // TODO ask francisco about this
\r
211 /// FIXME:UGLY tests!
\r
212 uint * seq = new uint[XML_Tree->tags_len];
\r
213 for(uint i=0;i<XML_Tree->tags_len;i++)
\r
214 seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i);
\r
215 //cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl;
\r
216 XML_Tree->Tags->test(seq,XML_Tree->tags_len);
\r
223 ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);
\r
225 XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
\r
228 int sample_rate_text = 64;
\r
230 if (!XML_Tree->disable_tc){
\r
231 XML_Tree->CachedText = new vector<string>;
\r
234 ufread(&sst, sizeof(int),1,fp);
\r
236 for (int i=0;i<sst;i++){
\r
237 ufread(&st, sizeof(int),1,fp);
\r
238 char* str = (char*) malloc(sizeof(char)*st+1);
\r
239 ufread(str,sizeof(char),st+1,fp);
\r
240 string cppstr = str;
\r
241 XML_Tree->CachedText->push_back(cppstr);
\r
245 XML_Tree->Text = TextCollection::Load(fp,sample_rate_text);
\r
247 else XML_Tree->Text = NULL;
\r
253 // root(): returns the tree root.
\r
254 inline treeNode XMLTree::Root()
\r
256 return 0; //root_node(Par);
\r
259 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.
\r
260 int XMLTree::SubtreeSize(treeNode x)
\r
262 return subtree_size(Par, x);
\r
265 // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.
\r
266 int XMLTree::SubtreeTags(treeNode x, TagType tag)
\r
269 x = first_child(Par,x);
\r
272 int s = x + 2*subtree_size(Par, x) - 1;
\r
274 return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1);
\r
277 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation
\r
278 // this is just a bit inspection.
\r
279 bool XMLTree::IsLeaf(treeNode x)
\r
281 return isleaf(Par, x);
\r
284 // IsAncestor(x,y): returns whether node x is ancestor of node y.
\r
285 bool XMLTree::IsAncestor(treeNode x, treeNode y)
\r
287 return is_ancestor(Par, x, y);
\r
290 // IsChild(x,y): returns whether node x is parent of node y.
\r
291 bool XMLTree::IsChild(treeNode x, treeNode y)
\r
293 if (!is_ancestor(Par, x, y)) return false;
\r
294 return depth(Par, x) == (depth(Par, y) + 1);
\r
297 // IsFirstChild(x): returns whether node x is the first child of its parent.
\r
298 bool XMLTree::IsFirstChild(treeNode x)
\r
300 return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));
\r
304 // NumChildren(x): number of children of node x. Constant time with the data structure
\r
306 int XMLTree::NumChildren(treeNode x)
\r
308 return degree(Par, x);
\r
311 // ChildNumber(x): returns i if node x is the i-th children of its parent.
\r
312 int XMLTree::ChildNumber(treeNode x)
\r
314 return child_rank(Par, x);
\r
317 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.
\r
318 int XMLTree::Depth(treeNode x)
\r
320 return depth(Par, x);
\r
323 // Preorder(x): returns the preorder number of node x, just counting the tree
\r
324 // nodes (i.e., tags, it disregards the texts in the tree).
\r
325 int XMLTree::Preorder(treeNode x)
\r
327 return preorder_rank(Par, x);
\r
330 // Postorder(x): returns the postorder number of node x, just counting the tree
\r
331 // nodes (i.e., tags, it disregards the texts in the tree).
\r
332 int XMLTree::Postorder(treeNode x)
\r
334 return postorder_rank(Par, x);
\r
337 // Tag(x): returns the tag identifier of node x.
\r
338 TagType XMLTree::Tag(treeNode x)
\r
340 return get_field(tags_fix,tags_blen,node2tagpos(x));
\r
343 // DocIds(x): returns the range of text identifiers that descend from node x.
\r
344 // returns {NULLT, NULLT} when there are no texts descending from x.
\r
345 range XMLTree::DocIds(treeNode x)
\r
355 int min = EBVector->rank1(x-1);
\r
356 int max = EBVector->rank1(x+2*subtree_size(Par, x)-2);
\r
357 if (min==max) { // range is empty, no texts within the subtree of x
\r
361 else { // the range is non-empty, there are texts within the subtree of x
\r
369 // Parent(x): returns the parent node of node x.
\r
370 treeNode XMLTree::Parent(treeNode x)
\r
375 return parent(Par, x);
\r
378 // Child(x,i): returns the i-th child of node x, assuming it exists.
\r
379 treeNode XMLTree::Child(treeNode x, int i)
\r
381 if (i <= OPTD) return naive_child(Par, x, i);
\r
382 else return child(Par, x, i);
\r
385 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.
\r
386 treeNode XMLTree::FirstChild(treeNode x)
\r
388 NULLT_IF(x==NULLT);
\r
389 return first_child(Par, x);
\r
392 treeNode XMLTree::FirstElement(treeNode x)
\r
394 NULLT_IF(x==NULLT);
\r
395 treeNode fc = first_child(Par, x);
\r
397 return ((fc == NULLT || Tag(fc) != PCDATA_TAG_ID) ? fc : next_sibling(Par,fc));
\r
401 treeNode XMLTree::NextElement(treeNode x)
\r
403 NULLT_IF(x==NULLT);
\r
404 treeNode ns = next_sibling(Par, x);
\r
405 return ((ns == NULLT || Tag(ns) != PCDATA_TAG_ID) ? ns : next_sibling(Par,ns));
\r
408 // LastChild(x): returns the last child of node x.
\r
409 treeNode XMLTree::LastChild(treeNode x)
\r
411 NULLT_IF(x==NULLT || x == Root() || isleaf(Par,x));
\r
412 return find_open(Par, find_close(Par, x)-1);
\r
416 // NextSibling(x): returns the next sibling of node x, assuming it exists.
\r
417 treeNode XMLTree::NextSibling(treeNode x)
\r
419 NULLT_IF(x==NULLT || x == Root() );
\r
420 return next_sibling(Par, x);
\r
423 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.
\r
424 treeNode XMLTree::PrevSibling(treeNode x)
\r
426 NULLT_IF(x==NULLT || x == Root());
\r
427 return prev_sibling(Par, x);
\r
430 // TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none.
\r
431 // Because of the balanced-parentheses representation of the tree, this operation is not supported
\r
432 // efficiently, just iterating among the children of node x until finding the desired child.
\r
433 treeNode XMLTree::TaggedChild(treeNode x, TagType tag)
\r
436 NULLT_IF(x==NULLT || isleaf(Par,x));
\r
439 child = first_child(Par, x); // starts at first child of node x
\r
440 if (get_field(tags_fix,tags_blen,node2tagpos(child)) == tag)
\r
443 return TaggedFollSibling(child,tag);
\r
446 // TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.
\r
447 treeNode XMLTree::TaggedFollSibling(treeNode x, TagType tag)
\r
449 NULLT_IF(x==NULLT);
\r
450 treeNode sibling = next_sibling(Par, x);
\r
451 while (sibling != NULLT) {
\r
452 if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest
\r
454 sibling = next_sibling(Par, sibling); // OK, let's try with the next sibling
\r
456 return NULLT; // no such sibling was found
\r
459 treeNode XMLTree::SelectChild(treeNode x, std::unordered_set<int> *tags)
\r
462 NULLT_IF(x==NULLT || isleaf(Par,x));
\r
464 treeNode child = first_child(Par, x);
\r
465 TagType t = get_field(tags_fix, tags_blen, node2tagpos(child));
\r
466 std::unordered_set<int>::const_iterator tagit = tags->find(t);
\r
467 if (tagit != tags->end()) return child;
\r
468 return SelectFollSibling(child,tags);
\r
472 treeNode XMLTree::SelectFollSibling(treeNode x, std::unordered_set<int> *tags)
\r
475 NULLT_IF(x==NULLT);
\r
478 treeNode sibling = next_sibling(Par, x);
\r
479 std::unordered_set<int>::const_iterator tagit;
\r
480 while (sibling != NULLT) {
\r
481 t = get_field(tags_fix, tags_blen, node2tagpos(sibling));
\r
482 tagit = tags->find(t);
\r
483 if (tagit != tags->end()) return sibling;
\r
484 sibling = next_sibling(Par, sibling);
\r
490 // TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within
\r
491 // the subtree of x. Returns NULLT if there is none.
\r
492 treeNode XMLTree::TaggedDesc(treeNode x, TagType tag)
\r
494 NULLT_IF(x==NULLT || isleaf(Par,x));
\r
496 int s = (int) Tags->select_next(tag,node2tagpos(x));
\r
497 NULLT_IF (s == -1);
\r
499 treeNode y = tagpos2node(s); // transforms the tag position into a node position
\r
501 return (is_ancestor(Par,x,y) ? y : NULLT);
\r
505 treeNode XMLTree::SelectDesc(treeNode x, std::unordered_set<int> *tags)
\r
507 NULLT_IF (x ==NULLT || isleaf(Par,x));
\r
509 treeNode min = NULLT;
\r
510 treeNode fc = first_child(Par,x);
\r
512 std::unordered_set<int>::const_iterator tagit;
\r
513 for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
\r
514 aux = TaggedDesc(x, (TagType) *tagit);
\r
515 if (aux == fc) return fc;
\r
516 if (aux == NULLT) continue;
\r
517 if ((min == NULLT) || (aux < min)) min = aux;
\r
524 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an
\r
525 // ancestor of x. Returns NULLT if there is none.
\r
526 treeNode XMLTree::TaggedPrec(treeNode x, TagType tag)
\r
529 treeNode node_s, root;
\r
530 r = (int)Tags->rank(tag, node2tagpos(x)-1);
\r
531 if (r==0) return NULLT; // there is no such node.
\r
532 s = (int)Tags->select(tag, r);
\r
533 root = root_node(Par);
\r
534 node_s = tagpos2node(s);
\r
535 while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x
\r
537 if (r==0) return NULLT; // there is no such node
\r
538 s = (int)Tags->select(tag, r); // we should use select_prev instead when provided
\r
539 node_s = tagpos2node(s);
\r
541 return NULLT; // there is no such node
\r
545 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in
\r
546 // the subtree of x. Returns NULLT if there is none.
\r
547 treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
\r
549 NULLT_IF (x ==NULLT || x == Root());
\r
551 return tagpos2node(Tags->select_next(tag,find_close(Par, x)));
\r
555 // TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x
\r
556 // and not in the subtree of x. Returns NULLT if there is none.
\r
557 treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root)
\r
560 NULLT_IF (x == NULLT || x == Root());
\r
562 treeNode s = tagpos2node(Tags->select_next(tag, find_close(Par, x)));
\r
564 if (root == Root()) return s;
\r
565 NULLT_IF (s == NULLT || s >= find_close(Par, root));
\r
570 /* Here we inline TaggedFoll to find the min globally, and only at the end
\r
571 we check if the min is below the context node */
\r
572 treeNode XMLTree::SelectFollBelow(treeNode x, std::unordered_set<int> *tags, treeNode root)
\r
575 NULLT_IF(x==NULLT || x==Root());
\r
577 treeNode min = NULLT;
\r
578 treeNode ns = next_sibling(Par, x);
\r
580 std::unordered_set<int>::const_iterator tagit;
\r
581 for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
\r
583 aux = tagpos2node(Tags->select_next(*tagit, find_close(Par, x)));
\r
585 // The next sibling of x is guaranteed to be below ctx
\r
586 // and is the node with lowest preorder which is after ctx.
\r
587 // if we find it, we return early;
\r
589 if (aux == ns ) return ns;
\r
590 if (aux == NULLT) continue;
\r
591 if ((min == NULLT) || (aux < min)) min = aux;
\r
594 // found the smallest node in preorder which is after x.
\r
595 // if ctx is the root node, just return what we found.
\r
597 if (root == Root()) return min;
\r
598 // else check whether if is in below the ctx node
\r
600 NULLT_IF (min == NULLT || min >= find_close(Par, root));
\r
607 // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return
\r
608 // NULLT is there is none.
\r
609 treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)
\r
611 if (x == NULLT || x == Root())
\r
614 treeNode s = parent(Par, x), r = Root();
\r
616 if (get_field(tags_fix,tags_blen,node2tagpos(s)) /*Tags->access(node2tagpos(s))*/ == tag) return s;
\r
617 s = parent(Par, s);
\r
624 // MyText(x): returns the document identifier of the text below node x,
\r
625 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc
\r
626 // ids start from 0.
\r
627 DocID XMLTree::MyText(treeNode x)
\r
629 TagType tag = Tag(x);
\r
630 // seems faster than testing EBVector->access(x);
\r
632 if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID)
\r
633 return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0
\r
635 return (DocID) NULLT;
\r
639 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of
\r
640 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.
\r
641 int XMLTree::TextXMLId(DocID d)
\r
643 int s = EBVector->select1(d+1);
\r
644 return rank_open(Par, s) + d + 1; // +1 because root has preorder 1
\r
648 // NodeXMLId(x): returns the preorder of node x in the tree consisting
\r
649 // of all tree nodes and all text nodes. Assumes that the tree root has
\r
651 int XMLTree::NodeXMLId(treeNode x)
\r
653 if (x == Root()) return 1; // root node has preorder 1
\r
654 return rank_open(Par, x) + EBVector->rank1(x-1);
\r
657 // ParentNode(d): returns the parent node of document identifier d.
\r
658 treeNode XMLTree::ParentNode(DocID d)
\r
660 NULLT_IF (d == NULLT);
\r
661 return (treeNode) EBVector->select1(d+1);
\r
664 // GetTagId: returns the tag identifier corresponding to a given tag name.
\r
665 // Returns NULLT in case that the tag name does not exists.
\r
666 TagType XMLTree::GetTagId(unsigned char *tagname)
\r
669 string s = (char *) tagname;
\r
670 TagIdMapIT it = tIdMap->find(s);
\r
671 return (TagType) ((it != tIdMap->end()) ? it->second : -1);
\r
676 // GetTagName(tagid): returns the tag name of a given tag identifier.
\r
677 // Returns NULL in case that the tag identifier is not valid.
\r
678 unsigned char *XMLTree::GetTagName(TagType tagid)
\r
681 if ( tagid < 0 || tagid >= TagName->size())
\r
682 return (unsigned char *) "<INVALID TAG>";
\r
683 strcpy((char *)s, TagName->at(tagid).c_str());
\r
685 return (s == NULL ? (unsigned char*) "<INVALID TAG>" : s);
\r
689 const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)
\r
693 if ( tagid < 0 || tagid >= TagName->size())
\r
694 return (unsigned char *) "<INVALID TAG>";
\r
696 return (const unsigned char *) TagName->at(tagid).c_str();
\r
702 TagType XMLTree::RegisterTag(unsigned char *tagname)
\r
704 TagType id = XMLTree::GetTagId(tagname);
\r
706 string s = (char *) tagname;
\r
707 REGISTER_TAG(TagName,tIdMap,s);
\r