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

From: ockham_at_[hidden]
Date: 2007-08-20 14:38:02

Author: bernhard.reiter
Date: 2007-08-20 14:38:01 EDT (Mon, 20 Aug 2007)
New Revision: 38802
URL: http://svn.boost.org/trac/boost/changeset/38802

Log:
Add ascending iterator
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending_iterator.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp
      - copied, changed from r38424, /sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_search_binary_tree_test.cpp
Removed:
   sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_search_binary_tree_test.cpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp                      |     7 +++++--                                 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2                    |     4 ++--                                    
   sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp |    12 ++++++++++++                            
   3 files changed, 19 insertions(+), 4 deletions(-)

Added: sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending.hpp	2007-08-20 14:38:01 EDT (Mon, 20 Aug 2007)
@@ -0,0 +1,63 @@
+//  Copyright (c) 2006, 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 ascending.hpp
+ * Ascending traversal algorithms for cursors
+ */
+//TODO:
+// Concept checks: MultiwayTree, parent?
+// Optimise for trees such as binary_tree with their own ascending begin() members!
+
+#ifndef BOOST_TREE_ASCENDING_HPP
+#define BOOST_TREE_ASCENDING_HPP
+
+#include <boost/tree/cursor.hpp>
+
+#include <boost/iterator/iterator_categories.hpp>
+
+
+namespace boost {
+namespace tree {
+
+namespace ascending {
+
+/** \addtogroup traversal */
+/*\@{*/
+
+/**
+ * @brief	Ascending successor
+ * @param c	MultiwayCursor to be set to its ascending successor
+ * @ingroup	traversal
+ */
+template <class MultiwayCursor>
+inline void forward(MultiwayCursor& c)
+{
+	c = c.parent();
+	return;
+}
+
+/**
+ * @brief	Ascending successor
+ * @param c	A cursor
+ * @return	Ascending successor of @a c
+ * @ingroup	traversal
+ */
+template <class MultiwayCursor>
+inline MultiwayCursor next(MultiwayCursor c)
+{
+	forward(c);
+	return c;
+}
+
+/*\@}*/
+
+} // namespace ascending
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_ASCENDING_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_iterator.hpp	2007-08-20 14:38:01 EDT (Mon, 20 Aug 2007)
@@ -0,0 +1,79 @@
+//  Copyright (c) 2006, 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 ascending_iterator.hpp
+ * Ascending iterator wrapper around cursor.
+ */
+
+// TODO: concept checks.
+
+#ifndef BOOST_TREE_ASCENDING_ITERATOR_HPP
+#define BOOST_TREE_ASCENDING_ITERATOR_HPP
+
+#include <boost/tree/ascending.hpp>
+#include <boost/tree/cursor.hpp>
+
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/utility/enable_if.hpp>
+
+namespace boost {
+namespace tree {
+	
+namespace ascending {
+
+template <class Cursor, class Tag = typename cursor_category<Cursor>::type>
+class iterator;
+
+template <class Cursor>
+class iterator<Cursor, bidirectional_traversal_tag>
+ : public boost::iterator_adaptor<iterator<Cursor, bidirectional_traversal_tag>
+      , Cursor
+      , boost::use_default
+      , forward_traversal_tag
+    > {
+ private:
+    struct enabler {};
+
+ public:
+    iterator()
+      : iterator::iterator_adaptor_() {}
+
+    explicit iterator(Cursor p)
+      : iterator::iterator_adaptor_(p) {}
+
+    template <class OtherCursor>
+    iterator(
+        iterator<OtherCursor> const& other
+      , typename boost::enable_if<
+            boost::is_convertible<OtherCursor,Cursor >
+          , enabler
+        >::type = enabler()
+    )
+      : iterator::iterator_adaptor_(other.base()) {}
+
+	operator Cursor()
+	{
+		return this->base();
+	}
+ private:
+    friend class boost::iterator_core_access;
+    
+    void increment()
+    {
+		forward(this->base_reference());
+    }
+    
+};
+
+
+} // namespace ascending
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_ASCENDING_ITERATOR_HPP

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-08-20 14:38:01 EDT (Mon, 20 Aug 2007)
@@ -6,14 +6,17 @@
 
 /**
  * @file iterators.hpp
- * In-, pre- and postorder iterator wrappers around cursors using the provided
- * traversal methods.
+ * Iterator wrappers around cursors using the provided
+ * traversal methods for:
+ * In-, pre- and postorder; ascending traversal.
  */
 
 
 #ifndef BOOST_TREE_ITERATORS_HPP
 #define BOOST_TREE_ITERATORS_HPP
 
+#include <boost/tree/ascending_iterator.hpp>
+
 #include <boost/tree/inorder_iterator.hpp>
 #include <boost/tree/preorder_iterator.hpp>
 #include <boost/tree/postorder_iterator.hpp>

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	2007-08-20 14:38:01 EDT (Mon, 20 Aug 2007)
@@ -22,7 +22,7 @@
         [ run binary_tree_test.cpp ]
         [ run key_search_binary_tree_test.cpp ]	
         [ run rank_search_binary_tree_test.cpp ]	
-	[ run traverse_search_binary_tree_test.cpp ]
+	[ run traverse_binary_tree_test.cpp ]
         [ run rotate_binary_tree_test.cpp ]
         [ run string_search_binary_tree_test.cpp ]
 
@@ -42,5 +42,5 @@
         [ run multiway_tree_test.cpp ]
         [ run unbalanced_binary_tree_test.cpp ]
         
-	[ run bind_return_test.cpp ]
+#	[ run bind_return_test.cpp ]
         ;

Copied: sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp (from r38424, /sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_search_binary_tree_test.cpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_search_binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp	2007-08-20 14:38:01 EDT (Mon, 20 Aug 2007)
@@ -166,6 +166,18 @@
         test_reverse_inorder_traversal(inorder::end(test_tree, forward_traversal_tag()), 
                                                                    inorder::begin(test_tree, forward_traversal_tag()));
 
+	binary_tree<int>::cursor c = test_tree.root();
+	ascending::iterator<binary_tree<int>::cursor> ai_root(c);
+	c = c.begin().end().begin().begin();
+	BOOST_CHECK(*c == 4);
+
+	ascending::iterator<binary_tree<int>::cursor> ais(c);
+	BOOST_CHECK(*ais == 4);
+	BOOST_CHECK(*++ais == 6);
+	BOOST_CHECK(*++ais == 3);
+	BOOST_CHECK(*++ais == 8);
+	BOOST_CHECK(++ais == ai_root);
+
         return 0;
 }
 

Deleted: sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_search_binary_tree_test.cpp	2007-08-20 14:38:01 EDT (Mon, 20 Aug 2007)
+++ (empty file)
@@ -1,203 +0,0 @@
-//  Copyright (c) 2006, 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)
-
-//TODO: Make this a test suite.
-//		Add iterator traversal tests - check if proper overloads (if present)
-//		are used.
-
-// TODO: get timings. that makes that no testcase anymore, right?
-//does boost have timers? what does the austern et al one look like?
-
-#include <boost/tree/binary_tree.hpp>
-
-#include <boost/tree/iterator.hpp>
-#include <boost/tree/traversal.hpp>
-
-#include <boost/test/minimal.hpp>
-
-#include <list>
-
-#include "helpers.hpp"
-
-using namespace boost::tree;
-using std::list;
-
-//std::vector<int> preorder_data()
-//{
-//	std::vector ret(9);
-//	ret[0] = 8;
-//	ret[1] = 3;
-//	ret[2] = 1;
-//	ret[3] = 6;
-//	ret[4] = 4;
-//	ret[5] = 7;
-//	ret[6] = 10;
-//	ret[7] = 14;
-//	ret[8] = 13;
-//}
-
-template <class Iterator>
-void test_inorder_traversal(Iterator a, Iterator b)
-{		
-	BOOST_CHECK(*a++ == 1);
-	BOOST_CHECK(*a++ == 3);
-	BOOST_CHECK(*a++ == 4);
-	BOOST_CHECK(*a++ == 6);
-	BOOST_CHECK(*a++ == 7);
-	BOOST_CHECK(*a++ == 8);
-	BOOST_CHECK(*a++ == 10);
-	BOOST_CHECK(*a++ == 11);
-	BOOST_CHECK(*a++ == 12);
-	BOOST_CHECK(*a++ == 13);
-	BOOST_CHECK(*a++ == 14);
-	BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_reverse_inorder_traversal(Iterator a, Iterator b)
-{	
-	BOOST_CHECK(*--a == 14);
-	BOOST_CHECK(*--a == 13);
-	BOOST_CHECK(*--a == 12);
-	BOOST_CHECK(*--a == 11);
-	BOOST_CHECK(*--a == 10);
-	BOOST_CHECK(*--a == 8);
-	BOOST_CHECK(*--a == 7);
-	BOOST_CHECK(*--a == 6);
-	BOOST_CHECK(*--a == 4);
-	BOOST_CHECK(*--a == 3);
-	BOOST_CHECK(*--a == 1);
-	BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_preorder_traversal(Iterator a, Iterator b)
-{	
-	BOOST_CHECK(*a++ == 8);
-	BOOST_CHECK(*a++ == 3);
-	BOOST_CHECK(*a++ == 1);
-	BOOST_CHECK(*a++ == 6);
-	BOOST_CHECK(*a++ == 4);
-	BOOST_CHECK(*a++ == 7);
-	BOOST_CHECK(*a++ == 10);
-	BOOST_CHECK(*a++ == 14);
-	BOOST_CHECK(*a++ == 13);
-	BOOST_CHECK(*a++ == 11);
-	BOOST_CHECK(*a++ == 12);
-	BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_reverse_preorder_traversal(Iterator a, Iterator b)
-{	 
-	BOOST_CHECK(*--a == 12);
-	BOOST_CHECK(*--a == 11);
-	BOOST_CHECK(*--a == 13);
-	BOOST_CHECK(*--a == 14);
-	BOOST_CHECK(*--a == 10);
-	BOOST_CHECK(*--a == 7);
-	BOOST_CHECK(*--a == 4);
-	BOOST_CHECK(*--a == 6);
-	BOOST_CHECK(*--a == 1);
-	BOOST_CHECK(*--a == 3);
-	BOOST_CHECK(*--a == 8);
-	BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_postorder_traversal(Iterator a, Iterator b)
-{	
-	BOOST_CHECK(*a++ == 1);	
-	BOOST_CHECK(*a++ == 4);
-	BOOST_CHECK(*a++ == 7);
-	BOOST_CHECK(*a++ == 6);
-	BOOST_CHECK(*a++ == 3);
-	BOOST_CHECK(*a++ == 12);
-	BOOST_CHECK(*a++ == 11);
-	BOOST_CHECK(*a++ == 13);
-	BOOST_CHECK(*a++ == 14);
-	BOOST_CHECK(*a++ == 10);
-	BOOST_CHECK(*a++ == 8);
-	BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_reverse_postorder_traversal(Iterator a, Iterator b)
-{	
-	BOOST_CHECK(*--a == 8);	
-	BOOST_CHECK(*--a == 10);
-	BOOST_CHECK(*--a == 14);
-	BOOST_CHECK(*--a == 13);
-	BOOST_CHECK(*--a == 11);
-	BOOST_CHECK(*--a == 12);
-	BOOST_CHECK(*--a == 3);
-	BOOST_CHECK(*--a == 6);
-	BOOST_CHECK(*--a == 7);
-	BOOST_CHECK(*--a == 4);
-	BOOST_CHECK(*--a == 1);
-	BOOST_CHECK(a == b);
-}
-
-template <class T> class list_push_back {
-	std::list<T> l;
-public:
-	list_push_back() { }
-	void operator() (T x) { l.push_back(x); }
-	std::list<T> const& result() const { return l; }
-	void reset() { l.clear(); }
-};
-
-int test_main(int, char* [])
-{
-	using boost::forward_traversal_tag;
-	
-	binary_tree<int> test_tree;
-	create_test_data_tree(test_tree);
-	
-	test_inorder_traversal(inorder::begin(test_tree), 
-						   inorder::end(test_tree));
-	test_reverse_inorder_traversal(inorder::end(test_tree), 
-								   inorder::begin(test_tree));
-		
-	test_preorder_traversal(preorder::begin(test_tree),
-							preorder::end(test_tree));
-//FIXME
-//	test_reverse_preorder_traversal(preorder::end(test_tree),
-//									preorder::begin(test_tree));
-	
-	test_postorder_traversal(postorder::begin(test_tree), 
-							 postorder::end(test_tree));
-	test_reverse_postorder_traversal(postorder::end(test_tree), 
-									 postorder::begin(test_tree));
-	
-	test_inorder_traversal(inorder::begin(test_tree, forward_traversal_tag()), 
-						   inorder::end(test_tree, forward_traversal_tag()));
-	test_reverse_inorder_traversal(inorder::end(test_tree, forward_traversal_tag()), 
-								   inorder::begin(test_tree, forward_traversal_tag()));
-
-	list_push_back<int> lpb;
-	//list<int> res;
-
-	// Each of the following blocks should be a 
-	// "recursive_*order_algorithm_test" of its own
-	lpb = inorder::for_each(test_tree.root().begin(), lpb);
-	//res = lpb.result();
-	test_inorder_traversal(lpb.result().begin(), lpb.result().end());
-	lpb.reset();
-
-	lpb = preorder::for_each(test_tree.root().begin(), lpb);
-	//res = lpb.result();
-	test_preorder_traversal(lpb.result().begin(), lpb.result().end());
-
-	lpb.reset();
-	lpb = postorder::for_each(test_tree.root().begin(), lpb);
-	//res = lpb.result();
-	test_postorder_traversal(lpb.result().begin(), lpb.result().end());
-
-	return 0;
-}
-
-