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

Subject: [Boost-commit] svn:boost r57456 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-11-07 12:37:44

Author: bernhard.reiter
Date: 2009-11-07 12:37:43 EST (Sat, 07 Nov 2009)
New Revision: 57456
URL: http://svn.boost.org/trac/boost/changeset/57456

Log:
Fixes to ascending to_first and to_last
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp                         |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp                     |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp              |    30 ++++++++++++++++++++++++++++--          
   sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp                        |     3 ++-                                     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp            |    27 ++++++++++++++++++++++++++-             
   sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp |     1 +                                       
   6 files changed, 59 insertions(+), 6 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp	2009-11-07 12:37:43 EST (Sat, 07 Nov 2009)
@@ -441,7 +441,7 @@
         // If yes, we could just insert at pos.
         
         cursor c = pos.base().base().base();
-        to_rightmost(c);
+        //to_rightmost(c);
         
         c = h.insert(c, data_type(val));
         

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-11-07 12:37:43 EST (Sat, 07 Nov 2009)
@@ -37,7 +37,7 @@
 public:
     typedef Tp value_type;
     typedef typename Alloc::template rebind<value_type>::other allocator_type;
-    // Allocator usage roghly follows gcc's stl_list.h practice. 
+    // Allocator usage roughly follows gcc's stl_list.h practice.
 
 private:        
     typedef detail::ascending_node<value_type> node_type;

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp	2009-11-07 12:37:43 EST (Sat, 07 Nov 2009)
@@ -135,10 +135,23 @@
     (void)) // return type
 to_first(inorder, Cursor& c, ascending_vertical_traversal_tag)
 {
+	Cursor d = c;
     to_leftmost(c);
-    c.to_parent();
+    if (c != d)
+		c.to_parent();
 }
 
+//template <class Cursor>
+//BOOST_CONCEPT_REQUIRES(
+//    ((RootTrackingCursor<Cursor>)),
+//    (void)) // return type
+//to_first(inorder, Cursor& c, root_tracking_vertical_traversal_tag)
+//{
+//    to_leftmost(c);
+//    if (!c.is_root())
+//		c.to_parent();
+//}
+
 /**
  * @brief   Last element of a subtree in inorder traversal
  * @param c Subtree root cursor that will be set to the last inorder 
@@ -175,10 +188,23 @@
     (void)) // return type
 to_last(inorder, Cursor& c, ascending_vertical_traversal_tag)
 {
+	Cursor d = c;
     to_rightmost(c);
-    c.to_parent();
+    if (c != d)
+		c.to_parent();
 }
 
+//template <class Cursor>
+//BOOST_CONCEPT_REQUIRES(
+//    ((RootTrackingCursor<Cursor>)),
+//    (void)) // return type
+//to_last(inorder, Cursor& c, root_tracking_vertical_traversal_tag)
+//{
+//    to_rightmost(c);
+//    if (!c.is_root())
+//		c.to_parent();
+//}
+
 /**
  * @brief   One position past the last element of a subtree in inorder 
  *          traversal

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp	2009-11-07 12:37:43 EST (Sat, 07 Nov 2009)
@@ -132,7 +132,8 @@
 
      void decrement()
      {
-         predecessor(inorder(), this->base_reference());
+    	 // Works also if we're past the last element:
+    	 predecessor(inorder(), this->base_reference());
      }
  };
 

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-11-07 12:37:43 EST (Sat, 07 Nov 2009)
@@ -27,6 +27,7 @@
 //    BOOST_CHECK_EQUAL(++x, &bt0.m_header.m_children.data()[1]);
 
     //BOOST_CHECK(bt0.root().begin() == bt0.root().end()); //FIXME
+
     // test with allocator? 
 }
 
@@ -50,7 +51,7 @@
 {
     binary_tree<int> bt0;
     
-    binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8); //FIXME   
+    binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.end()*/, 8); //FIXME
     c.to_begin();
 
     BOOST_CHECK(c == bt0.root().begin());
@@ -75,6 +76,30 @@
     BOOST_CHECK(bt0.root().begin().begin().is_leaf());
     
     BOOST_CHECK(++c == bt0.root().begin().end());
+
+    c = bt0.insert(c, 7);
+
+    BOOST_CHECK(c == bt0.root().begin().end());
+    BOOST_CHECK(bt0.root().begin().end().parent() == bt0.root().begin());
+    BOOST_CHECK(!bt0.root().begin().end().is_leaf());
+    BOOST_CHECK_EQUAL(*bt0.root().begin().end(), 7);
+    BOOST_CHECK(bt0.root().begin().end().end().is_leaf());
+
+    c = bt0.insert(c, 6); // Non-leaf insert
+
+    BOOST_CHECK(c == bt0.root().begin().end());
+    BOOST_CHECK(bt0.root().begin().end().parent() == bt0.root().begin());
+    BOOST_CHECK(!bt0.root().begin().end().is_leaf());
+    BOOST_CHECK_EQUAL(*bt0.root().begin().end(), 6);
+    BOOST_CHECK(!bt0.root().begin().end().end().is_leaf());
+
+    c.to_end();
+    BOOST_CHECK(c == bt0.root().begin().end().end());
+    BOOST_CHECK(bt0.root().begin().end().end().parent() == bt0.root().begin().end());
+    BOOST_CHECK(!bt0.root().begin().end().end().is_leaf());
+    BOOST_CHECK_EQUAL(*bt0.root().begin().end().end(), 7);
+    BOOST_CHECK(bt0.root().begin().end().end().end().is_leaf());
+
 }
 
 BOOST_AUTO_TEST_SUITE_END()

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp	2009-11-07 12:37:43 EST (Sat, 07 Nov 2009)
@@ -48,6 +48,7 @@
     BOOST_CHECK(c == my_tree.begin());
         
     c1 = my_tree.insert(c, 8);
+    BOOST_CHECK(c1 == my_tree.begin());
     
     BOOST_CHECK_EQUAL(*c1, 8);