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

From: ockham_at_[hidden]
Date: 2008-06-06 17:38:39

Author: bernhard.reiter
Date: 2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
New Revision: 46203
URL: http://svn.boost.org/trac/boost/changeset/46203

Log:
Pretty lot of polishing to *order iterators and algorithms.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                         |    46 ++++-----                               
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp             |   131 ++-------------------------             
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp           |    77 ++--------------                        
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp            |    74 ++-------------                         
   sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp                 |     4                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp                   |    89 ++++++++++++++++++                      
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp                        |    49 +++++++--                               
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp                |    14 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp |   188 +++++++++++++++------------------------ 
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder.hpp                       |    84 ++---------------                       
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp              |     9 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp                     |    81 ++--------------                        
   sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp            |     8 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp                      |   156 +++++++++++---------------------        
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp             |     7                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html             |     4                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/multiway_tree_test.cpp        |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/nary_tree_test.cpp            |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp |    51 ++++++++++                              
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp  |    13 --                                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp |   126 ++++++++++++++++++++++----              
   21 files changed, 513 insertions(+), 702 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -14,18 +14,31 @@
 [section TODO]
 
 General:
-
+* Actually implement stack-based pre- and postorder iterators for forward cursors.
+  (For now, they're only dummies.)
+* Get rid of checks for/assignments to root and shoot in pre/post/inorder algorithms,
+  as they are otherwise limited to "whole" trees and cannot be applied to subtrees.
+  In order to work for subtrees, it's probable that we need at least an int to store
+  the current depth. (Which, in turn, would make the free-standing forward/back/next/prior 
+  algortihms etc. more or less useless without that piece of extra information and would
+  only leave us with the iterators to store it.)
+* Deprecate shoot()? It's main use was for inorder::end(), which is now root().
+  Would (binary tree) lower_bound() be possible without shoot()? What would it have to be 
+  like? What would be the implications for balanced_trees? (Especially the lower_bound 
+  for search vs insert purposes problem.)
+* Take care of inorder::begin() for binary_tree<int>.  
+* Keep in mind it's not necessarily a good thing to have *order::end() be the last element's
+  right child. For inorder and postorder, it seems like the subtree root is a better choice.
+  For preorder, things are pretty diffcult.
+* Do a unit test that creates a random tree with a given number of elements. 
+  Let the cursor based *order algorithms then copy its elements into linear structures 
+  and compare these linear structures to an iterator-based *order traversal.
 * Should const_cursor have cbegin(), cend() and cparent() members?
 * Implement "flat" (sequential *order representation) trees (cf. Knuth, Fundamental Algorithms,
   pp. 348--351). Those should be especially useful for automated testing of "real" (binary, 
   forest) trees.
 * have `erase()` operations return cursor/iterator instead of void (as in new STD)
 * modify parity/parent specs according to newsgroup thread, but members add to binary_tree cursor!
-* Add O(n) generations(ancestor, descendant) algorithm (vertical distance) yielding number
-  of generations between ancestor and descendant (ascending cursor only)
-  Or rather, as this introduces something that shouldn't be conceptually different from
-  std::distance: introduce a (forward, of course) (hierarchy_)ascending::iterator that just moves up 
-  towards the root when incremented.
 * We might need still more binary_tree members for more efficient functions operating on
   ranges...
 * `insert()` and `erase()` semantics need reworking. For instance, Proposal 23.X.4.1.4 §2 
@@ -33,33 +46,16 @@
   for a really basic operation. Still, it's important to consider special cases such as
   root nodes and fields of use such as `forest_trees`; but for the latter, something similar
   as inorder_insert might come in handy.
-* Actually implement stack-based pre- and postorder iterators for forward cursors.
-* Get rid of checks for/assignments to root and shoot in pre/post/inorder algorithms,
-  as they are otherwise limited to "whole" trees and cannot be applied to subtrees.
-  In order to work for subtrees, it's probable that we need at least an int to store
-  the current depth. (Which, in turn, would make the free-standing forward/back/next/prior 
-  algortihms etc. more or less useless without that piece of extra information and would
-  only leave us with the iterators to store it.)
-  Alternatively (or additionally), we could implement (hierarchical) "subtree" versions
-  of linear algorithms (as in the STL) in the respective namespace, eg 
-  template <class Cur, class Op> Cur preorder::foreach(Cur subtree, Op f) { /* ... */ }
-  That would leave to the algorithm how to store information about what the root is,
-  or just not require that information by working recursively instead. (It might therefore even be
-  faster than a "linear" algorithm using the *order iterator adaptors.)
-  As for such an subtree-based algorithm approach, note that we already have an example:
-  inorder::lower_bound (and upper_bound, of course) performs binary tree search and just
-  *can't* be simulated via std::lower_bound (which just performs ordinary binary search)
-  in an equally efficient way.
 * 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:
 
 * Add a revision log:
  * Add to_parent() (replaces operator!()), to_begin() and to_end() descending cursor members.
+* Probably split up cursor categories into: cursor (value access) category, vertical traversal 
+  and horizontal traversal (along the lines of the new iterator concepts).
 * cursor's begin(), end() and parent() members now only return cursor, same for const_cursor.
   (This somewhat breaks with container requirements, but it makes sense this way.)
 * Add InputCursor requirements: binary cursor if it's a binary_tree member function, etc.

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	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -100,15 +100,18 @@
         return t;
 }
 
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor, forward_traversal_tag> 
-begin(MultiwayTree& t, forward_traversal_tag)
+
+/// Iterators
+
+template <class MultiwayCursor>
+iterator<MultiwayCursor, forward_traversal_tag> 
+begin(MultiwayCursor c, forward_traversal_tag)
 {
-	typedef typename MultiwayTree::cursor cursor;
+	typedef MultiwayCursor cursor;
         std::stack<cursor> s;
          typename cursor_size<cursor>::type branch = 0;
          typename cursor_size<cursor>::type i = 0;
-	s.push(t.root());
+	s.push(c);
         while (!s.top().empty()) {
                 ++i;
                 if (!branch && !s.top().end().empty())
@@ -118,126 +121,18 @@
         return iterator<cursor, forward_traversal_tag>(s, branch);
 }
 
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor> 
-begin(MultiwayTree& t, bidirectional_traversal_tag)
-{
-	return iterator<typename MultiwayTree::cursor>(first(t));
-}
-
-/**
- * @brief	First element of a MultiwayTree in inorder traversal
- * 			(equivalent to postorder::begin())
- * @param t	A MultiwayTree
- * @return	Mutable inorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor> begin(MultiwayTree& t)
-{
-	typedef typename cursor_category<typename MultiwayTree::cursor>::type
-		traversal;
-	return begin(t, traversal());
-}
-
-/**
- * @brief	First element of a MultiwayTree in inorder traversal
- * 			(Alias of cbegin(); equivalent to postorder::begin())
- * @param t	A MultiwayTree
- * @return	Read-only inorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> begin(MultiwayTree const& t)
-{
-	return cbegin(t);
-}
-
-
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor>
-cbegin(MultiwayTree const& t, bidirectional_traversal_tag)
-{
-	return iterator<typename MultiwayTree::const_cursor>(cfirst(t));
-}
-
-/**
- * @brief	First element of a MultiwayTree in inorder traversal
- * 			(equivalent to postorder::begin())
- * @param t	A MultiwayTree
- * @return	Read-only inorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> cbegin(MultiwayTree const& t)
-{
-	typedef typename cursor_category<
-		typename MultiwayTree::const_cursor>::type traversal;
-	return cbegin(t, traversal());
-}
-
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor, forward_traversal_tag> 
-end(MultiwayTree& t, forward_traversal_tag)
+template <class MultiwayCursor>
+iterator<MultiwayCursor, forward_traversal_tag> 
+end(MultiwayCursor c, forward_traversal_tag)
 {
-	typedef typename MultiwayTree::cursor cursor;
+	typedef MultiwayCursor cursor;
         std::stack<cursor> s;
-	s.push(t.root());
+	s.push(c);
         while (!s.top().empty())
                 s.push(s.top().end());
         return iterator<cursor, forward_traversal_tag>(s, s.size());
 }
 
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor, bidirectional_traversal_tag>
-end(MultiwayTree& t, bidirectional_traversal_tag)
-{
-	return iterator<typename MultiwayTree::cursor>(last(t));
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in inorder traversal (Alias of cend())
- * @param t	A MultiwayTree
- * @return	Mutable inorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor> end(MultiwayTree& t)
-{
-	typedef typename cursor_category<typename MultiwayTree::cursor>::type
-		traversal;
-	return end(t, traversal());
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in inorder traversal (Alias of cend())
- * @param t	A MultiwayTree
- * @return	Read-only inorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> end(MultiwayTree const& t)
-{
-	return cend(t);
-}
-
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor>
-cend(MultiwayTree const& t, bidirectional_traversal_tag)
-{
-	return iterator<typename MultiwayTree::const_cursor>(clast(t));
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in inorder traversal
- * @param t	A MultiwayTree
- * @return	Read-only inorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> cend(MultiwayTree const& t)
-{
-	typedef typename cursor_category<
-		typename MultiwayTree::const_cursor>::type traversal;
-	return cend(t, traversal());
-}
 
 } // namespace inorder
 

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	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -111,77 +111,20 @@
 
 ///Iterators
 
-
-/**
- * @brief	First element of a MultiwayTree in postorder traversal
- * 			(equivalent to inorder::begin())
- * @param t	A MultiwayTree
- * @return	Mutable postorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor> begin(MultiwayTree& t)
-{
-	return iterator<typename MultiwayTree::cursor>(first(t));
-}
-
-/**
- * @brief	First element of a MultiwayTree in postorder traversal
- * 			(Alias of cbegin(); equivalent to inorder::begin())
- * @param t	A MultiwayTree
- * @return	Read-only postorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> begin(MultiwayTree const& t)
-{
-	return cbegin(t);
-}
-
-/**
- * @brief	First element of a MultiwayTree in postorder traversal
- * 			(equivalent to inorder::begin())
- * @param t	A MultiwayTree
- * @return	Read-only postorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> cbegin(MultiwayTree const& t)
-{
-	return iterator<typename MultiwayTree::const_cursor>(first(t));
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in postorder traversal (Alias of cend())
- * @param t	A MultiwayTree
- * @return	Mutable postorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor> end(MultiwayTree& t)
-{
-	return iterator<typename MultiwayTree::cursor>(last(t));
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in postorder traversal (Alias of cend())
- * @param t	A MultiwayTree
- * @return	Read-only postorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> end(MultiwayTree const& t)
+template <class Cursor>
+iterator<Cursor, forward_traversal_tag> 
+begin(Cursor c, forward_traversal_tag)
 {
-	return cend(t);
+	// TODO: Only a (bidirectional) dummy!
+	return iterator<Cursor, forward_traversal_tag>(first(c));
 }
 
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in postorder traversal
- * @param t	A MultiwayTree
- * @return	Read-only postorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> cend(MultiwayTree const& t)
+template <class Cursor>
+iterator<Cursor, forward_traversal_tag> 
+end(Cursor c, forward_traversal_tag)
 {
-	return iterator<typename MultiwayTree::const_cursor>(clast(t));
+	// TODO: Only a (bidirectional) dummy!
+	return iterator<Cursor, forward_traversal_tag>(last(c));
 }
 
 } // namespace postorder

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	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -101,74 +101,20 @@
         return t;
 }
 
-/**
- * @brief	First element of a MultiwayTree in preorder traversal
- * @param t	A MultiwayTree
- * @return	Mutable preorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor> begin(MultiwayTree& t)
+template <class Cursor>
+iterator<Cursor, forward_traversal_tag> 
+begin(Cursor c, forward_traversal_tag)
 {
-	return iterator<typename MultiwayTree::cursor>(first(t));
+	// TODO: Only a (bidirectional) dummy!
+	return iterator<Cursor, forward_traversal_tag>(first(c));
 }
 
-/**
- * @brief	First element of a MultiwayTree in preorder traversal
- * 			(Alias of cbegin())
- * @param t	A MultiwayTree
- * @return	Read-only preorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> begin(MultiwayTree const& t)
+template <class Cursor>
+iterator<Cursor, forward_traversal_tag> 
+end(Cursor c, forward_traversal_tag)
 {
-	return cbegin(t);
-}
-
-/**
- * @brief	First element of a MultiwayTree in preorder traversal
- * @param t	A MultiwayTree
- * @return	Read-only preorder iterator to the first element of @a t
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> cbegin(MultiwayTree const& t)
-{
-	return iterator<typename MultiwayTree::const_cursor>(cfirst(t));
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in preorder traversal (Alias of cend())
- * @param t	A MultiwayTree
- * @return	Mutable preorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::cursor> end(MultiwayTree& t)
-{
-	return iterator<typename MultiwayTree::cursor>(last(t));
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in preorder traversal (Alias of cend())
- * @param t	A MultiwayTree
- * @return	Read-only preorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> end(MultiwayTree const& t)
-{
-	return cend(t);
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in preorder traversal
- * @param t	A MultiwayTree
- * @return	Read-only preorder iterator one position past the last element of @a t 
- */
-template <class MultiwayTree>
-iterator<typename MultiwayTree::const_cursor> cend(MultiwayTree const& t)
-{
-	return iterator<typename MultiwayTree::const_cursor>(clast(t));
+	// TODO: Only a (bidirectional) dummy!
+	return iterator<Cursor, forward_traversal_tag>(last(c));
 }
 
 } // namespace preorder

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -182,7 +182,7 @@
          */
         iterator end()
         {
-		return iterator(h.shoot());
+		return iterator(h.root());
         }
 
         /**
@@ -200,7 +200,7 @@
          */	
         const_iterator cend() const
         {
-		return const_iterator(h.cshoot());
+		return const_iterator(h.croot());
         }
 
         /**

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-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -603,7 +603,7 @@
  */
 template <class T, class Alloc>
 typename binary_tree<T, Alloc>::cursor 
-first(binary_tree<T, Alloc>& t)
+first_cursor(binary_tree<T, Alloc>& t)
 {
         return t.inorder_first();
 }
@@ -617,7 +617,7 @@
  */
 template <class T, class Alloc>
 typename binary_tree<T, Alloc>::const_cursor 
-first(binary_tree<T, Alloc>& t)
+first_cursor(binary_tree<T, Alloc> const& t)
 {
         return t.inorder_first();
 }
@@ -630,11 +630,94 @@
  */
 template <class T, class Alloc>
 typename binary_tree<T, Alloc>::const_cursor 
-cfirst(binary_tree<T, Alloc>& t)
+cfirst_cursor(binary_tree<T, Alloc> const& t)
 {
         return t.inorder_first();
 }
 
+/**
+ * @brief	First element of a binary_tree in inorder traversal
+ * 			(equivalent to postorder::begin())
+ * @param t	A binary_tree
+ * @return	Mutable inorder iterator to the first element of @a t
+ */
+template <class T, class Alloc>
+iterator<typename binary_tree<T, Alloc>::cursor>
+begin(binary_tree<T, Alloc>& t)
+{
+	return iterator<typename binary_tree<T, Alloc>::cursor>(first_cursor(t));
+}
+
+/**
+ * @brief	First element of a binary_tree in inorder traversal
+ * 			(Alias of cbegin(); equivalent to postorder::begin())
+ * @param t	A binary_tree
+ * @return	Read-only inorder iterator to the first element of @a t
+ */
+template <class T, class Alloc>
+iterator<typename binary_tree<T, Alloc>::const_cursor>
+begin(binary_tree<T, Alloc> const& t)
+{
+	return iterator<typename binary_tree<T, Alloc>::const_cursor>(first_cursor(t));
+}
+
+/**
+ * @brief	First element of a binary_tree in inorder traversal
+ * 			(equivalent to postorder::begin())
+ * @param t	A binary_tree
+ * @return	Read-only inorder iterator to the first element of @a t
+ */
+template <class T, class Alloc>
+iterator<typename binary_tree<T, Alloc>::const_cursor>
+cbegin(binary_tree<T, Alloc> const& t)
+{
+//	typedef
+//		typename cursor_vertical_traversal<
+//			typename binary_tree<T, Alloc>::const_cursor
+//		>::type traversal;
+	return iterator<typename binary_tree<T, Alloc>::const_cursor>(first_cursor(t));
+}
+
+
+/**
+ * @brief	One position past the last element of a binary_tree 
+ * 			in inorder traversal
+ * @param t	A binary_tree
+ * @return	Mutable inorder iterator to the first element of @a t
+ */
+template <class T, class Alloc>
+iterator<typename binary_tree<T, Alloc>::cursor>
+end(binary_tree<T, Alloc>& t)
+{
+	return iterator<typename binary_tree<T, Alloc>::cursor>(last(t.root()));
+}
+
+/**
+ * @brief	One position past the last element of a binary_tree
+ * 			in inorder traversal. (Alias of cend().)
+ * @param t	A binary_tree
+ * @return	Read-only inorder iterator to the first element of @a t
+ */
+template <class T, class Alloc>
+iterator<typename binary_tree<T, Alloc>::const_cursor>
+end(binary_tree<T, Alloc> const& t)
+{
+	return iterator<typename binary_tree<T, Alloc>::const_cursor>(last(t.root()));
+}
+
+/**
+ * @brief	One position past the last element of a binary_tree
+ * 			in inorder traversal
+ * @param t	A binary_tree
+ * @return	Read-only inorder iterator to the first element of @a t
+ */
+template <class T, class Alloc>
+iterator<typename binary_tree<T, Alloc>::const_cursor>
+cend(binary_tree<T, Alloc> const& t)
+{
+	return iterator<typename binary_tree<T, Alloc>::const_cursor>(last(t.root()));
+}
+
 } // namespace inorder
 
 } // namespace tree

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	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -60,35 +60,60 @@
         typedef typename Cursor::cursor_category type;
 };
 
+template <class Cursor>
+struct cursor_horizontal_traversal {
+	typedef typename Cursor::horizontal_traversal type;
+};
+
+template <class Cursor>
+struct cursor_vertical_traversal {
+	typedef typename Cursor::vertical_traversal type;
+};
+
 template <class Cat, class T, class Dist = ptrdiff_t, class Size = size_t,
                   class Ptr = T*, class Ref = T&>
 struct cursor {
         typedef Cat		cursor_category;
         typedef T		value_type;
-	typedef Dist		difference_type;
-	typedef Size		size_type;
+	typedef Dist	difference_type;
+	typedef Size	size_type;
         typedef Ptr		pointer;
         typedef Ref		reference;	
 };
 
-struct cursor_tag 
-	: public input_iterator_tag, public output_iterator_tag {};
+// Deprecate?
+struct cursor_tag {};
+
+struct descending_tag {}; 
 struct descending_cursor_tag
-	: public cursor_tag {};
+	: public cursor_tag, public descending_tag, 
+	  public input_iterator_tag, public output_iterator_tag {};
 struct descending_forward_cursor_tag
-	: public descending_cursor_tag, public forward_iterator_tag {};
+	: public cursor_tag, public descending_tag, public forward_iterator_tag {};
 struct descending_bidirectional_cursor_tag
-	: public descending_cursor_tag, public bidirectional_iterator_tag {};
+	: public cursor_tag, public descending_tag, public bidirectional_iterator_tag {};
 struct descending_random_access_cursor_tag
-	: public descending_cursor_tag, public random_access_iterator_tag {};
+	: public cursor_tag, public descending_tag, public random_access_iterator_tag {};
+
+struct ascending_tag {};
 struct ascending_cursor_tag
-	: public descending_cursor_tag {};
+	: public descending_cursor_tag, public ascending_tag {};
 struct ascending_forward_cursor_tag
-	: public descending_forward_cursor_tag {};
+	: public descending_forward_cursor_tag, public ascending_tag {};
 struct ascending_bidirectional_cursor_tag
-	: public descending_bidirectional_cursor_tag {};
+	: public descending_bidirectional_cursor_tag, public ascending_tag {};
 struct ascending_random_access_cursor_tag
-	: public descending_random_access_cursor_tag {};
+	: public descending_random_access_cursor_tag, public ascending_tag {};
+
+/*
+template <class Hor, class Vert>
+struct produce_cursor_category;
+
+template <>
+struct produce_cursor_category<> {
+	typedef descending_cursor_tag type;
+};
+*/
 
 /**
  * @brief Output cursor wrapper around an output iterator.

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -99,10 +99,8 @@
  : public iterator_facade<Derived, Value, HorizontalCategoryOrTraversal, 
                                                   Reference, Difference> {
  private:
- 	//typedef Derive<Value> Derived;
-	//
         // Curiously Recurring Template interface.
-	//
+
         Derived& derived()
         {
             return *static_cast<Derived*>(this);
@@ -113,16 +111,14 @@
             return *static_cast<Derived const*>(this);
         }
 
-//	typedef iterator_facade<Derived, Value, HorizontalCategoryOrTraversal, 
-//							Reference, Difference> iterator_facade_;
         typedef typename cursor_facade::iterator_facade_ iterator_facade_;
+
  protected:
          // For use by derived classes
         typedef cursor_facade<Derived, Value, HorizontalCategoryOrTraversal,
                                                   VerticalCategoryOrTraversal, Reference, Difference> 
                         cursor_facade_;
  public:
-
         typedef typename iterator_facade_::value_type value_type;
         typedef Reference reference;
         typedef Difference difference_type;
@@ -132,6 +128,12 @@
         typedef Size size_type;
 
         typedef bidirectional_traversal_tag cursor_category; //TODO
+	typedef typename 
+		iterator_category_to_traversal<iterator_category>::type
+		horizontal_traversal; 
+	typedef typename 
+		iterator_category_to_traversal<VerticalCategoryOrTraversal>::type
+		vertical_traversal; 
 
         bool const empty() const
         {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -30,7 +30,16 @@
 //	
 //namespace inorder {
 
-
+/** @file	bidirectional.hpp
+ * 
+ * Some definitions that are identical for all *order cursors (as we are just
+ * calling the appropriate traversal function that are defined in the 
+ * respective *order.hpp files).
+ */
+
+/**
+ * @brief	Specialisation for ascending cursors.
+ */
 template <class Cursor>
 class iterator<Cursor, bidirectional_traversal_tag>
  : public boost::iterator_adaptor<iterator<Cursor, bidirectional_traversal_tag>
@@ -77,119 +86,68 @@
 };
 
 
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::cursor> 
-//begin(MultiwayTree& t, bidirectional_traversal_tag)
-//{
-//	return iterator<typename MultiwayTree::cursor>(first(t));
-//}
-//
-///**
-// * @brief	First element of a MultiwayTree in inorder traversal
-// * 			(equivalent to postorder::begin())
-// * @param t	A MultiwayTree
-// * @return	Mutable inorder iterator to the first element of @a t
-// */
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::cursor> begin(MultiwayTree& t)
-//{
-//	typedef typename cursor_category<typename MultiwayTree::cursor>::type
-//		traversal;
-//	return begin(t, traversal());
-//}
-//
-///**
-// * @brief	First element of a MultiwayTree in inorder traversal
-// * 			(Alias of cbegin(); equivalent to postorder::begin())
-// * @param t	A MultiwayTree
-// * @return	Read-only inorder iterator to the first element of @a t
-// */
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::const_cursor> begin(MultiwayTree& t)
-//{
-//	return cbegin(t);
-//}
-//
-//
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::const_cursor>
-//cbegin(MultiwayTree& t, bidirectional_traversal_tag)
-//{
-//	return iterator<typename MultiwayTree::const_cursor>(cfirst(t));
-//}
-//
-///**
-// * @brief	First element of a MultiwayTree in inorder traversal
-// * 			(equivalent to postorder::begin())
-// * @param t	A MultiwayTree
-// * @return	Read-only inorder iterator to the first element of @a t
-// */
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::const_cursor> cbegin(MultiwayTree& t)
-//{
-//	typedef typename cursor_category<
-//		typename MultiwayTree::const_cursor>::type traversal;
-//	return cbegin(t, traversal());
-//}
-//
-//
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::cursor>
-//end(MultiwayTree const& t, bidirectional_traversal_tag)
-//{
-//	return iterator<typename MultiwayTree::cursor>(last(t));
-//}
-//
-///**
-// * @brief	One position past the last element of a MultiwayTree 
-// * 			in inorder traversal (Alias of cend())
-// * @param t	A MultiwayTree
-// * @return	Mutable inorder iterator one position past the last element of @a t 
-// */
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::cursor> end(MultiwayTree& t)
-//{
-//	typedef typename cursor_category<typename MultiwayTree::cursor>::type
-//		traversal;
-//	return end(t, traversal());
-//}
-//
-///**
-// * @brief	One position past the last element of a MultiwayTree 
-// * 			in inorder traversal (Alias of cend())
-// * @param t	A MultiwayTree
-// * @return	Read-only inorder iterator one position past the last element of @a t 
-// */
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::const_cursor> end(MultiwayTree const& t)
-//{
-//	return cend(t);
-//}
-//
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::const_cursor>
-//cend(MultiwayTree const& t, bidirectional_traversal_tag)
-//{
-//	return iterator<typename MultiwayTree::const_cursor>(clast(t));
-//}
-//
-///**
-// * @brief	One position past the last element of a MultiwayTree 
-// * 			in inorder traversal
-// * @param t	A MultiwayTree
-// * @return	Read-only inorder iterator one position past the last element of @a t 
-// */
-//template <class MultiwayTree>
-//iterator<typename MultiwayTree::const_cursor> cend(MultiwayTree& t)
-//{
-//	typedef typename cursor_category<
-//		typename MultiwayTree::const_cursor>::type traversal;
-//	return cend(t, traversal());
-//}
-
-//} // namespace inorder
-//
-//} // namespace tree
-//} // namespace boost
+/// Iterators
+
+template <class Cursor>
+iterator<Cursor> 
+begin(Cursor c, bidirectional_traversal_tag)
+{
+	return iterator<Cursor>(first(c));
+}
+
+/**
+ * @brief	First element of a subtree in traversal
+ * 			(equivalent to postorder::begin())
+ * @param c	A cursor
+ * @return	Iterator to the first element of @a c
+ */
+template <class Cursor>
+iterator<Cursor> begin(Cursor c)
+{
+	typedef
+		typename cursor_vertical_traversal<Cursor>::type
+		traversal;
+	return begin(c, traversal());
+}
+
+
+template <class Cursor>
+iterator<Cursor, bidirectional_traversal_tag>
+end(Cursor c, bidirectional_traversal_tag)
+{
+	return iterator<Cursor>(last(c));
+}
+
+/**
+ * @brief	One position past the last element of a subtree 
+ * 			in traversal (Alias of cend())
+ * @param c	A cursor
+ * @return	Iterator one position past the last element of @a c 
+ */
+template <class Cursor>
+iterator<Cursor> end(Cursor c)
+{
+	typedef
+		typename cursor_vertical_traversal<Cursor>::type
+		traversal;
+	return end(c, traversal());
+}
+
+
+/// Reverse iterators
+
+template <class Cursor>
+std::reverse_iterator< iterator<Cursor> >
+rbegin(Cursor c)
+{
+	return std::reverse_iterator< iterator<Cursor> >(end(c));
+}
+
+template <class Cursor>
+std::reverse_iterator< iterator<Cursor> >
+rend(Cursor c)
+{
+	return std::reverse_iterator< iterator<Cursor> >(begin(c));
+}
 
 //#endif // BOOST_TREE_DETAIL_ITERATOR_BIDIRECTIONAL_HPP

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -41,10 +41,8 @@
                 return;
         }
         
-	while (c.parity()) 
+	while (c.parity()) // Doesn't work with subtrees whose root's parity != 0
                 c.to_parent();
-	if (c.parent().begin() != c) // Root? Would be nice to get rid of.
-		c.to_parent(); // Shoot (root's parent)
         return;
 }
 
@@ -92,87 +90,29 @@
 }
 
 /**
- * @brief	First element of a MultiwayTree in inorder traversal
- * 			(equivalent to postorder::first())
- * @param t	A MultiwayTree
- * @return	Mutable cursor to the first element of @a t in inorder traversal
+ * @brief	First element of a Multiway subtree in inorder traversal
+ * @param c	A MultiwayCursor
+ * @return	Cursor to the first element of @a c in inorder traversal
  */
-template <class MultiwayTree>
-typename MultiwayTree::cursor first(MultiwayTree& t)
-{
-	typename MultiwayTree::cursor c = t.root();
-	while (!c.empty())
-		c.to_begin();
-	return c;
-}
-
-/**
- * @brief	First element of a MultiwayTree in inorder 
- * 			traversal (Alias of cfirst(); equivalent to postorder::first())
- * @param t	A MultiwayTree
- * @return	Read-only cursor to the first element of @a t in inorder traversal
- */
-template <class MultiwayTree>
-typename MultiwayTree::const_cursor first(MultiwayTree const& t)
-{
-	typename MultiwayTree::const_cursor c = t.root();
-	while (!c.empty())
-		c.to_begin();
-	return c;
-}
-
-/**
- * @brief	First element of a MultiwayTree in inorder 
- * 			traversal (equivalent to postorder::cfirst())
- * @param t	A MultiwayTree
- * @return	Read-only cursor to the first element of @a t in inorder traversal
- */
-template <class MultiwayTree>
-typename MultiwayTree::const_cursor cfirst(MultiwayTree const& t)
+template <class MultiwayCursor>
+MultiwayCursor first(MultiwayCursor c)
 {
-	typename MultiwayTree::const_cursor c = t.root();
         while (!c.empty())
                 c.to_begin();
         return c;
 }
 
 /**
- * @brief	One position past the last element of a MultiwayTree in 
+ * @brief	One position past the last element of a Multiway subtree in 
  * 			inorder traversal
- * @param t	A MultiwayTree
- * @return	Mutable cursor one position past the last element of @a t in inorder
+ * @param c	A MultiwayCursor
+ * @return	Cursor one position past the last element of @a c in inorder
  * 			traversal
  */
-template <class MultiwayTree>
-typename MultiwayTree::cursor last(MultiwayTree& t)
-{
-	return t.shoot();
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree 
- * 			in inorder traversal (Alias of clast())
- * @param t	A MultiwayTree
- * @return	Read-only cursor one position past the last element of @a t in 
- * 			inorder traversal
- */
-template <class MultiwayTree>
-typename MultiwayTree::const_cursor last(MultiwayTree const& t)
-{
-	return t.cshoot();
-}
-
-/**
- * @brief	One position past the last element of a MultiwayTree
- * 			in inorder traversal
- * @param t	A tree
- * @return	Read-only cursor one position past the last element of @a t in 
- * 			inorder traversal
- */
-template <class MultiwayTree>
-typename MultiwayTree::const_cursor clast(MultiwayTree const& t)
+template <class MultiwayCursor>
+MultiwayCursor last(MultiwayCursor c)
 {
-	return t.cshoot();
+	return c;
 }
 
 /*\@}*/

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -32,7 +32,8 @@
         
 namespace inorder {
 
-template <class Cursor, class Tag = typename cursor_category<Cursor>::type>
+template <class Cursor, 
+		  class Tag = typename cursor_vertical_traversal<Cursor>::type>
 class iterator;
 
 template <class Cursor>
@@ -48,7 +49,7 @@
     iterator() {}
 //      : iterator::iterator_adaptor_() {}
 
-    explicit iterator(stack<Cursor> s) //, bool branch = s.size()) // = s.size() 
+    explicit iterator(stack<Cursor> s) 
                     : m_s(s), m_branch() {}
 //      : iterator::iterator_adaptor_(p) {}
 
@@ -110,7 +111,7 @@
     
     void decrement()
     {
-	    	if (!m_s.top().empty()) {	    		
+	    if (!m_s.top().empty()) {	    		
                         while (!m_s.top().end().empty())
                                 m_s.push(m_s.top().end());
                         m_s.push(m_s.top().begin());
@@ -118,7 +119,7 @@
                 }
                 while (!m_s.top().parity())
                         m_s.pop();
-	    	if (++m_branch > m_s.size()) 
+	    if (++m_branch > m_s.size()) 
                         m_branch = m_s.size();
                 --m_branch;
                 --m_s.top();

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -39,7 +39,7 @@
                 return;
         }
         
-	if (/*!c.parity() &&*/ (c.parent().begin() != c)) // Root?
+	if (c.parent().begin() != c) // Root?
                 return;
         
         // Left child.
@@ -110,87 +110,30 @@
 }
 
 /**
- * @brief	First element of a tree in postorder traversal
+ * @brief	First element of a subtree in postorder traversal
  * 			(equivalent to inorder::first())
- * @param t	A tree
- * @return	Mutable cursor to the first element of @a t in postorder traversal
- */
-template <class Tree>
-typename Tree::cursor first(Tree& t)
-{
-	typename Tree::cursor c = t.root();
-	while (!c.empty())
-		c.to_begin();
-	return c;
-}
-
-/**
- * @brief	First element of a tree in postorder traversal
- * 			(Alias of cfirst(); equivalent to inorder::first())
- * @param t	A tree
- * @return	Read-only cursor to the first element of @a t in postorder traversal
- */
-template <class Tree>
-typename Tree::const_cursor first(Tree const& t)
-{
-	typename Tree::const_cursor c = t.root();
-	while (!c.empty())
-		c.to_begin();
-	return c;
-}
-
-/**
- * @brief	First element of a tree in postorder traversal
- * 			(equivalent to inorder::cfirst())
- * @param t	A tree
- * @return	Read-only cursor to the first element of @a t in postorder traversal
+ * @param c	A cursor
+ * @return	Cursor to the first element of @a c in postorder traversal
  */
-template <class Tree>
-typename Tree::const_cursor cfirst(Tree const& t)
+template <class Cursor>
+Cursor first(Cursor c)
 {
-	typename Tree::const_cursor c = t.root();
         while (!c.empty())
                 c.to_begin();
         return c;
 }
 
 /**
- * @brief	One position past the last element of a tree in postorder 
+ * @brief	One position past the last element of a subtree in postorder 
  * 			traversal
- * @param t	A tree
- * @return	Mutable cursor one position past the last element of @a t in 
- * 			postorder traversal
- */
-template <class Tree>
-typename Tree::cursor last(Tree& t)
-{
-	return t.root();
-}
-
-/**
- * @brief	One position past the last element of a tree in 
- * 			postorder traversal (Alias of clast())
- * @param t	A tree
- * @return	Read-only cursor one position past the last element of @a t in 
- * 			postorder traversal
- */
-template <class Tree>
-typename Tree::const_cursor last(Tree const& t)
-{
-	return t.croot();
-}
-
-/**
- * @brief	One position past the last element of a tree in 
- * 			postorder traversal
- * @param t	A tree
- * @return	Read-only cursor one position past the last element of @a t in 
+ * @param c	A cursor
+ * @return	Cursor one position past the last element of @a c in 
  * 			postorder traversal
  */
-template <class Tree>
-typename Tree::const_cursor clast(Tree const& t)
+template <class Cursor>
+Cursor last(Cursor c)
 {
-	return t.croot();
+	return c;
 }
 
 /*\@}*/

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -27,9 +27,11 @@
         
 namespace postorder {
 
-template <class Cursor, class Tag = typename cursor_category<Cursor>::type>
+template <class Cursor, 
+		  class Tag = typename cursor_vertical_traversal<Cursor>::type>
 class iterator;
 
+// TODO. For now, it's only a (bidirectional) dummy
 template <class Cursor>
 class iterator<Cursor, forward_traversal_tag>
  : public boost::iterator_facade<iterator<Cursor, forward_traversal_tag>
@@ -65,12 +67,12 @@
     
     void increment()
     {
-		forward(this->base_reference());
+		forward(this->base_reference()); //Dummy
     }
     
     void decrement()
     {
-    		back(this->base_reference());
+    	back(this->base_reference()); //Dummy
     }
 };
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -32,30 +32,38 @@
 template <class Cursor>
 inline void forward(Cursor& c)
 {
-	if (!c.empty()) { // Left.
+	// If we have a left child, go there.
+	if (!c.empty()) {
                 c.to_begin();
                 return;
         }
-	if (!(++c).empty()) { // Right.
-		c.to_begin();
-		return;
-	}
-
-	while (c.parity())
-		c.to_parent();
+	
+	// No left child. So if we have a right child, go there.
         if (!(++c).empty()) {
                 c.to_begin();
                 return;
         }
         
-	--c;
-	while (!c.empty()) {
-		c.to_end();
-		if (c.empty())
-			--c;
+	// (Here's where we'd need to check if this is the end().)
+	
+	// No children at all.
+	// As we've already visited all the ancestors, we'll move upwards until
+	// we find an ancestor that has a right child.
+	while (true) { // Doesn't work with subtrees!
+		if (!c.parity() && (c != c.parent().begin())) { // Root
+			c.to_parent();
+			return;
+		}
+		c.to_parent();
+		if (!c.parity()) {
+			if (c != c.parent().begin()) // Root?
+				return;
+			if (!(++c).empty()) {
+				c.to_begin();
+				return;
+			}
+		}
         }
-	if (!c.parity()) 
-		++c;
         return;
 }
 
@@ -78,13 +86,27 @@
 template <class Cursor>
 inline void back(Cursor& c)
 {
-	c.to_parent();
-	if (c.parity()) {
+	if (!(!c.parity() && (c != c.parent().begin()))) { // Not root
+		c.to_parent();
+		
+		// If this is a left child, just move to its parent.
+		if (!c.parity()) {
+			c.to_parent();
+			c.to_begin();
+			return;
+		}
+		
+		// So this is a right child.
                 --c;
-		while (!c.empty())
-			c.to_end();
-		return;
         }
+	
+	// Same for root (=end) and right children:
+	if (!c.empty())
+		while (!c.empty())
+			if (!c.end().empty())
+				c.to_end();
+			else
+				c.to_begin();
         return;
 }
 
@@ -101,97 +123,27 @@
 }
 
 /**
- * @brief	First element of a tree in preorder traversal
- * @param t	A tree
- * @return	Mutable cursor to the first element of @a t in preorder traversal
- */
-template <class Tree>
-typename Tree::cursor first(Tree& t)
-{
-	return t.root().begin();
-}
-
-/**
- * @brief	First element of a tree in preorder traversal
- * 			(Alias of cfirst())
- * @param t	A tree
- * @return	Read-only cursor to the first element of @a t in preorder traversal
- */
-template <class Tree>
-typename Tree::const_cursor first(Tree const& t)
-{
-	return t.croot().begin();
-}
-
-/**
- * @brief	First element of a tree in preorder traversal
- * @param t	A tree
- * @return	Read-only cursor to the first element of @a t in preorder traversal
+ * @brief	First element of a subtree in preorder traversal
+ * @param c	A cursor
+ * @return	Cursor to the first element of @a c in preorder traversal
  */
-template <class Tree>
-typename Tree::const_cursor cfirst(Tree const& t)
+template <class Cursor>
+Cursor first(Cursor c)
 {
-	return t.croot().begin();
+	return c.begin();
 }
 
 /**
- * @brief	One position past the last element of a tree in preorder 
+ * @brief	One position past the last element of a subtree in preorder 
  * 			traversal
- * @param t	A tree
- * @return	Mutable cursor one position past the last element of @a t in preorder
+ * @param c	A cursor
+ * @return	Cursor one position past the last element of @a c in preorder
  * 			traversal
  */
-template <class Tree>
-typename Tree::cursor last(Tree& t)
-{
-	typename Tree::cursor c = t.shoot();
-	--c;	
-	while (!c.empty()) {
-		c.to_end();
-		if (c.empty())
-			--c;
-	}
-	return ++c;
-}
-
-/**
- * @brief	One position past the last element of a tree in 
- * 			preorder traversal (Alias of clast())
- * @param t	A tree
- * @return	Read-only cursor one position past the last element of @a t in 
- * 			preorder traversal
- */
-template <class Tree>
-typename Tree::const_cursor last(Tree const& t)
-{
-	typename Tree::const_cursor c = t.cshoot();
-	--c;	
-	while (!c.empty()) {
-		c.to_end();
-		if (c.empty())
-			--c;
-	}
-	return ++c;
-}
-
-/**
- * @brief	const_cursor to one position past the last element of a tree in 
- * 			preorder traversal
- * @param t	A tree
- * @return	Read-only cursor one position past the last element of @a t in 
- * 			preorder traversal
- */
-template <class Tree>
-typename Tree::const_cursor clast(Tree const& t)
+template <class Cursor>
+Cursor last(Cursor c)
 {
-	typename Tree::const_cursor c = t.cshoot();
-	--c;	
-	while (!c.empty()) {
-		c.to_end();
-		if (c.empty())
-			--c;
-	}
-	return ++c;
+	return c;
 }
 
 /*\@}*/

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -27,7 +27,8 @@
         
 namespace preorder {
 
-template <class Cursor, class Tag = typename cursor_category<Cursor>::type>
+template <class Cursor, 
+		  class Tag = typename cursor_vertical_traversal<Cursor>::type>
 class iterator;
 
 template <class Cursor>
@@ -65,12 +66,12 @@
     
     void increment()
     {
-		forward(this->base_reference());
+		forward(this->base_reference()); //Dummy
     }
     
     void decrement()
     {
-    		back(this->base_reference());
+    	back(this->base_reference()); //Dummy
     }
 };
 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -3098,8 +3098,8 @@
               </tbody>
             </table>
 
-            <p>Notes: The expressions <tt>a.begin()</tt> and <tt>a.end()</tt>
-            are, as shown in Table 9, replaced with equivalent expressions
+            <p>Note: The expressions <tt>a.begin()</tt> and <tt>a.end()</tt>
+            are, as shown in Table 10, replaced with equivalent expressions
             for cursors.</p>
           </li>
 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/multiway_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/multiway_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/multiway_tree_test.cpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -18,7 +18,7 @@
         tree_type mytree;
 
         //tree_type::cursor c = 
-	//mytree.insert(mytree.shoot(), 3);
+	//mytree.insert(mytree.root(), 3);
 }
 
 int test_main(int, char* [])

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/nary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/nary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/nary_tree_test.cpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -16,7 +16,7 @@
         
         typedef nary_tree<int> tree_type;
         tree_type mytree;
-	tree_type::cursor c = mytree.shoot();
+	tree_type::cursor c = mytree.root();
         BOOST_CHECK(mytree.root().empty());
         BOOST_CHECK(c.empty());
 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -10,6 +10,8 @@
 #include <algorithm>
 #include <iterator>
 
+#include <boost/tree/binary_tree.hpp>
+
 #include "helpers.hpp"
 #include "test_tree_traversal_data.hpp"
 
@@ -53,5 +55,54 @@
         test_transform(c, d, oc_test_list, test_list);
 }
 
+void compare_cursor_to_iterator_traversal(boost::tree::binary_tree<int> const& t) {
+	
+	using boost::forward_traversal_tag;
+	
+	std::list<int> test_list;
+	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_test_list = std::back_inserter(test_list);
+	oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
+	
+	boost::tree::ORDER::copy(t.croot().begin(), oc_test_list);
+
+	// Are the elements accessed in the correct order?
+	BOOST_CHECK(std::equal(	boost::tree::ORDER::begin(t.root()),
+							boost::tree::ORDER::end(t.root()),
+							test_list.begin()
+							));
+
+	// Does end() mark the right element? 
+	BOOST_CHECK(std::distance(boost::tree::ORDER::begin(t.root()),
+							  boost::tree::ORDER::end(t.root())) == 
+				std::distance(test_list.begin(), test_list.end()));
+
+	// Reverse order.
+	BOOST_CHECK(std::equal(	boost::tree::ORDER::rbegin(t.root()),
+							boost::tree::ORDER::rend(t.root()),
+							test_list.rbegin()
+							));
+
+	BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(t.root()),
+							  boost::tree::ORDER::rend(t.root())) == 
+				std::distance(test_list.rbegin(), test_list.rend()));					
+
+	//Now same for "explicit stack"-based iterators
+	// TODO: Only possible when there are stack-based pre- and postorder iterators
+/*
+	BOOST_CHECK(std::equal(	boost::tree::ORDER::begin(t.root(), forward_traversal_tag()),
+							boost::tree::ORDER::end(t.root(), forward_traversal_tag()),
+							test_list.begin()
+							));
+
+	BOOST_CHECK(std::equal(	boost::tree::ORDER::rbegin(t.root(), forward_traversal_tag()),
+							boost::tree::ORDER::rend(t.root(), forward_traversal_tag()),
+							test_list.rbegin()
+							));
+*/
+}
+
+
 }
 }

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -52,9 +52,6 @@
 
 namespace preorder {
 
-//std::list data;
-
-
 template <class Iterator>
 void traversal(Iterator a, Iterator b) 
 {
@@ -104,16 +101,6 @@
 
 namespace inorder {
 
-
-
-template < class Tp, class Alloc = std::allocator<Tp> >
-class flat_binary_tree {
- protected:
-	std::list<Tp, Alloc> cont;
- public:
-	
-};
-
 template <class Iterator>
 void traversal(Iterator a, Iterator b)
 {		

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	2008-06-06 17:38:37 EDT (Fri, 06 Jun 2008)
@@ -26,34 +26,117 @@
 
 using namespace boost::tree;
 
+// Some macro magic, to save us from all too tedious redundant calls
+// to each of the three types of order algorithms and checks.
+
+#define ORDER preorder
+#include "subtree_algorithms_checks.hpp"
+
+#undef ORDER
+#define ORDER inorder
+#include "subtree_algorithms_checks.hpp"
+
+#undef ORDER
+#define ORDER postorder
+#include "subtree_algorithms_checks.hpp"
+
+#undef ORDER
+
+void comparisons(binary_tree<int> const& test_tree) {
+	test::preorder::compare_cursor_to_iterator_traversal(test_tree);
+	test::inorder::compare_cursor_to_iterator_traversal(test_tree);	
+	test::postorder::compare_cursor_to_iterator_traversal(test_tree);
+	return;
+}
+
+/** 
+ * Check all iterator traversals by comparing them to a recursive cursor
+ * algorithm output. Do that at different stages of the tree while adding
+ * elements to it, so different tree shapes are checked to be catered for
+ * by the iterator algorithms.
+ */ 
+void compare_cursor_to_iterator_traversal() {
+	binary_tree<int> test_tree2;
+
+	binary_tree<int>::cursor c = test_tree2.insert(test_tree2.root(), 8);
+	comparisons(test_tree2);
+
+	c = test_tree2.insert(c, 3);
+	comparisons(test_tree2);
+
+	test_tree2.insert(c, 1);
+	comparisons(test_tree2);
+	
+	c = test_tree2.insert(++c, 6);
+	comparisons(test_tree2);
+
+	test_tree2.insert(c, 4);
+	comparisons(test_tree2);
+	
+	test_tree2.insert(++c, 7);	
+	comparisons(test_tree2);
+
+	c = test_tree2.insert(test_tree2.root().end(), 10);
+	comparisons(test_tree2);
+
+	c = test_tree2.insert(test_tree2.root().end().end(), 14);	
+	comparisons(test_tree2);
+
+	c = test_tree2.insert(c, 13);
+	comparisons(test_tree2);
+
+	c = test_tree2.insert(c, 11);
+	comparisons(test_tree2);
+
+	c = test_tree2.insert(++c, 12);
+	comparisons(test_tree2);
+}
+
 int test_main(int, char* [])
 {
         using boost::forward_traversal_tag;
         
-	binary_tree<int> test_tree;
+	binary_tree<int> test_tree;	
         create_test_data_tree(test_tree);
         
-	test::inorder::traversal(inorder::begin(test_tree), 
-						   inorder::end(test_tree));
-	test::inorder::reverse_traversal(inorder::end(test_tree), 
-								   inorder::begin(test_tree));
-		
-	test::preorder::traversal(preorder::begin(test_tree),
-							preorder::end(test_tree));
-//FIXME
-//	test::preorder::reverse_traversal(preorder::end(test_tree),
-//									preorder::begin(test_tree));
-	
-	test::postorder::traversal(postorder::begin(test_tree), 
-							 postorder::end(test_tree));
-	test::postorder::reverse_traversal(postorder::end(test_tree), 
-									 postorder::begin(test_tree));
+	// Inorder
+	test::inorder::traversal(inorder::begin(test_tree.root()), 
+						   inorder::end(test_tree.root()));
+
+	test::inorder::reverse_traversal(inorder::end(test_tree.root()), 
+								   inorder::begin(test_tree.root()));
         
-	test::inorder::traversal(inorder::begin(test_tree, forward_traversal_tag()), 
-						   inorder::end(test_tree, forward_traversal_tag()));
-	test::inorder::reverse_traversal(inorder::end(test_tree, forward_traversal_tag()), 
-								   inorder::begin(test_tree, forward_traversal_tag()));
+	// TODO: Also check with binary_tree-specialized inorder begin()!
+
+	BOOST_CHECK(std::distance(inorder::begin(test_tree.root()), 
+						      inorder::end(test_tree.root())) == 11);
 
+	//Preorder	
+	test::preorder::traversal(preorder::begin(test_tree.root()),
+							  preorder::end(test_tree.root()));
+
+	test::preorder::reverse_traversal(preorder::end(test_tree.root()),
+									  preorder::begin(test_tree.root()));
+									
+	BOOST_CHECK(std::distance(preorder::begin(test_tree.root()), 
+						      preorder::end(test_tree.root())) == 11);
+
+	//Postorder
+	test::postorder::traversal(postorder::begin(test_tree.root()), 
+							 postorder::end(test_tree.root()));
+	test::postorder::reverse_traversal(postorder::end(test_tree.root()), 
+									 postorder::begin(test_tree.root()));
+
+	BOOST_CHECK(std::distance(postorder::begin(test_tree.root()), 
+						      postorder::end(test_tree.root())) == 11);
+
+	// Now the stack-based iterators (that don't use cursor.to_parent())
+	test::inorder::traversal(inorder::begin(test_tree.root(), forward_traversal_tag()), 
+						   inorder::end(test_tree.root(), forward_traversal_tag()));
+	test::inorder::reverse_traversal(inorder::end(test_tree.root(), forward_traversal_tag()), 
+								   inorder::begin(test_tree.root(), forward_traversal_tag()));
+
+	//Ascending iterator.
         binary_tree<int>::cursor c = test_tree.root();
         ascending::iterator<binary_tree<int>::cursor> ai_root(c);
         c = c.begin().end().begin().begin();
@@ -62,6 +145,9 @@
         ascending::iterator<binary_tree<int>::cursor> ais(c);
         test::ascending::traversal_from_leaf4(ais, ai_root);
 
+	//Now the advanced stuff
+	compare_cursor_to_iterator_traversal();
+		
         return 0;
 }