-treeNode XMLTree::Child(treeNode x, int i) \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
-\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
-treeNode XMLTree::LastChild(treeNode x) \r
-{\r
- if (x == Root() || isleaf(Par,x) || x == NULLT)\r
- return x;\r
- else\r
- return find_open(Par,find_close(Par,parent(Par,x))-1);\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() || x==NULLT)\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
-// TaggedChild(x,i,tag): returns the i-th child of node x tagged tag, or NULLT if there is none.\r
-// Because of the balanced-parentheses representation of the tree, this operation is not supported\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
- if (child==(treeNode)-1) return NULLT; // node x is a leaf, there is no such child\r
- while (child!=(treeNode)-1) {\r
- if (get_field(tags_fix,tags_blen,node2tagpos(child)) /*Tags->access(node2tagpos(child))*/ == tag) { // current child is labeled with tag of interest\r
- i--;\r
- if (i==0) return child; // we have seen i children of x tagged tag, this is the one we are looking for\r
- }\r
- child = next_sibling(Par, x); // OK, let's try with the next child\r
- }\r
- return NULLT; // no such child was found \r
- }\r
-\r
-// TaggedDesc(x,tag): returns the first node tagged tag with larger preorder than x and within\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
- if (isleaf(Par,x))\r
- return NULLT;\r
-\r
- r = (int) Tags->rank(tag, node2tagpos(x));\r
- s = (int) Tags->select(tag, r+1);\r
- if (s == -1) return NULLT; // there is no such node\r
- y = tagpos2node(s); // transforms the tag position into a node position\r
- if (!is_ancestor(Par, x, y)) return NULLT; // the next node tagged tag (in preorder) is not within the subtree of x.\r
- else return y;\r
- }\r
-\r
-treeNode XMLTree::TaggedDescOnly(treeNode x,TagType *desctags, unsigned int dtlen)\r