X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=ecc9a2786ee545c97deb9e4a76b465c2c0d466ce;hb=46dd7565a6c8d813459b81cf2b19446db1b51010;hp=a3fefeaed2b99284b2005f236f0b4457c4ba00ad;hpb=0bf9688e2615a9fc07860c5762240e4ce26ee5d3;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index a3fefea..ecc9a27 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,4 +1,3 @@ - #include "XMLTree.h" #include // functions to convert tag positions to the corresponding tree node and viceversa. @@ -51,7 +50,7 @@ void XMLTree::Save(unsigned char *filename) Tags->save(fp); // stores the texts - //Text->Save(fp); + Text->Save(fp); fclose(fp); @@ -102,10 +101,10 @@ XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp); // loads the tags - XML_Tree->Tags = static_sequence_wvtree::load(fp); + XML_Tree->Tags = static_sequence::load(fp); // loads the texts - //XML_Tree->Text->Load(fp,sample_rate_text); + XML_Tree->Text->Load(fp,sample_rate_text); fclose(fp); @@ -127,18 +126,18 @@ XMLTree::~XMLTree() free(TagName); if (!indexing_empty_texts) { - EBVector->~static_bitsequence_rrr02(); + //EBVector->~static_bitsequence_rrr02(); delete EBVector; EBVector = NULL; } - Tags->~static_sequence_wvtree(); + //Tags->~static_sequence_wvtree(); delete Tags; Tags = NULL; //Text->~TextCollection(); - // delete Text; - // Text = NULL; + delete Text; + Text = NULL; initialized = false; finished = false; @@ -147,18 +146,31 @@ XMLTree::~XMLTree() // root(): returns the tree root. treeNode XMLTree::Root() { + if (!finished) { + fprintf(stderr, "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) { + 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) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + int s = x + 2*subtree_size(Par, x) - 1; return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1); @@ -174,12 +186,22 @@ bool XMLTree::IsLeaf(treeNode x) // IsAncestor(x,y): returns whether node x is ancestor of node 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); } // IsChild(x,y): returns whether node x is parent of node 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; return depth(Par, x) == (depth(Par, y) + 1); } @@ -188,18 +210,33 @@ bool XMLTree::IsChild(treeNode x, treeNode y) // of Sadakane. 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) { + 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) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return depth(Par, x); } @@ -207,6 +244,11 @@ int XMLTree::Depth(treeNode x) // nodes (i.e., tags, it disregards the texts in the tree). 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); } @@ -214,12 +256,22 @@ int XMLTree::Preorder(treeNode x) // nodes (i.e., tags, it disregards the texts in the tree). 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) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return Tags->access(node2tagpos(x)); } @@ -227,6 +279,11 @@ TagType XMLTree::Tag(treeNode x) // returns {NULLT, NULLT} when there are no texts descending from x. range XMLTree::DocIds(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + range r; if (indexing_empty_texts) { // faster, no rank needed r.min = x; @@ -250,12 +307,24 @@ range XMLTree::DocIds(treeNode x) // Parent(x): returns the parent node of node x. treeNode XMLTree::Parent(treeNode x) { - return parent(Par, 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); } // Child(x,i): returns the i-th child of node x, assuming it exists. 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); } @@ -263,18 +332,35 @@ treeNode XMLTree::Child(treeNode x, int i) // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP. 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); } // NextSibling(x): returns the next sibling of node x, assuming it exists. treeNode XMLTree::NextSibling(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (x == Root()) + return NULLT; + return next_sibling(Par, x); } // PrevSibling(x): returns the previous sibling of node x, assuming it exists. 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); } @@ -283,6 +369,11 @@ treeNode XMLTree::PrevSibling(treeNode x) // efficiently, just iterating among the children of node x until finding the desired child. treeNode XMLTree::TaggedChild(treeNode x, int i, 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 @@ -301,6 +392,11 @@ treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag) // 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; r = (int) Tags->rank(tag, node2tagpos(x)); @@ -315,6 +411,11 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) // ancestor of x. Returns NULLT if there is none. treeNode XMLTree::TaggedPrec(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); @@ -335,6 +436,11 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) // the subtree of x. Returns NULLT if there is none. treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + int r, s; r = (int) Tags->rank(tag, node2tagpos(next_sibling(Par, x))-1); s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. @@ -347,6 +453,11 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) // 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; @@ -362,6 +473,11 @@ DocID XMLTree::PrevText(treeNode x) // 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); + } + if (x == Root()) return NULLT; if (indexing_empty_texts) // faster, no rank needed return (DocID)x+2*subtree_size(Par, x)-1; @@ -379,6 +495,11 @@ DocID XMLTree::NextText(treeNode x) // 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; @@ -394,6 +515,11 @@ DocID XMLTree::MyText(treeNode x) // all tree nodes and all text nodes. Assumes that the tree root has preorder 1. int XMLTree::TextXMLId(DocID d) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (indexing_empty_texts) return d + rank_open(Par, d)+1; // +1 because root has preorder 1 else { // slower, needs rank and select @@ -407,6 +533,11 @@ int XMLTree::TextXMLId(DocID d) // preorder 0; 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 { @@ -419,6 +550,11 @@ int XMLTree::NodeXMLId(treeNode x) // ParentNode(d): returns the parent node of document identifier d. treeNode XMLTree::ParentNode(DocID d) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + int s; if (indexing_empty_texts) s = d; else s = EBVector->select1(d); @@ -434,29 +570,53 @@ treeNode XMLTree::ParentNode(DocID d) // 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) +int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc) { initialized = true; finished = false; + found_attributes = false; npar = 0; - ntagnames = 0; + parArraySize = 1; + ntagnames = 2; + disable_tc = dtc; indexing_empty_texts = empty_texts; - par_aux = (pb *)malloc(sizeof(pb)); + par_aux = (pb *)malloc(sizeof(pb)*parArraySize); if (!par_aux) { fprintf(stderr, "Error: not enough memory\n"); return NULLT; } - setbit(par_aux,npar,OP); // marks a new opening parenthesis for the tree root - npar++; - tags_aux = (TagType *)malloc(sizeof(TagType)); + tags_aux = (TagType *) malloc(sizeof(TagType)); if (!tags_aux) { fprintf(stderr, "Error: not enough memory\n"); return NULLT; } + TagName = (unsigned char **) malloc(2*sizeof(unsigned char*)); + if (!TagName){ + fprintf(stderr, "Error: not enough memory\n"); + return NULLT; + } + + TagName[0] = (unsigned char *) malloc(4*sizeof(unsigned char)); + strcpy((char *) TagName[0], "<@>"); + + if (!TagName[0]){ + fprintf(stderr, "Error: not enough memory\n"); + return NULLT; + } + + TagName[1] = (unsigned char *) malloc(4*sizeof(unsigned char)); + if (!TagName[1]){ + fprintf(stderr, "Error: not enough memory\n"); + return NULLT; + } + + strcpy((char *) TagName[1], "<$>"); + + if (!indexing_empty_texts) { empty_texts_aux = (unsigned int *)malloc(sizeof(unsigned int)); if (!empty_texts_aux) { @@ -465,7 +625,7 @@ int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text) } } - //Text = TextCollection::InitTextCollection(sample_rate_text); + Text = TextCollection::InitTextCollection((unsigned)sample_rate_text); return 1; // indicates success in the initialization of the data structure } @@ -487,24 +647,38 @@ int XMLTree::CloseDocument() fprintf(stderr, "Error: not enough memory\n"); return NULLT; } - setbit(par_aux,npar,CP); - npar++; // creates the data structure for the tree topology - Par = (bp *)malloc(sizeof(bp)); + Par = (bp *)malloc(sizeof(bp)); bp_construct(Par, npar, par_aux, OPT_DEGREE|0); // creates structure for tags - alphabet_mapper * am = new alphabet_mapper_none(); - static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(32); - wt_coder * wtc = new wt_coder_huff((uint *)tags_aux,npar-1,am); - Tags = new static_sequence_wvtree((uint *) tags_aux, (uint) npar-1, wtc, bmb, am); + 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; + + Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,ntagsize, bmb, ssb); + + delete bmb; + delete pmb; + delete ssb; // makes the text collection static - //Text->MakeStatic(); + 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) + 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; + } + + free(tags_aux); + tags_aux = NULL; finished = true; @@ -525,18 +699,28 @@ int XMLTree::NewOpenTag(unsigned char *tagname) } // inserts a new opening parentheses in the bit sequence - par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb)))); + if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis + par_aux = (pb *)realloc(par_aux, sizeof(pb)*2*parArraySize); + parArraySize *= 2; + } + if (!par_aux) { fprintf(stderr, "Error: not enough memory\n"); return NULLT; } + 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 **)realloc(TagName, sizeof(char *)*(ntagnames+1)); @@ -549,9 +733,7 @@ int XMLTree::NewOpenTag(unsigned char *tagname) TagName[i] = (unsigned char *)malloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1)); strcpy((char *)TagName[i], (const char *)tagname); } - - tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1)); - + tags_aux = (TagType *) realloc(tags_aux, sizeof(TagType)*(npar + 1)); if (!tags_aux) { fprintf(stderr, "Error: not enough memory\n"); return NULLT; @@ -579,7 +761,11 @@ int XMLTree::NewClosingTag(unsigned char *tagname) } // inserts a new closing parentheses in the bit sequence - par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb)))); + if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis + par_aux = (pb *)realloc(par_aux, sizeof(pb)*2*parArraySize); + parArraySize *= 2; + } + if (!par_aux) { fprintf(stderr, "Error: not enough memory\n"); return NULLT; @@ -600,8 +786,9 @@ int XMLTree::NewClosingTag(unsigned char *tagname) } ntagnames++; - TagName[i] = (unsigned char *)malloc(sizeof(char)*(strlen((const char *)tagname)+1)); - strcpy((char *)TagName[i], (const char *)tagname); + TagName[i] = (unsigned char *)malloc(sizeof(char)*(strlen((const char *)tagname)+2)); + TagName[i][0] = '/'; + strcpy((char *)&(TagName[i][1]), (const char *)tagname); } tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1)); @@ -630,6 +817,11 @@ int XMLTree::NewText(unsigned char *s) return NULLT; } + if (disable_tc) { + XMLTree::NewEmptyText(); + return 1; + }; + if (!indexing_empty_texts) { empty_texts_aux = (unsigned int *)realloc(empty_texts_aux, sizeof(pb)*(1+(npar-1)/(8*sizeof(pb)))); if (!empty_texts_aux) { @@ -640,7 +832,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); + Text->InsertText(s); return 1; // success } @@ -667,7 +859,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 Text->InsertText(&c); // we insert the empty text just in case we index all the texts return 1; // success } @@ -698,3 +890,20 @@ unsigned char *XMLTree::GetTagName(TagType tagid) return s; } + +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 **) realloc(TagName,ntagnames*(sizeof(unsigned char*))); + strcpy((char*)TagName[id], (const char *)tagname); + }; + + return id; +}