[PPL-devel] [GIT] ppl/ppl(sparse_matrices): CO_Tree: add lower_bound() methods.

[Marco Poletti]

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

Author: Marco Poletti <poletti.marco at gmail.com>
Date:   Sat May  8 17:57:36 2010 +0200

CO_Tree: add lower_bound() methods.

---

 src/CO_Tree.defs.hh                              |   10 ++++
 src/CO_Tree.inlines.hh                           |   58 ++++++++++++++++++++++
 src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh |   52 +-------------------
 3 files changed, 70 insertions(+), 50 deletions(-)

diff --git a/src/CO_Tree.defs.hh b/src/CO_Tree.defs.hh
index d569673..21fcd1e 100644
--- a/src/CO_Tree.defs.hh
+++ b/src/CO_Tree.defs.hh
@@ -164,6 +164,16 @@ public:
   void go_down_searching_key(inorder_const_iterator& itr,
                              dimension_type key) const;
 
+  //! Searches for an element with key \p key , assuming \p itr->first is less
+  //! than or equal to \p key .
+  //! If there is no element with key \p key , itr will be set to end().
+  void lower_bound(inorder_iterator& itr, dimension_type key);
+
+  //! Searches for an element with key \p key , assuming \p itr->first is less
+  //! than or equal to \p key .
+  //! If there is no element with key \p key , itr will be set to end().
+  void lower_bound(inorder_const_iterator& itr, dimension_type key) const;
+
   class inorder_iterator;
   class inorder_const_iterator;
 
diff --git a/src/CO_Tree.inlines.hh b/src/CO_Tree.inlines.hh
index a3b3347..8797d65 100644
--- a/src/CO_Tree.inlines.hh
+++ b/src/CO_Tree.inlines.hh
@@ -352,6 +352,64 @@ CO_Tree::go_down_searching_key(inorder_const_iterator& itr,
 }
 
 inline void
+CO_Tree::lower_bound(inorder_iterator& itr, dimension_type key) {
+  PPL_ASSERT(!empty());
+  if (itr->first <= key)
+    while (itr.has_parent() && itr->first < key)
+      itr.get_parent();
+  else
+    while (itr.has_parent() && itr->first > key)
+      itr.get_parent();
+
+  go_down_searching_key(itr, key);
+
+#ifndef NDEBUG
+  CO_Tree::inorder_iterator itr2(this);
+  go_down_searching_key(itr2, key);
+  PPL_ASSERT(itr == itr2);
+#endif
+
+  if (itr->first < key)
+    itr.get_next_value();
+
+#ifndef NDEBUG
+  itr.get_previous_value();
+  PPL_ASSERT(itr.is_before_begin() || itr->first < key);
+  itr.get_next_value();
+#endif
+  PPL_ASSERT(itr.is_at_end() || itr->first >= key);
+}
+
+inline void
+CO_Tree::lower_bound(inorder_const_iterator& itr, dimension_type key) const {
+  PPL_ASSERT(!empty());
+  if (itr->first <= key)
+    while (itr.has_parent() && itr->first < key)
+      itr.get_parent();
+  else
+    while (itr.has_parent() && itr->first > key)
+      itr.get_parent();
+
+  go_down_searching_key(itr, key);
+
+#ifndef NDEBUG
+  CO_Tree::inorder_const_iterator itr2(this);
+  go_down_searching_key(itr2, key);
+  PPL_ASSERT(itr == itr2);
+#endif
+
+  if (itr->first < key)
+    itr.get_next_value();
+
+#ifndef NDEBUG
+  itr.get_previous_value();
+  PPL_ASSERT(itr.is_before_begin() || itr->first < key);
+  itr.get_next_value();
+#endif
+  PPL_ASSERT(itr.is_at_end() || itr->first >= key);
+}
+
+inline void
 CO_Tree::move_data_element(data_type& to, data_type& from) {
   // The following code is equivalent (but slower):
   //
diff --git a/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh b/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh
index 954e0a6..76d6bdb 100644
--- a/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh
+++ b/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh
@@ -500,62 +500,14 @@ inline void
 Unlimited_Sparse_Row_Over_CO_Tree
 ::lower_bound_hint_assign(dimension_type i,
                           CO_Tree::inorder_iterator& itr) {
-  PPL_ASSERT(!tree.empty());
-  if (itr->first <= i)
-    while (itr.has_parent() && itr->first < i)
-      itr.get_parent();
-  else
-    while (itr.has_parent() && itr->first > i)
-      itr.get_parent();
-
-  tree.go_down_searching_key(itr, i);
-
-#ifndef NDEBUG
-  CO_Tree::inorder_iterator itr2(&tree);
-  tree.go_down_searching_key(itr2, i);
-  PPL_ASSERT(itr == itr2);
-#endif
-
-  if (itr->first < i)
-    itr.get_next_value();
-
-#ifndef NDEBUG
-  itr.get_previous_value();
-  PPL_ASSERT(itr.is_before_begin() || itr->first < i);
-  itr.get_next_value();
-#endif
-  PPL_ASSERT(itr.is_at_end() || itr->first >= i);
+  tree.lower_bound(itr, i);
 }
 
 inline void
 Unlimited_Sparse_Row_Over_CO_Tree
 ::lower_bound_hint_assign(dimension_type i,
                           CO_Tree::inorder_const_iterator& itr) const {
-  PPL_ASSERT(!tree.empty());
-  if (itr->first <= i)
-    while (itr.has_parent() && itr->first < i)
-      itr.get_parent();
-  else
-    while (itr.has_parent() && itr->first > i)
-      itr.get_parent();
-
-  tree.go_down_searching_key(itr, i);
-
-#ifndef NDEBUG
-  CO_Tree::inorder_const_iterator itr2(&tree);
-  tree.go_down_searching_key(itr2, i);
-  PPL_ASSERT(itr == itr2);
-#endif
-
-  if (itr->first < i)
-    itr.get_next_value();
-
-#ifndef NDEBUG
-  itr.get_previous_value();
-  PPL_ASSERT(itr.is_before_begin() || itr->first < i);
-  itr.get_next_value();
-#endif
-  PPL_ASSERT(itr.is_at_end() || itr->first >= i);
+  tree.lower_bound(itr, i);
 }
 
 inline void