10 // functions to convert tag positions to the corresponding tree node and viceversa.
\r
11 // These are implemented in order to be able to change the tree and Tags representations,
\r
12 // without affecting the code so much.
\r
13 // Current implementation corresponds to balanced-parentheses representation for
\r
14 // the tree, and storing 2 tags per tree node (opening and closing tags).
\r
17 static int bits8 (int t ) {
\r
29 static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){
\r
31 if (tag == PCDATA_TAG_ID){
\r
33 return bp_inspect(Par,x)==OP ? x : NULLT;
\r
34 } else return bp_next_sibling(Par,x);
\r
41 inline uint get_field_no_power(uint *A, uint len, uint index) {
\r
43 register uint i=index*len/W, j=index*len-W*i;
\r
44 return (j+len <= W) ? (A[i] << (W-j-len)) >> (W-len) : (A[i] >> j) | (A[i+1] << (WW-j-len)) >> (W-len);
\r
48 static uint fast_get_field(uint* A,int len, int idx)
\r
53 return (uint) (((uchar*)A)[idx]);
\r
55 f2 = ((unsigned short*)A)[idx];
\r
56 f1 = ((unsigned short*)A)[idx+1];
\r
57 return (f1 << 16) + f2;
\r
59 return get_field_no_power (A,len,idx);
\r
67 XMLTree::XMLTree( pb * const par, uint npar, vector<string> * const TN, TagIdMap * const tim,
\r
68 uint *empty_texts_bmp, TagType *tags,
\r
69 TextCollectionBuilder * const TCB, bool dis_tc,
\r
70 TextCollectionBuilder::index_type_t _index_type )
\r
74 // creates the data structure for the tree topology
\r
76 Par = bp_construct(npar, (pb*) par, OPT_DEGREE|0);
\r
77 STOPTIMER(Building);
\r
78 PRINTTIME("Building parenthesis struct", Building);
\r
82 // creates structure for tags
\r
84 TagName = (vector<string>*)TN;
\r
85 tIdMap = (TagIdMap *) tim;
\r
87 uint max_tag = TN->size() - 1;
\r
89 static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray();
\r
90 alphabet_mapper *am = new alphabet_mapper_none();
\r
91 Tags = new static_sequence_bs((uint*)tags,npar,am,bmb);
\r
93 //cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl;
\r
95 //Ensures that for small tag numbers, we are on an 8bit boundary.
\r
96 //Makes tag access way faster with negligeable waste of space.
\r
97 tags_blen = bits8(max_tag);
\r
98 std::cerr << "Tags blen is " << tags_blen << "\n";
\r
99 tags_len = (uint)npar;
\r
100 tags_fix = new uint[uint_len(tags_blen,tags_len)];
\r
101 for(uint i=0;i<(uint)npar;i++)
\r
102 set_field(tags_fix,tags_blen,i,tags[i]);
\r
107 STOPTIMER(Building);
\r
108 PRINTTIME("Building Tag Structure", Building);
\r
110 EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32);
\r
111 free(empty_texts_bmp);
\r
112 empty_texts_bmp = NULL;
\r
115 disable_tc = dis_tc;
\r
116 text_index_type = _index_type;
\r
120 Text = TCB->InitTextCollection();
\r
122 STOPTIMER(Building);
\r
123 PRINTTIME("Building TextCollection", Building);
\r
129 std::cerr << "Number of distinct tags " << TagName->size() << "\n";
\r
130 //std::cerr.flush();
\r
134 // ~XMLTree: frees memory of XML tree.
\r
135 XMLTree::~XMLTree()
\r
160 void XMLTree::print_stats()
\r
162 uint total_space = Tags->size()+sizeof(static_sequence*);
\r
163 total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len));
\r
164 cout << "Space usage for XMLTree:" << endl
\r
165 << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl
\r
166 << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl
\r
167 << " ... add Diego structures ... " << endl
\r
168 << " *total* " << total_space << endl;
\r
171 // Save: saves XML tree data structure to file.
\r
172 void XMLTree::Save(int fd, char * name)
\r
176 off_t pos = lseek(fd, 0, SEEK_CUR);
\r
178 fp = fdopen(fd2, "w");
\r
179 fseek(fp, pos, SEEK_SET);
\r
180 // first stores the tree topology
\r
183 // stores the table with tag names
\r
184 int ntags = TagName->size();
\r
186 ufwrite(&ntags, sizeof(int), 1, fp);
\r
187 for (i = 0; i<ntags;i++)
\r
188 fprintf(fp, "%s\n",TagName->at(i).c_str());
\r
193 ufwrite(&tags_blen,sizeof(uint),1,fp);
\r
194 ufwrite(&tags_len,sizeof(uint),1,fp);
\r
195 ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp);
\r
198 ufwrite(&disable_tc, sizeof(bool),1,fp);
\r
201 EBVector->save(fp);
\r
202 std::cerr << "TC Index position: " << ftell(fp) << std::endl;
\r
203 // stores the texts
\r
205 std::cerr << "Writing " << sizeof(TextCollectionBuilder::index_type_t) << " bytes\n" << std::endl;
\r
206 ufwrite(&text_index_type, sizeof(TextCollectionBuilder::index_type_t), 1, fp);
\r
210 switch (text_index_type){
\r
211 case TextCollectionBuilder::index_type_default:
\r
212 file.append("_default");
\r
214 case TextCollectionBuilder::index_type_swcsa:
\r
215 file.append("_swcsa");
\r
217 case TextCollectionBuilder::index_type_rlcsa:
\r
218 file.append("_rlcsa");
\r
222 Text->Save(fp, file.c_str());
\r
230 // Load: loads XML tree data structure from file. Returns
\r
231 // a pointer to the loaded data structure
\r
232 XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name)
\r
240 buffer[1023] = '\0';
\r
242 fp = fdopen(fd, "r");
\r
244 XML_Tree = new XMLTree();
\r
246 // Load the tree structure
\r
247 XML_Tree->Par = loadTree(fp);
\r
248 STOPTIMER(Loading);
\r
249 PRINTTIME("Loading parenthesis struct", Loading);
\r
252 XML_Tree->TagName = new std::vector<std::string>();
\r
253 XML_Tree->tIdMap = new std::unordered_map<std::string,int>();
\r
257 // Load the tag names
\r
258 ufread(&ntags, sizeof(int), 1, fp);
\r
260 for (i=0; i<ntags;i++) {
\r
261 if (fgets(buffer,1022,fp) != buffer)
\r
262 throw "Cannot read tag list";
\r
264 // remove the trailing \n
\r
265 s.erase(s.size()-1);
\r
266 XML_Tree->TagName->push_back(s);
\r
267 XML_Tree->tIdMap->insert(std::make_pair(s,i));
\r
270 STOPTIMER(Loading);
\r
271 PRINTTIME("Loading tag names struct", Loading);
\r
274 // loads the tag structure
\r
275 XML_Tree->Tags = static_sequence::load(fp);
\r
276 ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);
\r
277 std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n";
\r
278 ufread(&XML_Tree->tags_len,sizeof(uint),1,fp);
\r
279 XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)];
\r
280 ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp);
\r
282 // TODO ask francisco about this
\r
283 /// FIXME:UGLY tests!
\r
284 //uint * seq = new uint[XML_Tree->tags_len];
\r
285 //for(uint i=0;i<XML_Tree->tags_len;i++)
\r
286 // seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i);
\r
287 //cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl;
\r
288 //XML_Tree->Tags->test(seq,XML_Tree->tags_len);
\r
292 STOPTIMER(Loading);
\r
293 std::cerr << (uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/(1024*1024) << " MB for tag sequence" << std::endl;
\r
294 PRINTTIME("Loading tag struct", Loading);
\r
299 ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);
\r
301 XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
\r
303 STOPTIMER(Loading);
\r
304 PRINTTIME("Loading text bitvector struct", Loading);
\r
306 std::cerr << "TC Load Index position: " << ftell(fp) << std::endl;
\r
309 if (!XML_Tree->disable_tc){
\r
310 ufread(&(XML_Tree->text_index_type),
\r
311 sizeof(TextCollectionBuilder::index_type_t), 1, fp);
\r
313 switch (XML_Tree->text_index_type){
\r
314 case TextCollectionBuilder::index_type_default:
\r
315 file.append("_default");
\r
317 case TextCollectionBuilder::index_type_swcsa:
\r
318 file.append("_swcsa");
\r
320 case TextCollectionBuilder::index_type_rlcsa:
\r
321 file.append("_rlcsa");
\r
326 XML_Tree->Text = TextCollection::Load(fp, file.c_str(), TextCollection::index_mode_default, sample_factor);
\r
329 else XML_Tree->Text = NULL;
\r
330 STOPTIMER(Loading);
\r
331 PRINTTIME("Loading TextCollection", Loading);
\r
335 XML_Tree->EBVector = NULL;
\r
336 XML_Tree->Text = NULL;
\r
337 XML_Tree->disable_tc = true;
\r
347 int XMLTree::SubtreeElements(treeNode x)
\r
350 int size = bp_subtree_size(Par, x);
\r
352 x = bp_first_child(Par,x);
\r
356 int s = x + 2*size - 1;
\r
357 int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1);
\r
358 size = size - ntext;
\r
359 treeNode fin = bp_find_close(Par,x);
\r
360 treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x));
\r
361 while (y != NULLT && y < fin){
\r
362 size -= SubtreeSize(y);
\r
363 y = Tags->select_next(ATTRIBUTE_TAG_ID, node2tagpos(y));
\r
368 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation
\r
369 // this is just a bit inspection.
\r
370 bool XMLTree::IsLeaf(treeNode x)
\r
372 NULLT_IF(x==NULLT);
\r
373 return bp_isleaf(Par, x);
\r
376 // IsAncestor(x,y): returns whether node x is ancestor of node y.
\r
377 bool XMLTree::IsAncestor(treeNode x, treeNode y)
\r
379 return bp_is_ancestor(Par, x, y);
\r
382 // IsChild(x,y): returns whether node x is parent of node y.
\r
383 bool XMLTree::IsChild(treeNode x, treeNode y)
\r
385 if (!bp_is_ancestor(Par, x, y)) return false;
\r
386 return bp_depth(Par, x) == (bp_depth(Par, y) + 1);
\r
390 // NumChildren(x): number of children of node x. Constant time with the data structure
\r
392 int XMLTree::NumChildren(treeNode x)
\r
394 return bp_degree(Par, x);
\r
397 // ChildNumber(x): returns i if node x is the i-th children of its parent.
\r
398 int XMLTree::ChildNumber(treeNode x)
\r
400 return bp_child_rank(Par, x);
\r
403 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.
\r
404 int XMLTree::Depth(treeNode x)
\r
406 return bp_depth(Par, x);
\r
409 // Preorder(x): returns the preorder number of node x, just counting the tree
\r
410 // nodes (i.e., tags, it disregards the texts in the tree).
\r
411 int XMLTree::Preorder(treeNode x)
\r
413 return bp_preorder_rank(Par, x);
\r
416 // Postorder(x): returns the postorder number of node x, just counting the tree
\r
417 // nodes (i.e., tags, it disregards the texts in the tree).
\r
418 int XMLTree::Postorder(treeNode x)
\r
420 return bp_postorder_rank(Par, x);
\r
423 // DocIds(x): returns the range of text identifiers that descend from node x.
\r
424 // returns {NULLT, NULLT} when there are no texts descending from x.
\r
425 range XMLTree::DocIds(treeNode x)
\r
433 int min = EBVector->rank1(x-1);
\r
434 int max = EBVector->rank1(x+2*bp_subtree_size(Par, x)-2);
\r
435 if (min==max) { // range is empty, no texts within the subtree of x
\r
439 else { // the range is non-empty, there are texts within the subtree of x
\r
447 // Child(x,i): returns the i-th child of node x, assuming it exists.
\r
448 treeNode XMLTree::Child(treeNode x, int i)
\r
450 if (i <= OPTD) return bp_naive_child(Par, x, i);
\r
451 else return bp_child(Par, x, i);
\r
455 treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags)
\r
458 NULLT_IF(x==NULLT || bp_isleaf(Par,x));
\r
460 treeNode child = bp_first_child(Par, x);
\r
462 while (child != NULLT) {
\r
464 if (tags->find(t) != tags->end()) return child;
\r
465 child = fast_sibling(Par, child,t);
\r
471 treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)
\r
474 NULLT_IF(x==NULLT);
\r
477 treeNode sibling = bp_next_sibling(Par, x);
\r
478 while (sibling != NULLT) {
\r
480 if (tags->find(t) != tags->end()) return sibling;
\r
481 sibling = fast_sibling(Par, sibling,t);
\r
487 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an
\r
488 // ancestor of x. Returns NULLT if there is none.
\r
489 treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)
\r
492 treeNode node_s, root;
\r
493 r = (int)Tags->rank(tag, node2tagpos(x)-1);
\r
494 if (r==0) return NULLT; // there is no such node.
\r
495 s = (int)Tags->select(tag, r);
\r
496 root = bp_root_node(Par);
\r
497 node_s = tagpos2node(s);
\r
498 while (bp_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x
\r
500 if (r==0) return NULLT; // there is no such node
\r
501 s = (int)Tags->select(tag, r); // we should use select_prev instead when provided
\r
502 node_s = tagpos2node(s);
\r
504 return NULLT; // there is no such node
\r
508 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in
\r
509 // the subtree of x. Returns NULLT if there is none.
\r
510 treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)
\r
512 NULLT_IF (x ==NULLT || x == Root());
\r
513 return tagpos2node(Tags->select_next(tag, bp_find_close(Par, x)));
\r
518 /* Here we inline TaggedFoll to find the min globally, and only at the end
\r
519 we check if the min is below the context node */
\r
520 treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor)
\r
523 NULLT_IF(x==NULLT || x==Root());
\r
525 treeNode close = bp_find_close(Par,x);
\r
526 treeNode ns = close+1;
\r
527 if ( (bp_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))
\r
531 treeNode min = NULLT;
\r
535 TagIdSet::const_iterator tagit;
\r
536 for (tagit = tags->begin(); tagit != tags->end(); ++tagit) {
\r
538 aux = tagpos2node(Tags->select_next(*tagit, close));
\r
539 if (aux == NULLT) continue;
\r
540 if ((min == NULLT) || (aux < min)) min = aux;
\r
543 // found the smallest node in preorder which is after x.
\r
544 // if ctx is the root node, just return what we found.
\r
546 if (ancestor == Root() || min == NULLT || min < bp_find_close(Par, ancestor)) return min;
\r
550 // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return
\r
551 // NULLT is there is none.
\r
552 treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)
\r
554 if (x == NULLT || x == Root())
\r
557 treeNode s = bp_parent(Par, x), r = Root();
\r
559 if (Tag(s) == tag) return s;
\r
560 s = bp_parent(Par, s);
\r
567 // MyText(x): returns the document identifier of the text below node x,
\r
568 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc
\r
569 // ids start from 0.
\r
570 DocID XMLTree::MyText(treeNode x)
\r
572 TagType tag = Tag(x);
\r
573 // seems faster than testing EBVector->access(x);
\r
575 if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID)
\r
576 return (DocID) (EBVector->rank1(x)-1);
\r
578 return (DocID) NULLT;
\r
581 // MyText(x): returns the document identifier of the text below node x,
\r
582 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc
\r
583 // ids start from 0.
\r
584 DocID XMLTree::MyTextUnsafe(treeNode x)
\r
586 return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0
\r
589 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of
\r
590 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.
\r
591 int XMLTree::TextXMLId(DocID d)
\r
593 NULLT_IF(d == NULLT);
\r
594 int s = EBVector->select1(d+1);
\r
595 return bp_rank_open(Par, s) + d + 1; // +1 because root has preorder 1
\r
599 // NodeXMLId(x): returns the preorder of node x in the tree consisting
\r
600 // of all tree nodes and all text nodes. Assumes that the tree root has
\r
602 int XMLTree::NodeXMLId(treeNode x)
\r
604 NULLT_IF(x == NULLT);
\r
605 if (x == Root()) return 1; // root node has preorder 1
\r
606 return bp_rank_open(Par, x) + EBVector->rank1(x-1);
\r
609 // ParentNode(d): returns the parent node of document identifier d.
\r
610 treeNode XMLTree::ParentNode(DocID d)
\r
612 NULLT_IF (d == NULLT);
\r
613 return (treeNode) EBVector->select1(d+1);
\r
616 // GetTagId: returns the tag identifier corresponding to a given tag name.
\r
617 // Returns NULLT in case that the tag name does not exists.
\r
618 TagType XMLTree::GetTagId(unsigned char *tagname)
\r
621 string s = (char *) tagname;
\r
622 TagIdMapIT it = tIdMap->find(s);
\r
623 return (TagType) ((it != tIdMap->end()) ? it->second : -1);
\r
628 // GetTagName(tagid): returns the tag name of a given tag identifier.
\r
629 // Returns NULL in case that the tag identifier is not valid.
\r
630 unsigned char *XMLTree::GetTagName(TagType tagid)
\r
633 if ( tagid < 0 || tagid >= TagName->size())
\r
634 return (unsigned char *) "<INVALID TAG>";
\r
635 strcpy((char *)s, (*TagName)[tagid].c_str());
\r
637 return (s == NULL ? (unsigned char*) "<INVALID TAG>" : s);
\r
641 const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)
\r
645 if ( tagid < 0 || tagid >= TagName->size())
\r
646 return (unsigned char *) "<INVALID TAG>";
\r
648 return (const unsigned char *) (*TagName)[tagid].c_str();
\r
654 TagType XMLTree::RegisterTag(unsigned char *tagname)
\r
656 TagType id = XMLTree::GetTagId(tagname);
\r
658 string s = (char *) tagname;
\r
659 REGISTER_TAG(TagName,tIdMap,s);
\r
666 treeNode XMLTree::Closing(treeNode x) {
\r
667 return bp_find_close(Par,x);
\r
669 bool XMLTree::IsOpen(treeNode x) { return bp_inspect(Par,x); }
\r
671 //WARNING this uses directly the underlying implementation for plain text
\r
674 void XMLTree::Print(int fd,treeNode x, bool no_text){
\r
677 buffer = new string(BUFFER_ALLOC, 0);
\r
679 print_stack = new std::vector<string *>();
\r
680 print_stack->reserve(256);
\r
683 treeNode fin = bp_find_close(Par,x);
\r
685 TagType tag = Tag(n);
\r
687 range r = DocIds(x);
\r
688 treeNode first_idx;
\r
689 treeNode first_text = (tag == PCDATA_TAG_ID ? x : ParentNode(r.min-1));
\r
690 treeNode first_att = NULLT;
\r
692 if (first_att == NULLT)
\r
693 first_idx = first_text;
\r
694 else if (first_text == NULLT)
\r
695 first_idx = first_att;
\r
697 first_idx = min(first_att,first_text);
\r
699 uchar * current_text=NULL;
\r
701 if (first_idx != NULLT)
\r
702 current_text = GetText(MyTextUnsafe(first_idx));
\r
707 if (bp_inspect(Par,n)){
\r
708 if (tag == PCDATA_TAG_ID) {
\r
711 _dputs("<$/>", fd);
\r
713 read = _dprintf((const char*) current_text, fd);
\r
714 current_text += (read + 1);
\r
716 n+=2; // skip closing $
\r
722 _dput_str((*TagName)[tag], fd);
\r
724 if (bp_inspect(Par,n)) {
\r
725 print_stack->push_back(&((*TagName)[tag]));
\r
727 if (tag == ATTRIBUTE_TAG_ID){
\r
729 if (no_text) _dputs("><@@>",fd);
\r
731 while (bp_inspect(Par,n)){
\r
734 _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);
\r
736 _dputs("<$@/></", fd);
\r
737 _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);
\r
742 _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd);
\r
745 read = _dprintf((const char*) current_text, fd);
\r
746 current_text += (read + 1);
\r
751 if (no_text) _dputs("</@@>", fd);
\r
752 else _dputc('>', fd);
\r
759 } else {// <foo /> tag
\r
767 _dput_str(*(print_stack->back()), fd);
\r
769 print_stack->pop_back();
\r
771 } while (!(bp_inspect(Par,n) || print_stack->empty()));
\r