\r
#include "XMLTree.h"\r
-#include <cstring>\r
+\r
// functions to convert tag positions to the corresponding tree node and viceversa. \r
// These are implemented in order to be able to change the tree and Tags representations, \r
// without affecting the code so much.\r
Tags->save(fp);\r
\r
// stores the texts \r
- //Text->Save(fp);\r
+ Text->Save(fp);\r
\r
fclose(fp);\r
\r
XML_Tree->Tags = static_sequence_wvtree::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
delete Tags;\r
Tags = NULL;\r
\r
- //Text->~TextCollection();\r
- // delete Text;\r
- // Text = NULL;\r
+ Text->~TextCollection();\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
+ if (!finished) {\r
+ fprintf(stderr, "Error: data structure has not been constructed properly\n");\r
+ exit(1);\r
+ }\r
+\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
+\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
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
Tags = new static_sequence_wvtree((uint *) tags_aux, (uint) npar-1, wtc, bmb, am);\r
\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
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