7 // functions to convert tag positions to the corresponding tree node and viceversa.
\r
8 // These are implemented in order to be able to change the tree and Tags representations,
\r
9 // without affecting the code so much.
\r
10 // Current implementation corresponds to balanced-parentheses representation for
\r
11 // the tree, and storing 2 tags per tree node (opening and closing tags).
\r
13 // tag position -> tree node
\r
14 static treeNode tagpos2node(int t)
\r
16 return (treeNode) t;
\r
19 static int bits8 (int t ) {
\r
29 // tree node -> tag position
\r
30 static int node2tagpos(treeNode x)
\r
35 static int fast_find_close(bp *b,int s)
\r
37 return fwd_excess(b,s,-1);
\r
40 static int fast_inspect(bp* Par,treeNode i)
\r
45 return (Par->B[j] >> (D-1-l)) & 1;
\r
48 static treeNode fast_first_child(bp *Par, treeNode x)
\r
51 return (fast_inspect(Par,x) == OP) ? x : NULLT;
\r
54 static treeNode fast_next_sibling(bp* Par,treeNode x)
\r
56 x = fwd_excess(Par,x,0);
\r
57 return (fast_inspect(Par,x) == OP) ? x : NULLT;
\r
61 static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){
\r
63 if (tag == PCDATA_TAG_ID){
\r
65 return fast_inspect(Par,x)==OP ? x : NULLT;
\r
66 } else return fast_next_sibling(Par,x);
\r
70 static bool fast_isleaf(bp* Par,treeNode x){
\r
71 return (fast_inspect(Par,x+1) == CP ? true : false);
\r
75 inline uint get_field_no_power(uint *A, uint len, uint index) {
\r
77 register uint i=index*len/W, j=index*len-W*i;
\r
78 return (j+len <= W) ? (A[i] << (W-j-len)) >> (W-len) : (A[i] >> j) | (A[i+1] << (WW-j-len)) >> (W-len);
\r
82 static uint fast_get_field(uint* A,int len, int idx)
\r
87 return (uint) (((uchar*)A)[idx]);
\r
89 f2 = ((unsigned short*)A)[idx];
\r
90 f1 = ((unsigned short*)A)[idx+1];
\r
91 return (f1 << 16) + f2;
\r
93 return get_field_no_power (A,len,idx);
\r
98 inline bool fast_is_ancestor(bp * Par,treeNode x,treeNode y){
\r
102 return (x==0) || (y <= fast_find_close(Par,x));
\r
106 XMLTree::XMLTree( pb * const par, uint npar, vector<string> * const TN, TagIdMap * const tim,
\r
107 uint *empty_texts_bmp, TagType *tags,
\r
108 TextCollection * const TC, bool dis_tc)
\r
110 // creates the data structure for the tree topology
\r
111 Par = (bp *)umalloc(sizeof(bp));
\r
113 bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0);
\r
114 STOPTIMER(Building);
\r
115 PRINTTIME("Building parenthesis struct", Building);
\r
119 // creates structure for tags
\r
121 TagName = (vector<string>*)TN;
\r
122 tIdMap = (TagIdMap *) tim;
\r
124 uint max_tag = TN->size() - 1;
\r
127 static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray();
\r
128 alphabet_mapper *am = new alphabet_mapper_none();
\r
129 Tags = new static_sequence_bs((uint*)tags,npar,am,bmb);
\r
131 //cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl;
\r
133 //Ensures that for small tag numbers, we are on an 8bit boundary.
\r
134 //Makes tag access way faster with negligeable waste of space.
\r
135 tags_blen = bits8(max_tag);
\r
136 std::cerr << "Tags blen is " << tags_blen << "\n";
\r
137 tags_len = (uint)npar;
\r
138 tags_fix = new uint[uint_len(tags_blen,tags_len)];
\r
139 for(uint i=0;i<(uint)npar;i++)
\r
140 set_field(tags_fix,tags_blen,i,tags[i]);
\r
145 STOPTIMER(Building);
\r
146 PRINTTIME("Building Tag Structure", Building);
\r
148 Text = (TextCollection*) TC;
\r
151 EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32);
\r
152 //EBVector = new static_bitsequence_sdarray(empty_texts_bmp,npar);
\r
153 free(empty_texts_bmp);
\r
154 empty_texts_bmp = NULL;
\r
157 disable_tc = dis_tc;
\r
160 std::cerr << "Number of distinct tags " << TagName->size() << "\n";
\r
161 //std::cerr.flush();
\r
165 // ~XMLTree: frees memory of XML tree.
\r
166 XMLTree::~XMLTree()
\r
171 free(Par); // frees the memory of struct Par
\r
187 if (stream != NULL){
\r
196 void XMLTree::print_stats()
\r
198 uint total_space = Tags->size()+sizeof(static_sequence*);
\r
199 total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len));
\r
200 cout << "Space usage for XMLTree:" << endl
\r
201 << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl
\r
202 << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl
\r
203 << " ... add Diego structures ... " << endl
\r
204 << " *total* " << total_space << endl;
\r
207 // Save: saves XML tree data structure to file.
\r
208 void XMLTree::Save(int fd)
\r
211 char filenameaux[1024];
\r
214 fp = fdopen(fd, "wa");
\r
215 // first stores the tree topology
\r
218 // stores the table with tag names
\r
219 int ntags = TagName->size();
\r
221 ufwrite(&ntags, sizeof(int), 1, fp);
\r
222 for (i = 0; i<ntags;i++)
\r
223 fprintf(fp, "%s\n",TagName->at(i).c_str());
\r
228 ufwrite(&tags_blen,sizeof(uint),1,fp);
\r
229 ufwrite(&tags_len,sizeof(uint),1,fp);
\r
230 ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp);
\r
233 ufwrite(&disable_tc, sizeof(bool),1,fp);
\r
236 EBVector->save(fp);
\r
238 // stores the texts
\r
247 // Load: loads XML tree data structure from file. Returns
\r
248 // a pointer to the loaded data structure
\r
249 XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor)
\r
258 fp = fdopen(fd, "r");
\r
260 XML_Tree = new XMLTree();
\r
262 // Load the tree structure
\r
263 XML_Tree->Par = (bp *)umalloc(sizeof(bp));
\r
265 loadTree(XML_Tree->Par, fp);
\r
266 STOPTIMER(Loading);
\r
267 PRINTTIME("Loading parenthesis struct", Loading);
\r
270 XML_Tree->TagName = new vector<string>();
\r
271 XML_Tree->tIdMap = new std::unordered_map<string,int>();
\r
276 // Load the tag names
\r
277 ufread(&ntags, sizeof(int), 1, fp);
\r
279 for (i=0; i<ntags;i++) {
\r
280 char * r = fgets(buffer,1023,fp);
\r
282 throw "Cannot read tag list";
\r
283 s = (const char*) buffer;
\r
284 // remove the trailing \n
\r
285 s.erase(s.size()-1);
\r
286 XML_Tree->TagName->push_back(s);
\r
287 XML_Tree->tIdMap->insert(std::make_pair(s,i));
\r
290 STOPTIMER(Loading);
\r
291 PRINTTIME("Loading tag names struct", Loading);
\r
294 // loads the tag structure
\r
295 XML_Tree->Tags = static_sequence::load(fp);
\r
296 ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);
\r
297 std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n";
\r
298 ufread(&XML_Tree->tags_len,sizeof(uint),1,fp);
\r
299 XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)];
\r
300 ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp);
\r
302 // TODO ask francisco about this
\r
303 /// FIXME:UGLY tests!
\r
304 //uint * seq = new uint[XML_Tree->tags_len];
\r
305 //for(uint i=0;i<XML_Tree->tags_len;i++)
\r
306 // seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i);
\r
307 //cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl;
\r
308 //XML_Tree->Tags->test(seq,XML_Tree->tags_len);
\r
312 STOPTIMER(Loading);
\r
313 std::cerr << (uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/(1024*1024) << " MB for tag sequence" << std::endl;
\r
314 PRINTTIME("Loading tag struct", Loading);
\r
319 ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);
\r
321 XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
\r
322 //XML_Tree->EBVector = static_bitsequence_sdarray::load(fp);
\r
324 STOPTIMER(Loading);
\r
325 PRINTTIME("Loading text bitvector struct", Loading);
\r
330 if (!XML_Tree->disable_tc){
\r
331 XML_Tree->Text = TextCollection::Load(fp,sample_factor);
\r
333 else XML_Tree->Text = NULL;
\r
334 STOPTIMER(Loading);
\r
335 PRINTTIME("Loading TextCollection", Loading);
\r
339 XML_Tree->EBVector = NULL;
\r
340 XML_Tree->Text = NULL;
\r
341 XML_Tree->disable_tc = true;
\r
344 XML_Tree->stream = NULL;
\r
345 XML_Tree->stream_fd = 0;
\r
352 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.
\r
353 int XMLTree::SubtreeSize(treeNode x)
\r
355 return subtree_size(Par, x);
\r
358 // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.
\r
359 int XMLTree::SubtreeTags(treeNode x, TagType tag)
\r
362 x = fast_first_child(Par,x);
\r
365 int s = x + 2*subtree_size(Par, x) - 1;
\r
367 return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1);
\r
369 int XMLTree::SubtreeElements(treeNode x)
\r
372 int size = subtree_size(Par,x);
\r
374 x = fast_first_child(Par,x);
\r
378 int s = x + 2*size - 1;
\r
379 int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1);
\r
380 size = size - ntext;
\r
381 treeNode fin = fast_find_close(Par,x);
\r
382 treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x));
\r
383 while (y != NULLT && y < fin){
\r
384 size -= SubtreeSize(y);
\r
385 y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y));
\r
390 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation
\r
391 // this is just a bit inspection.
\r
392 bool XMLTree::IsLeaf(treeNode x)
\r
394 NULLT_IF(x==NULLT);
\r
395 return fast_isleaf(Par, x);
\r
398 // IsAncestor(x,y): returns whether node x is ancestor of node y.
\r
399 bool XMLTree::IsAncestor(treeNode x, treeNode y)
\r
401 return fast_is_ancestor(Par, x, y);
\r
404 // IsChild(x,y): returns whether node x is parent of node y.
\r
405 bool XMLTree::IsChild(treeNode x, treeNode y)
\r
407 if (!fast_is_ancestor(Par, x, y)) return false;
\r
408 return depth(Par, x) == (depth(Par, y) + 1);
\r
411 // IsFirstChild(x): returns whether node x is the first child of its parent.
\r
412 bool XMLTree::IsFirstChild(treeNode x)
\r
414 return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1));
\r
418 // NumChildren(x): number of children of node x. Constant time with the data structure
\r
420 int XMLTree::NumChildren(treeNode x)
\r
422 return degree(Par, x);
\r
425 // ChildNumber(x): returns i if node x is the i-th children of its parent.
\r
426 int XMLTree::ChildNumber(treeNode x)
\r
428 return child_rank(Par, x);
\r
431 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.
\r
432 int XMLTree::Depth(treeNode x)
\r
434 return depth(Par, x);
\r
437 // Preorder(x): returns the preorder number of node x, just counting the tree
\r
438 // nodes (i.e., tags, it disregards the texts in the tree).
\r
439 int XMLTree::Preorder(treeNode x)
\r
441 return preorder_rank(Par, x);
\r
444 // Postorder(x): returns the postorder number of node x, just counting the tree
\r
445 // nodes (i.e., tags, it disregards the texts in the tree).
\r
446 int XMLTree::Postorder(treeNode x)
\r
448 return postorder_rank(Par, x);
\r
451 // Tag(x): returns the tag identifier of node x.
\r
452 TagType XMLTree::Tag(treeNode x)
\r
454 return fast_get_field(tags_fix,tags_blen,node2tagpos(x));
\r
457 // DocIds(x): returns the range of text identifiers that descend from node x.
\r
458 // returns {NULLT, NULLT} when there are no texts descending from x.
\r
459 range XMLTree::DocIds(treeNode x)
\r
467 int min = EBVector->rank1(x-1);
\r
468 int max = EBVector->rank1(x+2*subtree_size(Par, x)-2);
\r
469 if (min==max) { // range is empty, no texts within the subtree of x
\r
473 else { // the range is non-empty, there are texts within the subtree of x
\r
480 // Parent(x): returns the parent node of node x.
\r
482 treeNode XMLTree::Parent(treeNode x)
\r
487 return parent(Par, x);;
\r
490 // Child(x,i): returns the i-th child of node x, assuming it exists.
\r
491 treeNode XMLTree::Child(treeNode x, int i)
\r
493 if (i <= OPTD) return naive_child(Par, x, i);
\r
494 else return child(Par, x, i);
\r
497 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.
\r
499 treeNode XMLTree::FirstChild(treeNode x)
\r
501 NULLT_IF(x==NULLT);
\r
502 return fast_first_child(Par, x);
\r
505 treeNode XMLTree::FirstElement(treeNode x)
\r
507 NULLT_IF(x==NULLT);
\r
508 x = fast_first_child(Par, x);
\r
509 NULLT_IF(x == NULLT);
\r
512 case PCDATA_TAG_ID:
\r
514 return (fast_inspect(Par,x)==OP)? x : NULLT;
\r
516 case ATTRIBUTE_TAG_ID:
\r
517 x = fast_next_sibling(Par,x);
\r
518 if (x != NULLT && Tag(x) == PCDATA_TAG_ID){
\r
520 return (fast_inspect(Par,x)==OP)? x : NULLT;
\r
528 treeNode XMLTree::NextElement(treeNode x)
\r
530 NULLT_IF(x==NULLT);
\r
531 x = fast_next_sibling(Par, x);
\r
532 NULLT_IF(x == NULLT);
\r
533 if (Tag(x) == PCDATA_TAG_ID){
\r
535 return (fast_inspect(Par,x)==OP)? x : NULLT;
\r
539 value XMLTree::CamlFirstElement(value x)
\r
541 return Val_int(FirstElement(Int_val(x)));
\r
543 value XMLTree::CamlNextElement(value x)
\r
545 return Val_int(NextElement(Int_val(x)));
\r
548 extern "C" value caml_cpp_fast_first_element(value xmltree, value node){
\r
549 return XMLTREE(xmltree)->CamlFirstElement(node);
\r
552 extern "C" value caml_cpp_fast_next_element(value xmltree, value node){
\r
553 return XMLTREE(xmltree)->CamlNextElement(node);
\r
556 // LastChild(x): returns the last child of node x.
\r
557 treeNode XMLTree::LastChild(treeNode x)
\r
559 NULLT_IF(x == NULLT || fast_isleaf(Par,x));
\r
560 return find_open(Par, fast_find_close(Par, x)-1);
\r
563 // NextSibling(x): returns the next sibling of node x, assuming it exists.
\r
564 treeNode XMLTree::NextSibling(treeNode x)
\r
566 NULLT_IF(x==NULLT || x == Root() );
\r
567 x = fast_find_close(Par,x)+1;
\r
568 return (fast_inspect(Par,x) == CP ? NULLT : x);
\r
572 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.
\r
573 treeNode XMLTree::PrevSibling(treeNode x)
\r
575 NULLT_IF(x==NULLT);
\r
576 return prev_sibling(Par, x);
\r
579 // TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none.
\r
580 // Because of the balanced-parentheses representation of the tree, this operation is not supported
\r
581 // efficiently, just iterating among the children of node x until finding the desired child.
\r
582 treeNode XMLTree::TaggedChild(treeNode x, TagType tag)
\r
585 NULLT_IF(x==NULLT || fast_isleaf(Par,x));
\r
587 child = fast_first_child(Par, x); // starts at first child of node x
\r
588 if (Tag(child) == tag)
\r
591 return TaggedFollowingSibling(child,tag);
\r
594 // TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.
\r
595 treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)
\r
597 NULLT_IF(x==NULLT);
\r
598 treeNode sibling = fast_next_sibling(Par, x);
\r
600 while (sibling != NULLT) {
\r
601 ctag = Tag(sibling);
\r
602 if (ctag == tag) // current sibling is labeled with tag of interest
\r
604 sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling
\r
606 return NULLT; // no such sibling was found
\r
609 treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags)
\r
612 NULLT_IF(x==NULLT || fast_isleaf(Par,x));
\r
614 treeNode child = fast_first_child(Par, x);
\r
616 while (child != NULLT) {
\r
618 if (tags->find(t) != tags->end()) return child;
\r
619 child = fast_sibling(Par, child,t);
\r
625 treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags)
\r
628 NULLT_IF(x==NULLT);
\r
631 treeNode sibling = fast_next_sibling(Par, x);
\r
632 while (sibling != NULLT) {
\r
634 if (tags->find(t) != tags->end()) return sibling;
\r
635 sibling = fast_sibling(Par, sibling,t);
\r
641 // TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within
\r
642 // the subtree of x. Returns NULLT if there is none.
\r
643 treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag)
\r
645 //NULLT_IF(x==NULLT || fast_isleaf(Par,x));
\r
647 int s = (int) Tags->select_next(tag,node2tagpos(x));
\r
648 NULLT_IF (s == -1);
\r
650 treeNode y = tagpos2node(s); // transforms the tag position into a node position
\r
652 return (fast_is_ancestor(Par,x,y) ? y : NULLT);
\r
656 treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags)
\r
658 NULLT_IF (x ==NULLT || fast_isleaf(Par,x));
\r
660 treeNode min = NULLT;
\r
661 treeNode fc = fast_first_child(Par,x);
\r
663 TagIdSet::const_iterator tagit;
\r
664 for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
\r
665 aux = TaggedDescendant(x, (TagType) *tagit);
\r
666 if (aux == fc) return fc;
\r
667 if (aux == NULLT) continue;
\r
668 if ((min == NULLT) || (aux < min)) min = aux;
\r
675 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an
\r
676 // ancestor of x. Returns NULLT if there is none.
\r
677 treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag)
\r
680 treeNode node_s, root;
\r
681 r = (int)Tags->rank(tag, node2tagpos(x)-1);
\r
682 if (r==0) return NULLT; // there is no such node.
\r
683 s = (int)Tags->select(tag, r);
\r
684 root = root_node(Par);
\r
685 node_s = tagpos2node(s);
\r
686 while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x
\r
688 if (r==0) return NULLT; // there is no such node
\r
689 s = (int)Tags->select(tag, r); // we should use select_prev instead when provided
\r
690 node_s = tagpos2node(s);
\r
692 return NULLT; // there is no such node
\r
696 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in
\r
697 // the subtree of x. Returns NULLT if there is none.
\r
698 treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag)
\r
700 NULLT_IF (x ==NULLT || x == Root());
\r
701 return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x)));
\r
705 // TaggedFollBelow(x,tag,root): returns the first node tagged tag with larger preorder than x
\r
706 // and not in the subtree of x. Returns NULLT if there is none.
\r
707 treeNode XMLTree::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor)
\r
709 // NULLT_IF (x == NULLT || x == Root() || x == ancestor);
\r
711 //Special optimisation, test for the following sibling first
\r
712 treeNode close = fast_find_close(Par, x);
\r
714 treeNode ns = close+1;
\r
715 if (fast_inspect(Par,ns) == OP) {
\r
716 TagType tagns = Tag(ns);
\r
717 // cout << GetTagNameByRef(tagns) << endl;
\r
719 if (tagns == PCDATA_TAG_ID){
\r
722 if (fast_inspect(Par,ns) != OP)
\r
731 treeNode s = tagpos2node(Tags->select_next(tag, close));
\r
733 if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s;
\r
737 treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing)
\r
740 NULLT_IF (x == NULLT || x == Root());
\r
742 treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x)));
\r
743 NULLT_IF (s == NULLT || s >= closing);
\r
748 /* Here we inline TaggedFoll to find the min globally, and only at the end
\r
749 we check if the min is below the context node */
\r
750 treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor)
\r
753 NULLT_IF(x==NULLT || x==Root());
\r
755 treeNode close = fast_find_close(Par,x);
\r
756 treeNode ns = close+1;
\r
757 if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end()))
\r
761 treeNode min = NULLT;
\r
765 TagIdSet::const_iterator tagit;
\r
766 for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
\r
768 aux = tagpos2node(Tags->select_next(*tagit, close));
\r
770 // The next sibling of x is guaranteed to be below ctx
\r
771 // and is the node with lowest preorder which is after ctx.
\r
772 // if we find it, we return early;
\r
773 if (aux == NULLT) continue;
\r
774 if ((min == NULLT) || (aux < min)) min = aux;
\r
777 // found the smallest node in preorder which is after x.
\r
778 // if ctx is the root node, just return what we found.
\r
780 if (ancestor == Root()) return min;
\r
781 // else check whether if is in below the ctx node
\r
783 NULLT_IF (min == NULLT || min >= fast_find_close(Par, ancestor));
\r
788 treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing)
\r
791 NULLT_IF(x==NULLT || x==Root());
\r
793 treeNode min = NULLT;
\r
794 treeNode ns = fast_next_sibling(Par, x);
\r
795 treeNode close = ns - 1;
\r
797 TagIdSet::const_iterator tagit;
\r
798 for (tagit = tags->begin(); tagit != tags->end(); tagit++) {
\r
800 aux = tagpos2node(Tags->select_next(*tagit, close));
\r
802 // The next sibling of x is guaranteed to be below ctx
\r
803 // and is the node with lowest preorder which is after ctx.
\r
804 // if we find it, we return early;
\r
806 if (aux == ns ) return ns;
\r
807 if (aux == NULLT) continue;
\r
808 if ((min == NULLT) || (aux < min)) min = aux;
\r
811 // found the smallest node in preorder which is after x.
\r
812 // if ctx is the root node, just return what we found.
\r
814 NULLT_IF (min == NULLT || min >= closing);
\r
821 // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return
\r
822 // NULLT is there is none.
\r
823 treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)
\r
825 if (x == NULLT || x == Root())
\r
828 treeNode s = parent(Par, x), r = Root();
\r
830 if (Tag(s) == tag) return s;
\r
831 s = parent(Par, s);
\r
838 // MyText(x): returns the document identifier of the text below node x,
\r
839 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc
\r
840 // ids start from 0.
\r
841 DocID XMLTree::MyText(treeNode x)
\r
843 TagType tag = Tag(x);
\r
844 // seems faster than testing EBVector->access(x);
\r
846 if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID)
\r
847 //if (EBVector->access(x))
\r
848 return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0
\r
850 return (DocID) NULLT;
\r
853 // MyText(x): returns the document identifier of the text below node x,
\r
854 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc
\r
855 // ids start from 0.
\r
856 DocID XMLTree::MyTextUnsafe(treeNode x)
\r
858 return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0
\r
860 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of
\r
861 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.
\r
862 int XMLTree::TextXMLId(DocID d)
\r
864 NULLT_IF(d == NULLT);
\r
865 int s = EBVector->select1(d+1);
\r
866 return rank_open(Par, s) + d + 1; // +1 because root has preorder 1
\r
870 // NodeXMLId(x): returns the preorder of node x in the tree consisting
\r
871 // of all tree nodes and all text nodes. Assumes that the tree root has
\r
873 int XMLTree::NodeXMLId(treeNode x)
\r
875 NULLT_IF(x == NULLT);
\r
876 if (x == Root()) return 1; // root node has preorder 1
\r
877 return rank_open(Par, x) + EBVector->rank1(x-1);
\r
880 // ParentNode(d): returns the parent node of document identifier d.
\r
881 treeNode XMLTree::ParentNode(DocID d)
\r
883 NULLT_IF (d == NULLT);
\r
884 return (treeNode) EBVector->select1(d+1);
\r
887 // GetTagId: returns the tag identifier corresponding to a given tag name.
\r
888 // Returns NULLT in case that the tag name does not exists.
\r
889 TagType XMLTree::GetTagId(unsigned char *tagname)
\r
892 string s = (char *) tagname;
\r
893 TagIdMapIT it = tIdMap->find(s);
\r
894 return (TagType) ((it != tIdMap->end()) ? it->second : -1);
\r
899 // GetTagName(tagid): returns the tag name of a given tag identifier.
\r
900 // Returns NULL in case that the tag identifier is not valid.
\r
901 unsigned char *XMLTree::GetTagName(TagType tagid)
\r
904 if ( tagid < 0 || tagid >= TagName->size())
\r
905 return (unsigned char *) "<INVALID TAG>";
\r
906 strcpy((char *)s, (*TagName)[tagid].c_str());
\r
908 return (s == NULL ? (unsigned char*) "<INVALID TAG>" : s);
\r
912 const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)
\r
916 if ( tagid < 0 || tagid >= TagName->size())
\r
917 return (unsigned char *) "<INVALID TAG>";
\r
919 return (const unsigned char *) (*TagName)[tagid].c_str();
\r
925 TagType XMLTree::RegisterTag(unsigned char *tagname)
\r
927 TagType id = XMLTree::GetTagId(tagname);
\r
929 string s = (char *) tagname;
\r
930 REGISTER_TAG(TagName,tIdMap,s);
\r
937 treeNode XMLTree::Closing(treeNode x) {
\r
938 return fast_find_close(Par,x);
\r
940 bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); }
\r
942 //WARNING this uses directly the underlying implementation for plain text
\r
946 void XMLTree::Print(int fd,treeNode x, bool no_text){
\r
948 int newfd = dup(fd);
\r
949 stream = fdopen(newfd,"wa");
\r
953 treeNode fin = fast_find_close(Par,x);
\r
955 TagType tag = Tag(n);
\r
957 range r = DocIds(x);
\r
958 treeNode first_idx;
\r
959 treeNode first_text = (tag == PCDATA_TAG_ID ? x : TaggedDescendant(x,PCDATA_TAG_ID));
\r
960 treeNode first_att = NULLT;//TaggedDesc(x,ATTRIBUTE_DATA_TAG_ID);
\r
962 if (first_att == NULLT)
\r
963 first_idx = first_text;
\r
964 else if (first_text == NULLT)
\r
965 first_idx = first_att;
\r
967 first_idx = min(first_att,first_text);
\r
969 uchar * current_text=NULL;
\r
970 if (first_idx != NULLT)
\r
971 current_text = GetText(MyText(first_idx));
\r
974 std::stack<uchar*> st;
\r
976 if (fast_inspect(Par,n)){
\r
977 if (tag == PCDATA_TAG_ID ) {
\r
978 // myfputs((const char*) (GetText(MyTextUnsafe(n))),fp);
\r
980 myfputs("<$/>",fp);
\r
982 read = fprintf(fp,"%s",(const char*) current_text);
\r
983 current_text += (read + 1);
\r
985 n+=2; // skip closing $
\r
992 tagstr = (uchar*) GetTagNameByRef(tag);
\r
993 myfputs((const char*) tagstr ,fp);
\r
995 if (fast_inspect(Par,n)) {
\r
998 if (tag == ATTRIBUTE_TAG_ID){
\r
1000 if (no_text) myfputs("><@@>",fp);
\r
1001 while (fast_inspect(Par,n)){
\r
1004 myfputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp);
\r
1006 myfputs("<$@/></",fp);
\r
1007 myfputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp);
\r
1013 myfputs((const char*) &(GetTagNameByRef(Tag(n))[3]),fp);
\r
1015 myfputs("=\"",fp);
\r
1016 read = fprintf(fp,"%s",(const char*) current_text);
\r
1017 current_text += (read + 1);
\r
1018 //myfputs((const char*) GetText(MyTextUnsafe(n)),fp);
\r
1024 myfputs("</@@>",fp);
\r
1025 else myfputc('>',fp);
\r
1033 else {// <foo /> tag
\r
1043 myfputs((const char*)st.top(),fp);
\r
1047 }while (!fast_inspect(Par,n) && !st.empty());
\r
1051 mybufferflush(fp);
\r