[Boost-commit] svn:boost r39775 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/algorithm libs/tree/doc libs/tree/test

From: ockham_at_[hidden]
Date: 2007-10-07 21:06:36

Author: bernhard.reiter
Date: 2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
New Revision: 39775
URL: http://svn.boost.org/trac/boost/changeset/39775

Log:
Add *order::copy algorithms 
and an output_cursor_iterator_wrapper.
Yes, the latter needs renaming.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                         |     2 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp             |    11 ++++++++                                
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp           |    18 ++++++++++++++                          
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp            |    11 ++++++++                                
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp                        |    37 ++++++++++++++++++++++++++++++          
   sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp                      |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2                     |     1                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk                   |    10 ++++----                                
   sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp |    49 ++++++++++++++++++++++++++++++++++++++++
   9 files changed, 135 insertions(+), 6 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -49,6 +49,8 @@
 * Add (inorder-)threaded binary trees?? Are they useful? Can they be balanced?
 * 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?
+* How much sense would an output cursor make? Especially within the context 
+  of the previous item.
 
 Proposal:
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -59,6 +59,17 @@
         return f;
 }
 
+template <class InCursor, class OutCursor>
+OutCursor copy (InCursor s, OutCursor t)
+{
+	if (!s.empty())
+		copy(s.begin(), t.begin());
+	*t = *s;
+	if (!(++s).empty())
+		copy(s.begin(), (++t).begin());
+	return t;
+}
+
 template <class MultiwayTree>
 iterator<typename MultiwayTree::cursor, forward_traversal_tag> 
 begin(MultiwayTree& t, forward_traversal_tag)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -62,6 +62,24 @@
 }
 //]
 
+// TODO: Should work with root() instead of root().begin()
+template <class InCursor, class OutCursor>
+OutCursor copy (InCursor s, OutCursor t)
+{
+	InCursor insubtree = s;
+	OutCursor outsubtree = t;
+	if (!s.empty())
+		copy(s.begin(), t.begin());
+	if (!(++s).empty()) {
+		copy(s.begin(), (++t).begin());
+	}
+	*outsubtree = *insubtree;
+	return outsubtree;
+}
+
+///Iterators
+
+
 /**
  * @brief	First element of a MultiwayTree in postorder traversal
  * 			(equivalent to inorder::begin())

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -58,6 +58,17 @@
         return f;
 }
 
+template <class InCursor, class OutCursor>
+OutCursor copy (InCursor s, OutCursor t)
+{
+	*t = *s;
+	if (!s.empty())
+		copy(s.begin(), t.begin());
+	if (!(++s).empty())
+		copy(s.begin(), (++t).begin());
+	return t;
+}
+
 /**
  * @brief	First element of a MultiwayTree in preorder traversal
  * @param t	A MultiwayTree

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -90,6 +90,43 @@
 struct ascending_random_access_cursor_tag
         : public descending_random_access_cursor_tag {};
 
+// TODO: Complete this.
+template<class OutputIterator>
+class output_cursor_iterator_wrapper {
+protected:
+	OutputIterator& iter;
+public:
+	explicit output_cursor_iterator_wrapper(OutputIterator& i) : iter(i) {}
+
+	output_cursor_iterator_wrapper& operator=(output_cursor_iterator_wrapper const& x)
+	{
+		iter = x.iter;
+		return *this;
+	}
+
+	// Unfortunately, Output Iterators do not necessarily expose their
+	// value_type (they just give void), so the following member 
+	// function has to be a template.
+	// TODO: Consult C++0x if this has been changed
+	template <class ValueType>
+	output_cursor_iterator_wrapper& operator=(ValueType const& value)
+	{ 
+		*(iter++) = value;
+		return *this; 
+	}
+
+	output_cursor_iterator_wrapper& operator*() { return *this; }
+	output_cursor_iterator_wrapper& operator++() { return *this; }
+	output_cursor_iterator_wrapper operator++(int) { return *this; }
+	output_cursor_iterator_wrapper& begin() { return *this; }
+};
+
+template<class OutputIterator>
+inline output_cursor_iterator_wrapper<OutputIterator>
+outputter_cursor_iterator_wrapper(OutputIterator o)
+{
+	return output_cursor_iterator_wrapper<OutputIterator>(o);
+}
 
 //define freestanding begin, end, size, empty using node's member fns?
 

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	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -8,7 +8,7 @@
  * @file iterators.hpp
  * Iterator wrappers around cursors using the provided
  * traversal methods for:
- * In-, pre- and postorder; ascending traversal.
+ * Pre-, in- and postorder; ascending traversal.
  */
 
 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/Jamfile.v2	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -20,6 +20,7 @@
                 [ glob ../../../boost/tree/balancers/*.hpp ]
                 [ glob ../../../boost/tree/comparators/*.hpp ]
                 [ glob ../../../boost/tree/detail/cursor/*.hpp ]
+		[ glob ../../../boost/tree/detail/iterator/*.hpp ]
                 [ glob ../../../boost/tree/detail/node/*.hpp ]
         :
                 <doxygen:param>"PREDEFINED=\"BOOST_PROCESS_DOXYGEN\""

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -188,7 +188,7 @@
 
 [section Tree Traversal]
 An interesting aspect of trees is that there are many ways to traverse a tree in a meaningful order.
-Among others, ['preorder], ['postorder] and ['inorder] are frequently encountered. For an overview, 
+Among others, ['preorder], ['inorder] and ['postorder] are frequently encountered. For an overview, 
 consult your favorite Computer Science textbook or [@http://en.wikipedia.org/wiki/Tree_traversal 
 Wikipedia on Tree Traversal]. 
 Given only the essential minimum of information (i.e. child "pointers" from a parent "node", but
@@ -209,20 +209,20 @@
 
 [funcref boost::tree::preorder::for_each preorder::for_each]
 
-[funcref boost::tree::postorder::for_each postorder::for_each]
-
 [funcref boost::tree::inorder::for_each inorder::for_each]
 
+[funcref boost::tree::postorder::for_each postorder::for_each]
+
 The other two options are both invoked by constructing an `iterator` with a cursor as argument:
 
 [/warning FIXME: Invalid class reference]
 
 [classref boost::tree::preorder::iterator preorder::iterator]
 
-[classref boost::tree::postorder::iterator postorder::iterator]
-
 [classref boost::tree::inorder::iterator inorder::iterator]
 
+[classref boost::tree::postorder::iterator postorder::iterator]
+
 If the argument cursor is descending, the iterator that will be constructed will internally use a `std::stack`
 of cursors. If on the other hand the cursor is ascending (has a `parent` member function), the iterator 
 does not need such an explicit stack representation. Looking at textbook examples, 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp	2007-10-07 21:06:35 EDT (Sun, 07 Oct 2007)
@@ -18,10 +18,14 @@
 
 #include <boost/test/minimal.hpp>
 
+#include <list>
+#include <iterator>
+
 #include "helpers.hpp"
 
 using namespace boost::tree;
 
+
 //std::vector<int> preorder_data()
 //{
 //	std::vector ret(9);
@@ -178,6 +182,51 @@
         BOOST_CHECK(*++ais == 8);
         BOOST_CHECK(++ais == ai_root);
 
+	binary_tree<int> test_tree2;
+	create_test_data_tree(test_tree2);
+//	BOOST_CHECK(test_tree == test_tree2);
+	
+	binary_tree<int>::cursor d = test_tree2.root();
+	d = d.begin().end().begin().begin();
+	*d = 29;
+	
+	c = test_tree.root();
+	d = test_tree2.root();
+
+	// output_cursor_iterator_wrapper tests
+	
+	// preorder::copy tests
+	std::list<int> pre_lst;
+	typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
+	typedef output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
+	back_insert_iter_list_int it_pre_lst = std::back_inserter(pre_lst);
+	oc_bi_lst_type oc_pre_lst = oc_bi_lst_type(it_pre_lst);
+	preorder::copy(c.begin(), oc_pre_lst);
+	test_preorder_traversal(pre_lst.begin(), pre_lst.end());
+
+	// inorder::copy tests
+	std::list<int> in_lst;
+	back_insert_iter_list_int it_in_lst = std::back_inserter(in_lst);
+	oc_bi_lst_type oc_in_lst = oc_bi_lst_type(it_in_lst);
+	inorder::copy(c.begin(), oc_in_lst);
+	test_inorder_traversal(in_lst.begin(), in_lst.end());
+	
+	// postorder::copy tests	
+	// Using a list iterator
+	std::list<int> lst(11);	
+	typedef output_cursor_iterator_wrapper<std::list<int>::iterator> oc_lst_type;
+	std::list<int>::iterator li = lst.begin();
+	oc_lst_type oc_lst(li);
+	postorder::copy(c.begin(), oc_lst);
+	test_postorder_traversal(lst.begin(), lst.end());
+
+	// Using a list<int> back_inserter
+	std::list<int> lst2;
+	back_insert_iter_list_int bi_lst = std::back_inserter(lst2);
+	oc_bi_lst_type oc_bi_lst = oc_bi_lst_type(bi_lst);
+	postorder::copy(c.begin(), oc_bi_lst);
+	test_postorder_traversal(lst2.begin(), lst2.end());
+		
         return 0;
 }