Boost logo

Boost-Commit :

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)


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk