Merge branch remove-virtual

[SXSI/XMLTree.git] / xml-tree-inc.hpp

diff --git a/xml-tree-inc.hpp b/xml-tree-inc.hpp
index bb70513..30a321e 100644 (file)
--- a/xml-tree-inc.hpp
+++ b/xml-tree-inc.hpp
@@ -19,7 +19,7 @@ inline uint32_t xml_tree::num_tags() const
 
 inline uint32_t xml_tree::subtree_size(xml_tree::node_t x) const
 {
-  return bp_subtree_size(this->par, x);
+  return x == root() ? this->par->n/2 : bp_subtree_size(this->par, x);
 }
 
 inline uint32_t
@@ -32,7 +32,7 @@ xml_tree::subtree_tags(xml_tree::node_t x, xml_tree::tag_t label) const
       count += (tag(i) == label);
     return count;
   } else {
-    return tags->rank(label, y) - tags->rank(label, x);
+    return tags[label]->rank(y) - tags[label]->rank(x);
   };
 }
 
@@ -158,9 +158,22 @@ inline xml_tree::node_t xml_tree::next_element(xml_tree::node_t x) const
     return x;
 }
 
-inline xml_tree::node_t xml_tree::tagged_next(node_t x, tag_t tag) const
+
+inline xml_tree::node_t xml_tree::tagged_next_close(xml_tree::node_t x,
+                                             xml_tree::tag_t label) const
+{
+  xml_tree::node_t i=x;
+  for(xml_tree::node_t i = x+1; i < std::min(x+100, this->par->n); i++)
+    if (tag(i) == label)
+      return i;
+
+  return tags[label]->select_next(i);
+}
+
+inline xml_tree::node_t xml_tree::tagged_next(xml_tree::node_t x,
+                                             xml_tree::tag_t label) const
 {
-  return this->tags->select_next(tag, x);
+  return tags[label]->select_next(x);
 }
 
 inline xml_tree::node_t
@@ -174,7 +187,7 @@ xml_tree::tagged_descendant(xml_tree::node_t x,
 inline xml_tree::node_t
 xml_tree::tagged_following_before(xml_tree::node_t x,
                                   xml_tree::tag_t tag,
-                                  xml_tree::node_t limit) const
+                                 xml_tree::node_t limit) const
 {
   xml_tree::node_t close = bp_find_close(this->par, x);
   xml_tree::node_t s = tagged_next(close, tag);
@@ -207,6 +220,37 @@ inline xml_tree::node_t xml_tree::tagged_sibling(xml_tree::node_t x,
   return sibling;
 }
 
+inline xml_tree::node_t
+xml_tree::select_descendant(xml_tree::node_t x, xml_tree::tag_t *tags) const
+{
+  if (is_leaf(x)) return xml_tree::NIL;
+  auto min = xml_tree::NIL;
+  auto aux = xml_tree::NIL;
+  for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
+    aux = tagged_next(x, *tags);
+    if ((unsigned int) aux < (unsigned int) min) min = aux;
+  };
+  return (min == xml_tree::NIL || is_ancestor(x, min)) ? min : xml_tree::NIL;
+}
+
+
+inline xml_tree::node_t
+xml_tree::select_following_before(xml_tree::node_t x, xml_tree::tag_t *tags,
+                                  xml_tree::node_t limit) const
+{
+  auto min = xml_tree::NIL;
+  auto aux = xml_tree::NIL;
+  auto close = bp_find_close(this->par, x);
+
+  for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
+    aux = tagged_next(close, *tags);
+    if ((unsigned int) aux < (unsigned int) min) min = aux;
+  }
+
+  return (min == xml_tree::NIL || min < limit) ? min : xml_tree::NIL;
+}
+
+
 xml_tree::node_t xml_tree::closing(xml_tree::node_t x) const
 {
   return bp_find_close(this->par, x);