[Boost-commit] svn:boost r50515 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/test

Subject: [Boost-commit] svn:boost r50515 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-08 08:53:06

Author: bernhard.reiter
Date: 2009-01-08 08:53:06 EST (Thu, 08 Jan 2009)
New Revision: 50515
URL: http://svn.boost.org/trac/boost/changeset/50515

Log:
Some binary_tree and node implementation cleanup.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp          |    38 ++++++--------------------              
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp   |     3 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp     |    57 +++++++++++++++++++++------------------ 
   sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp            |     4 +-                                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp |     3 --                                      
   5 files changed, 43 insertions(+), 62 deletions(-)

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	2009-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -68,23 +68,13 @@
     explicit binary_tree (allocator_type const& alloc = allocator_type())
     : m_header(), m_value_alloc(alloc)
     {
-        m_header.m_children[0] = node_base_type::nil();
-        m_header.m_children[1] = &m_header;
     }
 
-//    explicit binary_tree (size_type n, value_type const& value = value_type(), 
-//        allocator_type const& alloc = allocator_type())
-//    : m_header(), m_value_alloc(alloc)
-//    {}
-
     template <class InputCursor>
         binary_tree (InputCursor subtree,
             allocator_type const& alloc = allocator_type())
             : m_header(), m_value_alloc(alloc)
     {
-        m_header.m_children[0] = node_base_type::nil();
-        m_header.m_children[1] = &m_header;
-
         insert(root(), subtree);
     }
     
@@ -98,9 +88,6 @@
     binary_tree (self_type const& x)
     : m_header(), m_value_alloc(x.m_value_alloc)
     {
-        m_header.m_children[0] = node_base_type::nil();
-        m_header.m_children[1] = &m_header;
-        
         if (!x.empty())
             insert(root(), x.root());
     }
@@ -207,14 +194,10 @@
      */
     cursor insert(cursor pos, value_type const& val)
     {
-        void* val_hint = 0;//TODO: need some method to obtain hints from cursor
         void* node_hint = 0;
         
-        pointer p_val = m_value_alloc.allocate(1, val_hint);
-        m_value_alloc.construct(p_val, val);
-        
         node_pointer p_node = m_node_alloc.allocate(1, node_hint);
-        m_node_alloc.construct(p_node, p_val);
+        m_node_alloc.construct(p_node, val);
         p_node->init();
         
         pos.attach(p_node);
@@ -316,9 +299,6 @@
          if (!position.empty()) {
              node_pointer pos_node = 
                  static_cast<node_pointer>(position.base_node()->m_children[position.m_pos]);
-             // delete the value position points to    
-             m_value_alloc.destroy(pos_node->data());
-             m_value_alloc.deallocate(pos_node->data(), 1);
              
             // recurse
              clear(position.begin());
@@ -357,7 +337,7 @@
             m_header.m_children[1] = other.m_header.m_children[1];
             //m_header.m_parent = other.m_header.m_parent;
             
-            other.m_header.m_children[0] = node_base_type::nil();
+            other.m_header.m_children[0] = 0;
             other.m_header.m_children[1] = &other.m_header;
             //other.m_header.m_parent = &other.m_header;
             
@@ -371,7 +351,7 @@
             other.m_header.m_children[1] = m_header.m_children[1];
             //other.m_header.m_parent = m_header.m_parent;
             
-            m_header.m_children[0] = node_base_type::nil();
+            m_header.m_children[0] = 0;
             m_header.m_children[1] = &m_header;
             //m_header.m_parent = &m_header;
             
@@ -391,9 +371,9 @@
      */
      void clear()
      {
-         clear(this->root());
-         m_header.m_parent = &m_header;
-         m_header.m_children[0] = node_base_type::nil();
+        clear(this->root());
+        m_header.m_parent = &m_header;
+        m_header.m_children[0] = 0;
         m_header.m_children[1] = &m_header;
      }
      
@@ -418,7 +398,7 @@
                 
             position.base_node()->m_children[position.m_pos] = x.m_header.m_children[0];
             //TODO: replace the following by some temporary-swapping?
-            x.m_header.m_children[0] = node_base_type::nil();
+            x.m_header.m_children[0] = 0;
             x.m_header.m_children[1] = &x.m_header;
             x.m_header.m_parent = &x.m_header;
         }
@@ -444,12 +424,12 @@
                 
             position.base_node()->node_base_type::operator[](position.m_pos) = root.base_node();
             
-            root.base_node()->m_children[0] = node_base_type::nil();
+            root.base_node()->m_children[0] = 0;
             if (root == x.root()) {
                 x.m_header.m_children[1] = &x.m_header;
                 x.m_header.m_parent = &x.m_header;            
             } else
-                root.base_node()->m_children[1] = node_base_type::nil();
+                root.base_node()->m_children[1] = 0;
         }        
     }
     

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp	2009-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -149,7 +149,8 @@
     // Container specific
     bool empty_() const
     {
-        return this->base_reference()->m_children[m_pos] == node_type::nil(); //->empty();
+        return //this->base_reference()->m_children[m_pos] == node_type::nil() ||
+        this->base_reference()->m_children[m_pos] == 0; //->empty()
         //return this->base_reference()->get_index();
     }
     

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp	2009-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -110,6 +110,16 @@
 public:
     typedef array<node_base*, 2> children_type;
     
+    node_with_children_base()
+    {
+        init();
+    }
+
+    inline void init()
+    {
+        for (children_type::size_type i=0; i<children_type::size(); ++i)
+            m_children[i] = 0;
+    }
 //protected:
     children_type m_children;
 };
@@ -124,24 +134,24 @@
     typedef self_type const* const_base_pointer;
         
     node_base() : node_with_parent_base(), node_with_children_base()
-    { }
+    {
+//        m_children[0] = 0;
+//        m_children[1] = 0;
+    }
 
     node_base(node_with_parent_base* p)
     : node_with_parent_base(p), node_with_children_base()
-    { }
-        
-    static base_pointer nil()
-    {
-        static self_type m_nil_obj;
-        static base_pointer m_nil = &m_nil_obj;
-        return m_nil;
-    }
-    
-    void init()
     {
-        for (children_type::size_type i=0; i<children_type::max_size(); ++i)
-            m_children[i] = nil();
+//        m_children[0] = 0;
+//        m_children[1] = 0;
     }
+        
+//    static base_pointer nil()
+//    {
+//        static self_type m_nil_obj;
+//        static base_pointer m_nil = &m_nil_obj;
+//        return m_nil;
+//    }
 
     // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
 //    bool const empty() const
@@ -179,7 +189,7 @@
         m_children[m_pos] = 
             m_children[m_pos]
           ->m_children[((m_children[m_pos])
-          ->m_children[0] == node_base::nil() ? 1 : 0)];
+          ->m_children[0] == 0 /*node_base::nil()*/ ? 1 : 0)];
         m_children[m_pos]->m_parent = this;
         return q;
     }
@@ -235,24 +245,17 @@
 
     //enum size_t { first = 0, second = 1 };
     //typedef std::size_t size_type;
-        
-    // TODO: add observers.
 
-    reference operator*() { return *m_data; } 
+    reference operator*() { return m_data; } 
 
-    const_reference operator*() const { return *m_data; } 
+    const_reference operator*() const { return m_data; } 
     
-    ascending_node(pointer data) : base_type(), m_data(data) {}
+    ascending_node(value_type data) : base_type(), m_data(data) {}
  
-    ascending_node(pointer data, base_pointer p) : base_type(p), m_data(data) {}
-    
-    pointer data()
-    {
-        return m_data;
-    }
+    ascending_node(value_type data, base_pointer p) : base_type(p), m_data(data) {}
     
- private:
-    pointer m_data;
+private:
+    value_type m_data;
 };
 
 } // namespace detail

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp	2009-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -89,8 +89,8 @@
 //        m_header.push_back(node_base_type::nil());
 //        m_header.push_back(&m_header);
         
-        m_header.m_children[0] = node_base_type::nil();
-        m_header.m_children[1] = &m_header;
+//        m_header.m_children[0] = node_base_type::nil();
+//        m_header.m_children[1] = &m_header;
     }
 
     explicit nary_tree (size_type n, value_type const& value = value_type(), 

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	2009-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -24,7 +24,6 @@
     binary_tree<int> bt0;
     BOOST_CHECK(bt0.root().empty());
     //BOOST_CHECK(bt0.root().begin() == bt0.root().end()); //FIXME
-    
     // test with allocator? 
 }
 
@@ -58,7 +57,6 @@
     BOOST_CHECK(bt0.root().begin().begin().empty());
     
     BOOST_CHECK(++c == bt0.root().begin().end());
-    //BOOST_CHECK_EQUAL(1, 2);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
@@ -127,7 +125,6 @@
     
     //c1 = mytree.erase(c1);
     //BOOST_CHECK_EQUAL(*c1, 2);
-
 }
 
 template <class Cursor>