-\r
#include "XMLTree.h"\r
#include <cstring>\r
// functions to convert tag positions to the corresponding tree node and viceversa. \r
Tags->save(fp);\r
\r
// stores the texts \r
- //Text->Save(fp);\r
+ Text->Save(fp);\r
\r
fclose(fp);\r
\r
if (!(XML_Tree->indexing_empty_texts)) XML_Tree->EBVector = static_bitsequence_rrr02::load(fp);\r
\r
// loads the tags\r
- XML_Tree->Tags = static_sequence_wvtree::load(fp);\r
+ XML_Tree->Tags = static_sequence::load(fp);\r
\r
// loads the texts \r
- //XML_Tree->Text->Load(fp,sample_rate_text);\r
+ XML_Tree->Text->Load(fp,sample_rate_text);\r
\r
fclose(fp);\r
\r
free(TagName);\r
\r
if (!indexing_empty_texts) {\r
- EBVector->~static_bitsequence_rrr02();\r
+ //EBVector->~static_bitsequence_rrr02();\r
delete EBVector;\r
EBVector = NULL;\r
}\r
\r
- Tags->~static_sequence_wvtree();\r
+ //Tags->~static_sequence_wvtree();\r
delete Tags;\r
Tags = NULL;\r
\r
//Text->~TextCollection();\r
- // delete Text;\r
- // Text = NULL;\r
+ delete Text;\r
+ Text = NULL;\r
\r
initialized = false;\r
finished = false;\r
// root(): returns the tree root.\r
treeNode XMLTree::Root() \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
return root_node(Par);\r
}\r
\r
// SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x.\r
int XMLTree::SubtreeSize(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
return subtree_size(Par, x);\r
}\r
\r
// SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x.\r
int XMLTree::SubtreeTags(treeNode x, TagType tag) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
int s = x + 2*subtree_size(Par, x) - 1;\r
\r
return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1);\r
// IsAncestor(x,y): returns whether node x is ancestor of node y.\r
bool XMLTree::IsAncestor(treeNode x, treeNode y) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return is_ancestor(Par, x, y);\r
}\r
\r
// IsChild(x,y): returns whether node x is parent of node y.\r
bool XMLTree::IsChild(treeNode x, treeNode y) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
if (!is_ancestor(Par, x, y)) return false;\r
return depth(Par, x) == (depth(Par, y) + 1);\r
}\r
// of Sadakane.\r
int XMLTree::NumChildren(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return degree(Par, x);\r
}\r
\r
// ChildNumber(x): returns i if node x is the i-th children of its parent.\r
int XMLTree::ChildNumber(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return child_rank(Par, x);\r
}\r
\r
// Depth(x): depth of node x, a simple binary rank on the parentheses sequence.\r
int XMLTree::Depth(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return depth(Par, x);\r
}\r
\r
// nodes (i.e., tags, it disregards the texts in the tree).\r
int XMLTree::Preorder(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return preorder_rank(Par, x);\r
}\r
\r
// nodes (i.e., tags, it disregards the texts in the tree).\r
int XMLTree::Postorder(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return postorder_rank(Par, x);\r
}\r
\r
// Tag(x): returns the tag identifier of node x.\r
TagType XMLTree::Tag(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return Tags->access(node2tagpos(x));\r
}\r
\r
// returns {NULLT, NULLT} when there are no texts descending from x.\r
range XMLTree::DocIds(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
range r;\r
if (indexing_empty_texts) { // faster, no rank needed\r
r.min = x;\r
// Parent(x): returns the parent node of node x.\r
treeNode XMLTree::Parent(treeNode x) \r
{\r
- return parent(Par, x);\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+ if (x == Root())\r
+ return NULLT;\r
+ else\r
+ return parent(Par, x);\r
}\r
\r
// Child(x,i): returns the i-th child of node x, assuming it exists.\r
treeNode XMLTree::Child(treeNode x, int i) \r
- {\r
+{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
if (i <= OPTD) return naive_child(Par, x, i);\r
else return child(Par, x, i);\r
}\r
// FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP.\r
treeNode XMLTree::FirstChild(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return first_child(Par, x);\r
}\r
\r
// NextSibling(x): returns the next sibling of node x, assuming it exists.\r
treeNode XMLTree::NextSibling(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+ if (x == Root())\r
+ return NULLT;\r
+ \r
return next_sibling(Par, x);\r
}\r
\r
// PrevSibling(x): returns the previous sibling of node x, assuming it exists.\r
treeNode XMLTree::PrevSibling(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
return prev_sibling(Par, x);\r
}\r
\r
// efficiently, just iterating among the children of node x until finding the desired child.\r
treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
treeNode child;\r
\r
child = first_child(Par, x); // starts at first child of node x\r
// the subtree of x. Returns NULLT if there is none.\r
treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
int r, s;\r
treeNode y;\r
r = (int) Tags->rank(tag, node2tagpos(x));\r
// ancestor of x. Returns NULLT if there is none.\r
treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+ \r
int r, s;\r
treeNode node_s, root;\r
r = (int)Tags->rank(tag, node2tagpos(x)-1);\r
// the subtree of x. Returns NULLT if there is none.\r
treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
int r, s;\r
r = (int) Tags->rank(tag, node2tagpos(next_sibling(Par, x))-1);\r
s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag.\r
// Assumes Doc ids start from 0.\r
DocID XMLTree::PrevText(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
if (x == Root()) return NULLT;\r
if (indexing_empty_texts) // faster, no rank needed\r
return (DocID)x-1;\r
// of node x, or NULLT if x is the root node. Assumes Doc ids start from 0.\r
DocID XMLTree::NextText(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
if (x == Root()) return NULLT;\r
if (indexing_empty_texts) // faster, no rank needed\r
return (DocID)x+2*subtree_size(Par, x)-1;\r
// ids start from 0.\r
DocID XMLTree::MyText(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
if (!IsLeaf(x)) return NULLT;\r
if (indexing_empty_texts) // faster, no rank needed\r
return (DocID)x;\r
// all tree nodes and all text nodes. Assumes that the tree root has preorder 1.\r
int XMLTree::TextXMLId(DocID d) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
if (indexing_empty_texts) \r
return d + rank_open(Par, d)+1; // +1 because root has preorder 1\r
else { // slower, needs rank and select\r
// preorder 0;\r
int XMLTree::NodeXMLId(treeNode x) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
if (indexing_empty_texts)\r
return x - 1 + rank_open(Par, x);\r
else {\r
// ParentNode(d): returns the parent node of document identifier d.\r
treeNode XMLTree::ParentNode(DocID d) \r
{\r
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\r
int s;\r
if (indexing_empty_texts) s = d;\r
else s = EBVector->select1(d);\r
initialized = true;\r
finished = false;\r
npar = 0;\r
- ntagnames = 0;\r
- \r
+ parArraySize = 1;\r
+ ntagnames = 0; \r
+ \r
indexing_empty_texts = empty_texts;\r
\r
- par_aux = (pb *)malloc(sizeof(pb));\r
+ par_aux = (pb *)malloc(sizeof(pb)*parArraySize);\r
if (!par_aux) {\r
fprintf(stderr, "Error: not enough memory\n");\r
return NULLT;\r
}\r
- setbit(par_aux,npar,OP); // marks a new opening parenthesis for the tree root\r
- npar++;\r
\r
- tags_aux = (TagType *)malloc(sizeof(TagType));\r
+ tags_aux = (TagType *) malloc(sizeof(TagType));\r
if (!tags_aux) {\r
fprintf(stderr, "Error: not enough memory\n");\r
return NULLT;\r
}\r
\r
+ TagName = NULL;\r
+\r
if (!indexing_empty_texts) {\r
empty_texts_aux = (unsigned int *)malloc(sizeof(unsigned int));\r
if (!empty_texts_aux) {\r
}\r
}\r
\r
- //Text = TextCollection::InitTextCollection(sample_rate_text);\r
+ Text = TextCollection::InitTextCollection((unsigned)sample_rate_text);\r
\r
return 1; // indicates success in the initialization of the data structure\r
}\r
fprintf(stderr, "Error: not enough memory\n");\r
return NULLT; \r
}\r
- setbit(par_aux,npar,CP); \r
- npar++;\r
\r
// creates the data structure for the tree topology\r
- Par = (bp *)malloc(sizeof(bp)); \r
+ Par = (bp *)malloc(sizeof(bp));\r
bp_construct(Par, npar, par_aux, OPT_DEGREE|0); \r
// creates structure for tags\r
- alphabet_mapper * am = new alphabet_mapper_none();\r
- static_bitsequence_builder * bmb = new static_bitsequence_builder_rrr02(32); \r
- wt_coder * wtc = new wt_coder_huff((uint *)tags_aux,npar-1,am);\r
- Tags = new static_sequence_wvtree((uint *) tags_aux, (uint) npar-1, wtc, bmb, am);\r
+ static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20);\r
+ static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb);\r
+ static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb);\r
\r
+ Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,2*ntagnames, bmb, ssb);\r
+ \r
+ delete bmb;\r
+ delete pmb;\r
+ delete ssb;\r
// makes the text collection static\r
- //Text->MakeStatic();\r
+ Text->MakeStatic();\r
\r
// creates the data structure marking the non-empty texts (just in the case it is necessary)\r
if (!indexing_empty_texts) \r
}\r
\r
// inserts a new opening parentheses in the bit sequence\r
- par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));\r
+ if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis\r
+ par_aux = (pb *)realloc(par_aux, sizeof(pb)*2*parArraySize);\r
+ parArraySize *= 2;\r
+ }\r
+ \r
if (!par_aux) {\r
fprintf(stderr, "Error: not enough memory\n");\r
return NULLT; \r
}\r
+\r
setbit(par_aux,npar,OP); // marks a new opening parenthesis\r
\r
// transforms the tagname into a tag identifier. If the tag is new, we insert\r
TagName[i] = (unsigned char *)malloc(sizeof(unsigned char)*(strlen((const char *)tagname)+1));\r
strcpy((char *)TagName[i], (const char *)tagname);\r
} \r
- \r
- tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1));\r
-\r
+ tags_aux = (TagType *) realloc(tags_aux, sizeof(TagType)*(npar + 1));\r
if (!tags_aux) {\r
fprintf(stderr, "Error: not enough memory\n");\r
return NULLT;\r
}\r
\r
// inserts a new closing parentheses in the bit sequence\r
- par_aux = (pb *)realloc(par_aux, sizeof(pb)*(1+npar/(8*sizeof(pb))));\r
+ if (sizeof(pb)*8*parArraySize == npar) { // no space left for the new parenthesis\r
+ par_aux = (pb *)realloc(par_aux, sizeof(pb)*2*parArraySize);\r
+ parArraySize *= 2;\r
+ }\r
+ \r
if (!par_aux) {\r
fprintf(stderr, "Error: not enough memory\n");\r
return NULLT; \r
}\r
\r
ntagnames++;\r
- TagName[i] = (unsigned char *)malloc(sizeof(char)*(strlen((const char *)tagname)+1));\r
- strcpy((char *)TagName[i], (const char *)tagname);\r
+ TagName[i] = (unsigned char *)malloc(sizeof(char)*(strlen((const char *)tagname)+2));\r
+ TagName[i][0] = '/';\r
+ strcpy((char *)&(TagName[i][1]), (const char *)tagname);\r
} \r
\r
tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1));\r
bitset(empty_texts_aux, npar-1); // marks the non-empty text with a 1 in the bit vector\r
}\r
\r
- //Text->InsertText(s);\r
+ Text->InsertText(s);\r
\r
return 1; // success\r
}\r
\r
bitclean(empty_texts_aux, npar-1); // marks the empty text with a 0 in the bit vector\r
}\r
- // else Text->InsertText(&c); // we insert the empty text just in case we index all the texts\r
+ else Text->InsertText(&c); // we insert the empty text just in case we index all the texts\r
\r
return 1; // success \r
}\r
return s;\r
}\r
\r
+\r
+\r
projects / SXSI / XMLTree.git / blobdiff