X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=bd728af5d665e695733364fc0783436b4f072ea2;hb=5db16dd3e0bf609bc0fa84ee7d067f6bbc58013e;hp=6fee8f4673d8a825a107e310d7e34c0de1d0ab79;hpb=82b89c86269e04916a4aef964977ee738d8f2927;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index 6fee8f4..bd728af 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -211,12 +211,19 @@ XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) s_tree+=2*sizeof(uint)+sizeof(uint)*uint_len(XML_Tree->tags_blen,XML_Tree->tags_len); s_tree+= XML_Tree->Tags->size(); + /// FIXME:UGLY tests! + uint * seq = new uint[XML_Tree->tags_len]; + for(uint i=0;itags_len;i++) + seq[i] = get_field(XML_Tree->tags_fix,XML_Tree->tags_blen,i); + cout << "Tags test: " << XML_Tree->Tags->test(seq,XML_Tree->tags_len) << endl; + delete [] seq; + /// End ugly tests + s_text = ftell(fp); // loads the texts if (!XML_Tree->disable_tc){ - XML_Tree->Text = TextCollection::InitTextCollection(sample_rate_text); - XML_Tree->Text->Load(fp,sample_rate_text); + XML_Tree->Text = TextCollection::Load(fp,sample_rate_text); int sst; int st; ufread(&sst, sizeof(int),1,fp); @@ -276,7 +283,9 @@ XMLTree::~XMLTree() Tags = NULL; //Text->~TextCollection(); - delete Text; + delete TextBuilder; + TextBuilder = NULL; + delete Text; Text = NULL; initialized = false; @@ -348,7 +357,9 @@ bool XMLTree::IsChild(treeNode x, treeNode y) if (!is_ancestor(Par, x, y)) return false; return depth(Par, x) == (depth(Par, y) + 1); } - +bool XMLTree::IsFirstChild(treeNode x){ + return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == NULLT)); +} // NumChildren(x): number of children of node x. Constant time with the data structure // of Sadakane. int XMLTree::NumChildren(treeNode x) @@ -427,6 +438,14 @@ range XMLTree::DocIds(treeNode x) } range r; + if (x == NULLT) + { + r.min = NULLT; + r.max = NULLT; + return r; + }; + + if (indexing_empty_texts) { // faster, no rank needed r.min = x; r.max = x+2*subtree_size(Par, x)-2; @@ -482,6 +501,14 @@ treeNode XMLTree::FirstChild(treeNode x) return first_child(Par, x); } +treeNode XMLTree::LastChild(treeNode x) +{ + if (x == Root() || isleaf(Par,x) || x == NULLT) + return x; + else + return find_open(Par,find_close(Par,parent(Par,x))-1); +} + // NextSibling(x): returns the next sibling of node x, assuming it exists. treeNode XMLTree::NextSibling(treeNode x) { @@ -489,9 +516,9 @@ treeNode XMLTree::NextSibling(treeNode x) fprintf(stderr, "Error: data structure has not been constructed properly\n"); exit(1); } - if (x == Root()) + if (x == Root() || x==NULLT) return NULLT; - + return next_sibling(Par, x); } @@ -539,38 +566,166 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) exit(1); } - int r, s; + //int r, s; treeNode y; if (isleaf(Par,x)) return NULLT; - r = (int) Tags->rank(tag, node2tagpos(x)); - s = (int) Tags->select(tag, r+1); + int s = (int) Tags->select_next(tag,node2tagpos(x)); + /*r = (int) Tags->rank(tag, node2tagpos(x)); + s = (int) Tags->select(tag, r+1);*/ if (s == -1) return NULLT; // there is no such node y = tagpos2node(s); // transforms the tag position into a node position if (!is_ancestor(Par, x, y)) return NULLT; // the next node tagged tag (in preorder) is not within the subtree of x. else return y; } +treeNode XMLTree::TaggedDescOnly(treeNode x,TagType *desctags, unsigned int dtlen) +{ + + treeNode res,y; + if (isleaf(Par,x)) + return NULLT; + + res=NULLT; + for (unsigned int i = 0; i < dtlen; i ++ ) + { + y = TaggedDesc(x,desctags[i]); + res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; + + }; + + return res; + +} + + +treeNode XMLTree::TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen, + TagType *desctags, unsigned int dtlen) +{ + treeNode fs,y,res; + TagType tag; + + if (isleaf(Par,x)) + return NULLT; + + res = NULLT; + fs = first_child(Par,x); + while (fs != NULLT) { + tag = get_field(tags_fix,tags_blen,node2tagpos(fs)); + + /* Check for first_child */ + for (unsigned int i = 0; i < ctlen; i++) { + if (childtags[i] == tag) + return fs; + }; + + for (unsigned int i = 0; i < dtlen; i++) + if (desctags[i] == tag) + return fs; + + /* check in the descendants */ + res = NULLT; + for (unsigned int i = 0; i < dtlen; i ++ ){ + /* maybe inline by hand */ + y = TaggedDesc(fs,desctags[i]); + res = (res==NULLT || (y != NULLT) &&(y < res)) ? y : res; + }; + if (res != NULLT) + return res; + + fs = next_sibling(Par,fs); + }; + return res; + +} +treeNode XMLTree::TaggedFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root) +{ + + treeNode res,y,lim; + lim = find_close(Par,root); + res=NULLT; + for (unsigned int i = 0; i < ftlen; i ++ ) + { + y = TaggedFoll(x,folltags[i]); + res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; + + }; + + return res < lim ? res : NULLT; + +} + +treeNode XMLTree::TaggedDescOrFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root) +{ + + treeNode res,y,lim; + //int r,s; + lim = find_close(Par,root); + res=NULLT; + for (unsigned int i = 0; i < ftlen; i ++ ) + { + + int s = (int) Tags->select_next(folltags[i],node2tagpos(x)); + /*r = (int) Tags->rank(folltags[i], node2tagpos(x)); + s = (int) Tags->select(folltags[i], r+1);*/ + if (s == -1) + y = NULLT; // there is no such node + else { + y = tagpos2node(s); + if (y >= lim) + y = NULLT; + }; + res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; + + }; + + return res < lim ? res : NULLT; + +} + + // TaggedNext(x,tag): returns the first node tagged tag with larger preorder than x // Returns NULLT if there is none. -treeNode XMLTree::TaggedNext(treeNode x, TagType tag) +treeNode XMLTree::TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen, + TagType *folltags, unsigned int flen,treeNode root) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } + treeNode y,old_y,lim,res; + TagType tag; + if (x == NULLT || x == Root()) + return NULLT; - int r, s; - treeNode y; - if (x==NULLT) - return NULLT; - r = (int) Tags->rank(tag, node2tagpos(x)); - s = (int) Tags->select(tag, r+1); - if (s == -1) return NULLT; // there is no such node - y = tagpos2node(s); // transforms the tag position into a node position - return (y<=x ? NULLT : y); + lim = find_close(Par,root); + + res = NULLT; + + y = next_sibling(Par,x); + while (y != NULLT) { + tag = get_field(tags_fix,tags_blen,node2tagpos(y)); + for(unsigned int i = 0; i < ctlen;i++) + if (childtags[i] == tag) + return y; + + for(unsigned int i = 0; i < flen;i++) + if (folltags[i] == tag) + return y; + + res = TaggedBelow(y,NULL,0,folltags,flen); + if (res != NULLT) + return res; + + y = next_sibling(Par,y); + }; + //Found nothing in the following sibling of x. + res = NULLT; + for(unsigned int i = 0; i < flen;i++){ + y = TaggedFoll(x,folltags[i]); + res = (y!= x && (res == NULLT || (y != NULLT && y < res)))? y : res; + }; + + return res < lim ? res : NULLT; + } @@ -609,16 +764,33 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) exit(1); } - int r, s; + //int r, s; if (x ==NULLT || x == Root()) return NULLT; - - r = (int) Tags->rank(tag, find_close(Par, x)); - s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. + + int s = (int) Tags->select_next(tag,find_close(Par,x)); + /*r = (int) Tags->rank(tag, find_close(Par, x)); + s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. */ if (s==-1) return NULLT; else return tagpos2node(s); } +// TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in +// the subtree of x. Returns NULLT if there is none. +treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root) + { + + if (x == NULLT || x == Root()) return NULLT; + treeNode s = (treeNode) Tags->select_next(tag,find_close(Par,x)); + /*int r = (int) Tags->rank(tag, find_close(Par, x)); + int s = (int) Tags->select(tag, r+1); */ + if (root == Root()) + return s; + + if (s == NULLT || s >= find_close(Par,root)) return NULLT; + return s; + } + // TaggedFollowingSibling(x,tag): returns the first node tagged tag with larger preorder than x and not in // the subtree of x. Returns NULLT if there is none. @@ -629,14 +801,15 @@ treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) exit(1); } - int r, s; + //int r, s; treeNode ns = next_sibling(Par,x); if (x == NULLT || x == Root() || ns == -1) return NULLT; - r = (int) Tags->rank(tag, node2tagpos(ns)-1); - s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. + int s = (int) Tags->select_next(tag,node2tagpos(ns)-1); + /*r = (int) Tags->rank(tag, node2tagpos(ns)-1); + s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag.*/ if (s==-1) return NULLT; else return tagpos2node(s); } @@ -786,6 +959,29 @@ treeNode XMLTree::ParentNode(DocID d) return (treeNode)s; } +treeNode XMLTree::PrevNode(DocID d) + { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + + if (d == NULLT) + return NULLT; + + int s; + + if (indexing_empty_texts) s = d; + else s = EBVector->select1(d+1); + if (s == -1) + return NULLT; + + if (inspect(Par,s) == CP) // is a closing parenthesis + return find_open(Par, s); + else // is an opening parenthesis + return NULLT; + + } // OpenDocument(empty_texts): it starts the construction of the data structure for @@ -830,9 +1026,11 @@ int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc) if (!indexing_empty_texts) empty_texts_aux = (unsigned int *)umalloc(sizeof(unsigned int)); - - - Text = TextCollection::InitTextCollection((unsigned)sample_rate_text); + if (disable_tc) + TextBuilder = 0; + else + TextBuilder = new TextCollectionBuilder((unsigned)sample_rate_text); + Text = 0; return 1; // indicates success in the initialization of the data structure } @@ -855,36 +1053,51 @@ int XMLTree::CloseDocument() Par = (bp *)umalloc(sizeof(bp)); bp_construct(Par, npar, par_aux, OPT_DEGREE|0); // creates structure for tags - //static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20); - //static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb); - //static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb); - // If we found an attribute then "<@>" is present in the tree // if we didn't then it is not. "<$>" is never present in the tree - int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2; - - static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20); - alphabet_mapper *am = new alphabet_mapper_none(); - wt_coder * wc = new wt_coder_huff((uint*)tags_aux,npar-1,am); - Tags = new static_sequence_wvtree((uint*)tags_aux,npar-1,wc ,bmb, am); - //Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,ntagsize, bmb, ssb); uint max_tag = 0; for(uint i=0;i<(uint)npar-1;i++) max_tag = max(max_tag,tags_aux[i]); + //max_tag++; + //tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1)); + //tags_aux[npar++] = max_tag; + //int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2; + int ntagsize = 2*ntagnames + 2; + + //static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20); + //static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb); + //static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb); + static_bitsequence_builder * bmb = new static_bitsequence_builder_sdarray(); + alphabet_mapper *am = new alphabet_mapper_none(); + //wt_coder * wc = new wt_coder_huff((uint*)tags_aux,npar,am); + //Tags = new static_sequence_wvtree((uint*)tags_aux,npar,wc ,bmb, am); + //Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar,ntagsize, bmb, ssb); + Tags = new static_sequence_bs((uint*)tags_aux,npar,am,bmb); + + cout << "Tags test: " << Tags->test((uint*)tags_aux,npar) << endl; + tags_blen = bits(max_tag); - tags_len = (uint)npar-1; + tags_len = (uint)npar; tags_fix = new uint[uint_len(tags_blen,tags_len)]; - for(uint i=0;i<(uint)npar-1;i++) + for(uint i=0;i<(uint)npar;i++) set_field(tags_fix,tags_blen,i,tags_aux[i]); delete bmb; //delete pmb; //delete ssb; + + // makes the text collection static if (!disable_tc) - Text->MakeStatic(); - + { + assert(Text == 0); + assert(TextBuilder != 0); + Text = TextBuilder->InitTextCollection(); + delete TextBuilder; + TextBuilder = 0; + } + // creates the data structure marking the non-empty texts (just in the case it is necessary) if (!indexing_empty_texts) { EBVector = new static_bitsequence_rrr02((uint *)empty_texts_aux,(ulong)npar,(uint)32); @@ -1022,7 +1235,7 @@ int XMLTree::NewText(unsigned char *s) bitset(empty_texts_aux, npar-1); // marks the non-empty text with a 1 in the bit vector } - Text->InsertText(s); + TextBuilder->InsertText(s); string cpps = (char*) s; CachedText.push_back(cpps); @@ -1047,7 +1260,7 @@ int XMLTree::NewEmptyText() bitclean(empty_texts_aux, npar-1); // marks the empty text with a 0 in the bit vector } - else Text->InsertText(&c); // we insert the empty text just in case we index all the texts + else TextBuilder->InsertText(&c); // we insert the empty text just in case we index all the texts return 1; // success } @@ -1061,7 +1274,7 @@ TagType XMLTree::GetTagId(unsigned char *tagname) // this should be changed for more efficient processing for (i=0; i= ntagnames) return NULL; // invalid tag identifier s = (unsigned char *)umalloc((strlen((const char *)TagName[tagid])+1)*sizeof(unsigned char)); strcpy((char *)s, (const char *)TagName[tagid]); @@ -1083,6 +1296,7 @@ unsigned char *XMLTree::GetTagName(TagType tagid) const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) { + if(tagid==(uint)-1) return NULL; if (tagid >= ntagnames) return NULL; // invalid tag identifier return ((const unsigned char*) TagName[tagid]); }