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

From: ockham_at_[hidden]
Date: 2008-08-02 13:09:16

Author: bernhard.reiter
Date: 2008-08-02 13:09:16 EDT (Sat, 02 Aug 2008)
New Revision: 47946
URL: http://svn.boost.org/trac/boost/changeset/47946

Log:
Remove size() member from *_tree. For rationale, see the std::list::size() O(n) vs. O(1) discussion, esp. the Howard Hinnant comments.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                              |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp        |     7 +------                                 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp |     8 ++++++--                                
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html  |     8 ++------                                
   4 files changed, 10 insertions(+), 15 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-08-02 13:09:16 EDT (Sat, 02 Aug 2008)
@@ -110,7 +110,7 @@
   (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()
+ * Remove shoot(), size()
  * 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 

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-02 13:09:16 EDT (Sat, 02 Aug 2008)
@@ -198,11 +198,6 @@
                 return m_header[1] == &m_header;
         }
         
-	size_type size() const
-	{
-		return boost::tree::size(root());
-	}
-	
         // Hierarchy-specific
         
         /**
@@ -571,7 +566,7 @@
 inline bool operator==(binary_tree<Tp, Alloc> const& x 
                                          , binary_tree<Tp, Alloc> const& y)
 {
-	 return (x.size() == y.size() 
+	 return (size(x.root()) == size(y.root()) 
                           && equal(x.root(), y.root()));
 }
 

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-02 13:09:16 EDT (Sat, 02 Aug 2008)
@@ -15,6 +15,7 @@
 
 #include <boost/tree/cursor_facade.hpp>
 #include <boost/tree/detail/node/nary.hpp>
+#include <boost/tree/detail/iterator/inorder.hpp>
 
 #include <boost/mpl/eval_if.hpp>
 #include <boost/mpl/identity.hpp>
@@ -52,11 +53,14 @@
         typedef base_type* base_pointer;
           
     struct enabler {};
-
- public:
+ 	
          typedef Node node_type;
         typedef node_type* node_pointer;
+	
+public:
 
+ 	//friend class inorder::iterator< nary_tree_cursor<Node> >;
+ 	
           typedef typename mpl::eval_if<
                                                 is_const<Node>
                                            , add_const<typename Node::value_type>

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-02 13:09:16 EDT (Sat, 02 Aug 2008)
@@ -1087,7 +1087,6 @@
 
     <i>// capacity:</i>
     bool      empty() const;
-    size_type size() const;
     size_type max_size() const;
 
     <i>// modifiers:</i>
@@ -1422,7 +1421,6 @@
 
     <i>// capacity:</i>
     bool      empty() const;
-    size_type size() const;
     size_type max_size() const;
     size_type capacity(cursor position) const;
     void      reserve(cursor position, size_type n);
@@ -1733,7 +1731,6 @@
 
     <i>// capacity:</i>
     bool      empty() const { return h.empty(); }
-    size_type size() const  { return h.size(); }
     size_type max_size() const;
 
     <i>// modifiers:</i>
@@ -1987,7 +1984,6 @@
 
     <i>// capacity:</i>
     bool      empty() const;
-    size_type size() const;
     size_type max_size() const;
     size_type capacity(cursor position) const;
     void      reserve(cursor position, size_type n);
@@ -2337,7 +2333,6 @@
 
     <i>// capacity:</i>
     bool      empty() const;
-    size_type size() const;
     size_type max_size() const;
     size_type capacity(cursor position) const;
     void      reserve(cursor position, size_type n);
@@ -2401,7 +2396,8 @@
       </li>
 
       <li>
-        <p><strong>Complexity:</strong> logarithmic in <tt>size()</tt>.</p>
+        <p><strong>Complexity:</strong> logarithmic in the <tt>rank_tree</tt>'s
+        size.</p>
       </li>
     </ol>