[Boost-commit] svn:boost r47955 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/cursor libs/tree/doc/html

From: ockham_at_[hidden]
Date: 2008-08-03 05:33:18

Author: bernhard.reiter
Date: 2008-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
New Revision: 47955
URL: http://svn.boost.org/trac/boost/changeset/47955

Log:
Cleanup of is_root() logic largely finished.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                              |    30 ++++++++++++++++--------------          
   sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp      |    38 ++++++++++++++++++++++++++++++++++++--  
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp        |     3 +--                                     
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp |     7 ++-----                                 
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html  |     2 +-                                      
   5 files changed, 56 insertions(+), 24 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -15,22 +15,10 @@
 
 General:
 
+* Revisit binary_tree (inorder::)iterator functions
 * 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 ===
-  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.
-  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.)
 * 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)?
@@ -110,7 +98,8 @@
   (and output_cursor_iterator_wrapper?) proposal.
 * Add a revision log:
  * Add to_parent() (replaces operator!()), to_begin() and to_end() descending cursor members.
- * Remove shoot(), size()
+ * Remove shoot(), size() (rationale for size(): see std::list::size() O(n) vs O(1) discussion,
+   esp the Howard Hinnant comments, http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html )
  * Change some occurences of "vector" (oops) to the respective tree type.
 * Add (subtree) cursor algorithms.
 * Probably split up cursor categories into: cursor (value access) category, vertical traversal 
@@ -148,6 +137,19 @@
   depict what is introduced at what step (nodes with pointers to their siblings, children, parents,
   a frame around a given cursor [and possibly additionally required information stated]
   that signifies what amount of information is contained within that cursor.
+* Add some rationale about the is_root problem() and its solution:
+  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, we need at least an int to store
+  the current depth.
+  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.)
 
 Further applications:
 

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-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -40,6 +40,8 @@
 
 struct empty_class { };
 
+// TODO: Remove Meta2. This stuff must be done via some MPL magic.
+ 
 template <class Val, class Meta, class Meta2 = empty_class>
 struct augmented_type {
         typedef Val value_type;
@@ -77,6 +79,38 @@
         typedef typename augmented_type<Val,Meta,Meta2>::metadata_type type;
 };
 
+template <class Cursor>
+class is_on_top_cursor
+: public Cursor {
+public:
+	is_on_top_cursor()
+	: Cursor() {}
+
+	is_on_top_cursor(Cursor p)
+	: Cursor(p) {}
+	
+	bool is_root() const
+	{
+		return this->is_on_top();
+	}
+};
+
+template <class Cursor>
+class balanced_tree_iterator
+: public inorder::iterator< is_on_top_cursor<Cursor> > {
+public:
+	balanced_tree_iterator()
+	: inorder::iterator< is_on_top_cursor<Cursor> >() {}
+	
+	explicit balanced_tree_iterator(Cursor p)
+    : inorder::iterator< is_on_top_cursor<Cursor> >(p) {}
+    
+	operator Cursor()
+	{
+		return Cursor(this->base());
+	}
+}; 
+
 /** 
  * @brief A %balanced_tree.
  * This class models the hierarchy concept, the container concept and the
@@ -105,8 +139,8 @@
         typedef typename hierarchy_type::const_cursor const_cursor;
 
  public:	
-	typedef augmented_iterator<inorder::iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
-	typedef augmented_iterator<inorder::iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
+	typedef augmented_iterator<balanced_tree_iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
+	typedef augmented_iterator<balanced_tree_iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
         
         typedef std::reverse_iterator<iterator> reverse_iterator;
         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

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-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -566,8 +566,7 @@
 inline bool operator==(binary_tree<Tp, Alloc> const& x 
                                          , binary_tree<Tp, Alloc> const& y)
 {
-	 return (size(x.root()) == size(y.root()) 
-	 		 && equal(x.root(), y.root()));
+	 return (size(x.root()) == size(y.root()) && equal(x.root(), y.root()));
 }
 
 /// Based on operator==

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp	2008-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -59,8 +59,6 @@
         
 public:
 
- 	//friend class inorder::iterator< nary_tree_cursor<Node> >;
- 	
           typedef typename mpl::eval_if<
                                                 is_const<Node>
                                            , add_const<typename Node::value_type>
@@ -181,9 +179,8 @@
                 m_node = static_cast<base_pointer>(m_node->parent());
         }
         
-public:
-	// TODO This isn't really a permanently public thing.
-	bool is_root() const
+protected:
+	bool is_on_top() const
         {
                 base_pointer parent_begin_node = 
                         static_cast<base_pointer>(m_node->parent())

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	2008-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -2512,7 +2512,7 @@
     
     <i>// capacity:</i>
     bool      empty() const { return h.empty(); }
-    size_type size() const  { return h.size(); }
+    size_type size() const;
     size_type max_size() const;
     void      resize(size_type sz, T c = T());