[Boost-commit] svn:boost r46422 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/algorithm/cursor libs/tree/test

From: ockham_at_[hidden]
Date: 2008-06-16 09:28:23

Author: bernhard.reiter
Date: 2008-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
New Revision: 46422
URL: http://svn.boost.org/trac/boost/changeset/46422

Log:
Add subtree algorithms equal() and size(), plus operator== and a size() member for binary_tree.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                             |     4 ++++                                    
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp                         |     1 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp                       |    32 ++++++++++++++++++++++++++++++++        
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp |     4 ----                                    
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp              |    23 +++++++++++++++++++++--                 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp         |    11 +++++++----                             
   sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp                    |     6 +++++-                                  
   7 files changed, 70 insertions(+), 11 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
@@ -14,6 +14,9 @@
 [section TODO]
 
 General:
+* Use the example trees form Knuth as test example data.
+* Write (internal/external?) adaptors for other tree libraries, as Kaspar Peeters' or
+  Adobe's.
 * 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:
@@ -66,6 +69,7 @@
   root nodes and fields of use such as `forest_trees`; but for the latter, something similar
   as inorder_insert might come in handy.
 * Add (inorder-)threaded binary trees?? Are they useful? Can they be balanced?
+  They'd surely be interesting for experimenting with algorithms!
 * Start an RFC: what subtree algorithms should there be? In particular, of which of
   the STL's linear algorithms should there be a hierarchical version?
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp	2008-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
@@ -12,6 +12,7 @@
 #ifndef BOOST_TREE_ALGORITHM_HPP
 #define BOOST_TREE_ALGORITHM_HPP
 
+#include <boost/tree/detail/algorithm/cursor/general.hpp>
 
 #include <boost/tree/detail/algorithm/cursor/ascending.hpp>
 

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-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
@@ -14,6 +14,7 @@
 #define BOOST_TREE_BINARY_TREE_HPP
 
 #include <boost/tree/cursor.hpp>
+#include <boost/tree/detail/algorithm/cursor/general.hpp>
 #include <boost/tree/detail/algorithm/cursor/inorder.hpp>
 
 #include <boost/tree/detail/node/traits.hpp>
@@ -197,6 +198,11 @@
                 return m_header[1] == &m_header;
         }
         
+	size_type size() const
+	{
+		return boost::tree::size(root());
+	}
+	
         // Hierarchy-specific
         
         /**
@@ -571,6 +577,32 @@
         } 
 };
 
+/**
+ *  @brief  Binary tree equality comparison.
+ *  @param  x  A %binary_tree.
+ *  @param  y  A %binary_tree of the same type as @a x.
+ *  @return  True iff the size and elements of the binary trees are equal.
+ *
+ *  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.
+ */
+template <class Tp, class Alloc>
+inline bool operator==(binary_tree<Tp, Alloc> const& x 
+					 , binary_tree<Tp, Alloc> const& y)
+{
+	 return (x.size() == y.size() 
+	 		 && equal(x.root(), y.root()));
+}
+
+/// Based on operator==
+template <class Tp, class Alloc>
+inline bool operator!=(binary_tree<Tp, Alloc> const& x 
+					 , binary_tree<Tp, Alloc> const& y)
+{
+	 return (!(x == y));
+}
+
 namespace inorder {
 
 /**

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp	2008-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
@@ -15,10 +15,6 @@
 #ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_ASCENDING_HPP
 #define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_ASCENDING_HPP
 
-#include <boost/tree/cursor.hpp>
-
-#include <boost/iterator/iterator_categories.hpp>
-
 
 namespace boost {
 namespace tree {

Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp	2008-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
@@ -0,0 +1,99 @@
+//  Copyright (c) 2006-2008, Bernhard Reiter
+//
+//  Distributed under the Boost Software License, Version 1.0.
+//  (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+/**
+ * @file general.hpp
+ * General algorithms for cursors
+ */
+//TODO:
+// Concept checks
+
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_GENERAL_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_GENERAL_HPP
+
+
+namespace boost {
+namespace tree {
+
+
+// What about the subtree shapes?
+/**
+ *  @brief		Checks two subtrees for element-wise equality.
+ *  @param c1	An input cursor.
+ *  @param c2	An input cursor.
+ *  @return		A boolean true or false.
+ *
+ *  Compares the elements of two subtrees using @c ==. Returns true if
+ *  all the corresponding elements of the subtrees are equal; otherwise,
+ *  it returns false.
+ */
+template <class InCursor1, class InCursor2>
+bool equal(InCursor1 c1, InCursor2 c2)
+{
+	InCursor1 d1 = c1.end();
+	c1.to_begin();
+	c2.to_begin();
+	if (!(*c1 == *c2))
+		return false;
+	do {
+		if (!c1.empty())
+			if (!equal(c1, c2))
+				return false;
+		++c2;
+	} while (c1++ != d1);
+	
+	return true;
+}
+
+
+// Is it really a good idea to use InCursor::size_type?
+// For a binary_cursor, a boolean size_type would be enough - but
+// not for a subtree algorithm like this one.
+/**
+ *  @brief		Calculates the number of elements in a subtree.
+ *  @param c	An input cursor.
+ *  @param s	The size type of @c c1.
+ * 
+ * After finishing, s will have been increased by the number of elements in c. 		
+ */
+template <class InCursor>
+void size(InCursor c, typename InCursor::size_type& s)
+{
+	InCursor d = c.end();
+	c.to_begin();
+	++s;
+	do
+		if (!c.empty())
+			size(c, s);
+	while (c++ != d);
+}
+
+
+/**
+ *  @brief		Returns the number of elements in a subtree.
+ *  @param c	An input cursor.
+ *  @return		The size type of @c c1.
+ */
+template <class InCursor>
+typename InCursor::size_type size(InCursor c)
+{
+	typename InCursor::size_type s = 0;
+	InCursor d = c.end();
+	c.to_begin();
+	++s;
+	do
+		if (!c.empty())
+			size(c, s);
+	while (c++ != d);
+	
+	return s;
+}
+
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_ALGORITHM_CURSOR_GENERAL_HPP

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-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
@@ -149,33 +149,52 @@
         typedef binary_tree<int> tree_t;
         tree_t tree1, tree2;
         
+	// Filling with test data.
         create_binary_tree(tree1);
         validate_binary_tree(tree1);
 
+	// Swap tree1 with empty tree2
         test_swap_binary_trees(tree1, tree2);
         validate_binary_tree(tree2);
         BOOST_CHECK(tree1.empty());
 
+	// Swap back
         test_swap_binary_trees(tree1, tree2);
         validate_binary_tree(tree1);
         BOOST_CHECK(tree2.empty());
         
+	// Fill empty tree2 with different data
         create_test_data_tree(tree2);
         validate_test_data_tree(tree2);
         
+	// Swap
         test_swap_binary_trees(tree1, tree2);
-	
         validate_test_data_tree(tree1);
         validate_binary_tree(tree2);
         
         destroy_binary_tree(tree2);
 
+	// Insert subtree
         tree_t::cursor c = tree2.insert(tree2.root(), tree1.root());	
         BOOST_CHECK(*c == 8);
         validate_test_data_tree(tree2);
         
-	tree_t tree3(tree2);	
+	// Copy constructor
+	tree_t tree3(tree2);
         validate_test_data_tree(tree3);
+	BOOST_CHECK(tree2 == tree3);
+	
+	// Change one value in test_tree3
+	c = tree3.root().begin().end().begin().begin();
+	int tmp = *c;
+	*c = tmp + 1;
+	BOOST_CHECK(tree2 != tree3);
+
+	// Change it back
+	c = tree3.root().begin().end().begin().begin();
+	*c = tmp;
+	BOOST_CHECK(tree2 == tree3);
+	
         c = tree3.inorder_first();
         BOOST_CHECK(*c == 1);
         c = tree3.root();

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp	2008-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
@@ -50,15 +50,18 @@
         binary_tree<int> test_tree, test_tree2;
         create_test_data_tree(test_tree);
         create_test_data_tree(test_tree2);
-//	BOOST_CHECK(test_tree == test_tree2);
-	
+		
         binary_tree<int>::cursor c = test_tree.root();
         binary_tree<int>::cursor d = test_tree2.root();
 
+	// Just to make sure we won't be getting any false positives when 
+	// copying test_tree1 to test_tree2, we'll change one of test_tree2's
+	// values.
         d = d.begin().end().begin().begin();
-	*d = 29;
+	++*d;
+	BOOST_CHECK(test_tree != test_tree2);
         d = test_tree2.root();
-		
+
         test::preorder::algorithms (test_tree.root(), test_tree2.root());
         test::inorder::algorithms  (test_tree.root(), test_tree2.root());
         test::postorder::algorithms(test_tree.root(), test_tree2.root());

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp	2008-06-16 09:28:22 EDT (Mon, 16 Jun 2008)
@@ -11,6 +11,7 @@
 
 #include <boost/test/minimal.hpp>
 
+#include <vector>
 #include <list>
 #include <iterator>
 
@@ -50,7 +51,10 @@
                                             boost::on_discover_vertex()));
         
         // We need a color map!
- 	//boost::depth_first_visit(test_tree, test_tree.root(), preorder_writer);
+	
+	std::vector<boost::default_color_type> color(test_tree.size());
+ 
+ 	//boost::depth_first_visit(test_tree, test_tree.root(), preorder_writer, &color[0]);
         
         // Output test_tree using write_graphviz. This might require copying
         // the IncidenceGraph to a VertexListGraph (using copy_component)