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>