[Boost-commit] svn:boost r46811 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail/algorithm/cursor libs/tree/test

From: ockham_at_[hidden]
Date: 2008-06-28 11:33:42

Author: bernhard.reiter
Date: 2008-06-28 11:33:41 EDT (Sat, 28 Jun 2008)
New Revision: 46811
URL: http://svn.boost.org/trac/boost/changeset/46811

Log:
Introduce upper_bound.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp                   |    67 +++++++++++++++++++++++++++++++++++++++ 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp |    45 ++++++++++++++++++++++++++              
   sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp                        |    28 ++++++++++++++++                        
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp     |    40 +++++++++++++----------                 
   4 files changed, 161 insertions(+), 19 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp	2008-06-28 11:33:41 EDT (Sat, 28 Jun 2008)
@@ -263,6 +263,68 @@
                  return const_iterator(boost::tree::inorder::lower_bound(h.croot(), k,
                          bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
          }
+
+	/**
+	 * @brief		Finds the last position in the @balanced_tree in which @a k
+	 * 				could be inserted without changing the ordering, using <
+	 * 				(less than) for comparisons.
+	 * @param k		The search term
+	 * @return		An iterator pointing to the first element greater than 
+	 *				@a k, or end() if no element in the @balanced_tree is
+	 * 				greater than @a k.
+	 */
+	 iterator upper_bound(value_type const& k)
+	 {
+	 	return upper_bound(k, std::less<value_type>());
+	 }
+
+	/**
+	 * @brief		Finds the last position in the @balanced_tree in which @a k
+	 * 				could be inserted without changing the ordering, using <
+	 * 				(less than) for comparisons.
+	 * @param k		The search term
+	 * @return		A const_iterator pointing to the first element greater than 
+	 *				@a k, or end() if no element in the @balanced_tree is
+	 * 				greater than @a k.
+	 */
+	 const_iterator upper_bound(value_type const& k) const
+	 {
+	 	return upper_bound(k, std::less<value_type>());
+	 }
+
+	/**
+	 * @brief		Finds the last position in the @balanced_tree in which @a k
+	 * 				could be inserted without changing the ordering, using cmp
+	 * 				for comparisons.
+	 * @param k		The search term
+	 * @param cmp	The comparison functor
+	 * @return		An iterator pointing to the first element greater than 
+	 *				@a k, or end() if no element in the @balanced_tree is
+	 * 				greater than @a k.
+	 */
+	 template <class Cmp>
+	 iterator upper_bound(value_type const& k, Cmp cmp)
+	 {
+	 	return iterator(boost::tree::inorder::upper_bound(h.root(), k, 
+	 		bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
+	 }
+
+	/**
+	 * @brief		Finds the last position in the @balanced_tree in which @a k
+	 * 				could be inserted without changing the ordering, using cmp
+	 * 				for comparisons.
+	 * @param k		The search term
+	 * @param cmp	The comparison functor
+	 * @return		A const_iterator pointing to the first element greater than 
+	 *				@a k, or end() if no element in the @balanced_tree is
+	 * 				greater than @a k.
+	 */
+	 template <class Cmp>
+	 const_iterator upper_bound(value_type const& k, Cmp cmp) const
+	 {
+	 	return const_iterator(boost::tree::inorder::upper_bound(h.croot(), k,
+		 	bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
+	 }
                   
         /**
          * @brief  Add data to the front of the %balanced_tree.
@@ -332,10 +394,13 @@
         iterator insert(iterator pos, value_type const& val)
         {
                 //TODO: we might need to go down in the hierarchy first
-		// That means some redundant work if pos was yielded by lower_bound,
+		// That means some redundant work if pos was yielded by upper_bound,
                 // so maybe saving two cursors in the iterator would make sense
                 // (one for deref, one for insert)
                 
+		// Then again... that's too much of a fuss. Maybe we should just
+		// build a searcher that does all that.
+		
                 cursor c = pos.base().base();
                 while (!c.empty())
                         c = c.end();

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp	2008-06-28 11:33:41 EDT (Sat, 28 Jun 2008)
@@ -263,6 +263,51 @@
         return y;
 }
 
+/**
+ * @brief		Finds the last position in a multiway subtree in which @a val 
+ * 				could be inserted without changing the ordering, using < (less
+ * 				than) for comparisons.
+ * @param x		The subtree's root
+ * @param val	The search term
+ * @return		A multiway cursor pointing to the first element greater than 
+ *				@a val, or @x if no element in the subtree is greater than 
+ * 				@a val.
+ */
+template <class MultiwayCursor, class T>
+MultiwayCursor upper_bound(MultiwayCursor x, T const& val)
+{
+	MultiwayCursor y = x;
+	while (!x.empty()) {
+		x = std::upper_bound(x.begin(), x.end(), val);
+		if (x.parity() == 0)
+			y = x;
+	}
+	return y;
+}
+
+/**
+ * @brief		Finds the last position in a multiway subtree in which @a val 
+ * 				could be inserted without changing the ordering, using @a cmp 
+ * 				for comparisons.
+ * @param x		The subtree's root
+ * @param val	The search term
+ * @param cmp	The comparison functor
+ * @return		A multiway cursor pointing to the first element greater than 
+ *				@a val, or @x if no element in the subtree is greater than
+ * 				@a val.
+ */
+template <class MultiwayCursor, class T, class Cmp>
+MultiwayCursor upper_bound(MultiwayCursor x, T const& val, Cmp cmp)
+{
+	MultiwayCursor y = x;
+	while (!x.empty()) {
+		x = std::upper_bound(x.begin(), x.end(), val, cmp);
+		if (x.parity() == 0)
+			y = x;
+	}
+	return y;
+}
+
 } // namespace inorder
 
 } // namespace tree

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp	2008-06-28 11:33:41 EDT (Sat, 28 Jun 2008)
@@ -188,6 +188,34 @@
          {
                  return c.lower_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
          }
+
+	/**
+	 * @brief		Finds the last position in the searcher in which @a val 
+	 * 				could be inserted without changing the ordering, using comp
+	 * 				for comparisons.
+	 * @param k		The search term
+	 * @return		An iterator pointing to the first element greater than 
+	 *				@a k, or end() if no element in the searcher is greater than 
+	 * 				@a k.
+	 */
+	 iterator upper_bound(key_type const& k)
+	 {
+	 	return c.upper_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
+	 }
+
+	/**
+	 * @brief		Finds the last position in the searcher in which @a val 
+	 * 				could be inserted without changing the ordering, using comp
+	 * 				for comparisons.
+	 * @param k		The search term
+	 * @return		A const_iterator pointing to the first element greater than 
+	 *				@a k, or end() if no element in the searcher is greater than 
+	 * 				@a k.
+	 */
+	 const_iterator upper_bound(key_type const& k) const
+	 {
+	 	return c.upper_bound(k, bind<bool>(comp, bind(ext(), _1), _2));
+	 }
          
          /**
          * @brief		Attempts to insert @a val into the %searcher

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp	2008-06-28 11:33:41 EDT (Sat, 28 Jun 2008)
@@ -21,27 +21,32 @@
 
 using namespace boost::tree;
 
+void search_single_element(binary_tree<int>::const_cursor r, int v)
+{
+	binary_tree<int>::const_cursor c, d;
+	c = inorder::lower_bound(r, v);
+	d = inorder::upper_bound(r, v); 
+	
+	BOOST_CHECK(*c == v);
+	BOOST_CHECK(inorder::next(c) == d);
+}
+
 int test_main(int, char* [])
 {
         binary_tree<int> test_tree;
         create_test_data_tree(test_tree);
                 
-	binary_tree<int>::cursor c = test_tree.root();
-
-	c = inorder::lower_bound(test_tree.root(), 4); // Leaf
-	BOOST_CHECK(*c == 4);
+	binary_tree<int>::cursor c, d;
 
-	c = inorder::lower_bound(test_tree.root(), 7); // Leaf
-	BOOST_CHECK(*c == 7);
-	
-	c = inorder::lower_bound(test_tree.root(), 6); // Non-leaf
-	BOOST_CHECK(*c == 6);
-
-	c = inorder::lower_bound(test_tree.root(), 8); // root().begin()
-	BOOST_CHECK(*c == 8);
+	search_single_element(test_tree.root(), 4); // (Left) Leaf
+	search_single_element(test_tree.root(), 7); // (Right) Leaf
+	search_single_element(test_tree.root(), 6); // Non-Leaf
+	search_single_element(test_tree.root(), 8); // root().begin()
 
         c = inorder::lower_bound(test_tree.root(), 5); // Not in tree
+	d = inorder::lower_bound(test_tree.root(), 5);
         BOOST_CHECK(*c == 6);
+	BOOST_CHECK(*d == 6);
         
         *c = 4;
         
@@ -49,14 +54,13 @@
         BOOST_CHECK(*c == 7);
 
         c = inorder::lower_bound(test_tree.root(), 4); // Twice in tree
+	d = inorder::upper_bound(test_tree.root(), 4);
         BOOST_CHECK(*c == 4);
-	BOOST_CHECK(*c.to_parent() == 4);
-	
-	//binary_tree<int>::cursor d = inorder::upper_bound(test_tree.root(), 4); // Twice in tree
-	//BOOST_CHECK(*d == 4);
-	
-	*c = 6;
+	BOOST_CHECK(*d == 7);
+	BOOST_CHECK(*c.parent() == 4);
+	BOOST_CHECK(inorder::next(inorder::next(c)) == d);
         
+	*c.to_parent() = 6;
         validate_test_data_tree(test_tree);
         
         return 0;