From: Kim Nguyễn <kn@lri.fr>
Date: Fri, 19 Oct 2012 13:09:11 +0000 (+0200)
Subject: Fix handling of subtree_elements. Make the function constant time
X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2FXMLTree.git;a=commitdiff_plain;h=158789da8352e9ad2ee3feeb39f59e5f64343438

Fix handling of subtree_elements. Make the function constant time
by making use of the internal representation (no need to remove
all the attribute tags one by one but only remove twice the number
of attribute-data tags).
---

diff --git a/xml-tree-inc.hpp b/xml-tree-inc.hpp
index faf4538..18c91e3 100644
--- a/xml-tree-inc.hpp
+++ b/xml-tree-inc.hpp
@@ -41,15 +41,12 @@ inline uint32_t xml_tree::subtree_elements(xml_tree::node_t x) const
 
   int32_t size = bp_subtree_size(par, x) - 1;
   if (size <= 0) return 0;
-  size -= subtree_tags(x, xml_tree::PCDATA_OPEN_TAG_ID);
-  size -= subtree_tags(x, xml_tree::ATTRIBUTE_OPEN_TAG_ID);
-  size -= subtree_tags(x, xml_tree::ATTRIBUTE_DATA_OPEN_TAG_ID);
-  if (size < 3) return (uint32_t) size;
-  std::unordered_set<xml_tree::tag_t>::iterator it;
-  for(it = this->attribute_ids->begin();
-      it != this->attribute_ids->end();
-      ++it)
-    size -= subtree_tags(x, *it);
+  uint32_t num_texts = subtree_tags(x, xml_tree::PCDATA_OPEN_TAG_ID);
+  uint32_t num_atts = subtree_tags(x, xml_tree::ATTRIBUTE_OPEN_TAG_ID);
+  uint32_t num_att_data = subtree_tags(x, xml_tree::ATTRIBUTE_DATA_OPEN_TAG_ID);
+  size -= num_texts;
+  size -= num_atts;
+  size -= 2*num_att_data;
   return (uint32_t) size;
 
 }
diff --git a/xml-tree.hpp b/xml-tree.hpp
index 1591285..0795ca0 100644
--- a/xml-tree.hpp
+++ b/xml-tree.hpp
@@ -75,7 +75,7 @@ public:
 
   /**
    * [subtree_elements(n)] returns the number of element nodes below [n]
-   * Runs in O(attribute_ids->size()+3)
+   * Runs in O(1)
    */
   inline uint32_t subtree_elements(node_t) const;