- 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
- return first_child(Par, x);\r
- }\r
-\r
-// LastChild(x): returns the last child of node x.\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
- return find_open(Par, find_close(Par, x)-1);\r
- }\r
-\r
-\r
-// NextSibling(x): returns the next sibling of node x, assuming it exists.\r
-treeNode XMLTree::NextSibling(treeNode x) \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
- return prev_sibling(Par, x);\r
- }\r
-\r
-// TaggedChild(x,tag): returns the first 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, TagType tag) \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)) == tag) // current child is labeled with tag of interest\r
- return child; \r
- child = next_sibling(Par, child); // OK, let's try with the next child\r
- }\r
- return NULLT; // no such child was found \r
- }\r
-\r
-\r
-treeNode XMLTree::SelectChild(treeNode x, TagType *tags, int ntags)\r
- {\r
- int i;\r
- treeNode child = first_child(Par, x);\r
-\r
- while (child!=(treeNode)-1) {\r
- TagType t = get_field(tags_fix, tags_blen, node2tagpos(child));\r
- for (i=0; i<ntags; i++)\r
- if (t==tags[i]) return child;\r
- child = next_sibling(Par, child);\r
- }\r
- return NULLT;\r
- }\r
-\r
-\r
-// TaggedSibling(x,tag): returns the first sibling of node x tagged tag, or NULLT if there is none.\r
-treeNode XMLTree::TaggedSibling(treeNode x, TagType tag)\r
- {\r
- treeNode sibling = next_sibling(Par, x);\r
- \r
- while (sibling!=(treeNode)-1) {\r
- if (get_field(tags_fix,tags_blen,node2tagpos(sibling)) == tag) // current sibling is labeled with tag of interest\r
- return sibling; \r
- sibling = next_sibling(Par, sibling); // OK, let's try with the next sibling\r
- }\r
- return NULLT; // no such sibling was found \r
- }\r
-\r
-\r
-treeNode XMLTree::SelectSibling(treeNode x, TagType *tags, int ntags)\r
- {\r
- int i;\r
- treeNode sibling = next_sibling(Par, x);\r
-\r
- while (sibling!=(treeNode)-1) {\r
- TagType t = get_field(tags_fix, tags_blen, node2tagpos(sibling));\r
- for (i=0; i<ntags; i++)\r
- if (t==tags[i]) return sibling;\r
- sibling = next_sibling(Par, sibling);\r
- }\r
- return NULLT; \r
- }\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
- treeNode y;\r
- if (isleaf(Par,x))\r
- return NULLT;\r
-\r
- int s = (int) Tags->select_next(tag,node2tagpos(x));\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
-\r
-treeNode XMLTree::SelectDesc(treeNode x, TagType *tags, int ntags)\r
- {\r
- int i;\r
- treeNode min = NULLT;\r
- treeNode fc = first_child(Par,x);\r
- \r
- for (i=0; i<ntags; i++) {\r
- treeNode aux = TaggedDesc(x, tags[i]);\r
- if (aux == fc) \r
- return fc;\r
- else \r
- if ((min == (treeNode)NULLT) || (aux < min)) min = aux;\r
- }\r
- return min;\r
- }\r
-\r
-\r
-treeNode XMLTree::TaggedDescOnly(treeNode x,TagType *desctags, unsigned int dtlen)\r
- {\r
- treeNode res, y;\r
- if (isleaf(Par,x))\r
- return NULLT;\r
- \r
- res=NULLT;\r
- for (unsigned int i = 0; i < dtlen; i ++ ) {\r
- y = TaggedDesc(x,desctags[i]);\r
- res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; \r
- }\r
- \r
- return res;\r
- } \r
-\r
-\r
-treeNode XMLTree::TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen,\r
- TagType *desctags, unsigned int dtlen) \r
- {\r
- treeNode fs,y,res;\r
- TagType tag;\r
-\r
- if (isleaf(Par,x))\r
- return NULLT;\r
- \r
- res = NULLT;\r
- fs = first_child(Par,x);\r
- while (fs != NULLT) {\r
- tag = get_field(tags_fix,tags_blen,node2tagpos(fs));\r
- \r
- /* Check for first_child */\r
- for (unsigned int i = 0; i < ctlen; i++) {\r
- if (childtags[i] == tag)\r
- return fs;\r
- }\r
- \r
- for (unsigned int i = 0; i < dtlen; i++)\r
- if (desctags[i] == tag)\r
- return fs; \r
- \r
- /* check in the descendants */\r
- res = NULLT;\r
- for (unsigned int i = 0; i < dtlen; i ++ ) {\r
- /* maybe inline by hand */\r
- y = TaggedDesc(fs,desctags[i]);\r
- res = (res==NULLT || (y != NULLT) &&(y < res)) ? y : res; \r
- } \r
- if (res != NULLT)\r
- return res;\r
- \r
- fs = next_sibling(Par,fs);\r
- }\r
- \r
- return res;\r