[Boost-commit] svn:boost r49689 - in sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor: . boost/tree boost/tree/detail/cursor boost/tree/detail/node libs/tree/test

Subject: [Boost-commit] svn:boost r49689 - in sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor: . boost/tree boost/tree/detail/cursor boost/tree/detail/node libs/tree/test
From: ockham_at_[hidden]
Date: 2008-11-11 17:29:02

Author: bernhard.reiter
Date: 2008-11-11 17:29:01 EST (Tue, 11 Nov 2008)
New Revision: 49689
URL: http://svn.boost.org/trac/boost/changeset/49689

Log:
Create branch for optimising binary tree cursor.
Added:
   sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/
      - copied from r49678, /sandbox/SOC/2006/tree/trunk/
   sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/cursor/nary.hpp
      - copied, changed from r49679, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
Text files modified: 
   sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/binary_tree.hpp          |    50 +-                                      
   sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/cursor/nary.hpp   |    54 ++-                                     
   sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/node/nary.hpp     |    15                                         
   sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_test.cpp |   521 +++++++++++++++++++++------------------ 
   4 files changed, 341 insertions(+), 299 deletions(-)

Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/binary_tree.hpp
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/binary_tree.hpp	2008-11-11 17:29:01 EST (Tue, 11 Nov 2008)
@@ -69,7 +69,7 @@
     explicit binary_tree (allocator_type const& alloc = allocator_type())
     : m_header(), m_value_alloc(alloc)
     {
-        m_header[0] = node_base_type::nil();
+        m_header[0] = &m_header; //node_base_type::nil();
         m_header[1] = &m_header;
     }
 
@@ -83,7 +83,7 @@
             allocator_type const& alloc = allocator_type())
             : m_header(), m_value_alloc(alloc)
     {
-        m_header[0] = node_base_type::nil();
+        m_header[0] = &m_header; //node_base_type::nil();
         m_header[1] = &m_header;
 
         insert(root(), subtree);
@@ -99,7 +99,7 @@
     binary_tree (self_type const& x)
     : m_header(), m_value_alloc(x.m_value_alloc)
     {
-        m_header[0] = node_base_type::nil();
+        m_header[0] = &m_header; //node_base_type::nil();
         m_header[1] = &m_header;
         
         if (!x.empty())
@@ -223,8 +223,8 @@
         pos.attach(p_node);
 
         // Readjust begin
-        if ((pos == this->inorder_first()))
-            m_header[1] = p_node; 
+//        if ((pos == this->inorder_first()))
+//            m_header[1] = p_node; 
 
         return pos.begin(); 
     }
@@ -292,21 +292,21 @@
      // TODO: Take care of header-pointers
      void clear(cursor position) 
      {
-         if (!position.empty()) {
-             node_pointer pos_node = 
-                 static_cast<node_pointer>(position.m_node->operator[](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());
-             clear(position.end());
-             
-             // delete the node position points to
-            m_node_alloc.destroy(pos_node);
-            m_node_alloc.deallocate(pos_node, 1);         
-          }
+//         if (!position.empty()) {
+//             node_pointer pos_node = 
+//                 static_cast<node_pointer>(position.m_node/*->operator[](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());
+//             clear(position.end());
+//             
+//             // delete the node position points to
+//            m_node_alloc.destroy(pos_node);
+//            m_node_alloc.deallocate(pos_node, 1);         
+//          }
      }     
      
     void rotate(cursor& pos)
@@ -336,7 +336,7 @@
             m_header[1] = other.m_header[1];
             //m_header.m_parent = other.m_header.m_parent;
             
-            other.m_header[0] = node_base_type::nil();
+            other.m_header[0] = &other.m_header; //node_base_type::nil();
             other.m_header[1] = &other.m_header;
             //other.m_header.m_parent = &other.m_header;
             
@@ -350,7 +350,7 @@
             other.m_header[1] = m_header[1];
             //other.m_header.m_parent = m_header.m_parent;
             
-            m_header[0] = node_base_type::nil();
+            m_header[0] = &m_header; //node_base_type::nil();
             m_header[1] = &m_header;
             //m_header.m_parent = &m_header;
             
@@ -370,9 +370,9 @@
      */
      void clear()
      {
-         clear(this->root());
-         m_header.m_parent = &m_header;
-         m_header[0] = node_base_type::nil();
+        clear(this->root());
+        m_header.m_parent = &m_header;
+        m_header[0] = &m_header; //node_base_type::nil();
         m_header[1] = &m_header;
      }
      

Copied: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/cursor/nary.hpp (from r49679, /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/branches/optimise-binary-tree-cursor/boost/tree/detail/cursor/nary.hpp	2008-11-11 17:29:01 EST (Tue, 11 Nov 2008)
@@ -115,39 +115,39 @@
     
     bool equal(cursor const& other) const
     {
-        return (this->m_node == other.m_node) && (this->m_pos == other.m_pos);
+        return (this->m_node == other.m_node); // && (this->m_pos == other.m_pos);
     }
     
     void increment()
     {
-        ++m_pos;
-        // m_node += sizeof(node_type);
+        //++m_pos;
+        m_node += sizeof(node_type);
     }
     
     void decrement()
     {
-        --m_pos;
-        //m_node -= sizeof(node_type);
+        //--m_pos;
+        m_node -= sizeof(node_type);
     }    
     
     void advance(typename nary_tree_cursor::cursor_facade_::difference_type n)
     {
-        m_pos += n;
-        //m_node += n * sizeof(node_type);
+        //m_pos += n;
+        m_node += n * sizeof(node_type);
     }
     
     typename nary_tree_cursor::cursor_facade_::difference_type
     distance_to(nary_tree_cursor z) const //FIXME: convertible to instead of nary_tree_cursor
     {
-        return (z.m_pos - this->m_pos);
-        //return (z.m_node - this->m_node) / sizeof(node_type); 
+        //return (z.m_pos - this->m_pos);
+        return (z.m_node - this->m_node) / sizeof(node_type); 
     }
     
     // Container specific
     bool empty_() const
     {
-        return m_node->operator[](m_pos)->empty();
-        //return m_node->get_index();
+        //return m_node->operator[](m_pos)->empty();
+        return (m_node == (*m_node)[0]) && (m_node == (*m_node)[1]); //m_node->empty();
     }
     
     size_type size_() const
@@ -162,31 +162,31 @@
     
     size_type idx() const
     {
-        return m_pos;
-        //return 
+        //return m_pos;
+        //return (((*(m_node->m_parent))[0] == m_node) ? 0 : 1);
+        return (static_cast<base_pointer>(m_node->m_parent)->base_type::operator[](0) == m_node ? 0 : 1); 
     }
 
     void left()
     {
-        m_node = m_node->operator[](m_pos);
-        m_pos  = 0;
-        //m_node = m_node->operator[0];
+//        m_node = m_node->operator[](m_pos);
+//        m_pos  = 0;
+        m_node = (*m_node)[0];
     }
 
     void right()
     {
-        size_type new_pos = m_node->size()-1; 
-        m_node = m_node->operator[](m_pos);
-        m_pos  = new_pos;
-        //m_node = m_node->operator[0];
+//        size_type new_pos = m_node->size()-1; 
+//        m_node = m_node->operator[](m_pos);
+//        m_pos  = new_pos;
+        m_node = (*m_node)[1];
     }
 
     // Cursor stuff
     void up()
     {
-        m_pos  = m_node->get_index();
+//        m_pos  = m_node->get_index();
         m_node = static_cast<base_pointer>(m_node->parent());
-        //m_node = m_node->parent();
     }
     
 protected:
@@ -203,13 +203,15 @@
     // TODO: protect?
     void attach(node_pointer p_node)
     {
-        p_node->m_parent = m_node;
+        p_node->m_parent = m_node->m_parent;
         
         // Only forest-relevant:
-        p_node->operator[](1) = m_node->operator[](m_pos);
-        m_node->operator[](m_pos)->m_parent = p_node;
+        //p_node->operator[](1) = m_node; //->operator[](m_pos);
+        //m_node->/*operator[](m_pos)->*/m_parent = p_node;
         
-        m_node->operator[](m_pos) = p_node;
+        //m_node/*->operator[](m_pos)*/ = p_node;
+        
+        (*m_node)[this->idx()] = p_node;
     }
 
 //    /** 

Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/node/nary.hpp
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp	(original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/node/nary.hpp	2008-11-11 17:29:01 EST (Tue, 11 Nov 2008)
@@ -70,8 +70,8 @@
     
  public:
  
-     typedef Container<node_base<Container>*> base_type;
-     typedef typename base_type::size_type size_type;
+    typedef Container<node_base<Container>*> base_type;
+    typedef typename base_type::size_type size_type;
     typedef self_type* base_pointer;
     typedef self_type const* const_base_pointer;
     
@@ -88,13 +88,13 @@
     void init()
     {
         for (typename base_type::size_type i=0; i<base_type::size(); ++i)
-            operator[](i) = nil();
+            operator[](i) = this; //nil();
     }
 
     // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
     bool const empty() const
     {
-        return ((this == nil()) || this->base_type::empty());
+        return ((this == nil()) || this->base_type::empty() || this == this->operator[](0) );
     }
 
     // O(n); n is number of parent's children
@@ -112,9 +112,9 @@
 : public node_with_parent_base, public binary_array<node_base<binary_array>*> {
     typedef node_base<binary_array> self_type;
     
- public:
+public:
  
-     typedef binary_array<node_base*> base_type;
+    typedef binary_array<node_base*> base_type;
     typedef self_type* base_pointer;
     typedef self_type const* const_base_pointer;
     
@@ -131,7 +131,7 @@
     void init()
     {
         for (base_type::size_type i=0; i<base_type::max_size(); ++i)
-            operator[](i) = nil();
+            operator[](i) = this; //nil();
     }
 
     // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
@@ -199,6 +199,7 @@
     base_type::size_type const get_index() const
     {
         return (static_cast<base_pointer>(this->m_parent)->base_type::operator[](0) == this ? 0 : 1);
+        //return 
     }
     
 };

Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_test.cpp	2008-11-11 17:29:01 EST (Tue, 11 Nov 2008)
@@ -15,265 +15,304 @@
 #include "helpers.hpp"
 #include "test_tree_traversal_data.hpp"
 
-BOOST_FIXTURE_TEST_SUITE(binary_tree_test, test_binary_tree_with_list_fixture<int>)
+BOOST_AUTO_TEST_SUITE( binary_tree_test /*, test_binary_tree_with_list_fixture<int>*/ )
 
 using namespace boost::tree;
 
-template <class Tree>
-void create_test_dataset2_tree(Tree& mytree)
-{
-    typename Tree::cursor c, c1, c2, c3, c4;
-    
-    c = mytree.root();
-
-    BOOST_CHECK(c.empty());
-    
-    c1 = mytree.insert(c, 1);
-    BOOST_CHECK_EQUAL(*c1, 1);
-    
-    BOOST_CHECK(!c.empty());
-    
-    BOOST_CHECK(c1.parent() == c);
-    
-    c2 = mytree.insert(c1, 2);
-    BOOST_CHECK(!c.empty());
-    BOOST_CHECK(c2.empty());
-    BOOST_CHECK_EQUAL(*c1, 1);
-    BOOST_CHECK_EQUAL(*c2, 2);
-    *c1 = 14;
-    BOOST_CHECK_EQUAL(*c1, 14);
-    BOOST_CHECK_EQUAL(*c2, 2);
-    BOOST_CHECK(c2.parent() == c1);
-    BOOST_CHECK(c1.parent() == c);
-    
-    c3 = c1.end();
-    BOOST_CHECK(c3 == c1.end());
-    --c3;
-    BOOST_CHECK_EQUAL(index(c3), 0);
-    BOOST_CHECK(c3.parent() != c3);
-    BOOST_CHECK(c3.parent() == c1);
-    BOOST_CHECK(c3 == c1.begin());
-    
-    *c3 = 3;
-    *(c1.begin()) = 2;
-    
-    BOOST_CHECK_EQUAL(*c3, 2);
-    ++c3;
-    c4 = mytree.insert(c3, 4);
-    BOOST_CHECK_EQUAL(*c4, 4);
-    c4 = c4.parent();
-    --c4;
-    BOOST_CHECK_EQUAL(*c4, 2);
-    BOOST_CHECK(c4.parent() == c1);
-    BOOST_CHECK(c4.empty());
-
-    BOOST_CHECK_EQUAL(*c1, 14);
-    
-    BOOST_CHECK(c1.begin().empty() || c1.end().empty());
-    
-    //c1 = mytree.erase(c1);
-    //BOOST_CHECK_EQUAL(*c1, 2);
-
-}
-
-template <class Tree>
-void validate_test_dataset2_tree(Tree const& mytree)
-{
-    typename Tree::const_cursor c = mytree.root();
-
-    BOOST_CHECK(!c.empty());
-    
-    c.to_begin();
-    BOOST_CHECK(c.parent() == mytree.root());
-    BOOST_CHECK_EQUAL(*c, 14);
-    
-    c.to_begin();
-    BOOST_CHECK(c.parent() == mytree.root().begin());
-    BOOST_CHECK_EQUAL(*c, 2);
-    
-    ++c;
-    BOOST_CHECK(c.parent() == mytree.root().begin());
-    BOOST_CHECK_EQUAL(*c.begin(), 4);
-    
-}
-
-template <class Tree>
-void inorder_erase_test_dataset1_tree(Tree& mytree)
-{
-    typename Tree::cursor c = mytree.root().end().end().begin();
-    BOOST_CHECK_EQUAL(*c, 14);
-    
-    c = c.parent().parent();
-    BOOST_CHECK_EQUAL(*(c.begin()), 10);
-    BOOST_CHECK(c.begin().empty());
-    BOOST_CHECK(!c.end().empty());
-    BOOST_CHECK_EQUAL(*c.end().begin(), 14);
-    c = c.begin();
-    
-    // Left child empty
-    c = mytree.inorder_erase(c);
-    BOOST_CHECK_EQUAL(*c, 11);
-
-    ++c;
-    BOOST_CHECK_EQUAL(*c.begin(), 12);
-    BOOST_CHECK(c.begin().empty());
-    BOOST_CHECK(c.end().empty());
-    c = c.begin();
-    
-    // Both children empty
-    c = mytree.inorder_erase(c);
-    BOOST_CHECK_EQUAL(*c, 13);
-}
-
-BOOST_AUTO_TEST_CASE( clear_test )
-{
-    bt.clear();    
-    BOOST_CHECK(bt.empty());
-}
+//template <class Tree>
+//void create_test_dataset2_tree(Tree& mytree)
+//{
+//    typename Tree::cursor c, c1, c2, c3, c4;
+//    
+//    c = mytree.root();
+//
+//    BOOST_CHECK(c.empty());
+//    
+//    c1 = mytree.insert(c, 1);
+//    BOOST_CHECK_EQUAL(*c1, 1);
+//    
+//    BOOST_CHECK(!c.empty());
+//    
+//    BOOST_CHECK(c1.parent() == c);
+//    
+//    c2 = mytree.insert(c1, 2);
+//    BOOST_CHECK(!c.empty());
+//    BOOST_CHECK(c2.empty());
+//    BOOST_CHECK_EQUAL(*c1, 1);
+//    BOOST_CHECK_EQUAL(*c2, 2);
+//    *c1 = 14;
+//    BOOST_CHECK_EQUAL(*c1, 14);
+//    BOOST_CHECK_EQUAL(*c2, 2);
+//    BOOST_CHECK(c2.parent() == c1);
+//    BOOST_CHECK(c1.parent() == c);
+//    
+//    c3 = c1.end();
+//    BOOST_CHECK(c3 == c1.end());
+//    --c3;
+//    BOOST_CHECK_EQUAL(index(c3), 0);
+//    BOOST_CHECK(c3.parent() != c3);
+//    BOOST_CHECK(c3.parent() == c1);
+//    BOOST_CHECK(c3 == c1.begin());
+//    
+//    *c3 = 3;
+//    *(c1.begin()) = 2;
+//    
+//    BOOST_CHECK_EQUAL(*c3, 2);
+//    ++c3;
+//    c4 = mytree.insert(c3, 4);
+//    BOOST_CHECK_EQUAL(*c4, 4);
+//    c4 = c4.parent();
+//    --c4;
+//    BOOST_CHECK_EQUAL(*c4, 2);
+//    BOOST_CHECK(c4.parent() == c1);
+//    BOOST_CHECK(c4.empty());
+//
+//    BOOST_CHECK_EQUAL(*c1, 14);
+//    
+//    BOOST_CHECK(c1.begin().empty() || c1.end().empty());
+//    
+//    //c1 = mytree.erase(c1);
+//    //BOOST_CHECK_EQUAL(*c1, 2);
+//
+//}
+//
+//template <class Tree>
+//void validate_test_dataset2_tree(Tree const& mytree)
+//{
+//    typename Tree::const_cursor c = mytree.root();
+//
+//    BOOST_CHECK(!c.empty());
+//    
+//    c.to_begin();
+//    BOOST_CHECK(c.parent() == mytree.root());
+//    BOOST_CHECK_EQUAL(*c, 14);
+//    
+//    c.to_begin();
+//    BOOST_CHECK(c.parent() == mytree.root().begin());
+//    BOOST_CHECK_EQUAL(*c, 2);
+//    
+//    ++c;
+//    BOOST_CHECK(c.parent() == mytree.root().begin());
+//    BOOST_CHECK_EQUAL(*c.begin(), 4);
+//    
+//}
+//
+//template <class Tree>
+//void inorder_erase_test_dataset1_tree(Tree& mytree)
+//{
+//    typename Tree::cursor c = mytree.root().end().end().begin();
+//    BOOST_CHECK_EQUAL(*c, 14);
+//    
+//    c = c.parent().parent();
+//    BOOST_CHECK_EQUAL(*(c.begin()), 10);
+//    BOOST_CHECK(c.begin().empty());
+//    BOOST_CHECK(!c.end().empty());
+//    BOOST_CHECK_EQUAL(*c.end().begin(), 14);
+//    c = c.begin();
+//    
+//    // Left child empty
+//    c = mytree.inorder_erase(c);
+//    BOOST_CHECK_EQUAL(*c, 11);
+//
+//    ++c;
+//    BOOST_CHECK_EQUAL(*c.begin(), 12);
+//    BOOST_CHECK(c.begin().empty());
+//    BOOST_CHECK(c.end().empty());
+//    c = c.begin();
+//    
+//    // Both children empty
+//    c = mytree.inorder_erase(c);
+//    BOOST_CHECK_EQUAL(*c, 13);
+//}
+//
+//BOOST_AUTO_TEST_CASE( clear_test )
+//{
+//    bt.clear();    
+//    BOOST_CHECK(bt.empty());
+//}
 
 BOOST_AUTO_TEST_CASE( constructors_test )
 {
     binary_tree<int> bt0;
+    BOOST_CHECK(bt0.root().m_node == (*bt0.root().m_node)[1]);
+    
     BOOST_CHECK(bt0.root().empty());
-    //BOOST_CHECK_EQUAL(0, 1);
+    BOOST_CHECK_EQUAL(0, 1);
     
     // test with allocator 
 }
 
-BOOST_AUTO_TEST_CASE( swap_binary_tree_test )
-{
-    using std::swap;
-    typedef binary_tree<int> tree_t;
-    tree_t tree1, tree2;
-    
-    // Filling with test data.
-    create_test_dataset2_tree(tree1);
-    validate_test_dataset2_tree(tree1);
-
-    // Swap tree1 with empty tree2
-    swap(tree1, tree2);
-    validate_test_dataset2_tree(tree2);
-    BOOST_CHECK(tree1.empty());
-    
-    // Swap back
-    swap(tree1, tree2);
-    validate_test_dataset2_tree(tree1);
-    BOOST_CHECK(tree2.empty());
-    
-    // Swap with tree containing different data
-    swap(tree1, bt);
-    validate_test_dataset1_tree(tree1);
-    validate_test_dataset2_tree(bt);
-}
-
-BOOST_AUTO_TEST_CASE( insert_subtree_test )
-{
-    binary_tree<int> bt0;
-    binary_tree<int>::cursor c = bt0.insert(bt0.root(), bt.root());    
-    validate_test_dataset1_tree(bt0);
-}
-
-BOOST_AUTO_TEST_CASE( copy_constructor_test )
-{
-    binary_tree<int> bt0(bt);
-    validate_test_dataset1_tree(bt0);
-}
-
-BOOST_AUTO_TEST_CASE( comparison_operator_test )
-{
-    BOOST_CHECK(bt == bt2);
-}
+//BOOST_AUTO_TEST_CASE( swap_binary_tree_test )
+//{
+//    using std::swap;
+//    typedef binary_tree<int> tree_t;
+//    tree_t tree1, tree2;
+//    
+//    // Filling with test data.
+//    create_test_dataset2_tree(tree1);
+//    validate_test_dataset2_tree(tree1);
+//
+//    // Swap tree1 with empty tree2
+//    swap(tree1, tree2);
+//    validate_test_dataset2_tree(tree2);
+//    BOOST_CHECK(tree1.empty());
+//    
+//    // Swap back
+//    swap(tree1, tree2);
+//    validate_test_dataset2_tree(tree1);
+//    BOOST_CHECK(tree2.empty());
+//    
+//    // Swap with tree containing different data
+//    swap(tree1, bt);
+//    validate_test_dataset1_tree(tree1);
+//    validate_test_dataset2_tree(bt);
+//}
+
+//BOOST_AUTO_TEST_CASE( insert_subtree_test )
+//{
+//    binary_tree<int> bt0;
+//    binary_tree<int>::cursor c = bt0.insert(bt0.root(), bt.root());    
+//    validate_test_dataset1_tree(bt0);
+//}
 
-BOOST_AUTO_TEST_CASE( splice_test )
+BOOST_AUTO_TEST_CASE( insert_value_test )
 {
     binary_tree<int> bt0;
-    bt0.splice(bt0.root(), bt);
-
-    BOOST_CHECK(bt.empty());    
-    validate_test_dataset1_tree(bt0);
-}
-
-BOOST_AUTO_TEST_CASE( binary_tree_test )
-{
-    binary_tree<int> bt0(bt);
-
-    // Change one value in bt0
-    binary_tree<int>::cursor c = bt0.root().begin().end().begin().begin();
-    int tmp = *c;
-    *c = tmp + 1;
-    BOOST_CHECK(bt != bt0);
-
-    // Change it back
-    c = bt0.root().begin().end().begin().begin();
-    *c = tmp;
-    BOOST_CHECK(bt == bt0);
-    
-    c = bt0.inorder_first();
-    BOOST_CHECK_EQUAL(*c, 1);
-    c = bt0.root();
-    //inorder::back(c);
-    //BOOST_CHECK_EQUAL(*c, 14);    
-
-    //inorder_erase_test_dataset1_tree(bt);
-}
-
-BOOST_AUTO_TEST_CASE( rotate_binary_tree_test )
-{
-    binary_tree<int>::cursor c = bt.root().begin().end();
-    BOOST_CHECK_EQUAL(*c.begin(), 6);
-
-    BOOST_CHECK_EQUAL(*c.parent(), 8);
-    BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant candidate
-    
-    BOOST_CHECK_EQUAL(*--c, 3); // differently (not invariantly!) spoken
-    BOOST_CHECK_EQUAL(*c.begin(), 1);
-    BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
-    BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
-
-    BOOST_CHECK_EQUAL(index(c), 1);    
-    BOOST_CHECK_EQUAL(*c.begin(), 6);
-        
-    bt.rotate(c); // Left rotate
-
-    BOOST_CHECK_EQUAL(*c.begin(), 6);
-    BOOST_CHECK_EQUAL(*c.parent().begin(), 8);
-    
-    BOOST_CHECK_EQUAL(*c.end().begin(), 7);
-    BOOST_CHECK_EQUAL(*c.begin().begin(), 3);
-    BOOST_CHECK_EQUAL(*c.begin().begin().begin(), 1);
-
-    BOOST_CHECK_EQUAL(*c.begin().end().begin(), 4);
-
-    c = c.begin();
-    BOOST_CHECK_EQUAL(*c.begin(), 3);
-    
-    bt.rotate(c); // Right rotate
-    
-    BOOST_CHECK_EQUAL(*c.begin(), 3);
-    c = c.end();
-
-    BOOST_CHECK_EQUAL(*c.begin(), 6);
-
-    BOOST_CHECK_EQUAL(*c.parent(), 8);
-    BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // other invariant candidate
-    
-    BOOST_CHECK_EQUAL(*--c, 3);
-    BOOST_CHECK_EQUAL(*c.begin(), 1);
-    BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
-    BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
-    
-    BOOST_CHECK_EQUAL(*c.begin(), 6);
+    BOOST_CHECK(bt0.root().empty());
     
-//    BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
-//    BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
+    binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8);
     
+    BOOST_CHECK(c == bt0.root().begin());
+    BOOST_CHECK(bt0.root().begin().parent() == bt0.root());
+    BOOST_CHECK(!bt0.root().empty());
+    BOOST_CHECK_EQUAL(*bt0.root().begin(), 8);
+    BOOST_CHECK(bt0.root().begin().empty());
+    
+    c = bt0.insert(c, 3);
+    
+    // The 8 valued cursor still ok?
+    BOOST_CHECK(bt0.root().begin().parent() == bt0.root());
+    BOOST_CHECK(!bt0.root().empty());
+    BOOST_CHECK_EQUAL(*bt0.root().begin(), 8);
+    
+    // The 3 valued cursor.
+    BOOST_CHECK(c == bt0.root().begin().begin());
+    BOOST_CHECK(bt0.root().begin().begin().parent() == bt0.root().begin());
+    BOOST_CHECK(!bt0.root().begin().empty());
+    BOOST_CHECK_EQUAL(*bt0.root().begin().begin(), 3);
+    BOOST_CHECK(bt0.root().begin().begin().empty());
+    
+    BOOST_CHECK(++c == bt0.root().begin().end());
+    
+    BOOST_CHECK_EQUAL(1, 2);
+}
+
+//BOOST_AUTO_TEST_CASE( insert_values_test )
+//{
+//    validate_test_dataset1_tree(bt);
+//}
+
+//BOOST_AUTO_TEST_CASE( copy_constructor_test )
+//{
+//    binary_tree<int> bt0(bt);
+//    validate_test_dataset1_tree(bt0);
+//}
+
+//BOOST_AUTO_TEST_CASE( comparison_operator_test )
+//{
+//    BOOST_CHECK(bt == bt2);
+//}
+//
+//BOOST_AUTO_TEST_CASE( splice_test )
+//{
+//    binary_tree<int> bt0;
+//    bt0.splice(bt0.root(), bt);
+//
+//    BOOST_CHECK(bt.empty());    
+//    validate_test_dataset1_tree(bt0);
+//}
+//
+//BOOST_AUTO_TEST_CASE( binary_tree_test )
+//{
+//    binary_tree<int> bt0(bt);
+//
+//    // Change one value in bt0
+//    binary_tree<int>::cursor c = bt0.root().begin().end().begin().begin();
+//    int tmp = *c;
+//    *c = tmp + 1;
+//    BOOST_CHECK(bt != bt0);
+//
+//    // Change it back
+//    c = bt0.root().begin().end().begin().begin();
+//    *c = tmp;
+//    BOOST_CHECK(bt == bt0);
+//    
+//    c = bt0.inorder_first();
+//    BOOST_CHECK_EQUAL(*c, 1);
+//    c = bt0.root();
+//    //inorder::back(c);
+//    //BOOST_CHECK_EQUAL(*c, 14);    
+//
+//    //inorder_erase_test_dataset1_tree(bt);
+//}
+//
+//BOOST_AUTO_TEST_CASE( rotate_binary_tree_test )
+//{
+//    binary_tree<int>::cursor c = bt.root().begin().end();
+//    BOOST_CHECK_EQUAL(*c.begin(), 6);
+//
+//    BOOST_CHECK_EQUAL(*c.parent(), 8);
+//    BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant candidate
+//    
+//    BOOST_CHECK_EQUAL(*--c, 3); // differently (not invariantly!) spoken
 //    BOOST_CHECK_EQUAL(*c.begin(), 1);
-//    BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant?
+//    BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
+//    BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
+//
+//    BOOST_CHECK_EQUAL(index(c), 1);    
+//    BOOST_CHECK_EQUAL(*c.begin(), 6);
+//        
+//    bt.rotate(c); // Left rotate
+//
+//    BOOST_CHECK_EQUAL(*c.begin(), 6);
+//    BOOST_CHECK_EQUAL(*c.parent().begin(), 8);
 //    
-//    BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
-//    BOOST_CHECK_EQUAL(*c.parent().parent().parent().begin(), 8);
-//    BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
-    
-}
+//    BOOST_CHECK_EQUAL(*c.end().begin(), 7);
+//    BOOST_CHECK_EQUAL(*c.begin().begin(), 3);
+//    BOOST_CHECK_EQUAL(*c.begin().begin().begin(), 1);
+//
+//    BOOST_CHECK_EQUAL(*c.begin().end().begin(), 4);
+//
+//    c = c.begin();
+//    BOOST_CHECK_EQUAL(*c.begin(), 3);
+//    
+//    bt.rotate(c); // Right rotate
+//    
+//    BOOST_CHECK_EQUAL(*c.begin(), 3);
+//    c = c.end();
+//
+//    BOOST_CHECK_EQUAL(*c.begin(), 6);
+//
+//    BOOST_CHECK_EQUAL(*c.parent(), 8);
+//    BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // other invariant candidate
+//    
+//    BOOST_CHECK_EQUAL(*--c, 3);
+//    BOOST_CHECK_EQUAL(*c.begin(), 1);
+//    BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
+//    BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
+//    
+//    BOOST_CHECK_EQUAL(*c.begin(), 6);
+//    
+////    BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
+////    BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
+//    
+////    BOOST_CHECK_EQUAL(*c.begin(), 1);
+////    BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant?
+////    
+////    BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
+////    BOOST_CHECK_EQUAL(*c.parent().parent().parent().begin(), 8);
+////    BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
+//    
+//}
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file