Boost logo

Boost-Commit :

From: ockham_at_[hidden]
Date: 2008-06-30 03:28:16


Author: bernhard.reiter
Date: 2008-06-30 03:28:14 EDT (Mon, 30 Jun 2008)
New Revision: 46886
URL: http://svn.boost.org/trac/boost/changeset/46886

Log:
Small header dependency fix, and others.

Text files modified:
   sandbox/SOC/2006/tree/trunk/TODO | 13 +++++++++----
   sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 3 +++
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 2 +-
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp | 7 +++++--
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp | 3 +--
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp | 3 +--
   sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp | 1 -
   7 files changed, 20 insertions(+), 12 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-06-30 03:28:14 EDT (Mon, 30 Jun 2008)
@@ -43,6 +43,8 @@
 * _Possibly_ move detail/algorithm/cursor/ to detail/cursor/algorithm/ or even just
   detail/cursor/ (same for iterator).
 * Make *order iterators work with empty subtrees; same for cursor algorithms.
+ (Not necessarily! If that means a check for empty(), it's better to leave it to
+ the user!)
 * Get rid of checks for/assignments to root in pre/post/inorder algorithms,
   as they are otherwise limited to "whole" trees and cannot be applied to subtrees.
   In order to work for subtrees, it's probable that we need at least an int to store
@@ -52,10 +54,13 @@
   -> This is going to be done by the RootTracker object, which I personally hate,
   but I don't see much of a choice for iterative traversal of subtrees other than that
   (and haven't found any on the Web, either).
-* Deprecate shoot()? It's main use was for inorder::end(), which is now root().
- Would (binary tree) lower_bound() be possible without shoot()? What would it have to be
- like? What would be the implications for balanced_trees? (Especially the lower_bound
- for search vs insert purposes problem.)
+ Our options, in more detail:
+ * Saving a copy of root, obviously. (Only comparison, no later calculation of depth involved)
+ * Iterators based on ascending cursor shouldn't check for size==1, but for size==root_size,
+ where root_size is the size of the stack with all cursors up to the root cursor
+ are pushed. (Comparison, no calculation)
+ * Some color map approach? (Cf BGL, Knuth?)
+* Investigate the lower_bound for search vs insert purposes problem.
 * Take care of inorder::begin() for binary_tree<int>.
 * Keep in mind it's not necessarily a good thing to have *order::end() be the last element's
   right child. For inorder and postorder, it seems like the subtree root is a better choice.

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-30 03:28:14 EDT (Mon, 30 Jun 2008)
@@ -401,6 +401,9 @@
                 // Then again... that's too much of a fuss. Maybe we should just
                 // build a searcher that does all that.
                 
+ // Do balancers have to work for non-leaf newly inserted elements?
+ // If yes, we could just insert at pos.
+
                 cursor c = pos.base().base();
                 while (!c.empty())
                         c = c.end();

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2008-06-30 03:28:14 EDT (Mon, 30 Jun 2008)
@@ -15,7 +15,7 @@
 
 #include <boost/tree/cursor.hpp>
 #include <boost/tree/detail/algorithm/cursor/general.hpp>
-#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
+#include <boost/tree/detail/algorithm/iterator/inorder.hpp>
 
 #include <boost/tree/detail/node/traits.hpp>
 #include <boost/tree/detail/cursor/nary.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-30 03:28:14 EDT (Mon, 30 Jun 2008)
@@ -6,7 +6,7 @@
 
 /**
  * @file inorder.hpp
- * Non-modifying hierarchy inorder range algorithms
+ * Subtree intorder traversal and search algorithms
  */
 
 // TODO: concept checks.
@@ -14,7 +14,6 @@
 #ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
 #define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
 
-#include <boost/tree/detail/iterator/inorder.hpp>
 
 namespace boost {
 namespace tree {
@@ -308,6 +307,10 @@
         return y;
 }
 
+// Implement equal_range? Maybe not, if it'd only return a pair
+// consisting of cursors calculated by calling lower_bound and upper_bound.
+// This might be a bit more subtle for non-binary multiway trees.
+
 } // namespace inorder
 
 } // namespace tree

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp 2008-06-30 03:28:14 EDT (Mon, 30 Jun 2008)
@@ -6,7 +6,7 @@
 
 /**
  * @file postorder.hpp
- * Non-modifying hierarchy postorder range algorithms
+ * Subtree postorder traversal algorithms
  */
 
 // TODO: concept checks.
@@ -14,7 +14,6 @@
 #ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
 #define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
 
-#include <boost/tree/detail/iterator/postorder.hpp>
 
 namespace boost {
 namespace tree {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp 2008-06-30 03:28:14 EDT (Mon, 30 Jun 2008)
@@ -6,7 +6,7 @@
 
 /**
  * @file preorder.hpp
- * Non-modifying hierarchy preorder range algorithms
+ * Subtree preorder traversal algorithms
  */
 
 // TODO: concept checks.
@@ -14,7 +14,6 @@
 #ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
 #define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
 
-#include <boost/tree/detail/iterator/preorder.hpp>
 
 namespace boost {
 namespace tree {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp 2008-06-30 03:28:14 EDT (Mon, 30 Jun 2008)
@@ -19,7 +19,6 @@
 
 #include <boost/test/minimal.hpp>
 
-//#include <memory>
 
 namespace boost {
 namespace tree {


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