[Boost-commit] svn:boost r47113 - in sandbox/SOC/2006/tree/trunk: . boost/tree

From: ockham_at_[hidden]
Date: 2008-07-05 12:34:40

Author: bernhard.reiter
Date: 2008-07-05 12:34:40 EDT (Sat, 05 Jul 2008)
New Revision: 47113
URL: http://svn.boost.org/trac/boost/changeset/47113

Log:
TODO notes, mostly regarding a possible solution to the the subtree root problem.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                            |    49 +++++++++++++++++++++++++++------------ 
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp |    27 +++++++++++++++++++++                   
   2 files changed, 60 insertions(+), 16 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-07-05 12:34:40 EDT (Sat, 05 Jul 2008)
@@ -15,6 +15,33 @@
 
 General:
 
+* Possibly sort out some more concepts, like trees with "downwards" or "upwards" insertion
+  (insert()/insert_above()), trees with values only at the leaves (makes sense in combination
+  with "upwards" insertion"), etc.
+* === The is_root problem() and its solution ===
+  Introduce a root tracking cursor concept providing c.is_root(). *order::forward(), back(),
+  next() and prior() functions as well as *order::iterators then require this concept.
+  Write a root_tracking_cursor adaptor that does exactly that, with suitable specializations
+  for different underlying cursors. 
+  (Why? Because any root_tracker object would have to be
+  passed along with a cursor, plus in- or decremented when going down or up in the hierarchy, 
+  resp. This kind of naturally suggests some kind of encapsulation/adaptation.)
+  (Earlier thoughts:)
+  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
+  the current depth. (Which, in turn, would make the free-standing forward/back/next/prior 
+  algorithms etc. more or less useless without that piece of extra information and would
+  only leave us with the iterators to store it.)
+  -> 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).
+  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?)
 * Do we want/need an O(1) inorder_begin() for binary_tree? 
   Does Gnu's rb_tree (used in std::map) have one?
 * Is it really a good idea to use InCursor::size_type for size(Cursor)?
@@ -25,6 +52,13 @@
 * Use the example trees form Knuth as test example data.
 * Write (internal/external?) adaptors for other tree libraries, as Kaspar Peeters' or
   Adobe's.
+  * External: what would we need? next()/prior(), plus to_begin()/to_end()/to_parent(),
+    deref, ...?
+  * Compare to BGL: Is it possible to modify adapted graphs using graph semantics?
+    If not, adaptation within the BGL would only map inspecting (read-only) functions.
+    (Compare this again to container vs sequence; also look into graph concepts.)
+    Finally, mind the implications for internal/external adaptation; they might be
+    generalised, if the above assumption is true.
 * Revisit binary_tree. Can it be usable for both balanced and forest trees and still be
   "light-weight" at the same time?
 * Re-organize traversal tests:
@@ -45,21 +79,6 @@
 * 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
-  the current depth. (Which, in turn, would make the free-standing forward/back/next/prior 
-  algorithms etc. more or less useless without that piece of extra information and would
-  only leave us with the iterators to store it.)
-  -> 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).
-  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

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp	2008-07-05 12:34:40 EDT (Sat, 05 Jul 2008)
@@ -15,6 +15,7 @@
 
 #include <boost/tree/cursor.hpp>
 #include <boost/tree/cursor_facade.hpp>
+#include <boost/tree/detail/iterator/ascending.hpp>
 
 #include <boost/mpl/eval_if.hpp>
 #include <boost/mpl/identity.hpp>
@@ -28,6 +29,14 @@
 namespace tree {
 
 template <class DescendingCursor> 
+class ascending_cursor;
+
+template <class Cursor>
+typename ascending::iterator< ascending_cursor<Cursor> >::difference_type
+distance(ascending::iterator< ascending_cursor<Cursor> > iter1
+	   , ascending::iterator< ascending_cursor<Cursor> > iter2);
+
+template <class DescendingCursor> 
 class ascending_cursor
  : public cursor_facade<ascending_cursor<DescendingCursor>
       , typename cursor_value<DescendingCursor>::type
@@ -36,7 +45,7 @@
     > {
  private:
     struct enabler {};
-
+	typedef ascending_cursor<DescendingCursor> self_type;
  public:
           typedef typename DescendingCursor::value_type value_type;
 
@@ -97,6 +106,12 @@
          friend class boost::iterator_core_access;
     friend class boost::tree::cursor_core_access;
     
+//    friend 
+//    	typename ascending::iterator<self_type>::difference_type 
+//    	boost::tree::distance<>(
+//    		boost::tree::ascending::iterator<self_type> 
+//	      , boost::tree::ascending::iterator<self_type>);
+    
          std::stack<DescendingCursor> m_s; // pimpl?
          
     value_type& dereference() const
@@ -180,6 +195,16 @@
         return ascending_cursor<Cursor>(c);
 }
 
+/// Specialization
+template <class Cursor>
+typename ascending::iterator< ascending_cursor<Cursor> >::difference_type
+distance(ascending::iterator< ascending_cursor<Cursor> > iter1
+	   , ascending::iterator< ascending_cursor<Cursor> > iter2)
+{
+	return ascending_cursor<Cursor>(iter2).m_s.size() 
+		 - ascending_cursor<Cursor>(iter1).m_s.size();
+}
+
 } // namespace tree
 } // namespace boost