From: Kim Nguyễn <kn@lri.fr>
Date: Wed, 18 Apr 2012 12:27:09 +0000 (+0200)
Subject: Change select_* functions from unordered_set<tag_t> to sorted tag_t[]
X-Git-Url: http://git.nguyen.vg/gitweb/?p=SXSI%2FXMLTree.git;a=commitdiff_plain;h=a69b38028aa38dd50b3e5db1acf0ff51faa9b511

Change select_* functions from unordered_set<tag_t> to sorted tag_t[]
---

diff --git a/xml-tree.cpp b/xml-tree.cpp
index df7efe2..8c0386e 100644
--- a/xml-tree.cpp
+++ b/xml-tree.cpp
@@ -42,7 +42,13 @@ static int bits8 (int t ) {
 }
 
 
-
+static bool array_mem(xml_tree::tag_t *a, xml_tree::tag_t t)
+{
+  for(; *a != xml_tree::NIL_TAG_ID; a++){
+    if (*a >= t) return (*a == t);
+  };
+  return false;
+}
 
 static void ufread(void *ptr, size_t size, size_t nmemb, FILE *stream)
  {
@@ -162,52 +168,48 @@ uint32_t xml_tree::postorder(xml_tree::node_t x) const
 }
 
 xml_tree::node_t
-xml_tree::select_child(xml_tree::node_t x,
-                       std::unordered_set<tag_t> *tags) const
+xml_tree::select_child(xml_tree::node_t x, xml_tree::tag_t *tags) const
 {
   if (is_nil(x) || is_leaf(x)) return xml_tree::NIL;
   xml_tree::node_t child = first_child(x);
-  if (tags->find(tag(child)) != tags->end()) return child;
+  if (array_mem(tags, tag(child))) return child;
   return select_sibling(child, tags);
 }
 
 xml_tree::node_t
-xml_tree::select_descendant(xml_tree::node_t x,
-                            std::unordered_set<tag_t> *tags) const
+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(auto tag = tags->begin(); tag != tags->end(); ++ tag){
-    aux = tagged_descendant(x, *tag);
+  for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
+    aux = tagged_descendant(x, *tags);
     if ((unsigned int) aux < (unsigned int) min) min = aux;
   };
   return min;
 }
 
 xml_tree::node_t
-xml_tree::select_sibling(xml_tree::node_t x,
-                         std::unordered_set<tag_t> *tags) const
+xml_tree::select_sibling(xml_tree::node_t x, xml_tree::tag_t *tags) const
 {
   xml_tree::node_t sibling = next_sibling(x);
   xml_tree::tag_t t;
   while(!is_nil(sibling)) {
     t = tag(sibling);
-    if (tags->find(t) != tags->end()) return sibling;
+    if (array_mem(tags, t)) return sibling;
     sibling = next_sibling(sibling);
   };
   return sibling;
 }
 
 xml_tree::node_t
-xml_tree::select_following_before(xml_tree::node_t x,
-                                  std::unordered_set<tag_t> *tags,
+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;
-  for(auto tag = tags->begin(); tag != tags->end(); ++tag){
-    aux = tagged_following_before(x, *tag, limit);
+  for(; *tags != xml_tree::NIL_TAG_ID; ++tags){
+    aux = tagged_following_before(x, *tags, limit);
     if ((unsigned int) aux < (unsigned int) min) min = aux;
   }
   return min;
diff --git a/xml-tree.hpp b/xml-tree.hpp
index debabe9..c2b86ca 100644
--- a/xml-tree.hpp
+++ b/xml-tree.hpp
@@ -3,7 +3,6 @@
 
 
 #include <cstdint>
-#include <unordered_set>
 #include <unordered_map>
 #include <bp/bp.h>
 #include <bp/bp-darray.h>
@@ -88,11 +87,10 @@ public:
   inline node_t tagged_following_before(node_t, tag_t, node_t) const;
   inline node_t tagged_child(node_t, tag_t) const;
   inline node_t tagged_sibling(node_t, tag_t) const;
-  node_t select_child(node_t, std::unordered_set<tag_t>*) const;
-  node_t select_descendant(node_t, std::unordered_set<tag_t>*) const;
-  node_t select_sibling(node_t, std::unordered_set<tag_t>*) const;
-  node_t select_following_before (node_t,
-                                  std::unordered_set<tag_t>*, node_t) const;
+  node_t select_child(node_t, tag_t*) const;
+  node_t select_descendant(node_t, tag_t*) const;
+  node_t select_sibling(node_t, tag_t*) const;
+  node_t select_following_before (node_t, tag_t*, node_t) const;
   inline node_t closing(node_t) const;
 
   //Text functions