[Boost-commit] svn:boost r46233 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/algorithm/cursor boost/tree/detail/iterator

From: ockham_at_[hidden]
Date: 2008-06-08 09:02:10

Author: bernhard.reiter
Date: 2008-06-08 09:02:09 EDT (Sun, 08 Jun 2008)
New Revision: 46233
URL: http://svn.boost.org/trac/boost/changeset/46233

Log:
Directory and file cleanup, part 5.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp
      - copied, changed from r46034, /sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                             |     2 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp                         |     2                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp                     |     3 -                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp |     6 ++--                                    
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp   |    47 ++++++++++++++++++++++++++++++++++++++++
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp         |     2                                         
   6 files changed, 55 insertions(+), 7 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-06-08 09:02:09 EDT (Sun, 08 Jun 2008)
@@ -14,6 +14,7 @@
 [section TODO]
 
 General:
+* Include all *order iterator headers from a "iterator_algorithm.hpp" (or whatever) file.
 * Make *order iterators work with empty subtrees.
 * Possibly further abstract stack-based iterators by introducing a cursor adaptor
   that uses a stack of descending cursors to implement an ascending one.
@@ -55,6 +56,7 @@
 
 * Add a revision log:
  * Add to_parent() (replaces operator!()), to_begin() and to_end() descending cursor members.
+* Add (subtree) cursor algorithms.
 * Probably split up cursor categories into: cursor (value access) category, vertical traversal 
   and horizontal traversal (along the lines of the new iterator concepts).
 * cursor's begin(), end() and parent() members now only return cursor, same for const_cursor.

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp	2008-06-08 09:02:09 EDT (Sun, 08 Jun 2008)
@@ -13,7 +13,7 @@
 #define BOOST_TREE_ALGORITHM_HPP
 
 
-#include <boost/tree/search.hpp>
+#include <boost/tree/detail/algorithm/cursor/ascending.hpp>
 
 #include <boost/tree/detail/algorithm/cursor/inorder.hpp>
 #include <boost/tree/detail/algorithm/cursor/preorder.hpp>

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-08 09:02:09 EDT (Sun, 08 Jun 2008)
@@ -19,8 +19,7 @@
 #include <boost/tree/balancers/unbalanced.hpp>
 #include <boost/tree/augmentors/unaugmented.hpp>
 
-#include <boost/tree/search.hpp>
-
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
 #include <boost/tree/detail/iterator/augmented.hpp>
 
 #include <boost/bind.hpp>

Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp (from r46034, /sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp	2008-06-08 09:02:09 EDT (Sun, 08 Jun 2008)
@@ -12,8 +12,8 @@
 // Concept checks: MultiwayTree, parent?
 // Optimise for trees such as binary_tree with their own ascending begin() members!
 
-#ifndef BOOST_TREE_ASCENDING_HPP
-#define BOOST_TREE_ASCENDING_HPP
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_ASCENDING_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_ASCENDING_HPP
 
 #include <boost/tree/cursor.hpp>
 
@@ -60,4 +60,4 @@
 } // namespace tree
 } // namespace boost
 
-#endif // BOOST_TREE_ASCENDING_HPP
+#endif // BOOST_TREE_DETAIL_ALGORITHM_CURSOR_ASCENDING_HPP

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-08 09:02:09 EDT (Sun, 08 Jun 2008)
@@ -192,6 +192,53 @@
         return t;
 }
 
+/// Search
+
+/**
+ * @brief		Finds the first 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 not less than 
+ *				@a val, or @x if every element in the subtree is less than 
+ * 				@a val.
+ */
+template <class MultiwayCursor, class T>
+MultiwayCursor lower_bound(MultiwayCursor x, T const& val)
+{
+	MultiwayCursor y = x;
+	while (!x.empty()) {
+		x = std::lower_bound(x.begin(), x.end(), val);
+		if (x.parity() == 0)
+			y = x;
+	}
+	return y;
+}
+
+/**
+ * @brief		Finds the first 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 not less than 
+ *				@a val, or @x if every element in the subtree is less than 
+ * 				@a val.
+ */
+template <class MultiwayCursor, class T, class Cmp>
+MultiwayCursor lower_bound(MultiwayCursor x, T const& val, Cmp cmp)
+{
+	MultiwayCursor y = x;
+	while (!x.empty()) {
+		x = std::lower_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/detail/iterator/ascending.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp	2008-06-08 09:02:09 EDT (Sun, 08 Jun 2008)
@@ -14,7 +14,7 @@
 #ifndef BOOST_TREE_DETAIL_ITERATOR_ASCENDING_HPP
 #define BOOST_TREE_DETAIL_ITERATOR_ASCENDING_HPP
 
-#include <boost/tree/ascending.hpp>
+#include <boost/tree/detail/algorithm/cursor/ascending.hpp>
 #include <boost/tree/cursor.hpp>
 
 #include <boost/iterator/iterator_adaptor.hpp>