[PPL-devel] [GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row_Over_CO_Tree: optimize combine_needs_second().

[Marco Poletti]

Module: ppl/ppl
Branch: sparse_matrices
Commit: c75a75d9eb636efc7facf173d098aebb480d304b
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c75a75d9eb636efc7facf173d098aebb480d304b

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Sun Apr 25 12:43:06 2010 +0200

Unlimited_Sparse_Row_Over_CO_Tree: optimize combine_needs_second().

---

 src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh |  121 +++++---------------
 1 files changed, 27 insertions(+), 94 deletions(-)

diff --git a/src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh b/src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh
index 22b2181..eb5b2d4 100644
--- a/src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh
+++ b/src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh
@@ -76,74 +76,13 @@ template <typename Func1, typename Func2>
 void
 Unlimited_Sparse_Row_Over_CO_Tree
 ::combine_needs_second(const Unlimited_Sparse_Row_Over_CO_Tree& y,
-                       const Func1& g, const Func2& h) {
-  iterator i = begin();
-  iterator last_i = begin();
-  const_iterator j = y.begin();
-  if (!i.itr.is_at_end()) {
-    if (!j.itr.is_at_end()) {
-      if (i->first == j->first) {
-        g(i->second, j->second);
-        last_i = i;
-        ++i;
-        ++j;
-      } else
-        if (i->first < j->first) {
-          last_i = i;
-          ++i;
-        } else {
-          last_i = find_create(j->first);
-          h(last_i->second, j->second);
-          i = last_i;
-          ++i;
-          if (this == &y)
-            j = last_i;
-          ++j;
-        }
-    } else {
-      last_i = i;
-      ++i;
-    }
-  } else {
-    if (!j.itr.is_at_end()) {
-      last_i = find_create(j->first);
-      h(last_i->second, j->second);
-      i = last_i;
-      ++i;
-      if (this == &y)
-        j = last_i;
-      ++j;
-    } else {
-      PPL_ASSERT(i.itr.is_at_end());
-      PPL_ASSERT(j.itr.is_at_end());
-
-      return;
-    }
-  }
-  PPL_ASSERT(!last_i.itr.is_at_end());
-  while (!i.itr.is_at_end() && !j.itr.is_at_end())
-    if (i->first == j->first) {
-      g(i->second, j->second);
-      last_i = i;
-      ++i;
-      ++j;
-    } else
-      if (i->first < j->first) {
-        last_i = i;
-        i = lower_bound(j->first, i);
-      } else {
-        last_i = find_create(j->first, last_i);
-        h(last_i->second, j->second);
-        i = last_i;
-        ++i;
-        if (this == &y)
-          j = last_i;
-        ++j;
-      }
-  while (!j.itr.is_at_end()) {
-    last_i = find_create(j->first, last_i);
-    h(last_i->second, j->second);
-    ++j;
+                       const Func1& g, const Func2& /* h */) {
+  iterator i;
+  unordered_const_iterator j = y.unordered_begin();
+  unordered_const_iterator j_end = y.unordered_end();
+  for ( ; j != j_end; ++j) {
+    find_create_assign(j->first, i);
+    g(i->second, j->second);
   }
 }
 
@@ -153,42 +92,36 @@ Unlimited_Sparse_Row_Over_CO_Tree
 ::combine(const Unlimited_Sparse_Row_Over_CO_Tree& y, const Func1& f,
           const Func2& g, const Func3& h) {
   iterator i = begin();
-  iterator last_i = begin();
   const_iterator j = y.begin();
   if (!i.itr.is_at_end()) {
     if (!j.itr.is_at_end()) {
       if (i->first == j->first) {
         g(i->second, j->second);
-        last_i = i;
         ++i;
         ++j;
       } else
         if (i->first < j->first) {
           f(i->second);
-          last_i = i;
           ++i;
         } else {
-          last_i = find_create(j->first);
-          h(last_i->second, j->second);
-          i = last_i;
-          ++i;
+          find_create_assign(j->first, i);
+          h(i->second, j->second);
           if (this == &y)
-            j = last_i;
+            j = i;
+          ++i;
           ++j;
         }
     } else {
       f(i->second);
-      last_i = i;
       ++i;
     }
   } else {
     if (!j.itr.is_at_end()) {
-      last_i = find_create(j->first);
-      h(last_i->second, j->second);
-      i = last_i;
-      ++i;
+      find_create_assign(j->first, i);
+      h(i->second, j->second);
       if (this == &y)
-        j = last_i;
+        j = i;
+      ++i;
       ++j;
     } else {
       PPL_ASSERT(i.itr.is_at_end());
@@ -197,35 +130,35 @@ Unlimited_Sparse_Row_Over_CO_Tree
       return;
     }
   }
-  PPL_ASSERT(!last_i.itr.is_at_end());
   while (!i.itr.is_at_end() && !j.itr.is_at_end())
     if (i->first == j->first) {
       g(i->second, j->second);
-      last_i = i;
       ++i;
       ++j;
     } else
       if (i->first < j->first) {
         f(i->second);
-        last_i = i;
         ++i;
       } else {
-        last_i = find_create(j->first, last_i);
-        h(last_i->second, j->second);
-        i = last_i;
-        ++i;
+        --i;
+        find_create_hint_assign(j->first, i);
+        h(i->second, j->second);
         if (this == &y)
-          j = last_i;
+          j = i;
+        ++i;
         ++j;
       }
   while (!i.itr.is_at_end()) {
     f(i->second);
     ++i;
   }
-  while (!j.itr.is_at_end()) {
-    last_i = find_create(j->first, last_i);
-    h(last_i->second, j->second);
-    ++j;
+  if (!j.itr.is_at_end()) {
+    --i;
+    while (!j.itr.is_at_end()) {
+      find_create_hint_assign(j->first, i);
+      h(i->second, j->second);
+      ++j;
+    }
   }
 }