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

Subject: [Boost-commit] svn:boost r49829 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/algorithm libs/tree/doc libs/tree/example libs/tree/test
From: ockham_at_[hidden]
Date: 2008-11-18 17:16:09

Author: bernhard.reiter
Date: 2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
New Revision: 49829
URL: http://svn.boost.org/trac/boost/changeset/49829

Log:
Documentation fixes.
Added:
   sandbox/SOC/2006/tree/trunk/libs/tree/example/stl_lower_bound.cpp
      - copied, changed from r49827, /sandbox/SOC/2006/tree/trunk/libs/tree/example/for_each.cpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                       |    16 ++---                                   
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp            |    11 +++                                     
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp                 |   108 ++++----------------------------------- 
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp              |     5 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp             |    25 ++++++++-                               
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp               |    11 ++++                                    
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp    |     4                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp  |     4                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp   |     4                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp               |    54 +++++++++++--------                     
   sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp                    |    22 +++++--                                 
   sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp                   |    19 +++---                                  
   sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp        |    18 +++++-                                  
   sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp               |    16 ++--                                    
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk                 |    46 ++++++++--------                        
   sandbox/SOC/2006/tree/trunk/libs/tree/example/stl_lower_bound.cpp      |    44 ++++-----------                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp |    17 ++++++                                  
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp        |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp              |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp |     2                                         
   21 files changed, 207 insertions(+), 225 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -22,26 +22,24 @@
   * Recursive preorder: OK.
   * Recursive postorder: TBD.
   * Iterative pre- and postorder: TBD.
-* Implement a real output cursor (if possible) and use preorder::copy to build a new tree.
+* Implement a real output cursor (if possible) and use copy(preorder(), ...) to build a new tree.
   Then, do some performance measurements comparing
   * Different *orders;
   * BOOST_RECURSIVE_ORDER_ALGORITHMS on and off;
   * cursor and iterator based algorithms (from Boost.Tree and the STL, respectively)
   Do these measurements also with algorithms other than copy.
 * Test cursor adaptors wrapped around output cursors!
-* Add tests for *order::copy involving a second tree cursor (not just a cursor adaptor).
+* Add tests for copy involving a second tree cursor (not just a cursor adaptor).
 * Think of a couple good examples (draw inspiration eg from Wikipedia: Tree traversal
   or CRLS) and include them in the docs. Maybe move some files from libs/test to
   example.
-  Eg.: maybe use preorder::copy in combination with an inserting cursor to "physically"
-  copy a tree?
 * Migrate to using Jamfile.v2 from Intrusive (already used in our libs/example dir)
 * Add performance checks (to a libs/perf/ directory).
 * Look into SOC 2008 projects dsearch (already using concepts from Boost.Tree) and 
   spacial_indexing (with tree classes of its own)
 * Can't we really do without inorder_erase()?
 * Check if Cursor(balanced_tree_iterator) really has no is_root member()! (BOOST_STATIC_ASSERT?)
-* Revisit binary_tree (inorder::)iterator functions
+* Revisit binary_tree inorder iterator functions
 * Possibly sort out some more concepts, like trees with "downwards" or "upwards" insertion
   (insert()/insert_above()), trees with values only at the leaves (makes sense in combination
   with "upwards" insertion"), etc.
@@ -81,8 +79,8 @@
   (Not necessarily! If that means a check for empty(), it's better to leave it to
   the user!)
 * Investigate 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
+* 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. 
@@ -178,8 +176,8 @@
   In order to work for subtrees, we need at least an int to store
   the current depth.
   Solution:
-  Introduce a root tracking cursor concept providing c.is_root(). *order::forward(), back(),
-  next() and prior() functions as well as *order::iterators then require this concept.
+  Introduce a root tracking cursor concept providing c.is_root(). *order forward(), back(),
+  next() and prior() functions as well as *order iterators then require this concept.
   Write a root_tracking_cursor adaptor that does exactly that, with suitable specializations
   for different underlying cursors. 
   (Why? Because any root_tracker object would have to be

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -39,6 +39,14 @@
 distance(iterator< ascending, ascending_cursor<Cursor> > iter1
        , iterator< ascending, ascending_cursor<Cursor> > iter2);
 
+/**
+ * @brief Turns any descending cursor into an ascending one. 
+ * 
+ * When descending from a given initial cursor, this wrapper
+ * tracks any cursors along the way. This way, it is able to
+ * re-ascend later (only up to the initially passed cursor,
+ * of course).  
+ */
 template <class DescendingCursor> 
 class ascending_cursor
 : public cursor_facade<ascending_cursor<DescendingCursor>
@@ -257,8 +265,7 @@
 //    {
 //    }
 
-public:
-    bool is_root() const
+    bool is_root_() const
     {
         return this->base().m_s.size() == m_root_depth;
     }

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-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -604,10 +604,10 @@
 }
 
 /**
- * @brief    First element of a MultiwayTree in inorder traversal
- *             (equivalent to postorder::first()) - O(1) overload for binary_tree
- * @param t    A binary_tree
- * @return    Mutable cursor to the first element of @a t in inorder traversal
+ * @brief   First element of a MultiwayTree in inorder traversal.
+ *          O(1) overload for binary_tree
+ * @param t A binary_tree
+ * @return  Mutable cursor to the first element of @a t in inorder traversal
  */
 template <class T, class Alloc>
 typename binary_tree<T, Alloc>::cursor 
@@ -617,11 +617,10 @@
 }
 
 /**
- * @brief    First element of a MultiwayTree in inorder traversal
- *             (Alias of cfirst(); equivalent to postorder::first()) -
- *             O(1) overload for binary_tree
- * @param t    A binary_tree
- * @return    Read-only cursor to the first element of @a t in inorder traversal
+ * @brief   First element of a MultiwayTree in inorder traversal 
+ *          (alias of cfirst()). O(1) overload for binary_tree.
+ * @param t A binary_tree
+ * @return  Read-only cursor to the first element of @a t in inorder traversal
  */
 template <class T, class Alloc>
 typename binary_tree<T, Alloc>::const_cursor 
@@ -631,10 +630,10 @@
 }
 
 /**
- * @brief    First element of a MultiwayTree in inorder traversal
- *             (equivalent to postorder::first()) - O(1) overload for binary_tree
- * @param t    A binary_tree
- * @return    Read-only cursor to the first element of @a t in inorder traversal
+ * @brief   First element of a MultiwayTree in inorder traversal.
+ *          O(1) overload for binary_tree
+ * @param t A binary_tree
+ * @return  Read-only cursor to the first element of @a t in inorder traversal
  */
 template <class T, class Alloc>
 typename binary_tree<T, Alloc>::const_cursor 
@@ -643,89 +642,6 @@
     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<inorder, typename binary_tree<T, Alloc>::cursor>
-begin(inorder, binary_tree<T, Alloc>& t)
-{
-    return iterator<inorder, typename binary_tree<T, Alloc>::cursor>(first_cursor(inorder(), 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<inorder, typename binary_tree<T, Alloc>::const_cursor>
-begin(inorder, binary_tree<T, Alloc> const& t)
-{
-    return iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>(first_cursor(inorder(), 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<inorder, typename binary_tree<T, Alloc>::const_cursor>
-cbegin(inorder, binary_tree<T, Alloc> const& t)
-{
-//    typedef
-//        typename cursor_vertical_traversal<
-//            typename binary_tree<T, Alloc>::const_cursor
-//        >::type traversal;
-    return iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>(first_cursor(inorder(), 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<inorder, typename binary_tree<T, Alloc>::cursor>
-end(inorder, binary_tree<T, Alloc>& t)
-{
-    return iterator<inorder, typename binary_tree<T, Alloc>::cursor>(last(inorder(), 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<inorder, typename binary_tree<T, Alloc>::const_cursor>
-end(inorder, binary_tree<T, Alloc> const& t)
-{
-    return iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>(last(inorder(), 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<inorder, typename binary_tree<T, Alloc>::const_cursor>
-cend(inorder, binary_tree<T, Alloc> const& t)
-{
-    return iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>(last(inorder(), t.root()));
-}
-
 } // namespace tree
 } // namespace boost
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -191,6 +191,11 @@
     {
         return m_cursor.empty();
     }
+
+    bool const is_root_() const
+    {
+        return m_cursor.is_root();
+    }
     
     size_type const size_() const
     {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -48,20 +48,39 @@
 };
 
 // Derive from DescendingCursor or not?
+// See eg Knuth 2.3.3, p 353.
 template <class X>
-struct AscendingCursor
+struct Ascendor
 {
 public:
-    BOOST_CONCEPT_USAGE(AscendingCursor)
+    BOOST_CONCEPT_USAGE(Ascendor)
     {
         a.to_parent();
         a.parent();
     }
-    
 private:
     X a;
 };
 
+template <class X>
+struct AscendingCursor
+  : Ascendor<X>, LvalueIterator<X>
+{
+};
+
+template <class X>
+struct RootTrackingCursor
+  : AscendingCursor<X>
+{
+    BOOST_CONCEPT_USAGE(RootTrackingCursor)
+    {
+        b = r.is_root();
+    }
+private:
+    X r;
+    bool b;
+};
+
 } // namespace boost_concepts
 
 #endif // BOOST_TREE_CURSOR_CONCEPTS_HPP

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -39,6 +39,12 @@
     {
         return f.empty_();
     }
+
+    template <class Facade>
+    static bool is_root_(Facade const& f)
+    {
+        return f.is_root_();
+    }
     
     template <class Facade>
     static typename Facade::size_type size_(Facade const& f)
@@ -134,6 +140,11 @@
     {
         return cursor_core_access::empty_(this->derived());
     }
+
+    bool const is_root() const
+    {
+        return cursor_core_access::is_root_(this->derived());
+    }
     
     size_type const size() const
     {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -41,7 +41,7 @@
 inline
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<MultiwayCursor>))
-    ((AscendingCursor<MultiwayCursor>)),
+    ((RootTrackingCursor<MultiwayCursor>)),
     (void)) // return type
 forward(inorder, MultiwayCursor& c)
 {
@@ -63,7 +63,7 @@
 inline
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<MultiwayCursor>))
-    ((AscendingCursor<MultiwayCursor>)),
+    ((RootTrackingCursor<MultiwayCursor>)),
     (void)) // return type
 back(inorder, MultiwayCursor& c)
 {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -38,7 +38,7 @@
 inline
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<Cursor>))
-    ((AscendingCursor<Cursor>)),
+    ((RootTrackingCursor<Cursor>)),
     (void)) // return type
 forward(postorder, Cursor& c)
 {
@@ -72,7 +72,7 @@
 inline
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<Cursor>))
-    ((AscendingCursor<Cursor>)),
+    ((RootTrackingCursor<Cursor>)),
     (void)) // return type
 back(postorder, Cursor& c)
 {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -40,7 +40,7 @@
 inline
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<Cursor>))
-    ((AscendingCursor<Cursor>)),
+    ((RootTrackingCursor<Cursor>)),
     (void)) // return type
 forward(preorder, Cursor& c)
 {
@@ -81,7 +81,7 @@
 inline
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<Cursor>))
-    ((AscendingCursor<Cursor>)),
+    ((RootTrackingCursor<Cursor>)),
     (void)) // return type
 back(preorder, Cursor& c)
 {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -14,49 +14,57 @@
 
 #include <boost/tree/cursor_adaptor.hpp>
 
+#include <boost/tree/cursor_concepts.hpp>
+#include <boost/tree/tree_concepts.hpp>
+
 namespace boost {
 namespace tree {
 
 using boost::iterator_core_access;
+using namespace boost_concepts;
 
 template <class Tree>
 class insert_cursor;
 
 /**
- * @brief Output cursor wrapper around an output iterator.
+ * @brief Turns assignment into insertion.
  * 
- * This can be very useful e.g. to have cursor algorithms actually work on
- * iterators, thus permitting some kind of linearization of a given subtree.
- * (Modelled after std::insert_iterator and the like.)
+ * This is a generalisation of std::insert_iterator. Consequently,
+ * it requires a Tree and a cursor to a position in that tree,
+ * which will we used as the root of the subtree of elements that
+ * will be inserted.
  * 
- * For construction, the outputter_cursor_iterator_wrapper might come in useful
+ * For construction, the tree_insert wrapper might come in useful
  * in saving keystrokes.
  */
 // TODO: Complete this.
 // Shouldn't we be using cursor_facade?
-template <class Tree>
+template <class Tr>
 class insert_cursor
-: public cursor_adaptor<insert_cursor<Tree>
-                      , typename Tree::cursor 
+: public cursor_adaptor<insert_cursor<Tr>
+                      , typename Tr::cursor 
 //                      , boost::use_default
 //                      , boost::use_default
 //                      , boost::use_default
     >
- {
+{
+
+BOOST_CONCEPT_ASSERT((Tree<Tr>));
+
 protected:
-    mutable Tree& tree;
+    mutable Tr& tree;
 public:        
     /**
      * For construction, we obviously need a tree and a cursor to work on (i.e., write to).
      */
-    explicit insert_cursor(Tree& x, typename Tree::cursor cur)
+    explicit insert_cursor(Tr& x, typename Tr::cursor cur)
     : insert_cursor::cursor_adaptor_(cur), tree(x) {}
 
     // Cursor-specific
-    typedef insert_cursor<typename Tree::cursor> cursor;
-    typedef insert_cursor<typename Tree::const_cursor> const_cursor;
+    typedef insert_cursor<typename Tr::cursor> cursor;
+    typedef insert_cursor<typename Tr::const_cursor> const_cursor;
 
-    operator typename Tree::cursor()
+    operator typename Tr::cursor()
     {
         return this->base_reference();
     }
@@ -68,8 +76,8 @@
     typename insert_cursor::cursor_adaptor_::reference dereference() const
     {
         if (index(this->base_reference())) {
-            const_cast<typename Tree::cursor&>(this->base_reference())
-            = tree.insert(this->base_reference(), typename Tree::value_type());
+            const_cast<typename Tr::cursor&>(this->base_reference())
+            = tree.insert(this->base_reference(), typename Tr::value_type());
         }
         return *this->base_reference();
     }
@@ -77,21 +85,21 @@
     void left()
     {
         this->base_reference() = 
-            tree.insert(this->base_reference(), typename Tree::value_type());
+            tree.insert(this->base_reference(), typename Tr::value_type());
     }
 };
 
 /** 
- * @param o    An output iterator.
- * @result    An instance of insert_cursor working on o.
+ * @param o An output cursor.
+ * @result  An instance of insert_cursor working on o.
  * 
  * Use as shortcut for cumbersome typenames, just as with std::inserter and the like.
  */
-template<class Tree>
-inline insert_cursor<Tree>
-tree_inserter(Tree& t, typename Tree::cursor c)
+template<class Tr>
+inline insert_cursor<Tr>
+tree_inserter(Tr& t, typename Tr::cursor c)
 {
-    return insert_cursor<Tree>(t, c);
+    return insert_cursor<Tr>(t, c);
 }
 
 } // namespace tree

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	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -12,19 +12,26 @@
 #ifndef BOOST_TREE_ITERATOR_HPP
 #define BOOST_TREE_ITERATOR_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>
 
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept_check.hpp>
+
 namespace boost {
 namespace tree {
+    
+using namespace boost_concepts;
 
 /**
  * @brief   Traversal order iterator adaptor
  * 
- *          Only works with ascending cursors.
+ * This wrapper adapts a cursor (which is used for hierarchical
+ * traversal) to work as an iterator (for linear traversal, such
+ * as required by STL algorithms), along a specified order.
+ * 
  */
 template <class Order, class Cursor>
 class iterator
@@ -33,6 +40,8 @@
       , boost::use_default
       , typename Order::iterator_category
     > {
+BOOST_CONCEPT_ASSERT((AscendingCursor<Cursor>));
+
  private:
     struct enabler {};
 
@@ -74,10 +83,9 @@
 };
 
 /**
- * @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
+ * @brief   First element of a subtree in traversal
+ * @param c A cursor
+ * @return  Iterator to the first element of @a c
  */
 template <class Order, class Cursor>
 iterator<Order, Cursor>

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -276,9 +276,9 @@
 //namespace inorder {
 //
 ///**
-// * @brief    First element of a MultiwayTree in inorder traversal
-// *             (equivalent to postorder::first()) - O(1) overload for nary_tree
-// * @param t    A nary_tree
+// * @brief     First element of a MultiwayTree in inorder traversal.
+// *            O(1) overload for nary_tree
+// * @param t   A nary_tree
 // * @return    Mutable cursor to the first element of @a t in inorder traversal
 // */
 //template <class T, class Balance, class Augment, class Alloc>
@@ -289,10 +289,9 @@
 //}
 //
 ///**
-// * @brief    First element of a MultiwayTree in inorder traversal
-// *             (Alias of cfirst(); equivalent to postorder::first()) -
-// *             O(1) overload for nary_tree
-// * @param t    A nary_tree
+// * @brief     First element of a MultiwayTree in inorder traversal
+// *            (alias of cfirst()). O(1) overload for nary_tree
+// * @param t   A nary_tree
 // * @return    Read-only cursor to the first element of @a t in inorder traversal
 // */
 //template <class T, class Balance, class Augment, class Alloc>
@@ -303,9 +302,9 @@
 //}
 //
 ///**
-// * @brief    First element of a MultiwayTree in inorder traversal
-// *             (equivalent to postorder::first()) - O(1) overload for nary_tree
-// * @param t    A nary_tree
+// * @brief     First element of a MultiwayTree in inorder traversal.
+// *            O(1) overload for nary_tree
+// * @param t   A nary_tree
 // * @return    Read-only cursor to the first element of @a t in inorder traversal
 // */
 //template <class T, class Balance, class Augment, class Alloc>

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -23,7 +23,20 @@
 namespace boost {
 namespace tree {
 
-
+/**
+ * @brief Turns any cursor into an root tracking one. 
+ * 
+ * This wrapper tracks the cursor it is initially given as root.
+ * When later descending and possibly re-ascending, it can thus
+ * tell if any cursor reached via those operations is the root.
+ * 
+ * It works for any cursor, but doesn't make much sense
+ * with descending ones as they will never re-ascend.
+ * 
+ * This adaptor is required for the treatment of subtrees - if we were only
+ * requiring algorithms to work on entire trees (as in many textbooks),
+ * we wouldn't really need such a device.
+ */
 template <class Cursor> 
 class root_tracking_cursor
 : public cursor_adaptor<root_tracking_cursor<Cursor>
@@ -104,8 +117,7 @@
         this->base_reference().to_parent();
     }
 
-public:
-    bool is_root() const
+    bool is_root_() const
     {
         return !m_depth;
     }

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -14,28 +14,28 @@
 
 #include <boost/concept_check.hpp>
 
-namespace boost {
-namespace tree {
+namespace boost_concepts {
 
 template <class X>
 struct Tree
 {
 public:
-    typedef typename Tree::cursor cursor;
-    typedef typename Tree::const_cursor const_cursor;
+    typedef typename X::cursor cursor;
+    typedef typename X::const_cursor const_cursor;
 
     BOOST_CONCEPT_USAGE(Tree)
     {
-        t.root();
+        c = t.root();
+        cc = t.root();
     }
     
 private:
     X t;
+    cursor c;
+    const_cursor cc;
     
 };
 
-
-} // namespace tree
-} // namespace boost
+} // namespace boost_concepts
 
 #endif // BOOST_TREE_TREE_CONCEPTS_HPP

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	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -15,6 +15,18 @@
 [section Overview]
 
 [section Motivation]
+Trees can be found in most fields of computer science. In C++, 
+[http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree self-balancing binary search trees
+(SBBSTs)] are used in prominent implementations of the Standard Template Library's (STL) associative containers, ie
+`std::map`, `std::set` and their "multi" variants (Ref gcc?). But as we're only talking about implementations here,
+the actual trees aren't ever visible to a user of the STL. This of course already hints at the importance of
+trees plus at least one other level of indirection: trees for quick (O(log n)) associative storage and 
+retrieval of data.
+
+Furthermore, there are a couple of libraries that provide tree classes for the somewhat more obvious cases 
+in which the tree is not just an implementation detail, but where the actual hierarchical structure interface 
+is needed, eg for representing a directory hierarchy or an XML file.
+
 Existing efforts concerning C++ tree designs and implementations mostly try either to present somewhat 
 STL-compatible iterator-like types and tree classes for mapping the latter kind of external or "explicit" 
 structures (ref); or, on the other hand, untangle balancing mechanisms from key search and other 
@@ -22,7 +34,7 @@
 [link clrs CLRS]). 
 At the time of this writing, no efforts are known to the author that would cater for both cases; and, as 
 an aspect of this fact, there are presently no efforts that try in turn to separate the underlying tree 
-structure or "topology" from searching, balancing and augmenting.
+structure or "topology" from searching, balancing and augmenting and open up its hierarchical interface.
 
 The present approach in providing a consistent framework for trees is arranged roughly around the following 
 principles:
@@ -59,7 +71,10 @@
 [section Some Introductory Examples]
 
 [section (Multiway) Tree Search]
-Due to their implicit-only nature within the Standard Library (as used by `map`or `set` internally), 
+
+[import ../example/stl_lower_bound.cpp]
+
+Due to their implicit-only nature within the Standard Library (as used by `map` or `set` internally), 
 there are no algorithms that deal with tree structures -- which naturally require an approach differing 
 from the one-dimesional, iterator(-interval)-based ones present in the STL. Most notably, binary search 
 algorithms like `lower_bound` and `upper_bound` hardly make sense using a linearized version of the tree 
@@ -73,14 +88,7 @@
 To motivate this, we illustrate this by crafting a `lower_bound` binary tree search algorithm. 
 To do so, consider the following piece of code:
 
-	std::vector<int> v(1, 1066); // c contains one element: 1066
-	std::vector<int>::const_iterator ci996  = std::lower_bound(v.begin(), v.end(),  996);
-	std::vector<int>::const_iterator ci1066 = std::lower_bound(v.begin(), v.end(), 1066);
-	std::vector<int>::const_iterator ci2006 = std::lower_bound(v.begin(), v.end(), 2006);
-
-	assert(ci996  == v.begin());
-	assert(ci1066 == v.begin());
-	assert(ci2006 == v.end());
+[stl_lower_bound_example]
 
 If this doesn't really excite you, that's perfectly okay. Note however that this kind of binary "flat"
 search does something that is similar to what a binary tree search algorithm just as well at every 
@@ -103,14 +111,14 @@
 
 Note that while coupling range with iterator concepts, we decide at the same time for a separation
 of the (user-supplied) value contents of a tree cursor and its children. This reflects the desire
-that tree traversal, as achieved by cursors, should be mapped a structural matter rather than a
+that tree traversal, as achieved by cursors, should be a structural matter rather than a
 content-dependent one (which can more concretely be seen e.g. in the fact that there is always one
  child node more than values in a (multiway) tree).
 
 In particular, although `c.end()` can still not be dereferenced, there may well be other valid operations
 (independent of its `*` and `->` operators - those would only be useful in case ). In our case, this is
  mainly range operations like `c.end().begin()` and `c.end().end()`; but as we can hardly always guarantee
-that there actually ['is] a child range, we need some way to detect these operations are actually legal.
+that there actually ['is] a child range, we need some way to detect these operations are really legal.
 This is what `c.empty()` is used for, and this includes an actual change to its expression semantics; it
 is guaranteed to be legal for any valid cursor `c` even if that cursor's `c.begin()` and `c.end()` are not
 (so we cannot really say that it is equivalent to `c.begin() == c.end()`). It is, however, about the
@@ -202,7 +210,7 @@
 # With any amount of extra information, such as parent "pointers", using a stack can become obsolete
 altogether.
 
-[/import ../../../boost/tree/algorithm/postorder.hpp]
+[/import ../../../boost/tree/detail/algorithm/postorder.hpp]
 
 Boost.Tree offers you each of the options listed above, each found in a namepace indicating the respective
 traversal order. For option number 1, pass the (root cursor of the) subtree to be traversed to either of
@@ -210,21 +218,13 @@
 [/postorder_for_each]
 [/warning TODO: Use up-to-date Boostbook to embed current code snip form header files directly!]
 
-[funcref boost::tree::preorder::for_each preorder::for_each]
-
-[funcref boost::tree::inorder::for_each inorder::for_each]
-
-[funcref boost::tree::postorder::for_each postorder::for_each]
+[funcref boost::tree::for_each 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::inorder::iterator inorder::iterator]
-
-[classref boost::tree::postorder::iterator postorder::iterator]
+[classref boost::tree::iterator 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 

Copied: sandbox/SOC/2006/tree/trunk/libs/tree/example/stl_lower_bound.cpp (from r49827, /sandbox/SOC/2006/tree/trunk/libs/tree/example/for_each.cpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/libs/tree/example/for_each.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/example/stl_lower_bound.cpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -4,38 +4,20 @@
 //  (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
 
-#include <boost/tree/binary_tree.hpp>
-//[ for_each_include_algorithm
-#include <boost/tree/algorithm.hpp>
-//]
-
-#include <iostream>
-
-#include "../test/test_tree_traversal_data.hpp"
-
-using namespace boost::tree;
-
-//[ for_each_example
-void to_cout(int i) {
-    std::cout << ' ' << i;
-    return;
-}
+#include <vector>
+#include <algorithm>
+#include <cassert>
 
 int main() {
-    binary_tree<int> bt;
-    
-    // Fill it with data...
-    test_binary_tree_fixture<int>::create_test_dataset1_tree(bt);
-
-    std::cout << "Preorder:";
-    for_each(preorder(), bt.root(), to_cout);
-    
-    std::cout << std::endl << "Inorder:";
-    for_each(inorder(), bt.root(), to_cout);
-    
-    std::cout << std::endl << "Postorder:";
-    for_each(postorder(), bt.root(), to_cout);
-
+//[ stl_lower_bound_example
+    std::vector<int> v(1, 1066); // c contains one element: 1066
+    std::vector<int>::const_iterator ci996  = std::lower_bound(v.begin(), v.end(),  996);
+    std::vector<int>::const_iterator ci1066 = std::lower_bound(v.begin(), v.end(), 1066);
+    std::vector<int>::const_iterator ci2006 = std::lower_bound(v.begin(), v.end(), 2006);
+
+    assert(ci996  == v.begin());
+    assert(ci1066 == v.begin());
+    assert(ci2006 == v.end());
+//]
     return 0;
 }
-//]
\ No newline at end of file

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -36,4 +36,21 @@
     boost::tree::for_each(Order(), c, f);
 }
 
+//BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy, Order, orders )
+//{
+////    boost::detail::dummy_constructor dummy_cons;
+//    cursor_archetype< boost::null_archetype<>
+//                      , boost::iterator_archetypes::readable_lvalue_iterator_t // Really lvalue?
+//                      , boost::forward_traversal_tag
+//                      , boost::forward_traversal_tag
+//                      > i;
+//    cursor_archetype< boost::assignable_archetype<>
+//                      , boost::iterator_archetypes::writable_lvalue_iterator_t // Really lvalue?
+//                      , boost::forward_traversal_tag
+//                      , boost::forward_traversal_tag
+//                      > o;
+//    
+//    boost::tree::copy(Order(), i, o);
+//}
+
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -33,7 +33,7 @@
     d = upper_bound(r, v); 
     
     BOOST_CHECK_EQUAL(*c, v);
-    //BOOST_CHECK_EQUAL(inorder::next(c) , d);
+    //BOOST_CHECK_EQUAL(next(inorder(), c) , d);
 }
 
 BOOST_AUTO_TEST_CASE( binary_tree_search_test )

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-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -252,7 +252,7 @@
     c = bt0.inorder_first();
     BOOST_CHECK_EQUAL(*c, 1);
     c = bt0.root();
-    //inorder::back(c);
+    //back(inorder(), c);
     //BOOST_CHECK_EQUAL(*c, 14);    
 
     //inorder_erase_test_dataset1_tree(bt);

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-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -114,7 +114,7 @@
 //    BOOST_CHECK_EQUAL(*ci, 8);
 //    BOOST_CHECK_EQUAL(*++ci, 10); //FIXME
     
-//    test::preorder::traversal(test_list.begin(), test_list.end());
+//    test::traversal(preorder(), test_list.begin(), test_list.end());
     
     // Output bt using write_graphviz. This might require copying
     // the IncidenceGraph to a VertexListGraph (using copy_component) 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp	2008-11-18 17:16:07 EST (Tue, 18 Nov 2008)
@@ -164,7 +164,7 @@
 //    std::list<int> test_list;
 //    
 //    // TODO: Put this into a better testing context.
-//    boost::tree::preorder::for_each(
+//    boost::tree::for_each(preorder(), 
 //        test_tree.root(), 
 //        boost::lambda::bind(&std::list<int>::push_back, &test_list, boost::lambda::_1)
 //    );