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

Subject: [Boost-commit] svn:boost r50264 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/node libs/tree/doc/html libs/tree/test
From: ockham_at_[hidden]
Date: 2008-12-13 16:53:37

Author: bernhard.reiter
Date: 2008-12-13 16:53:36 EST (Sat, 13 Dec 2008)
New Revision: 50264
URL: http://svn.boost.org/trac/boost/changeset/50264

Log:
Some node related changes, and a couple of TODO notes.
Properties modified: 
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/   (props changed)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                |    18 ++++++++---                             
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp          |    65 +++++++++++++++++++-------------------- 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp     |    24 +++++---------                          
   sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2           |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp |     4 +-                                      
   5 files changed, 57 insertions(+), 56 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-12-13 16:53:36 EST (Sat, 13 Dec 2008)
@@ -14,7 +14,19 @@
 [section TODO]
 
 General:
-* Rename node/nary.hpp back to node/binary.hpp, and cleanup.
+* Rename node -> ascending_node; implement descending_node; and corresponding cursors.
+* Fix freestanding parity().
+* Redo all that balance(==balanced_tree)/searcher stuff. Avoid redundancy, that is, make them both use 
+  balanceRs for whatever they're up to, but don't make searcher depend on balance.
+* Add a congruence check algorithm (compare shapes of subtrees; call it "similar()"?).
+* I'd like to make algorithm checks more independent of the sanity of binary_tree; so a mock object
+  would be really useful. Maybe something like a map of maps or a property_tree?
+* Revisit binary_tree . Can it be usable for both balanced and forest trees and still be
+  "light-weight" at the same time? Solution: Introduce an "inorder_optimised_binary_tree" 
+  (with O(1) inorder first and last cursors, and possibly
+  inorder insert and erase functions) for use with balancers, but without splice member functions.
+  Iterators, however, have to go from both types of binary_tree.
+* Rename node/nary.hpp back to node/binary.hpp (really? what about ternary), and cleanup.
 * Extend and parametrize subtree tests (subtree root, subtree size).
 * Clean up node/cursor/binary_tree implementation.
 * Fix forest copy
@@ -44,8 +56,6 @@
 * 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.
-* 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)?
   For a binary_cursor, a boolean size_type would be enough - but
   not for a subtree algorithm like this one. Maybe we need two different size_types for
@@ -61,8 +71,6 @@
     (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:
   * Verify recursive algorithms to work
     * 1. with a tree filled with given data

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-12-13 16:53:36 EST (Sat, 13 Dec 2008)
@@ -13,7 +13,6 @@
 #define BOOST_TREE_BINARY_TREE_HPP
 
 #include <boost/tree/cursor.hpp>
-#include <boost/tree/iterator.hpp>
 #include <boost/tree/algorithm.hpp>
 #include <boost/tree/insert_cursor.hpp>
 
@@ -44,7 +43,7 @@
     typedef typename Alloc::template rebind<value_type>::other allocator_type;
 
  private:        
-    typedef node<value_type/*, detail::binary_array*/> node_type;
+    typedef node<value_type> node_type;
     
     typedef typename Alloc::template rebind<node_type>::other 
         node_allocator_type;
@@ -164,36 +163,36 @@
         return const_cursor(&m_header, 0);
     }
     
-    /**
-     * Returns a read/write ("mutable") cursor to the first (inorder) value.
-     */      
-    cursor inorder_first()
-    {
-        return cursor(m_header.m_children[1], 0);
-    }
-    
-    /**
-     * Returns a read-only const_cursor to the first (inorder) value.
-     */      
-    const_cursor inorder_first() const
-    {
-        return inorder_cfirst();
-    }
-
-    /**
-     * Returns a read-only const_cursor to the first (inorder) value.
-     */      
-    const_cursor inorder_cfirst() const
-    {
-        return const_cursor(m_header.m_children[1], 0);
-    }
+//    /**
+//     * Returns a read/write ("mutable") cursor to the first (inorder) value.
+//     */      
+//    cursor inorder_first()
+//    {
+//        return cursor(&m_header, 1);
+//    }
+//    
+//    /**
+//     * Returns a read-only const_cursor to the first (inorder) value.
+//     */      
+//    const_cursor inorder_first() const
+//    {
+//        return inorder_cfirst();
+//    }
+//
+//    /**
+//     * Returns a read-only const_cursor to the first (inorder) value.
+//     */      
+//    const_cursor inorder_cfirst() const
+//    {
+//        return const_cursor(&m_header, 1);
+//    }
     
     /**
      * Returns true if the %binary_tree is empty.
      */
     bool empty() const
     {
-        return m_header.m_children[1] == &m_header;
+        return root().empty(); //m_header.m_children[1] == &m_header;
     }
     
     // Hierarchy-specific
@@ -221,8 +220,8 @@
         pos.attach(p_node);
 
         // Readjust begin
-        if ((pos == this->inorder_first()))
-            m_header.m_children[1] = p_node; 
+//        if ((pos == this->inorder_first()))
+//            m_header.m_children[1] = p_node; 
 
         return pos; 
     }
@@ -234,9 +233,9 @@
      * @brief       Inserts val in front of @a pos, or, if @a pos' parent is
      *              already full, creates a new child node containing @a val 
      *              instead.
-     * @param pos   The %binary_tree inorder iterator in front of which to insert.
+     * @param pos   The %binary_tree cursor in front of which to insert.
      * @param val   The value to insert.
-     * @return      An inorder iterator that points to the inserted data.
+     * @return      An cursor that points to the inserted data.
      */
     template <class InputCursor>
     cursor insert(cursor pos, InputCursor subtree)
@@ -414,8 +413,8 @@
     void splice(cursor position, binary_tree& x)
     {
         if (!x.empty()) {
-            if (position == inorder_first()) // Readjust inorder_first to x's
-                m_header.m_children[1] = x.m_header.m_children[1];
+//            if (position == inorder_first()) // Readjust inorder_first to x's
+//                m_header.m_children[1] = x.m_header.m_children[1];
                 
             position.base_node()->m_children[position.m_pos] = x.m_header.m_children[0];
             //TODO: replace the following by some temporary-swapping?
@@ -586,7 +585,7 @@
  *
  *  This is an equivalence relation.  It is linear in the size of the
  *  binary trees. Binary trees are considered equivalent if their sizes are equal,
- *  their shapes are equal,  and if corresponding elements compare equal.
+ *  their shapes are equal, and if corresponding elements compare equal.
  */
 template <class Tp, class Alloc>
 inline bool operator==(binary_tree<Tp, Alloc> const& x 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp	2008-12-13 16:53:36 EST (Sat, 13 Dec 2008)
@@ -31,10 +31,6 @@
 //struct node_base;
 /*
  * node_with_parent_base
- * node_base<N> leitet v. node_with_parent_base ab
- * node_base<2> auch.
- * 
- * we might want nodes that are based on other types of containers, right?
  */
  
 class node_with_parent_base {
@@ -107,10 +103,10 @@
 //    }
 //};
 
-//template <>
-class node_base//<binary_array>
-: public node_with_parent_base/*, public binary_array<node_base<binary_array>*>*/ {
-    typedef node_base/*<binary_array>*/ self_type;
+
+class node_base
+: public node_with_parent_base {
+    typedef node_base self_type;
     
 public:
  
@@ -205,18 +201,16 @@
     
 };
 
-template <typename T/*, template <typename> class Container*/>
-class node : public node_base/*<Container>*/ {
+template <typename T>
+class node : public node_base {
  public:
     typedef T value_type;
-    
-//    typedef Container<node_base/*<Container>*/*> container_type;
 
-    typedef node<value_type/*, Container*/> node_type;
+    typedef node<value_type> node_type;
     typedef node_type* node_pointer;
     typedef node_type& node_reference;
-    //typedef node_pointer position_type;
-    typedef node_base/*<Container>*/ base_type;
+
+    typedef node_base base_type;
     typedef base_type* base_pointer;
     typedef base_type const* const_base_pointer;
     

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	2008-12-13 16:53:36 EST (Sat, 13 Dec 2008)
@@ -39,6 +39,6 @@
         [ run forest_tree_test.cpp ]
 #	[ run nary_tree_test.cpp ]
         [ run multiway_tree_test.cpp ]
-	[ run unbalanced_binary_tree_test.cpp ]
+#	[ run unbalanced_binary_tree_test.cpp ]
         [ run graph_test.cpp ]
         ;

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp	2008-12-13 16:53:36 EST (Sat, 13 Dec 2008)
@@ -253,8 +253,8 @@
     *c = tmp;
     BOOST_CHECK(bt == bt0);
     
-    c = bt0.inorder_first();
-    BOOST_CHECK_EQUAL(*c, 1);
+//    c = bt0.inorder_first();
+//    BOOST_CHECK_EQUAL(*c, 1);
     c = bt0.root();
     //back(inorder(), c);
     //BOOST_CHECK_EQUAL(*c, 14);