Module: ppl/ppl Branch: sparse_matrices Commit: ab2585fce082a05a988ba8b6a4e8e72325a07cf6 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ab2585fce082a...
Author: Marco Poletti poletti.marco@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