4 // functions to convert tag positions to the corresponding tree node and viceversa.
\r
5 // These are implemented in order to be able to change the tree and Tags representations,
\r
6 // without affecting the code so much.
\r
7 // Current implementation corresponds to balanced-parentheses representation for
\r
8 // the tree, and storing 2 tags per tree node (opening and closing tags).
\r
10 // tag position -> tree node
\r
11 inline treeNode tagpos2node(int t) {
\r
15 // tree node -> tag position
\r
16 inline int node2tagpos(treeNode x) {
\r
21 //KIM OJO to prevent suprious "unused result" warnings
\r
23 inline void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream){
\r
25 res = fread(ptr,size,nmemb,stream);
\r
27 throw "ufread I/O error";
\r
32 inline void ufwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream){
\r
34 res = fwrite(ptr,size,nmemb,stream);
\r
36 throw "ufwrite I/O error";
\r
40 // OJO to fail cleanly while doing a realloc
\r
41 // if we can't realloc we are pretty much screwed anyway but
\r
42 // it makes the code clearer to not have a bunch of if (!ptr) { printf("..."); exit(1); };
\r
43 inline void * urealloc(void *ptr, size_t size){
\r
45 void * dest = realloc(ptr,size);
\r
46 //don't fail if we requested size 0
\r
47 if (dest == NULL && size > 0 )
\r
48 throw std::bad_alloc();
\r
53 inline void * ucalloc(size_t nmemb, size_t size){
\r
55 void * dest = calloc(nmemb,size);
\r
56 //don't fail if we requested size 0
\r
57 if (dest == NULL && nmemb > 0 && size > 0 )
\r
58 throw std::bad_alloc();
\r
63 inline void * umalloc(size_t size){
\r
64 void * dest = malloc(size);
\r
65 if (dest == NULL && size > 0)
\r
66 throw std::bad_alloc();
\r
70 void XMLTree::print_stats() {
\r
71 uint total_space = Tags->size()+sizeof(static_sequence*);
\r
72 total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len));
\r
73 cout << "Space usage for XMLTree:" << endl
\r
74 << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl
\r
75 << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl
\r
76 << " ... add Diego structures ... " << endl
\r
77 << " *total* " << total_space << endl;
\r
80 // Save: saves XML tree data structure to file.
\r
81 void XMLTree::Save(unsigned char *filename)
\r
85 char filenameaux[1024];
\r
88 sprintf(filenameaux, "%s.srx", filename);
\r
89 fp = fopen(filenameaux, "w");
\r
91 printf("Error: cannot create file %s to store the tree structure of XML collection\n", filenameaux);
\r
95 // first stores the tree topology
\r
98 // stores the table with tag names
\r
99 ufwrite(&ntagnames, sizeof(int), 1, fp);
\r
100 for (i=0; i<ntagnames;i++)
\r
101 fprintf(fp, "%s\n",TagName[i]);
\r
104 // stores the flags
\r
105 ufwrite(&indexing_empty_texts, sizeof(bool), 1, fp);
\r
106 ufwrite(&initialized, sizeof(bool), 1, fp);
\r
107 ufwrite(&finished, sizeof(bool), 1, fp);
\r
108 ufwrite(&disable_tc, sizeof(bool),1,fp);
\r
110 if (!indexing_empty_texts) EBVector->save(fp);
\r
114 ufwrite(&tags_blen,sizeof(uint),1,fp);
\r
115 ufwrite(&tags_len,sizeof(uint),1,fp);
\r
116 ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp);
\r
118 // stores the texts
\r
121 int st = CachedText.size();
\r
122 ufwrite(&st, sizeof(int),1,fp);
\r
123 for (int i = 0; i< CachedText.size(); i++){
\r
124 st = CachedText.at(i).size();
\r
125 ufwrite(&st, sizeof(int),1,fp);
\r
126 ufwrite(CachedText.at(i).c_str(),sizeof(char),1+CachedText.at(i).size(),fp);
\r
134 // Load: loads XML tree data structure from file. Returns
\r
135 // a pointer to the loaded data structure
\r
136 XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text)
\r
147 // first load the tree topology
\r
148 sprintf(buffer, "%s.srx", filename);
\r
149 fp = fopen(buffer, "r");
\r
151 printf("Error: cannot open file %s to load the tree structure of XML collection\n", buffer);
\r
155 XML_Tree = new XMLTree();
\r
157 XML_Tree->Par = (bp *)umalloc(sizeof(bp));
\r
159 loadTree(XML_Tree->Par, fp);
\r
161 s_tree += sizeof(bp);
\r
163 // stores the table with tag names
\r
164 ufread(&XML_Tree->ntagnames, sizeof(int), 1, fp);
\r
166 s_tree += sizeof(int);
\r
168 XML_Tree->TagName = (unsigned char **)umalloc(XML_Tree->ntagnames*sizeof(unsigned char *));
\r
170 s_tags += sizeof(unsigned char*)*XML_Tree->ntagnames;
\r
173 for (i=0; i<XML_Tree->ntagnames;i++) {
\r
175 // OJO Kim is it needed ?
\r
179 // fscanf chokes on "\n" which is the case for the root element
\r
180 char * r = fgets(buffer,1023,fp);
\r
181 // int r = fscanf(fp, "%s\n",buffer);
\r
183 throw "Cannot read tag list";
\r
185 // strlen is actually the right size, since there is a trailing '\n'
\r
186 int len = strlen((const char*)buffer);
\r
187 XML_Tree->TagName[i] = (unsigned char *)ucalloc(len,sizeof(char));
\r
188 strncpy((char *)XML_Tree->TagName[i], (const char *)buffer,len - 1);
\r
189 s_tags+= len*sizeof(char);
\r
194 ufread(&(XML_Tree->indexing_empty_texts), sizeof(bool), 1, fp);
\r
195 ufread(&(XML_Tree->initialized), sizeof(bool), 1, fp);
\r
196 ufread(&(XML_Tree->finished), sizeof(bool), 1, fp);
\r
197 ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp);
\r
199 s_tree+=sizeof(bool)*4;
\r
201 if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);
\r
203 s_tree+= XML_Tree->EBVector->size();
\r
206 XML_Tree->Tags = static_sequence::load(fp);
\r
207 ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp);
\r
208 ufread(&XML_Tree->tags_len,sizeof(uint),1,fp);
\r
209 XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)];
\r
210 ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp);
\r
211 s_tree+=2*sizeof(uint)+sizeof(uint)*uint_len(XML_Tree->tags_blen,XML_Tree->tags_len);
\r
212 s_tree+= XML_Tree->Tags->size();
\r
214 /// FIXME:UGLY tests!
\r
215 /*uint * seq = new uint[XML_Tree->tags_len];
\r
216 for(uint i=0;i<XML_Tree->tags_len;i++)
\r
217 seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i);
\r
218 cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl;
\r
222 s_text = ftell(fp);
\r
225 if (!XML_Tree->disable_tc){
\r
226 XML_Tree->Text = TextCollection::Load(fp,sample_rate_text);
\r
229 ufread(&sst, sizeof(int),1,fp);
\r
230 for (int i=0;i<sst;i++){
\r
231 ufread(&st, sizeof(int),1,fp);
\r
232 char* str = (char*) malloc(sizeof(char)*st+1);
\r
233 ufread(str,sizeof(char),st+1,fp);
\r
234 string cppstr = str;
\r
235 XML_Tree->CachedText.push_back(cppstr);
\r
241 XML_Tree->Text = NULL;
\r
243 s_text = ftell(fp) - s_text;
\r
250 /*std::cerr << "Tree part is " << s_tree/1024 << " Kbytes,\n"
\r
251 << "with node->tagid part " << XML_Tree->Tags->size()/1024+(uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/1024 << "Kbytes \n"
\r
252 << "size of Tag part : " << XML_Tree->Tags->length () << " elements\n"
\r
253 << "sizof(unsigned int)* " << XML_Tree->Tags->length () << " = " <<
\r
254 sizeof(unsigned int) * XML_Tree->Tags->length () / 1024 << " Kbytes\n"
\r
255 << "Tag part is " << s_tags/1024 << " Kbytes,\n"
\r
256 << "Text collection is " << s_text/1024 << " Kbytes \n";*/
\r
257 XML_Tree->print_stats();
\r
262 // ~XMLTree: frees memory of XML tree.
\r
263 XMLTree::~XMLTree()
\r
268 free(Par); // frees the memory of struct Par
\r
270 for (i=0; i<ntagnames;i++)
\r
275 if (!indexing_empty_texts) {
\r
276 //EBVector->~static_bitsequence_rrr02();
\r
281 //Tags->~static_sequence_wvtree();
\r
285 //Text->~TextCollection();
\r
286 delete TextBuilder;
\r
287 TextBuilder = NULL;
\r
291 initialized = false;
\r
295 // root(): returns the tree root.
\r
296 treeNode XMLTree::Root()
\r
299 fprintf(stderr, "Root() : Error: data structure has not been constructed properly\n");
\r
302 return root_node(Par);
\r
305 // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.
\r
306 int XMLTree::SubtreeSize(treeNode x)
\r
309 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
312 return subtree_size(Par, x);
\r
315 // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.
\r
316 int XMLTree::SubtreeTags(treeNode x, TagType tag)
\r
319 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
323 x = first_child(Par,x);
\r
326 int s = x + 2*subtree_size(Par, x) - 1;
\r
328 return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1);
\r
331 // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation
\r
332 // this is just a bit inspection.
\r
333 bool XMLTree::IsLeaf(treeNode x)
\r
335 return isleaf(Par, x);
\r
338 // IsAncestor(x,y): returns whether node x is ancestor of node y.
\r
339 bool XMLTree::IsAncestor(treeNode x, treeNode y)
\r
342 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
346 return is_ancestor(Par, x, y);
\r
349 // IsChild(x,y): returns whether node x is parent of node y.
\r
350 bool XMLTree::IsChild(treeNode x, treeNode y)
\r
353 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
357 if (!is_ancestor(Par, x, y)) return false;
\r
358 return depth(Par, x) == (depth(Par, y) + 1);
\r
361 // NumChildren(x): number of children of node x. Constant time with the data structure
\r
363 int XMLTree::NumChildren(treeNode x)
\r
366 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
370 return degree(Par, x);
\r
373 // ChildNumber(x): returns i if node x is the i-th children of its parent.
\r
374 int XMLTree::ChildNumber(treeNode x)
\r
377 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
381 return child_rank(Par, x);
\r
384 // Depth(x): depth of node x, a simple binary rank on the parentheses sequence.
\r
385 int XMLTree::Depth(treeNode x)
\r
388 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
392 return depth(Par, x);
\r
395 // Preorder(x): returns the preorder number of node x, just counting the tree
\r
396 // nodes (i.e., tags, it disregards the texts in the tree).
\r
397 int XMLTree::Preorder(treeNode x)
\r
400 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
404 return preorder_rank(Par, x);
\r
407 // Postorder(x): returns the postorder number of node x, just counting the tree
\r
408 // nodes (i.e., tags, it disregards the texts in the tree).
\r
409 int XMLTree::Postorder(treeNode x)
\r
412 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
415 return postorder_rank(Par, x);
\r
418 // Tag(x): returns the tag identifier of node x.
\r
419 TagType XMLTree::Tag(treeNode x)
\r
422 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
426 return get_field(tags_fix,tags_blen,node2tagpos(x)); //Tags->access(node2tagpos(x));
\r
429 // DocIds(x): returns the range of text identifiers that descend from node x.
\r
430 // returns {NULLT, NULLT} when there are no texts descending from x.
\r
431 range XMLTree::DocIds(treeNode x)
\r
434 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
447 if (indexing_empty_texts) { // faster, no rank needed
\r
449 r.max = x+2*subtree_size(Par, x)-2;
\r
451 else { // we are not indexing empty texts, we need rank
\r
452 int min = EBVector->rank1(x-1);
\r
453 int max = EBVector->rank1(x+2*subtree_size(Par, x)-2);
\r
454 if (min==max) { // range is empty, no texts within the subtree of x
\r
458 else { // the range is non-empty, there are texts within the subtree of x
\r
466 // Parent(x): returns the parent node of node x.
\r
467 treeNode XMLTree::Parent(treeNode x)
\r
470 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
476 return parent(Par, x);
\r
479 // Child(x,i): returns the i-th child of node x, assuming it exists.
\r
480 treeNode XMLTree::Child(treeNode x, int i)
\r
483 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
487 if (i <= OPTD) return naive_child(Par, x, i);
\r
488 else return child(Par, x, i);
\r
491 // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.
\r
492 treeNode XMLTree::FirstChild(treeNode x)
\r
495 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
499 return first_child(Par, x);
\r
502 // NextSibling(x): returns the next sibling of node x, assuming it exists.
\r
503 treeNode XMLTree::NextSibling(treeNode x)
\r
506 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
509 if (x == Root() || x==NULLT)
\r
512 return next_sibling(Par, x);
\r
515 // PrevSibling(x): returns the previous sibling of node x, assuming it exists.
\r
516 treeNode XMLTree::PrevSibling(treeNode x)
\r
519 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
523 return prev_sibling(Par, x);
\r
526 // TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or NULLT if there is none.
\r
527 // Because of the balanced-parentheses representation of the tree, this operation is not supported
\r
528 // efficiently, just iterating among the children of node x until finding the desired child.
\r
529 treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag)
\r
532 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
538 child = first_child(Par, x); // starts at first child of node x
\r
539 if (child==(treeNode)-1) return NULLT; // node x is a leaf, there is no such child
\r
540 while (child!=(treeNode)-1) {
\r
541 if (get_field(tags_fix,tags_blen,node2tagpos(child)) /*Tags->access(node2tagpos(child))*/ == tag) { // current child is labeled with tag of interest
\r
543 if (i==0) return child; // we have seen i children of x tagged tag, this is the one we are looking for
\r
545 child = next_sibling(Par, x); // OK, let's try with the next child
\r
547 return NULLT; // no such child was found
\r
550 // TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within
\r
551 // the subtree of x. Returns NULLT if there is none.
\r
552 treeNode XMLTree::TaggedDesc(treeNode x, TagType tag)
\r
555 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
564 r = (int) Tags->rank(tag, node2tagpos(x));
\r
565 s = (int) Tags->select(tag, r+1);
\r
566 if (s == -1) return NULLT; // there is no such node
\r
567 y = tagpos2node(s); // transforms the tag position into a node position
\r
568 if (!is_ancestor(Par, x, y)) return NULLT; // the next node tagged tag (in preorder) is not within the subtree of x.
\r
572 treeNode XMLTree::TaggedDescOnly(treeNode x,TagType *desctags, unsigned int dtlen)
\r
580 for (unsigned int i = 0; i < dtlen; i ++ )
\r
582 y = TaggedDesc(x,desctags[i]);
\r
583 res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;
\r
592 treeNode XMLTree::TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen,
\r
593 TagType *desctags, unsigned int dtlen)
\r
602 fs = first_child(Par,x);
\r
603 while (fs != NULLT) {
\r
604 tag = get_field(tags_fix,tags_blen,node2tagpos(fs));
\r
606 /* Check for first_child */
\r
607 for (unsigned int i = 0; i < ctlen; i++) {
\r
608 if (childtags[i] == tag)
\r
612 for (unsigned int i = 0; i < dtlen; i++)
\r
613 if (desctags[i] == tag)
\r
616 /* check in the descendants */
\r
618 for (unsigned int i = 0; i < dtlen; i ++ ){
\r
619 /* maybe inline by hand */
\r
620 y = TaggedDesc(fs,desctags[i]);
\r
621 res = (res==NULLT || (y != NULLT) &&(y < res)) ? y : res;
\r
626 fs = next_sibling(Par,fs);
\r
631 treeNode XMLTree::TaggedFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root)
\r
634 treeNode res,y,lim;
\r
635 lim = find_close(Par,root);
\r
637 for (unsigned int i = 0; i < ftlen; i ++ )
\r
639 y = TaggedFoll(x,folltags[i]);
\r
640 res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;
\r
644 return res < lim ? res : NULLT;
\r
648 treeNode XMLTree::TaggedDescOrFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root)
\r
651 treeNode res,y,lim;
\r
653 lim = find_close(Par,root);
\r
655 for (unsigned int i = 0; i < ftlen; i ++ )
\r
658 r = (int) Tags->rank(folltags[i], node2tagpos(x));
\r
659 s = (int) Tags->select(folltags[i], r+1);
\r
661 y = NULLT; // there is no such node
\r
663 y = tagpos2node(s);
\r
667 res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res;
\r
671 return res < lim ? res : NULLT;
\r
676 // TaggedNext(x,tag): returns the first node tagged tag with larger preorder than x
\r
677 // Returns NULLT if there is none.
\r
678 treeNode XMLTree::TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen,
\r
679 TagType *folltags, unsigned int flen,treeNode root)
\r
681 treeNode y,old_y,lim,res;
\r
683 if (x == NULLT || x == Root())
\r
687 lim = find_close(Par,root);
\r
691 y = next_sibling(Par,x);
\r
692 while (y != NULLT) {
\r
693 tag = get_field(tags_fix,tags_blen,node2tagpos(y));
\r
694 for(unsigned int i = 0; i < ctlen;i++)
\r
695 if (childtags[i] == tag)
\r
698 for(unsigned int i = 0; i < flen;i++)
\r
699 if (folltags[i] == tag)
\r
702 res = TaggedBelow(y,NULL,0,folltags,flen);
\r
706 y = next_sibling(Par,y);
\r
708 //Found nothing in the following sibling of x.
\r
710 for(unsigned int i = 0; i < flen;i++){
\r
711 y = TaggedFoll(x,folltags[i]);
\r
712 res = (y!= x && (res == NULLT || (y != NULLT && y < res)))? y : res;
\r
715 return res < lim ? res : NULLT;
\r
720 // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an
\r
721 // ancestor of x. Returns NULLT if there is none.
\r
722 treeNode XMLTree::TaggedPrec(treeNode x, TagType tag)
\r
725 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
730 treeNode node_s, root;
\r
731 r = (int)Tags->rank(tag, node2tagpos(x)-1);
\r
732 if (r==0) return NULLT; // there is no such node.
\r
733 s = (int)Tags->select(tag, r);
\r
734 root = root_node(Par);
\r
735 node_s = tagpos2node(s);
\r
736 while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x
\r
738 if (r==0) return NULLT; // there is no such node
\r
739 s = (int)Tags->select(tag, r); // we should use select_prev instead when provided
\r
740 node_s = tagpos2node(s);
\r
742 return NULLT; // there is no such node
\r
746 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in
\r
747 // the subtree of x. Returns NULLT if there is none.
\r
748 treeNode XMLTree::TaggedFoll(treeNode x, TagType tag)
\r
751 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
756 if (x ==NULLT || x == Root())
\r
759 r = (int) Tags->rank(tag, find_close(Par, x));
\r
760 s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag.
\r
761 if (s==-1) return NULLT;
\r
762 else return tagpos2node(s);
\r
765 // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in
\r
766 // the subtree of x. Returns NULLT if there is none.
\r
767 treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root)
\r
771 int lim = node2tagpos(find_close(Par,root));
\r
772 if (x ==NULLT || x == Root())
\r
775 r = (int) Tags->rank(tag,find_close(Par,x));
\r
776 s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag.
\r
777 if (s==-1 || s >= lim)
\r
780 return tagpos2node(s);
\r
784 // TaggedFollowingSibling(x,tag): returns the first node tagged tag with larger preorder than x and not in
\r
785 // the subtree of x. Returns NULLT if there is none.
\r
786 treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag)
\r
789 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
794 treeNode ns = next_sibling(Par,x);
\r
796 if (x == NULLT || x == Root() || ns == -1)
\r
799 r = (int) Tags->rank(tag, node2tagpos(ns)-1);
\r
800 s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag.
\r
801 if (s==-1) return NULLT;
\r
802 else return tagpos2node(s);
\r
806 // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return
\r
807 // NULLT is there is none.
\r
808 treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag)
\r
811 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
815 if (x == NULLT || x == Root())
\r
818 treeNode s = parent(Par, x), r = Root();
\r
820 if (get_field(tags_fix,tags_blen,node2tagpos(s)) /*Tags->access(node2tagpos(s))*/ == tag) return s;
\r
821 s = parent(Par, s);
\r
827 // PrevText(x): returns the document identifier of the text to the left
\r
828 // of node x, or NULLT if x is the root node or the text is empty.
\r
829 // Assumes Doc ids start from 0.
\r
830 DocID XMLTree::PrevText(treeNode x)
\r
833 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
837 if (x == Root()) return NULLT;
\r
838 if (indexing_empty_texts) // faster, no rank needed
\r
840 else { // we are not indexing empty texts, rank is needed
\r
841 if (EBVector->access(x-1) == 0)
\r
842 return (DocID)NULLT; // there is no text to the left of node (text is empty)
\r
844 return (DocID)EBVector->rank1(x-1)-1; //-1 because document ids start from 0
\r
848 // NextText(x): returns the document identifier of the text to the right
\r
849 // of node x, or NULLT if x is the root node. Assumes Doc ids start from 0.
\r
850 DocID XMLTree::NextText(treeNode x)
\r
853 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
857 if (x == Root()) return NULLT;
\r
858 if (indexing_empty_texts) // faster, no rank needed
\r
859 return (DocID)x+2*subtree_size(Par, x)-1;
\r
860 else { // we are not indexing empty texts, rank is needed
\r
861 int p = x+2*subtree_size(Par, x)-1;
\r
862 if (EBVector->access(p) == 0) // there is no text to the right of node
\r
863 return (DocID)NULLT;
\r
865 return (DocID)EBVector->rank1(p)-1; //-1 because document ids start from 0
\r
869 // MyText(x): returns the document identifier of the text below node x,
\r
870 // or NULLT if x is not a leaf node or the text is empty. Assumes Doc
\r
871 // ids start from 0.
\r
872 DocID XMLTree::MyText(treeNode x)
\r
875 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
879 if (!IsLeaf(x)) return NULLT;
\r
880 if (indexing_empty_texts) // faster, no rank needed
\r
882 else { // we are not indexing empty texts, rank is needed
\r
883 if (EBVector->access(x) == 0) // there is no text below node x
\r
884 return (DocID)NULLT;
\r
886 return (DocID)EBVector->rank1(x)-1; //-1 because document ids start from 0
\r
890 // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of
\r
891 // all tree nodes and all text nodes. Assumes that the tree root has preorder 1.
\r
892 int XMLTree::TextXMLId(DocID d)
\r
895 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
899 if (indexing_empty_texts)
\r
900 return d + rank_open(Par, d)+1; // +1 because root has preorder 1
\r
901 else { // slower, needs rank and select
\r
902 int s = EBVector->select1(d+1);
\r
903 return rank_open(Par, s) + d + 1; // +1 because root has preorder 1
\r
907 // NodeXMLId(x): returns the preorder of node x in the tree consisting
\r
908 // of all tree nodes and all text nodes. Assumes that the tree root has
\r
910 int XMLTree::NodeXMLId(treeNode x)
\r
913 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
917 if (indexing_empty_texts)
\r
918 return x - 1 + rank_open(Par, x);
\r
920 if (x == Root()) return 1; // root node has preorder 1
\r
922 return rank_open(Par, x) + EBVector->rank1(x-1);
\r
926 // ParentNode(d): returns the parent node of document identifier d.
\r
927 treeNode XMLTree::ParentNode(DocID d)
\r
930 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
938 // OJO : Kim : I added the d+1. before that, else branch was
\r
939 // EBVector->select1(d)
\r
940 // and gave wrong results (I'm really poking a bear with a stick here).
\r
941 if (indexing_empty_texts) s = d;
\r
942 else s = EBVector->select1(d+1);
\r
944 if (inspect(Par,s) == CP) // is a closing parenthesis
\r
945 return parent(Par, find_open(Par, s));
\r
946 else // is an opening parenthesis
\r
947 return (treeNode)s;
\r
950 treeNode XMLTree::PrevNode(DocID d)
\r
953 fprintf(stderr, "Error: data structure has not been constructed properly\n");
\r
962 if (indexing_empty_texts) s = d;
\r
963 else s = EBVector->select1(d+1);
\r
967 if (inspect(Par,s) == CP) // is a closing parenthesis
\r
968 return find_open(Par, s);
\r
969 else // is an opening parenthesis
\r
975 // OpenDocument(empty_texts): it starts the construction of the data structure for
\r
976 // the XML document. Parameter empty_texts indicates whether we index empty texts
\r
977 // in document or not. Returns a non-zero value upon success, NULLT in case of error.
\r
978 int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc)
\r
980 initialized = true;
\r
982 found_attributes = false;
\r
988 indexing_empty_texts = empty_texts;
\r
990 par_aux = (pb *)umalloc(sizeof(pb)*parArraySize);
\r
992 tags_aux = (TagType *) umalloc(sizeof(TagType));
\r
994 TagName = (unsigned char **) umalloc(4*sizeof(unsigned char*));
\r
996 TagName[0] = (unsigned char *) umalloc(4*sizeof(unsigned char));
\r
998 strcpy((char *) TagName[0], "<@>");
\r
1000 TagName[1] = (unsigned char *) umalloc(4*sizeof(unsigned char));
\r
1002 strcpy((char *) TagName[1], "<$>");
\r
1004 //OJO need to put these in the table too.
\r
1005 TagName[2] = (unsigned char *) umalloc(5*sizeof(unsigned char));
\r
1007 strcpy((char *) TagName[2], "/<@>");
\r
1009 TagName[3] = (unsigned char *) umalloc(5*sizeof(unsigned char));
\r
1011 strcpy((char *) TagName[3], "/<$>");
\r
1014 if (!indexing_empty_texts)
\r
1015 empty_texts_aux = (unsigned int *)umalloc(sizeof(unsigned int));
\r
1020 TextBuilder = new TextCollectionBuilder((unsigned)sample_rate_text);
\r
1023 return 1; // indicates success in the initialization of the data structure
\r
1026 // CloseDocument(): it finishes the construction of the data structure for the XML
\r
1027 // document. Tree and tags are represented in the final form, dynamic data
\r
1028 // structures are made static, and the flag "finished" is set to true. After that,
\r
1029 // the data structure can be queried.
\r
1030 int XMLTree::CloseDocument()
\r
1032 if (!initialized) { // data structure has not been initialized properly
\r
1033 fprintf(stderr, "Error: data structure has not been initialized properly (by calling method OpenDocument)\n");
\r
1037 // closing parenthesis for the tree root
\r
1038 par_aux = (pb *)urealloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));
\r
1040 // creates the data structure for the tree topology
\r
1041 Par = (bp *)umalloc(sizeof(bp));
\r
1042 bp_construct(Par, npar, par_aux, OPT_DEGREE|0);
\r
1043 // creates structure for tags
\r
1045 // If we found an attribute then "<@>" is present in the tree
\r
1046 // if we didn't then it is not. "<$>" is never present in the tree
\r
1048 for(uint i=0;i<(uint)npar-1;i++)
\r
1049 max_tag = max(max_tag,tags_aux[i]);
\r
1051 //tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1));
\r
1052 //tags_aux[npar++] = max_tag;
\r
1053 //int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2;
\r
1054 int ntagsize = 2*ntagnames + 2;
\r
1056 //static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20);
\r
1057 //static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb);
\r
1058 //static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb);
\r
1059 static_bitsequence_builder * bmb = new static_bitsequence_builder_sdarray();
\r
1060 alphabet_mapper *am = new alphabet_mapper_none();
\r
1061 //wt_coder * wc = new wt_coder_huff((uint*)tags_aux,npar,am);
\r
1062 //Tags = new static_sequence_wvtree((uint*)tags_aux,npar,wc ,bmb, am);
\r
1063 //Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar,ntagsize, bmb, ssb);
\r
1064 Tags = new static_sequence_bs((uint*)tags_aux,npar,am,bmb);
\r
1066 cout << "Tags test: " << Tags->test((uint*)tags_aux,npar) << endl;
\r
1068 tags_blen = bits(max_tag);
\r
1069 tags_len = (uint)npar;
\r
1070 tags_fix = new uint[uint_len(tags_blen,tags_len)];
\r
1071 for(uint i=0;i<(uint)npar;i++)
\r
1072 set_field(tags_fix,tags_blen,i,tags_aux[i]);
\r
1079 // makes the text collection static
\r
1082 assert(Text == 0);
\r
1083 assert(TextBuilder != 0);
\r
1084 Text = TextBuilder->InitTextCollection();
\r
1085 delete TextBuilder;
\r
1089 // creates the data structure marking the non-empty texts (just in the case it is necessary)
\r
1090 if (!indexing_empty_texts) {
\r
1091 EBVector = new static_bitsequence_rrr02((uint *)empty_texts_aux,(ulong)npar,(uint)32);
\r
1092 free (empty_texts_aux);
\r
1093 empty_texts_aux = NULL;
\r
1096 // OJO was leaked before, found by valgrind
\r
1104 return 1; // indicates success in the inicialization
\r
1108 // NewOpenTag(tagname): indicates the event of finding a new opening tag in the document.
\r
1109 // Tag name is given. Returns a non-zero value upon success, and returns NULLT
\r
1110 // in case of failing when trying to insert the new tag.
\r
1111 int XMLTree::NewOpenTag(unsigned char *tagname)
\r
1115 if (!initialized) { // data structure has not been initialized properly
\r
1116 fprintf(stderr, "Error: you cannot insert a new opening tag without first calling method OpenDocument first\n");
\r
1120 // inserts a new opening parentheses in the bit sequence
\r
1121 if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis
\r
1122 par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize);
\r
1123 parArraySize *= 2;
\r
1126 setbit(par_aux,npar,OP); // marks a new opening parenthesis
\r
1128 // transforms the tagname into a tag identifier. If the tag is new, we insert
\r
1129 // it in the table.
\r
1130 for (i=0; i<ntagnames; i++)
\r
1131 if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break;
\r
1134 // NewOpenTag("<@>") was called
\r
1136 found_attributes=true;
\r
1138 if (i==ntagnames) { // the tag is a new one, then we insert it
\r
1139 TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1));
\r
1142 fprintf(stderr, "Error: not enough memory\n");
\r
1147 TagName[i] = (unsigned char *)umalloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1));
\r
1148 strcpy((char *)TagName[i], (const char *)tagname);
\r
1150 tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1));
\r
1152 tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags
\r
1161 // NewClosingTag(tagname): indicates the event of finding a new closing tag in the document.
\r
1162 // Tag name is given. Returns a non-zero value upon success, and returns NULLT
\r
1163 // in case of failing when trying to insert the new tag.
\r
1164 int XMLTree::NewClosingTag(unsigned char *tagname)
\r
1168 if (!initialized) { // data structure has not been initialized properly
\r
1169 fprintf(stderr, "Error: you cannot insert a new closing tag without first calling method OpenDocument first\n");
\r
1173 // inserts a new closing parentheses in the bit sequence
\r
1174 if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis
\r
1175 par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize);
\r
1176 parArraySize *= 2;
\r
1179 setbit(par_aux,npar,CP); // marks a new closing parenthesis
\r
1181 // transforms the tagname into a tag identifier. If the tag is new, we insert
\r
1182 // it in the table.
\r
1183 for (i=0; i<ntagnames; i++)
\r
1184 if ((strcmp((const char *)tagname,(const char *)(TagName[i]+1))==0) && (TagName[i][0]=='/')) break;
\r
1186 if (i==ntagnames) { // the tag is a new one, then we insert it
\r
1187 TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1));
\r
1190 TagName[i] = (unsigned char *)umalloc(sizeof(char)*(strlen((const char *)tagname)+2));
\r
1191 TagName[i][0] = '/';
\r
1192 strcpy((char *)&(TagName[i][1]), (const char *)tagname);
\r
1195 tags_aux = (TagType *)urealloc(tags_aux, sizeof(TagType)*(npar + 1));
\r
1197 tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags
\r
1201 return 1; // success
\r
1206 // NewText(s): indicates the event of finding a new (non-empty) text s in the document.
\r
1207 // The new text is inserted within the text collection. Returns a non-zero value upon
\r
1208 // success, NULLT in case of error.
\r
1209 int XMLTree::NewText(unsigned char *s)
\r
1211 if (!initialized) { // data structure has not been initialized properly
\r
1212 fprintf(stderr, "Error: you cannot insert a new text without first calling method OpenDocument first\n");
\r
1217 XMLTree::NewEmptyText();
\r
1221 if (!indexing_empty_texts) {
\r
1222 empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));
\r
1223 bitset(empty_texts_aux, npar-1); // marks the non-empty text with a 1 in the bit vector
\r
1226 TextBuilder->InsertText(s);
\r
1227 string cpps = (char*) s;
\r
1228 CachedText.push_back(cpps);
\r
1230 return 1; // success
\r
1233 // NewEmptyText(): indicates the event of finding a new empty text in the document.
\r
1234 // In case of indexing empty and non-empty texts, we insert the empty texts into the
\r
1235 // text collection. In case of indexing only non-empty texts, it just indicates an
\r
1236 // empty text in the bit vector of empty texts. Returns a non-zero value upon
\r
1237 // success, NULLT in case of error.
\r
1238 int XMLTree::NewEmptyText()
\r
1240 unsigned char c = 0;
\r
1241 if (!initialized) { // data structure has not been initialized properly
\r
1242 fprintf(stderr, "Error: you cannot insert a new empty text without first calling method OpenDocument first\n");
\r
1246 if (!indexing_empty_texts) {
\r
1247 empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb))));
\r
1249 bitclean(empty_texts_aux, npar-1); // marks the empty text with a 0 in the bit vector
\r
1251 else TextBuilder->InsertText(&c); // we insert the empty text just in case we index all the texts
\r
1253 return 1; // success
\r
1257 // GetTagId: returns the tag identifier corresponding to a given tag name.
\r
1258 // Returns NULLT in case that the tag name does not exists.
\r
1259 TagType XMLTree::GetTagId(unsigned char *tagname)
\r
1262 // this should be changed for more efficient processing
\r
1263 for (i=0; i<ntagnames; i++)
\r
1264 if (strcmp((const char *)tagname,(const char *)TagName[i])==0) break;
\r
1265 if (i==ntagnames) return (TagType)-1; //ntagnames; //(TagType)NULLT; // tagname does not exists in the table
\r
1270 // GetTagName(tagid): returns the tag name of a given tag identifier.
\r
1271 // Returns NULL in case that the tag identifier is not valid.
\r
1272 unsigned char *XMLTree::GetTagName(TagType tagid)
\r
1275 if(tagid==(uint)-1) return NULL;
\r
1276 if (tagid >= ntagnames) return NULL; // invalid tag identifier
\r
1277 s = (unsigned char *)umalloc((strlen((const char *)TagName[tagid])+1)*sizeof(unsigned char));
\r
1278 strcpy((char *)s, (const char *)TagName[tagid]);
\r
1283 //KIM : OJO need the two following methods
\r
1285 const unsigned char *XMLTree::GetTagNameByRef(TagType tagid)
\r
1287 if(tagid==(uint)-1) return NULL;
\r
1288 if (tagid >= ntagnames) return NULL; // invalid tag identifier
\r
1289 return ((const unsigned char*) TagName[tagid]);
\r
1294 TagType XMLTree::RegisterTag(unsigned char *tagname)
\r
1299 TagType id = XMLTree::GetTagId(tagname);
\r
1302 ntagnames = ntagnames + 1;
\r
1303 TagName = (unsigned char **) urealloc(TagName,ntagnames*(sizeof(unsigned char*)));
\r
1304 TagName[id] = (unsigned char *) umalloc(sizeof(unsigned char)*strlen( (const char*) tagname)+1);
\r
1305 strcpy((char*)TagName[id], (const char *)tagname);
\r