Boost logo

Boost-Commit :

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>


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk