X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=20e680165fd6e9e99d60f8aa36cee74336e08857;hb=d79d6498e2d585560d915592ef59f3ad6a57b3c7;hp=f03360ee1b9dd67d439fa5d6e479d91727bbdfd0;hpb=1413ae2197d87e87571c9d8d6fc9f20f691fcea3;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index f03360e..20e6801 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,101 +1,163 @@ - -#include "basics.h" -#include +#include "common.h" #include "XMLTree.h" - -// 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) +static int bits8 (int t ) { + int r = bits(t); + if (r <= 8) + return 8; + else if (r <= 16) + return 16; + else + return r; +} + + + +static treeNode fast_sibling(bp* Par,treeNode x,TagType tag){ + + if (tag == PCDATA_TAG_ID){ + x = x+2; + return bp_inspect(Par,x)==OP ? x : NULLT; + } else return bp_next_sibling(Par,x); + +} + + + + +inline uint get_field_no_power(uint *A, uint len, uint index) { + + 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); + +} + +static uint fast_get_field(uint* A,int len, int idx) { - return (int)x; + 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); + }; + } -// returns NULLT if the test is true -#define NULLT_IF(x) do { if (x) return NULLT; } while (0) -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) +XMLTree::XMLTree( pb * const par, uint npar, vector * const TN, TagIdMap * const tim, + uint *empty_texts_bmp, TagType *tags, + TextCollectionBuilder * const TCB, bool dis_tc, + TextCollectionBuilder::index_type_t _index_type ) { - // creates the data structure for the tree topology - Par = (bp *)umalloc(sizeof(bp)); - bp_construct(Par, npar, (pb*) par, OPT_DEGREE|0); - + buffer = 0; + print_stack = 0; + // creates the data structure for the tree topology + STARTTIMER(); + Par = bp_construct(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; - tags_blen = bits(max_tag); + //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; + delete bmb; free(tags); tags = NULL; - - Text = (TextCollection*) TC; + STOPTIMER(Building); + PRINTTIME("Building Tag Structure", Building); EBVector = new static_bitsequence_rrr02(empty_texts_bmp,npar,32); free(empty_texts_bmp); empty_texts_bmp = NULL; - + disable_tc = dis_tc; + text_index_type = _index_type; + if (!disable_tc) { + assert(TCB != 0); + STARTTIMER(); + Text = TCB->InitTextCollection(); + delete TCB; + STOPTIMER(Building); + PRINTTIME("Building TextCollection", Building); + + } else { + Text = NULL; + } + + std::cerr << "Number of distinct tags " << TagName->size() << "\n"; + //std::cerr.flush(); } // ~XMLTree: frees memory of XML tree. -XMLTree::~XMLTree() - { +XMLTree::~XMLTree() + { int i; - destroyTree(Par); - free(Par); // frees the memory of struct Par - + bp_delete(Par); + Par = NULL; + delete tIdMap; tIdMap = NULL; - + delete TagName; TagName = NULL; - + delete Tags; Tags = NULL; - delete Text; + delete Text; Text = NULL; delete EBVector; EBVector = NULL; - } -void XMLTree::print_stats() +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)); @@ -106,14 +168,15 @@ void XMLTree::print_stats() << " *total* " << total_space << endl; } -// Save: saves XML tree data structure to file. -void XMLTree::Save(int fd) +// Save: saves XML tree data structure to file. +void XMLTree::Save(int fd, char * name) { FILE *fp; - char filenameaux[1024]; int i; - - fp = fdopen(fd, "wa"); + off_t pos = lseek(fd, 0, SEEK_CUR); + int fd2 = dup(fd); + fp = fdopen(fd2, "w"); + fseek(fp, pos, SEEK_SET); // first stores the tree topology saveTree(Par, fp); @@ -123,7 +186,7 @@ void XMLTree::Save(int fd) ufwrite(&ntags, sizeof(int), 1, fp); for (i = 0; iat(i).c_str()); - + // stores the tags Tags->save(fp); @@ -131,521 +194,434 @@ void XMLTree::Save(int fd) ufwrite(&tags_len,sizeof(uint),1,fp); ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp); - // flags + // flags ufwrite(&disable_tc, sizeof(bool),1,fp); - + //text positions EBVector->save(fp); - - // stores the texts + std::cerr << "TC Index position: " << ftell(fp) << std::endl; + // stores the texts if (!disable_tc) { - Text->Save(fp); - }; + std::cerr << "Writing " << sizeof(TextCollectionBuilder::index_type_t) << " bytes\n" << std::endl; + 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; + }; + + Text->Save(fp, file.c_str()); + + } + fflush(fp); + fclose(fp); + } // Load: loads XML tree data structure from file. Returns // a pointer to the loaded data structure -XMLTree *XMLTree::Load(int fd) +XMLTree *XMLTree::Load(int fd, bool load_tc,int sample_factor, char * name) { + FILE *fp; char buffer[1024]; XMLTree *XML_Tree; int i; - + buffer[1023] = '\0'; fp = fdopen(fd, "r"); XML_Tree = new XMLTree(); - + STARTTIMER(); // Load the tree structure - XML_Tree->Par = (bp *)umalloc(sizeof(bp)); - - loadTree(XML_Tree->Par, fp); - - XML_Tree->TagName = new vector(); - XML_Tree->tIdMap = new std::unordered_map(); - - string s; + XML_Tree->Par = loadTree(fp); + STOPTIMER(Loading); + PRINTTIME("Loading parenthesis struct", Loading); + STARTTIMER(); + + XML_Tree->TagName = new std::vector(); + XML_Tree->tIdMap = new std::unordered_map(); + std::string s; int ntags; - + // 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)); - - }; + }; + STOPTIMER(Loading); + PRINTTIME("Loading tag names struct", Loading); + STARTTIMER(); // 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); + //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; + //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(); // loads the flags - + ufread(&(XML_Tree->disable_tc), sizeof(bool), 1, fp); + if (load_tc) { + XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); + + STOPTIMER(Loading); + PRINTTIME("Loading text bitvector struct", Loading); + STARTTIMER(); + std::cerr << "TC Load Index position: " << ftell(fp) << std::endl; + // 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; + XML_Tree->disable_tc = true; + }; - XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); - // Not used - int sample_rate_text = 64; - // loads the texts - if (!XML_Tree->disable_tc){ - XML_Tree->Text = TextCollection::Load(fp,sample_rate_text); - } - else XML_Tree->Text = NULL; - return XML_Tree; } -// root(): returns the tree root. -inline treeNode XMLTree::Root() - { - return 0; //root_node(Par); - } -// SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x. -int XMLTree::SubtreeSize(treeNode x) - { - 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::SubtreeElements(treeNode x) { - if (x == Root()) - x = first_child(Par,x); - - int s = x + 2*subtree_size(Par, x) - 1; - - return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1); + int size = bp_subtree_size(Par, x); + if (x == Root()){ + x = bp_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 = bp_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 bp_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) { - return is_ancestor(Par, x, y); + return bp_is_ancestor(Par, x, y); } // IsChild(x,y): returns whether node x is parent of node y. -bool XMLTree::IsChild(treeNode x, treeNode y) - { - if (!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) +bool XMLTree::IsChild(treeNode x, treeNode y) { - return ((x != NULLT)&&(x==Root() || prev_sibling(Par,x) == (treeNode)-1)); + if (!bp_is_ancestor(Par, x, y)) return false; + return bp_depth(Par, x) == (bp_depth(Par, y) + 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) { - return degree(Par, x); + return bp_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) { - return child_rank(Par, x); + return bp_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) { - return depth(Par, x); + return bp_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) { - return preorder_rank(Par, x); + return bp_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) { - return postorder_rank(Par, x); - } - -// Tag(x): returns the tag identifier of node x. -TagType XMLTree::Tag(treeNode x) - { - return get_field(tags_fix,tags_blen,node2tagpos(x)); + return bp_postorder_rank(Par, 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) { - 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; - + 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*bp_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) - { - if (x == Root()) - return NULLT; - else - 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) -{ - 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) - { - NULLT_IF(x==NULLT); - return first_child(Par, x); - } - -treeNode XMLTree::FirstElement(treeNode x) - { - NULLT_IF(x==NULLT); - treeNode fc = first_child(Par, x); - //<$> is 2 - return ((fc == NULLT || Tag(fc) != PCDATA_TAG_ID) ? fc : next_sibling(Par,fc)); - - } - -treeNode XMLTree::NextElement(treeNode x) +treeNode XMLTree::Child(treeNode x, int i) { - NULLT_IF(x==NULLT); - treeNode ns = next_sibling(Par, x); - return ((ns == NULLT || Tag(ns) != PCDATA_TAG_ID) ? ns : next_sibling(Par,ns)); + if (i <= OPTD) return bp_naive_child(Par, x, i); + else return bp_child(Par, x, i); } -// LastChild(x): returns the last child of node x. -treeNode XMLTree::LastChild(treeNode x) - { - NULLT_IF(x==NULLT || x == Root() || isleaf(Par,x)); - return find_open(Par, find_close(Par, x)-1); - } - - -// NextSibling(x): returns the next sibling of node x, assuming it exists. -treeNode XMLTree::NextSibling(treeNode x) - { - NULLT_IF(x==NULLT || x == Root() ); - return next_sibling(Par, x); - } - -// PrevSibling(x): returns the previous sibling of node x, assuming it exists. -treeNode XMLTree::PrevSibling(treeNode x) - { - NULLT_IF(x==NULLT || x == Root()); - return prev_sibling(Par, x); - } -// 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, TagType tag) - { - - NULLT_IF(x==NULLT || isleaf(Par,x)); - - treeNode child; - child = first_child(Par, x); // starts at first child of node x - if (get_field(tags_fix,tags_blen,node2tagpos(child)) == tag) - return child; - else - return TaggedFollSibling(child,tag); - } - -// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none. -treeNode XMLTree::TaggedFollSibling(treeNode x, TagType tag) +treeNode XMLTree::SelectChild(treeNode x, TagIdSet *tags) { - NULLT_IF(x==NULLT); - treeNode sibling = next_sibling(Par, x); - while (sibling != NULLT) { - if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest - return sibling; - sibling = next_sibling(Par, sibling); // OK, let's try with the next sibling - } - return NULLT; // no such sibling was found -} -treeNode XMLTree::SelectChild(treeNode x, std::unordered_set *tags) -{ - - NULLT_IF(x==NULLT || isleaf(Par,x)); + NULLT_IF(x==NULLT || bp_isleaf(Par,x)); int i; - treeNode child = first_child(Par, x); - TagType t = get_field(tags_fix, tags_blen, node2tagpos(child)); - std::unordered_set::const_iterator tagit = tags->find(t); - if (tagit != tags->end()) return child; - return SelectFollSibling(child,tags); + treeNode child = bp_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::SelectFollSibling(treeNode x, std::unordered_set *tags) +treeNode XMLTree::SelectFollowingSibling(treeNode x, TagIdSet *tags) { NULLT_IF(x==NULLT); int i; TagType t; - treeNode sibling = next_sibling(Par, x); - std::unordered_set::const_iterator tagit; + treeNode sibling = bp_next_sibling(Par, x); while (sibling != NULLT) { - t = get_field(tags_fix, tags_blen, node2tagpos(sibling)); - tagit = tags->find(t); - if (tagit != tags->end()) return sibling; - sibling = next_sibling(Par, sibling); + t = Tag(sibling); + if (tags->find(t) != tags->end()) return sibling; + sibling = fast_sibling(Par, sibling,t); } - return NULLT; - } - - -// 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) - { - NULLT_IF(x==NULLT || isleaf(Par,x)); - - 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 - - return (is_ancestor(Par,x,y) ? y : NULLT); - } - - -treeNode XMLTree::SelectDesc(treeNode x, std::unordered_set *tags) - { - NULLT_IF (x ==NULLT || isleaf(Par,x)); - int i; - treeNode min = NULLT; - treeNode fc = first_child(Par,x); - treeNode aux; - std::unordered_set::const_iterator tagit; - for (tagit = tags->begin(); tagit != tags->end(); tagit++) { - aux = TaggedDesc(x, (TagType) *tagit); - if (aux == fc) return fc; - if (aux == NULLT) continue; - if ((min == NULLT) || (aux < min)) min = aux; - }; - return min; + return NULLT; } - // 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) + { int r, s; treeNode node_s, root; r = (int)Tags->rank(tag, node2tagpos(x)-1); if (r==0) return NULLT; // there is no such node. s = (int)Tags->select(tag, r); - root = root_node(Par); + root = bp_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 (bp_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) { NULLT_IF (x ==NULLT || x == Root()); - - return tagpos2node(Tags->select_next(tag,find_close(Par, x))); - - } + return tagpos2node(Tags->select_next(tag, bp_find_close(Par, x))); -// 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::TaggedFollBelow(treeNode x, TagType tag, treeNode root) -{ + } - NULLT_IF (x == NULLT || x == Root()); - - treeNode s = tagpos2node(Tags->select_next(tag, find_close(Par, x))); - - if (root == Root()) return s; - NULLT_IF (s == NULLT || s >= find_close(Par, root)); - - 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::SelectFollBelow(treeNode x, std::unordered_set *tags, treeNode root) +treeNode XMLTree::SelectFollowingBelow(treeNode x, TagIdSet *tags, treeNode ancestor) { NULLT_IF(x==NULLT || x==Root()); + + treeNode close = bp_find_close(Par,x); + treeNode ns = close+1; + if ( (bp_inspect(Par,ns) == OP) && (tags->find(Tag(ns)) != tags->end())) + return ns; + int i; treeNode min = NULLT; - treeNode ns = next_sibling(Par, x); treeNode aux; - std::unordered_set::const_iterator tagit; - for (tagit = tags->begin(); tagit != tags->end(); tagit++) { - - aux = tagpos2node(Tags->select_next(*tagit, find_close(Par, x))); - - // 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; + + + 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 (root == Root()) return min; - // else check whether if is in below the ctx node + if (ancestor == Root() || min == NULLT || min < bp_find_close(Par, ancestor)) return min; + else return NULLT; - NULLT_IF (min == NULLT || min >= find_close(Par, root)); - - 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 (x == NULLT || x == Root()) return NULLT; - - treeNode s = parent(Par, x), r = Root(); + + treeNode s = bp_parent(Par, x), r = Root(); while (s != r) { - if (get_field(tags_fix,tags_blen,node2tagpos(s)) /*Tags->access(node2tagpos(s))*/ == tag) return s; - s = parent(Par, s); + if (Tag(s) == tag) return s; + s = bp_parent(Par, s); } return 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) +DocID XMLTree::MyText(treeNode x) { TagType tag = Tag(x); // seems faster than testing EBVector->access(x); if (tag == PCDATA_TAG_ID || tag == ATTRIBUTE_DATA_TAG_ID) - return (DocID) (EBVector->rank1(x)-1); //-1 because document ids start from 0 - else + 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 +// 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) { NULLT_IF(d == NULLT); int s = EBVector->select1(d+1); - return rank_open(Par, s) + d + 1; // +1 because root has preorder 1 - + return bp_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) { NULLT_IF(x == NULLT); if (x == Root()) return 1; // root node has preorder 1 - return rank_open(Par, x) + EBVector->rank1(x-1); + return bp_rank_open(Par, x) + EBVector->rank1(x-1); } // ParentNode(d): returns the parent node of document identifier d. -treeNode XMLTree::ParentNode(DocID d) - { - NULLT_IF (d == NULLT); - return (treeNode) EBVector->select1(d+1); +treeNode XMLTree::ParentNode(DocID d) + { + NULLT_IF (d == NULLT); + return (treeNode) EBVector->select1(d+1); } // 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) { - + string s = (char *) tagname; - TagIdMapIT it = tIdMap->find(s); + TagIdMapIT it = tIdMap->find(s); return (TagType) ((it != tIdMap->end()) ? it->second : -1); - + } @@ -656,8 +632,8 @@ unsigned char *XMLTree::GetTagName(TagType tagid) unsigned char *s; if ( tagid < 0 || tagid >= TagName->size()) return (unsigned char *) ""; - strcpy((char *)s, TagName->at(tagid).c_str()); - + strcpy((char *)s, (*TagName)[tagid].c_str()); + return (s == NULL ? (unsigned char*) "" : s); } @@ -668,23 +644,133 @@ const unsigned char *XMLTree::GetTagNameByRef(TagType tagid) unsigned char *s; if ( tagid < 0 || tagid >= TagName->size()) return (unsigned char *) ""; - - return (const unsigned char *) TagName->at(tagid).c_str(); - + + return (const unsigned char *) (*TagName)[tagid].c_str(); + } TagType XMLTree::RegisterTag(unsigned char *tagname) - { + { TagType id = XMLTree::GetTagId(tagname); if (id == NULLT) { - string s = (char *) tagname; + string s = (char *) tagname; REGISTER_TAG(TagName,tIdMap,s); - }; - + return id; } +treeNode XMLTree::Closing(treeNode x) { + return bp_find_close(Par,x); +} +bool XMLTree::IsOpen(treeNode x) { return bp_inspect(Par,x); } + +//WARNING this uses directly the underlying implementation for plain text + + +void XMLTree::Print(int fd,treeNode x, bool no_text){ + + if (buffer == 0) { + buffer = new string(BUFFER_ALLOC, 0); + buffer->clear(); + print_stack = new std::vector(); + print_stack->reserve(256); + }; + + treeNode fin = bp_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 (bp_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 (bp_inspect(Par,n)) { + print_stack->push_back(&((*TagName)[tag])); + tag = Tag(n); + if (tag == ATTRIBUTE_TAG_ID){ + n++; + if (no_text) _dputs("><@@>",fd); + + while (bp_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 (!(bp_inspect(Par,n) || print_stack->empty())); + tag = Tag(n); + }; + _dputc('\n', fd); + //_flush(fd); +}