X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=a1eb13c4a188f5d8c83aa6dce1d7fba499ba5737;hb=32dc08cc3c732aff96456d1a596bd3825c5c5c51;hp=ae80fc2a489680d270c6fba2d59939a8c9bddc00;hpb=b53633fb64f387edb5cebefbb3308b6347b2389c;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index ae80fc2..a1eb13c 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,730 +1,654 @@ +#include "basics.h" #include "XMLTree.h" -#include - -// functions to convert tag positions to the corresponding tree node and viceversa. -// These are implemented in order to be able to change the tree and Tags representations, +#include "timings.h" +#include +using std::cout; +using std::endl; +using std::min; +using std::string; + +// functions to convert tag positions to the corresponding tree node and viceversa. +// These are implemented in order to be able to change the tree and Tags representations, // without affecting the code so much. // Current implementation corresponds to balanced-parentheses representation for // the tree, and storing 2 tags per tree node (opening and closing tags). -// tag position -> tree node -inline treeNode tagpos2node(int t) { - return (treeNode)t; -} -// tree node -> tag position -inline int node2tagpos(treeNode x) { - return (int)x; +static int bits8 (int t ) { + int r = bits(t); + if (r <= 8) + return 8; + else if (r <= 16) + return 16; + else + return r; } -//KIM OJO to prevent suprious "unused result" warnings -inline void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream){ - size_t res; - res = fread(ptr,size,nmemb,stream); - if (res < nmemb) - throw "ufread I/O error"; +static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){ - return; -} + if (tag == PCDATA_TAG_ID){ + x = x+2; + return fast_inspect(Par,x)==OP ? x : NULLT; + } else return fast_next_sibling(Par,x); -inline void ufwrite(const void *ptr, size_t size, size_t nmemb, FILE *stream){ - size_t res; - res = fwrite(ptr,size,nmemb,stream); - if (res < nmemb) - throw "ufwrite I/O error"; - return; } -// OJO to fail cleanly while doing a realloc -// if we can't realloc we are pretty much screwed anyway but -// it makes the code clearer to not have a bunch of if (!ptr) { printf("..."); exit(1); }; -inline void * urealloc(void *ptr, size_t size){ - void * dest = realloc(ptr,size); - //don't fail if we requested size 0 - if (dest == NULL && size > 0 ) - throw std::bad_alloc(); - return dest; -} -inline void * ucalloc(size_t nmemb, size_t size){ +inline uint get_field_no_power(uint *A, uint len, uint index) { - void * dest = calloc(nmemb,size); - //don't fail if we requested size 0 - if (dest == NULL && nmemb > 0 && size > 0 ) - throw std::bad_alloc(); - return dest; + register uint i=index*len/W, j=index*len-W*i; + return (j+len <= W) ? (A[i] << (W-j-len)) >> (W-len) : (A[i] >> j) | (A[i+1] << (WW-j-len)) >> (W-len); } -inline void * umalloc(size_t size){ - void * dest = malloc(size); - if (dest == NULL && size > 0) - throw std::bad_alloc(); - return dest; -} +static uint fast_get_field(uint* A,int len, int idx) +{ + uint f1, f2; + switch (len) { + case 8: + return (uint) (((uchar*)A)[idx]); + case 16: + f2 = ((unsigned short*)A)[idx]; + f1 = ((unsigned short*)A)[idx+1]; + return (f1 << 16) + f2; + default: + return get_field_no_power (A,len,idx); + }; -void XMLTree::print_stats() { - uint total_space = Tags->size()+sizeof(static_sequence*); - total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)); - cout << "Space usage for XMLTree:" << endl - << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl - << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl - << " ... add Diego structures ... " << endl - << " *total* " << total_space << endl; } -// Save: saves XML tree data structure to file. -void XMLTree::Save(unsigned char *filename) + + + +XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, + uint *empty_texts_bmp, TagType *tags, + TextCollection * const TC, bool dis_tc, + TextCollectionBuilder::index_type_t _index_type ) + { + buffer = 0; + print_stack = 0; + // creates the data structure for the tree topology + Par = (bp *)umalloc(sizeof(bp)); + STARTTIMER(); + bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0); + STOPTIMER(Building); + PRINTTIME("Building parenthesis struct", Building); + STARTTIMER(); + + + // creates structure for tags + + TagName = (vector*)TN; + tIdMap = (TagIdMap *) tim; + + uint max_tag = TN->size() - 1; + + + static_bitsequence_builder *bmb = new static_bitsequence_builder_sdarray(); + alphabet_mapper *am = new alphabet_mapper_none(); + Tags = new static_sequence_bs((uint*)tags,npar,am,bmb); + + //cout << "Tags test: " << Tags->test((uint*)tags,npar) << endl; + + //Ensures that for small tag numbers, we are on an 8bit boundary. + //Makes tag access way faster with negligeable waste of space. + tags_blen = bits8(max_tag); + std::cerr << "Tags blen is " << tags_blen << "\n"; + tags_len = (uint)npar; + tags_fix = new uint[uint_len(tags_blen,tags_len)]; + for(uint i=0;i<(uint)npar;i++) + set_field(tags_fix,tags_blen,i,tags[i]); + delete bmb; + free(tags); + tags = NULL; + + STOPTIMER(Building); + PRINTTIME("Building Tag Structure", Building); + + Text = (TextCollection*) TC; + + + EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32); + //EBVector = new static_bitsequence_sdarray(empty_texts_bmp,npar); + free(empty_texts_bmp); + empty_texts_bmp = NULL; + + + disable_tc = dis_tc; + text_index_type = _index_type; + std::cerr << "Number of distinct tags " << TagName->size() << "\n"; + //std::cerr.flush(); + } + + +// ~XMLTree: frees memory of XML tree. +XMLTree::~XMLTree() + { + int i; + + destroyTree(Par); + free(Par); // frees the memory of struct Par + + delete tIdMap; + tIdMap = NULL; + + delete TagName; + TagName = NULL; + + delete Tags; + Tags = NULL; + + delete Text; + Text = NULL; + + delete EBVector; + EBVector = NULL; + + } + + +void XMLTree::print_stats() { + uint total_space = Tags->size()+sizeof(static_sequence*); + total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)); + cout << "Space usage for XMLTree:" << endl + << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl + << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl + << " ... add Diego structures ... " << endl + << " *total* " << total_space << endl; + } +// Save: saves XML tree data structure to file. +void XMLTree::Save(int fd, char * name) + { FILE *fp; - char filenameaux[1024]; int i; - - sprintf(filenameaux, "%s.srx", filename); - fp = fopen(filenameaux, "w"); - if (fp == NULL) { - printf("Error: cannot create file %s to store the tree structure of XML collection\n", filenameaux); - exit(1); - } - + + fp = fdopen(fd, "wa"); // first stores the tree topology saveTree(Par, fp); - + // stores the table with tag names - ufwrite(&ntagnames, sizeof(int), 1, fp); - for (i=0; isave(fp); - + int ntags = TagName->size(); + + ufwrite(&ntags, sizeof(int), 1, fp); + for (i = 0; iat(i).c_str()); + + // stores the tags Tags->save(fp); - ufwrite(&tags_blen,sizeof(uint),1,fp); - ufwrite(&tags_len,sizeof(uint),1,fp); - ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp); + ufwrite(&tags_blen,sizeof(uint),1,fp); + ufwrite(&tags_len,sizeof(uint),1,fp); + ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp); - // stores the texts + // flags + ufwrite(&disable_tc, sizeof(bool),1,fp); + + //text positions + EBVector->save(fp); + + // stores the texts if (!disable_tc) { - Text->Save(fp); - int st = CachedText.size(); - ufwrite(&st, sizeof(int),1,fp); - for (int i = 0; i< CachedText.size(); i++){ - st = CachedText.at(i).size(); - ufwrite(&st, sizeof(int),1,fp); - ufwrite(CachedText.at(i).c_str(),sizeof(char),1+CachedText.at(i).size(),fp); + + ufwrite(&text_index_type, sizeof(TextCollectionBuilder::index_type_t), 1, fp); + + + string file(name); + switch (text_index_type){ + case TextCollectionBuilder::index_type_default: + file.append(".default"); + break; + case TextCollectionBuilder::index_type_swcsa: + file.append(".swcsa"); + break; + case TextCollectionBuilder::index_type_rlcsa: + file.append(".rlcsa"); + break; }; - }; - fclose(fp); - } + Text->Save(fp, file.c_str()); + } + } + // Load: loads XML tree data structure from file. Returns // a pointer to the loaded data structure -XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) +XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name) { FILE *fp; char buffer[1024]; XMLTree *XML_Tree; int i; - size_t s_tree = 0; - long s_text = 0; - size_t s_tags = 0; - - // first load the tree topology - sprintf(buffer, "%s.srx", filename); - fp = fopen(buffer, "r"); - if (fp == NULL) { - printf("Error: cannot open file %s to load the tree structure of XML collection\n", buffer); - exit(1); - } - XML_Tree = new XMLTree(); + buffer[1023] = '\0'; - XML_Tree->Par = (bp *)umalloc(sizeof(bp)); + fp = fdopen(fd, "r"); - loadTree(XML_Tree->Par, fp); + XML_Tree = new XMLTree(); + STARTTIMER(); + // Load the tree structure + XML_Tree->Par = (bp *)umalloc(sizeof(bp)); - s_tree += sizeof(bp); + loadTree(XML_Tree->Par, fp); + STOPTIMER(Loading); + PRINTTIME("Loading parenthesis struct", Loading); + STARTTIMER(); - // stores the table with tag names - ufread(&XML_Tree->ntagnames, sizeof(int), 1, fp); - - s_tree += sizeof(int); + XML_Tree->TagName = new std::vector(); + XML_Tree->tIdMap = new std::unordered_map(); + std::string s; + int ntags; - XML_Tree->TagName = (unsigned char **)umalloc(XML_Tree->ntagnames*sizeof(unsigned char *)); - - s_tags += sizeof(unsigned char*)*XML_Tree->ntagnames; + // Load the tag names + ufread(&ntags, sizeof(int), 1, fp); + for (i=0; iTagName->push_back(s); + XML_Tree->tIdMap->insert(std::make_pair(s,i)); - for (i=0; intagnames;i++) { - - // OJO Kim is it needed ? - int k = feof(fp); + }; + STOPTIMER(Loading); + PRINTTIME("Loading tag names struct", Loading); + STARTTIMER(); - - // fscanf chokes on "\n" which is the case for the root element - char * r = fgets(buffer,1023,fp); - // int r = fscanf(fp, "%s\n",buffer); - if (r==NULL) - throw "Cannot read tag list"; + // loads the tag structure + XML_Tree->Tags = static_sequence::load(fp); + ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp); + std::cerr << "tags_blen is "<< XML_Tree->tags_blen <<"\n"; + ufread(&XML_Tree->tags_len,sizeof(uint),1,fp); + XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)]; + ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp); + + // TODO ask francisco about this + /// 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; + //XML_Tree->Tags->test(seq,XML_Tree->tags_len); + //delete [] seq; + /// End ugly tests + + STOPTIMER(Loading); + std::cerr << (uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/(1024*1024) << " MB for tag sequence" << std::endl; + PRINTTIME("Loading tag struct", Loading); + STARTTIMER(); - // strlen is actually the right size, since there is a trailing '\n' - int len = strlen((const char*)buffer); - XML_Tree->TagName[i] = (unsigned char *)ucalloc(len,sizeof(char)); - strncpy((char *)XML_Tree->TagName[i], (const char *)buffer,len - 1); - s_tags+= len*sizeof(char); - } - // loads the flags - ufread(&(XML_Tree->indexing_empty_texts), sizeof(bool), 1, fp); - ufread(&(XML_Tree->initialized), sizeof(bool), 1, fp); - ufread(&(XML_Tree->finished), sizeof(bool), 1, fp); ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp); - - s_tree+=sizeof(bool)*4; - - if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); - - s_tree+= XML_Tree->EBVector->size(); - - // loads the tags - XML_Tree->Tags = static_sequence::load(fp); - ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp); - ufread(&XML_Tree->tags_len,sizeof(uint),1,fp); - XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)]; - ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp); - 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); - int sst; - int st; - ufread(&sst, sizeof(int),1,fp); - for (int i=0;iCachedText.push_back(cppstr); - free(str); - }; - + if (load_tc) { + XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); + + STOPTIMER(Loading); + PRINTTIME("Loading text bitvector struct", Loading); + STARTTIMER(); + + // Not used + // loads the texts + if (!XML_Tree->disable_tc){ + ufread(&(XML_Tree->text_index_type), + sizeof(TextCollectionBuilder::index_type_t), 1, fp); + string file(name); + switch (XML_Tree->text_index_type){ + case TextCollectionBuilder::index_type_default: + file.append(".default"); + break; + case TextCollectionBuilder::index_type_swcsa: + file.append(".swcsa"); + break; + case TextCollectionBuilder::index_type_rlcsa: + file.append(".rlcsa"); + break; + }; + XML_Tree->Text = TextCollection::Load(fp, file.c_str(), TextCollection::index_mode_default, sample_factor); + + } + else XML_Tree->Text = NULL; + STOPTIMER(Loading); + PRINTTIME("Loading TextCollection", Loading); + STARTTIMER(); } else { + XML_Tree->EBVector = NULL; XML_Tree->Text = NULL; - } - s_text = ftell(fp) - s_text; - - - + XML_Tree->disable_tc = true; + }; - fclose(fp); - /*std::cerr << "Tree part is " << s_tree/1024 << " Kbytes,\n" - << "with node->tagid part " << XML_Tree->Tags->size()/1024+(uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/1024 << "Kbytes \n" - << "size of Tag part : " << XML_Tree->Tags->length () << " elements\n" - << "sizof(unsigned int)* " << XML_Tree->Tags->length () << " = " << - sizeof(unsigned int) * XML_Tree->Tags->length () / 1024 << " Kbytes\n" - << "Tag part is " << s_tags/1024 << " Kbytes,\n" - << "Text collection is " << s_text/1024 << " Kbytes \n";*/ - XML_Tree->print_stats(); return XML_Tree; } -// ~XMLTree: frees memory of XML tree. -XMLTree::~XMLTree() - { - int i; - - destroyTree(Par); - free(Par); // frees the memory of struct Par - - for (i=0; i~static_bitsequence_rrr02(); - delete EBVector; - EBVector = NULL; - } - - //Tags->~static_sequence_wvtree(); - delete Tags; - Tags = NULL; - - //Text->~TextCollection(); - delete Text; - Text = NULL; - - initialized = false; - finished = false; - } - -// root(): returns the tree root. -treeNode XMLTree::Root() - { - if (!finished) { - fprintf(stderr, "Root() : Error: data structure has not been constructed properly\n"); - exit(1); - } - return root_node(Par); - } // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x. -int XMLTree::SubtreeSize(treeNode x) +/*int XMLTree::SubtreeSize(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } return subtree_size(Par, x); } - +*/ // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x. -int XMLTree::SubtreeTags(treeNode x, TagType tag) +/* +int XMLTree::SubtreeTags(treeNode x, TagType tag) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } if (x == Root()) - x = first_child(Par,x); - + x = fast_first_child(Par,x); + int s = x + 2*subtree_size(Par, x) - 1; - - return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1); + + return (Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1))+1; + } +*/ +int XMLTree::SubtreeElements(treeNode x) + { + + int size = subtree_size(Par,x); + if (x == Root()){ + x = fast_first_child(Par,x); + size = size - 1; + }; + + int s = x + 2*size - 1; + int ntext = Tags->rank(PCDATA_TAG_ID, s) - Tags->rank(PCDATA_TAG_ID, node2tagpos(x)-1); + size = size - ntext; + treeNode fin = fast_find_close(Par,x); + treeNode y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(x)); + while (y != NULLT && y < fin){ + size -= SubtreeSize(y); + y = Tags->select_next(ATTRIBUTE_TAG_ID,node2tagpos(y)); + }; + return size; } // IsLeaf(x): returns whether node x is leaf or not. In the succinct representation // this is just a bit inspection. -bool XMLTree::IsLeaf(treeNode x) +bool XMLTree::IsLeaf(treeNode x) { - return isleaf(Par, x); - } + NULLT_IF(x==NULLT); + return fast_isleaf(Par, x); + } // IsAncestor(x,y): returns whether node x is ancestor of node y. -bool XMLTree::IsAncestor(treeNode x, treeNode y) +bool XMLTree::IsAncestor(treeNode x, treeNode y) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - return is_ancestor(Par, x, y); + return fast_is_ancestor(Par, x, y); } // IsChild(x,y): returns whether node x is parent of node y. -bool XMLTree::IsChild(treeNode x, treeNode y) +bool XMLTree::IsChild(treeNode x, treeNode y) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (!is_ancestor(Par, x, y)) return false; + if (!fast_is_ancestor(Par, x, y)) return false; return depth(Par, x) == (depth(Par, y) + 1); } +// IsFirstChild(x): returns whether node x is the first child of its parent. +/*bool XMLTree::IsFirstChild(treeNode x) + { + return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1)); + } +*/ + // NumChildren(x): number of children of node x. Constant time with the data structure // of Sadakane. -int XMLTree::NumChildren(treeNode x) +int XMLTree::NumChildren(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - return degree(Par, x); } // ChildNumber(x): returns i if node x is the i-th children of its parent. -int XMLTree::ChildNumber(treeNode x) +int XMLTree::ChildNumber(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - return child_rank(Par, x); } // Depth(x): depth of node x, a simple binary rank on the parentheses sequence. -int XMLTree::Depth(treeNode x) +int XMLTree::Depth(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - return depth(Par, x); } // Preorder(x): returns the preorder number of node x, just counting the tree // nodes (i.e., tags, it disregards the texts in the tree). -int XMLTree::Preorder(treeNode x) +int XMLTree::Preorder(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - return preorder_rank(Par, x); } // Postorder(x): returns the postorder number of node x, just counting the tree // nodes (i.e., tags, it disregards the texts in the tree). -int XMLTree::Postorder(treeNode x) +int XMLTree::Postorder(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } return postorder_rank(Par, x); } - +/* // Tag(x): returns the tag identifier of node x. -TagType XMLTree::Tag(treeNode x) +TagType XMLTree::Tag(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - return get_field(tags_fix,tags_blen,node2tagpos(x)); //Tags->access(node2tagpos(x)); + return fast_get_field(tags_fix,tags_blen,node2tagpos(x)); } - +*/ // DocIds(x): returns the range of text identifiers that descend from node x. // returns {NULLT, NULLT} when there are no texts descending from x. -range XMLTree::DocIds(treeNode x) +range XMLTree::DocIds(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - 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; - } - else { // we are not indexing empty texts, we need rank - int min = EBVector->rank1(x-1); - int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); - if (min==max) { // range is empty, no texts within the subtree of x - r.min = NULLT; - r.max = NULLT; - } - else { // the range is non-empty, there are texts within the subtree of x - r.min = min+1; - r.max = max; - } - } - return r; + range r; + if (x == NULLT) { + r.min = NULLT; + r.max = NULLT; + return r; + }; + int min = EBVector->rank1(x-1); + int max = EBVector->rank1(x+2*subtree_size(Par, x)-2); + if (min==max) { // range is empty, no texts within the subtree of x + r.min = NULLT; + r.max = NULLT; + } + else { // the range is non-empty, there are texts within the subtree of x + r.min = min+1; + r.max = max; + } + return r; } // Parent(x): returns the parent node of node x. -treeNode XMLTree::Parent(treeNode x) +/* +treeNode XMLTree::Parent(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } if (x == Root()) return NULLT; else - return parent(Par, x); - } + return parent(Par, x);; + }*/ // Child(x,i): returns the i-th child of node x, assuming it exists. -treeNode XMLTree::Child(treeNode x, int i) +treeNode XMLTree::Child(treeNode x, int i) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - if (i <= OPTD) return naive_child(Par, x, i); else return child(Par, x, i); - } +} // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP. -treeNode XMLTree::FirstChild(treeNode x) +/* +treeNode XMLTree::FirstChild(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - return first_child(Par, x); + NULLT_IF(x==NULLT); + return fast_first_child(Par, x); } - +*/ +/* +treeNode XMLTree::FirstElement(treeNode x) + { + NULLT_IF(x==NULLT); + x = fast_first_child(Par, x); + NULLT_IF(x == NULLT); + switch (Tag(x)){ + + case PCDATA_TAG_ID: + x = x+2; + return (fast_inspect(Par,x)==OP)? x : NULLT; + + case ATTRIBUTE_TAG_ID: + x = fast_next_sibling(Par,x); + if (x != NULLT && Tag(x) == PCDATA_TAG_ID){ + x = x+2; + return (fast_inspect(Par,x)==OP)? x : NULLT; + } + else return x; + default: + return x; + } + } +*//* +treeNode XMLTree::NextElement(treeNode x) +{ + NULLT_IF(x==NULLT); + x = fast_next_sibling(Par, x); + NULLT_IF(x == NULLT); + if (Tag(x) == PCDATA_TAG_ID){ + x = x+2; + return (fast_inspect(Par,x)==OP)? x : NULLT; + } + else return x; + }*/ + +// LastChild(x): returns the last child of node x. + /*treeNode XMLTree::LastChild(treeNode x) + { + NULLT_IF(x == NULLT || fast_isleaf(Par,x)); + return find_open(Par, fast_find_close(Par, x)-1); + } + */ // NextSibling(x): returns the next sibling of node x, assuming it exists. -treeNode XMLTree::NextSibling(treeNode x) +/*treeNode XMLTree::NextSibling(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - if (x == Root() || x==NULLT) - return NULLT; - - return next_sibling(Par, x); + NULLT_IF(x==NULLT || x == Root() ); + x = fast_find_close(Par,x)+1; + return (fast_inspect(Par,x) == CP ? NULLT : x); } +*/ // PrevSibling(x): returns the previous sibling of node x, assuming it exists. -treeNode XMLTree::PrevSibling(treeNode x) +/*treeNode XMLTree::PrevSibling(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - return prev_sibling(Par, x); + NULLT_IF(x==NULLT); + return prev_sibling(Par, x); } - -// TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or NULLT if there is none. +*/ +// TaggedChild(x,tag): returns the first child of node x tagged tag, or NULLT if there is none. // Because of the balanced-parentheses representation of the tree, this operation is not supported // efficiently, just iterating among the children of node x until finding the desired child. -treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag) +/* +treeNode XMLTree::TaggedChild(treeNode x, TagType tag) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - treeNode child; - - child = first_child(Par, x); // starts at first child of node x - if (child==(treeNode)-1) return NULLT; // node x is a leaf, there is no such child - while (child!=(treeNode)-1) { - if (get_field(tags_fix,tags_blen,node2tagpos(child)) /*Tags->access(node2tagpos(child))*/ == tag) { // current child is labeled with tag of interest - i--; - if (i==0) return child; // we have seen i children of x tagged tag, this is the one we are looking for - } - child = next_sibling(Par, x); // OK, let's try with the next child - } - return NULLT; // no such child was found + NULLT_IF(x==NULLT || fast_isleaf(Par,x)); + treeNode child; + child = fast_first_child(Par, x); // starts at first child of node x + if (Tag(child) == tag) + return child; + else + return TaggedFollowingSibling(child,tag); } -// TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within -// the subtree of x. Returns NULLT if there is none. -treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - 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); - 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) +// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none. +treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) +{ + NULLT_IF(x==NULLT); + treeNode sibling = fast_next_sibling(Par, x); + TagType ctag; + while (sibling != NULLT) { + ctag = Tag(sibling); + if (ctag == tag) // current sibling is labeled with tag of interest + return sibling; + sibling = fast_sibling(Par, sibling, ctag); // OK, let's try with the next sibling + } + return NULLT; // no such sibling was found +} +*/ +treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags) { - 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; - + NULLT_IF(x==NULLT || fast_isleaf(Par,x)); + int i; + treeNode child = fast_first_child(Par, x); + TagType t; + while (child != NULLT) { + t = Tag(child); + if (tags->find(t) != tags->end()) return child; + child = fast_sibling(Par, child,t); + } + return NULLT; } -treeNode XMLTree::TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen, - TagType *desctags, unsigned int dtlen) +treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags) { - 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) -{ + NULLT_IF(x==NULLT); + int i; + TagType t; + treeNode sibling = fast_next_sibling(Par, x); + while (sibling != NULLT) { + t = Tag(sibling); + if (tags->find(t) != tags->end()) return sibling; + sibling = fast_sibling(Par, sibling,t); + } + return NULLT; + } - 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) -{ +// TaggedDescendant(x,tag): returns the first node tagged tag with larger preorder than x and within +// the subtree of x. Returns NULLT if there is none. +/* +treeNode XMLTree::TaggedDescendant(treeNode x, TagType tag) + { + //NULLT_IF(x==NULLT || fast_isleaf(Par,x)); - treeNode res,y,lim; - int r,s; - lim = find_close(Par,root); - res=NULLT; - for (unsigned int i = 0; i < ftlen; i ++ ) - { - - 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; - -} + int s = (int) Tags->select_next(tag,node2tagpos(x)); + NULLT_IF (s == -1); + treeNode y = tagpos2node(s); // transforms the tag position into a node position -// 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 *childtags, unsigned int ctlen, - TagType *folltags, unsigned int flen,treeNode root) + return (fast_is_ancestor(Par,x,y) ? y : NULLT); + } +*/ +/* +treeNode XMLTree::SelectDescendant(treeNode x, TagIdSet *tags) { - treeNode y,old_y,lim,res; - TagType tag; - if (x == NULLT || x == Root()) - return NULLT; - - - 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; + NULLT_IF (x ==NULLT || fast_isleaf(Par,x)); + int i; + treeNode min = NULLT; + treeNode fc = fast_first_child(Par,x); + treeNode aux; + TagIdSet::const_iterator tagit; + for (tagit = tags->begin(); tagit != tags->end(); tagit++) { + aux = TaggedDescendant(x, (TagType) *tagit); + if (aux == fc) return fc; + if (aux == NULLT) continue; + if ((min == NULLT) || (aux < min)) min = aux; }; - - return res < lim ? res : NULLT; - + return min; } +*/ // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an // ancestor of x. Returns NULLT if there is none. -treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) +treeNode XMLTree::TaggedPreceding(treeNode x, TagType tag) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - int r, s; treeNode node_s, root; r = (int)Tags->rank(tag, node2tagpos(x)-1); @@ -732,569 +656,374 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) s = (int)Tags->select(tag, r); root = root_node(Par); node_s = tagpos2node(s); - while (is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x + while (fast_is_ancestor(Par, node_s, x) && (node_s!=root)) { // the one that we found is an ancestor of x r--; if (r==0) return NULLT; // there is no such node s = (int)Tags->select(tag, r); // we should use select_prev instead when provided node_s = tagpos2node(s); } - return NULLT; // there is no such node + return NULLT; // there is no such node } // 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::TaggedFoll(treeNode x, TagType tag) +treeNode XMLTree::TaggedFollowing(treeNode x, TagType tag) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } + NULLT_IF (x ==NULLT || x == Root()); + return tagpos2node(Tags->select_next(tag,fast_find_close(Par, x))); - 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. - 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) +// TaggedFollBelow(x,tag,root): 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::TaggedFollowingBelow(treeNode x, TagType tag, treeNode ancestor) +{ + // NULLT_IF (x == NULLT || x == Root() || x == ancestor); + + //Special optimisation, test for the following sibling first + treeNode close = fast_find_close(Par, x); + treeNode s = tagpos2node(Tags->select_next(tag, close)); + + if (ancestor == Root() || s==NULLT || s < fast_find_close(Par,ancestor)) return s; + else return NULLT; +} +*/ + /* +treeNode XMLTree::TaggedFollowingBefore(treeNode x, TagType tag, treeNode closing) +{ + + NULLT_IF (x == NULLT || x == Root()); + + treeNode s = tagpos2node(Tags->select_next(tag, fast_find_close(Par, x))); + NULLT_IF (s == NULLT || s >= closing); + + return s; +} + */ +/* Here we inline TaggedFoll to find the min globally, and only at the end + we check if the min is below the context node */ +treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor) { - int r, s; - int lim = node2tagpos(find_close(Par,root)); - 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. - if (s==-1 || s >= lim) - return NULLT; - else - return tagpos2node(s); - } + NULLT_IF(x==NULLT || x==Root()); + treeNode close = fast_find_close(Par,x); + treeNode ns = close+1; + if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end())) + return ns; -// 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. -treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) + int i; + treeNode min = NULLT; + treeNode aux; + + + TagIdSet::const_iterator tagit; + for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { + + aux = tagpos2node(Tags->select_next(*tagit, close)); + if (aux == NULLT) continue; + if ((min == NULLT) || (aux < min)) min = aux; + }; + + // found the smallest node in preorder which is after x. + // if ctx is the root node, just return what we found. + + if (ancestor == Root() || min == NULLT || min < fast_find_close(Par, ancestor)) return min; + else return NULLT; + + } +/* +treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode ancestor_closing) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - int r, s; - treeNode ns = next_sibling(Par,x); + NULLT_IF(x==NULLT || x==Root()); - if (x == NULLT || x == Root() || ns == -1) - return NULLT; + treeNode close = fast_find_close(Par,x); + treeNode ns = close+1; + if ( (fast_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end())) + return ns; + + int i; + treeNode min = NULLT; + treeNode aux; + + + TagIdSet::const_iterator tagit; + for (tagit = tags->begin(); tagit != tags->end(); ++tagit) { + + aux = tagpos2node(Tags->select_next(*tagit, close)); + if (aux == NULLT) continue; + if ((min == NULLT) || (aux < min)) min = aux; + }; + + // found the smallest node in preorder which is after x. + // if ctx is the root node, just return what we found. + + if (ancestor_closing == Root() || min == NULLT || min < ancestor_closing) return min; + else 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. - if (s==-1) return NULLT; - else return tagpos2node(s); } +*/ +/* +treeNode XMLTree::SelectFollowingBefore(treeNode x, TagIdSet *tags, treeNode closing) + { + + NULLT_IF(x==NULLT || x==Root()); + int i; + treeNode min = NULLT; + treeNode ns = fast_next_sibling(Par, x); + treeNode close = ns - 1; + treeNode aux; + TagIdSet::const_iterator tagit; + for (tagit = tags->begin(); tagit != tags->end(); tagit++) { + aux = tagpos2node(Tags->select_next(*tagit, close)); + + // The next sibling of x is guaranteed to be below ctx + // and is the node with lowest preorder which is after ctx. + // if we find it, we return early; + + if (aux == ns ) return ns; + if (aux == NULLT) continue; + if ((min == NULLT) || (aux < min)) min = aux; + }; + + // found the smallest node in preorder which is after x. + // if ctx is the root node, just return what we found. + + NULLT_IF (min == NULLT || min >= closing); + + return min; + + } +*/ // TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return // NULLT is there is none. treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - if (x == NULLT || x == Root()) return NULLT; - + treeNode s = parent(Par, x), r = Root(); while (s != r) { - if (get_field(tags_fix,tags_blen,node2tagpos(s)) /*Tags->access(node2tagpos(s))*/ == tag) return s; + if (Tag(s) == tag) return s; s = parent(Par, s); } return NULLT; } -// PrevText(x): returns the document identifier of the text to the left -// of node x, or NULLT if x is the root node or the text is empty. -// Assumes Doc ids start from 0. -DocID XMLTree::PrevText(treeNode x) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - if (x == Root()) return NULLT; - if (indexing_empty_texts) // faster, no rank needed - return (DocID)x-1; - else { // we are not indexing empty texts, rank is needed - if (EBVector->access(x-1) == 0) - return (DocID)NULLT; // there is no text to the left of node (text is empty) - else - return (DocID)EBVector->rank1(x-1)-1; //-1 because document ids start from 0 - } - } - -// NextText(x): returns the document identifier of the text to the right -// of node x, or NULLT if x is the root node. Assumes Doc ids start from 0. -DocID XMLTree::NextText(treeNode x) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } +// MyText(x): returns the document identifier of the text below node x, +// or NULLT if x is not a leaf node or the text is empty. Assumes Doc +// ids start from 0. +DocID XMLTree::MyText(treeNode x) +{ + TagType tag = Tag(x); + // seems faster than testing EBVector->access(x); - if (x == Root()) return NULLT; - if (indexing_empty_texts) // faster, no rank needed - return (DocID)x+2*subtree_size(Par, x)-1; - else { // we are not indexing empty texts, rank is needed - int p = x+2*subtree_size(Par, x)-1; - if (EBVector->access(p) == 0) // there is no text to the right of node - return (DocID)NULLT; - else - return (DocID)EBVector->rank1(p)-1; //-1 because document ids start from 0 - } - } + if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID) + return (DocID) (EBVector->rank1(x)-1); + else + return (DocID) NULLT; -// MyText(x): returns the document identifier of the text below node x, -// or NULLT if x is not a leaf node or the text is empty. Assumes Doc +} +// MyText(x): returns the document identifier of the text below node x, +// or NULLT if x is not a leaf node or the text is empty. Assumes Doc // ids start from 0. -DocID XMLTree::MyText(treeNode x) - { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (!IsLeaf(x)) return NULLT; - if (indexing_empty_texts) // faster, no rank needed - return (DocID)x; - else { // we are not indexing empty texts, rank is needed - if (EBVector->access(x) == 0) // there is no text below node x - return (DocID)NULLT; - else - return (DocID)EBVector->rank1(x)-1; //-1 because document ids start from 0 - } - } +DocID XMLTree::MyTextUnsafe(treeNode x) +{ + return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0 +} // TextXMLId(d): returns the preorder of document with identifier d in the tree consisting of // all tree nodes and all text nodes. Assumes that the tree root has preorder 1. -int XMLTree::TextXMLId(DocID d) +int XMLTree::TextXMLId(DocID d) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } + NULLT_IF(d == NULLT); + int s = EBVector->select1(d+1); + return rank_open(Par, s) + d + 1; // +1 because root has preorder 1 - if (indexing_empty_texts) - return d + rank_open(Par, d)+1; // +1 because root has preorder 1 - else { // slower, needs rank and select - int s = EBVector->select1(d+1); - return rank_open(Par, s) + d + 1; // +1 because root has preorder 1 - } } -// NodeXMLId(x): returns the preorder of node x in the tree consisting +// NodeXMLId(x): returns the preorder of node x in the tree consisting // of all tree nodes and all text nodes. Assumes that the tree root has // preorder 0; -int XMLTree::NodeXMLId(treeNode x) +int XMLTree::NodeXMLId(treeNode x) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (indexing_empty_texts) - return x - 1 + rank_open(Par, x); - else { - if (x == Root()) return 1; // root node has preorder 1 - else - return rank_open(Par, x) + EBVector->rank1(x-1); - } + NULLT_IF(x == NULLT); + if (x == Root()) return 1; // root node has preorder 1 + return rank_open(Par, x) + EBVector->rank1(x-1); } // ParentNode(d): returns the parent node of document identifier d. -treeNode XMLTree::ParentNode(DocID d) +treeNode XMLTree::ParentNode(DocID d) { - if (!finished) { - fprintf(stderr, "Error: data structure has not been constructed properly\n"); - exit(1); - } - - if (d == NULLT) - return NULLT; - - int s; - // OJO : Kim : I added the d+1. before that, else branch was - // EBVector->select1(d) - // and gave wrong results (I'm really poking a bear with a stick here). - if (indexing_empty_texts) s = d; - else s = EBVector->select1(d+1); - - if (inspect(Par,s) == CP) // is a closing parenthesis - return parent(Par, find_open(Par, s)); - else // is an opening parenthesis - return (treeNode)s; - + NULLT_IF (d == NULLT); + return (treeNode) EBVector->select1(d+1); } -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 -// the XML document. Parameter empty_texts indicates whether we index empty texts -// in document or not. Returns a non-zero value upon success, NULLT in case of error. -int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc) +// GetTagId: returns the tag identifier corresponding to a given tag name. +// Returns NULLT in case that the tag name does not exists. +TagType XMLTree::GetTagId(unsigned char *tagname) { - initialized = true; - finished = false; - found_attributes = false; - npar = 0; - parArraySize = 1; - ntagnames = 4; - disable_tc = dtc; - - indexing_empty_texts = empty_texts; - - par_aux = (pb *)umalloc(sizeof(pb)*parArraySize); - - tags_aux = (TagType *) umalloc(sizeof(TagType)); - - TagName = (unsigned char **) umalloc(4*sizeof(unsigned char*)); - - TagName[0] = (unsigned char *) umalloc(4*sizeof(unsigned char)); - - strcpy((char *) TagName[0], "<@>"); - - TagName[1] = (unsigned char *) umalloc(4*sizeof(unsigned char)); - - strcpy((char *) TagName[1], "<$>"); - - //OJO need to put these in the table too. - TagName[2] = (unsigned char *) umalloc(5*sizeof(unsigned char)); - - strcpy((char *) TagName[2], "/<@>"); - - TagName[3] = (unsigned char *) umalloc(5*sizeof(unsigned char)); - - strcpy((char *) TagName[3], "/<$>"); - - - if (!indexing_empty_texts) - empty_texts_aux = (unsigned int *)umalloc(sizeof(unsigned int)); - - - - Text = TextCollection::InitTextCollection((unsigned)sample_rate_text); - - return 1; // indicates success in the initialization of the data structure - } -// CloseDocument(): it finishes the construction of the data structure for the XML -// document. Tree and tags are represented in the final form, dynamic data -// structures are made static, and the flag "finished" is set to true. After that, -// the data structure can be queried. -int XMLTree::CloseDocument() - { - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: data structure has not been initialized properly (by calling method OpenDocument)\n"); - return NULLT; - } - - // closing parenthesis for the tree root - par_aux = (pb *)urealloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb)))); - - // creates the data structure for the tree topology - Par = (bp *)umalloc(sizeof(bp)); - bp_construct(Par, npar, par_aux, OPT_DEGREE|0); - // creates structure for tags + string s = (char *) tagname; + TagIdMapIT it = tIdMap->find(s); + return (TagType) ((it != tIdMap->end()) ? it->second : -1); - // 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 - //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; - tags_fix = new uint[uint_len(tags_blen,tags_len)]; - 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(); - - // 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); - free (empty_texts_aux); - empty_texts_aux = NULL; - } - - // OJO was leaked before, found by valgrind - free(tags_aux); - - tags_aux = NULL; - - finished = true; - print_stats(); - - return 1; // indicates success in the inicialization } -// NewOpenTag(tagname): indicates the event of finding a new opening tag in the document. -// Tag name is given. Returns a non-zero value upon success, and returns NULLT -// in case of failing when trying to insert the new tag. -int XMLTree::NewOpenTag(unsigned char *tagname) +// GetTagName(tagid): returns the tag name of a given tag identifier. +// Returns NULL in case that the tag identifier is not valid. +unsigned char *XMLTree::GetTagName(TagType tagid) { - int i; + unsigned char *s; + if ( tagid < 0 || tagid >= TagName->size()) + return (unsigned char *) ""; + strcpy((char *)s, (*TagName)[tagid].c_str()); - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: you cannot insert a new opening tag without first calling method OpenDocument first\n"); - return NULLT; - } - - // inserts a new opening parentheses in the bit sequence - if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis - par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize); - parArraySize *= 2; - } - - setbit(par_aux,npar,OP); // marks a new opening parenthesis - - // transforms the tagname into a tag identifier. If the tag is new, we insert - // it in the table. - for (i=0; i") was called - if (i==0) - found_attributes=true; - - if (i==ntagnames) { // the tag is a new one, then we insert it - TagName = (unsigned char **)urealloc(TagName, sizeof(char *)*(ntagnames+1)); - - if (!TagName) { - fprintf(stderr, "Error: not enough memory\n"); - return NULLT; - } - - ntagnames++; - TagName[i] = (unsigned char *)umalloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1)); - strcpy((char *)TagName[i], (const char *)tagname); - } - tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1)); - - tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags - - npar++; - - return 1; - + return (s == NULL ? (unsigned char*) "" : s); } -// NewClosingTag(tagname): indicates the event of finding a new closing tag in the document. -// Tag name is given. Returns a non-zero value upon success, and returns NULLT -// in case of failing when trying to insert the new tag. -int XMLTree::NewClosingTag(unsigned char *tagname) +const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) { - int i; - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: you cannot insert a new closing tag without first calling method OpenDocument first\n"); - return NULLT; - } - - // inserts a new closing parentheses in the bit sequence - if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis - par_aux = (pb *)urealloc(par_aux, sizeof(pb)*2*parArraySize); - parArraySize *= 2; - } - - setbit(par_aux,npar,CP); // marks a new closing parenthesis - - // transforms the tagname into a tag identifier. If the tag is new, we insert - // it in the table. - for (i=0; i= TagName->size()) + return (unsigned char *) ""; + return (const unsigned char *) (*TagName)[tagid].c_str(); -// NewText(s): indicates the event of finding a new (non-empty) text s in the document. -// The new text is inserted within the text collection. Returns a non-zero value upon -// success, NULLT in case of error. -int XMLTree::NewText(unsigned char *s) - { - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: you cannot insert a new text without first calling method OpenDocument first\n"); - return NULLT; - } - - if (disable_tc) { - XMLTree::NewEmptyText(); - return 1; - }; - - if (!indexing_empty_texts) { - empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb)))); - bitset(empty_texts_aux, npar-1); // marks the non-empty text with a 1 in the bit vector - } - - Text->InsertText(s); - string cpps = (char*) s; - CachedText.push_back(cpps); - - return 1; // success } -// NewEmptyText(): indicates the event of finding a new empty text in the document. -// In case of indexing empty and non-empty texts, we insert the empty texts into the -// text collection. In case of indexing only non-empty texts, it just indicates an -// empty text in the bit vector of empty texts. Returns a non-zero value upon -// success, NULLT in case of error. -int XMLTree::NewEmptyText() - { - unsigned char c = 0; - if (!initialized) { // data structure has not been initialized properly - fprintf(stderr, "Error: you cannot insert a new empty text without first calling method OpenDocument first\n"); - return NULLT; - } - - if (!indexing_empty_texts) { - empty_texts_aux = (unsigned int *)urealloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb)))); - - 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 - - return 1; // success - } -// GetTagId: returns the tag identifier corresponding to a given tag name. -// Returns NULLT in case that the tag name does not exists. -TagType XMLTree::GetTagId(unsigned char *tagname) +TagType XMLTree::RegisterTag(unsigned char *tagname) { - int i; - // 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]); - return s; + return id; } -//KIM : OJO need the two following methods +treeNode XMLTree::Closing(treeNode x) { + return fast_find_close(Par,x); +} +bool XMLTree::IsOpen(treeNode x) { return fast_inspect(Par,x); } -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]); - } +//WARNING this uses directly the underlying implementation for plain text +void XMLTree::Print(int fd,treeNode x, bool no_text){ -TagType XMLTree::RegisterTag(unsigned char *tagname) -{ - if (!finished) - return NULLT; - - TagType id = XMLTree::GetTagId(tagname); - if (id == NULLT){ - id = ntagnames; - ntagnames = ntagnames + 1; - TagName = (unsigned char **) urealloc(TagName,ntagnames*(sizeof(unsigned char*))); - TagName[id] = (unsigned char *) umalloc(sizeof(unsigned char)*strlen( (const char*) tagname)+1); - strcpy((char*)TagName[id], (const char *)tagname); + if (buffer == 0) { + buffer = new string(BUFFER_ALLOC, 0); + buffer->clear(); + print_stack = new std::vector(); + print_stack->reserve(256); }; - return id; + treeNode fin = fast_find_close(Par,x); + treeNode n = x; + TagType tag = Tag(n); + + range r = DocIds(x); + treeNode first_idx; + treeNode first_text = (tag == PCDATA_TAG_ID ? x : ParentNode(r.min-1)); + treeNode first_att = NULLT; + + if (first_att == NULLT) + first_idx = first_text; + else if (first_text == NULLT) + first_idx = first_att; + else + first_idx = min(first_att,first_text); + + uchar * current_text=NULL; + + if (first_idx != NULLT) + current_text = GetText(MyTextUnsafe(first_idx)); + + size_t read = 0; + + while (n <= fin){ + if (fast_inspect(Par,n)){ + if (tag == PCDATA_TAG_ID) { + + if (no_text) + _dputs("<$/>", fd); + else { + read = _dprintf((const char*) current_text, fd); + current_text += (read + 1); + }; + n+=2; // skip closing $ + tag = Tag(n); + + } else { + + _dputc('<',fd); + _dput_str((*TagName)[tag], fd); + n++; + if (fast_inspect(Par,n)) { + print_stack->push_back(&((*TagName)[tag])); + tag = Tag(n); + if (tag == ATTRIBUTE_TAG_ID){ + n++; + if (no_text) _dputs("><@@>",fd); + + while (fast_inspect(Par,n)){ + if (no_text) { + _dputc('<', fd); + _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd); + _dputc('>', fd); + _dputs("<$@/>', fd); + n+= 4; + } else { + _dputc(' ', fd); + _dputs((const char*) &(GetTagNameByRef(Tag(n))[3]), fd); + n++; + _dputs("=\"", fd); + read = _dprintf((const char*) current_text, fd); + current_text += (read + 1); + _dputc('"', fd); + n+=3; + } + }; + if (no_text) _dputs("", fd); + else _dputc('>', fd); + n++; + tag=Tag(n); + + } else + _dputc('>', fd); + + } else {// tag + _dputs("/>", fd); + n++; + tag=Tag(n); + }; + }; + } else do { + _dputs("back()), fd); + _dputc('>', fd); + print_stack->pop_back(); + n++; + } while (!(fast_inspect(Par,n) || print_stack->empty())); + tag = Tag(n); + }; + _dputc('\n', fd); + //_flush(fd); }