[Boost-commit] svn:boost r49732 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail/algorithm boost/tree/detail/cursor boost/tree/detail/node libs/tree/test

Subject: [Boost-commit] svn:boost r49732 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail/algorithm boost/tree/detail/cursor boost/tree/detail/node libs/tree/test
From: ockham_at_[hidden]
Date: 2008-11-13 17:08:23

Author: bernhard.reiter
Date: 2008-11-13 17:08:22 EST (Thu, 13 Nov 2008)
New Revision: 49732
URL: http://svn.boost.org/trac/boost/changeset/49732

Log:
Start introducing concept checks.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp
      - copied, changed from r49720, /sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp                |    24 +++                                     
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp            |   280 ++++++--------------------------------- 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp   |    61 +++++++-                                
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp |    10 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp |    38 ++++                                    
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp  |    40 ++++-                                   
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp       |     1                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp         |     3                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp           |    12                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp                |     8 +                                       
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp       |    18 -                                       
   11 files changed, 217 insertions(+), 278 deletions(-)

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-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -282,6 +282,25 @@
 //        m_node_alloc.deallocate(p_node, 1);
 //    }
      
+//     static void destroy_node(cursor position)
+//     {
+//        if (!position.empty()) {
+//             node_pointer pos_node = 
+//                 static_cast<node_pointer>(position.m_node->operator[](position.m_pos));
+//             // delete the value position points to    
+//             m_value_alloc.destroy(pos_node->data());
+//             m_value_alloc.deallocate(pos_node->data(), 1);
+//             
+//            // recurse
+////             clear(position.begin());
+////             clear(position.end());
+//             
+//             // delete the node position points to
+//            m_node_alloc.destroy(pos_node);
+//            m_node_alloc.deallocate(pos_node, 1);         
+//          }
+//     }
+     
      /** 
       * Removes a node and its descendants recursively in postorder
       * without rebalancing
@@ -290,6 +309,11 @@
      // TODO: Take care of header-pointers
      void clear(cursor position) 
      {
+//    return cursor(boost::tree::for_each(boost::tree::postorder()
+//                , direct_cursor(position)
+//                , destroy_node
+//                , forward_traversal_tag()));
+
          if (!position.empty()) {
              node_pointer pos_node = 
                  static_cast<node_pointer>(position.m_node->operator[](position.m_pos));

Copied: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp (from r49720, /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_concepts.hpp	2008-11-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -5,260 +5,70 @@
 //  http://www.boost.org/LICENSE_1_0.txt)
 
 /** 
- * @file cursor.hpp
- * Cursor traits structs, traversal tags, ...
+ * @file cursor_concepts.hpp
+ * Cursor concepts
  */
  
-#ifndef BOOST_TREE_CURSOR_HPP
-#define BOOST_TREE_CURSOR_HPP
+#ifndef BOOST_TREE_CURSOR_CONCEPTS_HPP
+#define BOOST_TREE_CURSOR_CONCEPTS_HPP
 
-#include <boost/iterator/iterator_facade.hpp>
-#include <boost/iterator/iterator_adaptor.hpp>
-
-#include <stddef.h>
-#include <iterator>
-
-using std::input_iterator_tag;
-using std::output_iterator_tag;
-using std::forward_iterator_tag;
-using std::bidirectional_iterator_tag;
-using std::random_access_iterator_tag;
+#include <boost/concept_check.hpp>
 
 namespace boost {
 namespace tree {
 
-
-template <class Cursor>
-struct cursor_value {
-    typedef typename Cursor::value_type type;
-};
-
-template <class Cursor>
-struct cursor_reference {
-    typedef typename Cursor::reference type;
-};
-
-template <class Cursor>
-struct cursor_const_reference {
-    typedef typename Cursor::const_reference type;
-};
-
-template <class Cursor>
-struct cursor_pointer {
-    typedef typename Cursor::pointer type;
-};
-
-template <class Cursor>
-struct cursor_difference {
-    typedef typename Cursor::difference_type type;
-};
-
-template <class Cursor>
-struct cursor_size {
-    typedef typename Cursor::size_type type;
-};
-
-template <class Cursor>
-struct cursor_category {
-    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 Ptr        pointer;
-    typedef Ref        reference;    
+template <class X>
+struct DescendingCursor
+{
+public:
+    BOOST_CONCEPT_USAGE(DescendingCursor)
+    {
+        d.to_begin();
+        d.to_end();
+    }
+    
+private:
+    X d;
+    
 };
 
-// Deprecate?
-struct cursor_tag {};
-
-struct descending_tag {}; 
-struct descending_cursor_tag
-    : public cursor_tag, public descending_tag, 
-      public input_iterator_tag, public output_iterator_tag {};
-struct descending_forward_cursor_tag
-    : public cursor_tag, public descending_tag, public forward_iterator_tag {};
-struct descending_bidirectional_cursor_tag
-    : public cursor_tag, public descending_tag, public bidirectional_iterator_tag {};
-struct descending_random_access_cursor_tag
-    : public cursor_tag, public descending_tag, public random_access_iterator_tag {};
-
-struct ascending_tag {};
-struct ascending_cursor_tag
-    : public descending_cursor_tag, public ascending_tag {};
-struct ascending_forward_cursor_tag
-    : public descending_forward_cursor_tag, public ascending_tag {};
-struct ascending_bidirectional_cursor_tag
-    : public descending_bidirectional_cursor_tag, public ascending_tag {};
-struct ascending_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;
+template <class T>
+class descending_cursor_archetype
+{
+public:
+    void to_begin() {}
+    void to_end() {}
 };
-*/
 
-//define freestanding begin, end, size, empty using cursor's member fns?
-
-template <
-    class OutputIterator
-//  , class Value                         
-//  , class HorizontalTraversalOrCategory 
-//  , class VerticalTraversalOrCategory
-//  , class Reference                     
-//  , class Difference                
-//  , class Size                          
->
-class output_cursor_iterator_wrapper;
-
-/**
- * @brief Output cursor wrapper around an output iterator.
- * 
- * 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.)
- * 
- * For construction, the outputter_cursor_iterator_wrapper might come in useful
- * in saving keystrokes.
- */
-// TODO: Complete this.
-// Shouldn't we be using cursor_facade?
-template <
-    class OutputIterator
-//  , class Value                         = use_default
-//  , class HorizontalTraversalOrCategory = use_default
-//  , class VerticalTraversalOrCategory   = bidirectional_traversal_tag
-//  , class Reference                     = use_default
-//  , class Difference                    = use_default
-//  , class Size                          = use_default
->
-class output_cursor_iterator_wrapper {
-protected:
-    OutputIterator* iter;
-//private:
-//    typedef iterator_adaptor<output_cursor_iterator_wrapper<OutputIterator> 
-//                         , OutputIterator
-//                         , Value
-//                         , HorizontalTraversalOrCategory
-//                         , Reference
-//                         , Difference> ia_type;
+// Derive from DescendingCursor or not?
+template <class X>
+struct AscendingCursor
+{
 public:
-    /// Make the iterator type publicly accessible.
-    typedef OutputIterator iterator;
-
-    // FIXME: Very adhoc.
-    typedef output_cursor_iterator_wrapper<OutputIterator> value_type;
-    typedef std::size_t size_type;
-    typedef output_cursor_iterator_wrapper<OutputIterator> const_cursor;
-    typedef forward_traversal_tag horizontal_traversal;
-    typedef bidirectional_traversal_tag vertical_traversal;
-    typedef forward_traversal_tag iterator_category;
-    typedef std::ptrdiff_t difference_type;
-    typedef value_type* pointer;
-    typedef value_type& reference;
-        
-    /**
-     * For construction, we obviously need an Output Iterator to work on (i.e., write to).
-     */
-    explicit output_cursor_iterator_wrapper(OutputIterator& i) : iter(&i) {}
-
-    /** 
-     * @param value A const& value of the value_type of container that iter is
-     *              associated with.
-     * @return      This cursor, for chained operations.
-     * Assigning a value to this cursor will insert it before iter, the iterator it is
-     * wrapped around.
-     * 
-     * Unfortunately, Output Iterators do not necessarily expose their
-     * value_type (they might just give back void), so the following assignment operator
-     * has to be a template.
-     */
-    // TODO: Consult C++0x if this has been changed
-    template <class ValueType>
-    output_cursor_iterator_wrapper& operator=(ValueType const& value)
-    { 
-        *((*iter)++) = value;
-        return *this; 
+    BOOST_CONCEPT_USAGE(AscendingCursor)
+    {
+        a.to_parent();
     }
-
-    /// Returns *this.
-    output_cursor_iterator_wrapper& operator*() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& operator++() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper operator++(int) { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& operator--() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper operator--(int) { return *this; }
-    
-    /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& to_begin() { return *this; }
-    output_cursor_iterator_wrapper& begin() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& to_end() { return *this; }
-    output_cursor_iterator_wrapper& end() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& to_parent() { return *this; }
-    output_cursor_iterator_wrapper& parent() { return *this; }
     
-    /// Returns true, in case an algorithm has a loop only terminating at root.
-    bool is_root() const { return true; }
-    
-    /// Returns true, in case an algorithm has a loop only terminating at a leaf.
-    bool empty() const { return true; }
-    
-    std::size_t const index() const { return 0; }
+private:
+    X a;
 };
 
-template <class OutputIterator>
-typename output_cursor_iterator_wrapper<OutputIterator>::size_type
-index(output_cursor_iterator_wrapper<OutputIterator> const& cur)
+template <class X>
+struct OutputCursor
 {
-    return cur.index();
-}
+public:
+    BOOST_CONCEPT_USAGE(OutputCursor)
+    {
+        /// TODO
+    }
+    
+private:
+    X o;
+};
 
-/** 
- * @param o    An output iterator.
- * @result    An instance of output_cursor_iterator_wrapper working on o.
- * 
- * Use as shortcut for cumbersome typenames, just as with std::inserter and the like.
- */
-template<class OutputIterator>
-inline output_cursor_iterator_wrapper<OutputIterator>
-outputter_cursor_iterator_wrapper(OutputIterator o)
-{
-    return output_cursor_iterator_wrapper<OutputIterator>(o);
-}
 
 } // namespace tree
 } // namespace boost
 
-
-#endif // BOOST_TREE_CURSOR_HPP
+#endif // BOOST_TREE_CURSOR_CONCEPTS_HPP

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-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -14,6 +14,9 @@
 
 #include <boost/tree/root_tracking_cursor.hpp>
 #include <boost/tree/ascending_cursor.hpp>
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
 
 #include <algorithm>
 
@@ -33,7 +36,12 @@
  * @ingroup    traversal
  */
 template <class MultiwayCursor>
-inline void forward(inorder, MultiwayCursor& c)
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<MultiwayCursor>))
+    ((AscendingCursor<MultiwayCursor>)),
+    (void)) // return type
+forward(inorder, MultiwayCursor& c)
 {
     if (!(++c).empty()) {
         while (!c.to_begin().empty());
@@ -50,7 +58,12 @@
  * @param c    MultiwayCursor to be set to its inorder predecessor
  */
 template <class MultiwayCursor>
-inline void back(inorder, MultiwayCursor& c)
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<MultiwayCursor>))
+    ((AscendingCursor<MultiwayCursor>)),
+    (void)) // return type
+back(inorder, MultiwayCursor& c)
 {
     if (!c.empty()) {
         while (!c.to_end().empty());
@@ -71,7 +84,10 @@
  *          position in the subtree.
  */
 template <class Cursor>
-void to_first(inorder, Cursor& c)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+to_first(inorder, Cursor& c)
 {
     while (!c.empty())
         c.to_begin();
@@ -98,7 +114,10 @@
  * @endif
  */
 template <class MultiwayCursor, class Op>
-void for_each_recursive(inorder, MultiwayCursor s, Op& f)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<MultiwayCursor>)),
+    (void)) // return type
+for_each_recursive(inorder, MultiwayCursor s, Op& f)
 {
     MultiwayCursor t = s.end();
 
@@ -125,7 +144,10 @@
  * If @p f has a return value it is ignored.
  */
 template <class MultiwayCursor, class Op>
-Op for_each(inorder, MultiwayCursor s, Op f, forward_traversal_tag)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<MultiwayCursor>)),
+    (Op)) // return type
+for_each(inorder, MultiwayCursor s, Op f, forward_traversal_tag)
 {
     MultiwayCursor t = s.end();
 
@@ -155,7 +177,12 @@
  * op must not change its argument.
  */
 template <class InCursor, class OutCursor, class Op>
-OutCursor transform(inorder, InCursor s, OutCursor t, Op op, forward_traversal_tag)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<InCursor>))
+    ((DescendingCursor<OutCursor>))
+    /*((UnaryFunction<Op>))*/,
+    (OutCursor)) // return type
+transform(inorder, InCursor s, OutCursor t, Op op, forward_traversal_tag)
 {
     InCursor r = s.end();
 
@@ -190,7 +217,10 @@
  */
 //[ lower_bound
 template <class MultiwayCursor, class T>
-MultiwayCursor lower_bound(MultiwayCursor x, T const& val)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<MultiwayCursor>)),
+    (MultiwayCursor)) // return type
+lower_bound(MultiwayCursor x, T const& val)
 //]
 {
     MultiwayCursor y = x;
@@ -215,7 +245,11 @@
  */
 //[ lower_bound_cmp
 template <class MultiwayCursor, class T, class Cmp>
-MultiwayCursor lower_bound(MultiwayCursor x, T const& val, Cmp cmp)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<MultiwayCursor>))
+    /*((LessThanComparable<Cmp>))*/, // Problem with balanced_tree
+    (MultiwayCursor)) // return type
+lower_bound(MultiwayCursor x, T const& val, Cmp cmp)
 //]
 {
     MultiwayCursor y = x;
@@ -239,7 +273,10 @@
  */
 //[ upper_bound
 template <class MultiwayCursor, class T>
-MultiwayCursor upper_bound(MultiwayCursor x, T const& val)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<MultiwayCursor>)),
+    (MultiwayCursor)) // return type
+upper_bound(MultiwayCursor x, T const& val)
 //]
 {
     MultiwayCursor y = x;
@@ -264,7 +301,11 @@
  */
 //[ upper_bound_cmp
 template <class MultiwayCursor, class T, class Cmp>
-MultiwayCursor upper_bound(MultiwayCursor x, T const& val, Cmp cmp)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<MultiwayCursor>))
+    ((LessThanComparable<Cmp>)),
+    (MultiwayCursor)) // return type
+upper_bound(MultiwayCursor x, T const& val, Cmp cmp)
 //]
 {
     MultiwayCursor y = x;

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp	2008-11-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -20,11 +20,19 @@
 #include <boost/tree/detail/algorithm/inorder.hpp>
 #include <boost/tree/detail/algorithm/postorder.hpp>
 
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
+
 namespace boost {
 namespace tree {
 
 template <class Order, class Cursor, class Op>
-Op for_each(Order, Cursor is, Op f, bidirectional_traversal_tag)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>))
+    ((AscendingCursor<Cursor>)),
+    (Op)) // return type
+for_each(Order, Cursor is, Op f, bidirectional_traversal_tag)
 {
     root_tracking_cursor<Cursor> s(is);
     root_tracking_cursor<Cursor> s2(s);

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-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -14,6 +14,9 @@
 
 #include <boost/tree/root_tracking_cursor.hpp>
 #include <boost/tree/ascending_cursor.hpp>
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
 
 namespace boost {
 namespace tree {
@@ -30,7 +33,12 @@
  * @param c    Cursor to be set to its postorder successor
  */
 template <class Cursor>
-inline void forward(postorder, Cursor& c)
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>))
+    ((AscendingCursor<Cursor>)),
+    (void)) // return type
+forward(postorder, Cursor& c)
 {
     c.to_parent();
 
@@ -59,7 +67,12 @@
  * @param c    Cursor to be set to its postorder predecessor
  */
 template <class Cursor>
-inline void back(postorder, Cursor& c)
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>))
+    ((AscendingCursor<Cursor>)),
+    (void)) // return type
+back(postorder, Cursor& c)
 {
     if (c.is_root()) { // Root?
         c.to_begin();
@@ -94,7 +107,10 @@
  *          position in the subtree.
  */
 template <class Cursor>
-void to_first(postorder, Cursor& c)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+to_first(postorder, Cursor& c)
 {
     while (true)
         if (!c.empty())
@@ -128,7 +144,10 @@
  * @endif
  */
 template <class Cursor, class Op>
-void for_each_recursive(postorder, Cursor s, Op& f)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+for_each_recursive(postorder, Cursor s, Op& f)
 {
     Cursor t = s;
     for (s.to_begin(); s != t.end(); ++s)
@@ -153,7 +172,10 @@
  * If @p f has a return value it is ignored.
  */
 template <class Cursor, class Op>
-Op for_each(postorder, Cursor s, Op f, forward_traversal_tag)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (Op)) // return type
+for_each(postorder, Cursor s, Op f, forward_traversal_tag)
 {
     Cursor t = s;
     for (s.to_begin(); s != t.end(); ++s)
@@ -183,7 +205,11 @@
  * op must not change its argument.
  */
 template <class InCursor, class OutCursor, class Op>
-OutCursor transform(postorder, InCursor s, OutCursor t, Op op, forward_traversal_tag)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<InCursor>))
+    ((DescendingCursor<OutCursor>)),
+    (OutCursor)) // return type
+transform(postorder, InCursor s, OutCursor t, Op op, forward_traversal_tag)
 {
     InCursor r = s;
     s.to_begin();

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-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -16,6 +16,9 @@
 
 #include <boost/tree/root_tracking_cursor.hpp>
 #include <boost/tree/ascending_cursor.hpp>
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
 
 namespace boost {
 namespace tree {
@@ -31,8 +34,13 @@
  * @brief    Preorder successor
  * @param c    Cursor to be set to its preorder successor
  */
-template <class Cursor>
-inline void forward(preorder, Cursor& c)
+template <typename Cursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>))
+    ((AscendingCursor<Cursor>)),
+    (void)) // return type
+forward(preorder, Cursor& c)
 {
     // If we have a left child, go there.
     if (!c.empty()) {
@@ -68,7 +76,12 @@
  * @param c    Cursor to be set to its preorder predecessor
  */
 template <class Cursor>
-inline void back(preorder, Cursor& c)
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>))
+    ((AscendingCursor<Cursor>)),
+    (void)) // return type
+back(preorder, Cursor& c)
 {
     if (!c.is_root()) {
         c.to_parent();
@@ -99,7 +112,10 @@
  *          position in the subtree.
  */
 template <class Cursor>
-void to_first(preorder, Cursor& c)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+to_first(preorder, Cursor& c)
 {
     c.to_begin();
 }
@@ -125,7 +141,10 @@
  * @endif
  */
 template <class Cursor, class Op>
-void for_each_recursive(preorder, Cursor s, Op& f)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+for_each_recursive(preorder, Cursor s, Op& f)
 {
     Cursor t = s.end();
     for (s.to_begin(); s != t; ++s) {
@@ -150,7 +169,10 @@
  * If @p f has a return value it is ignored.
  */
 template <class Cursor, class Op>
-Op for_each(preorder, Cursor s, Op f, forward_traversal_tag)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (Op)) // return type
+for_each(preorder, Cursor s, Op f, forward_traversal_tag)
 {
     Cursor t = s.end();
     for (s.to_begin(); s != t; ++s) {
@@ -182,7 +204,11 @@
  * op must not change its argument.
  */
 template <class InCursor, class OutCursor, class Op>
-OutCursor transform(preorder, InCursor s, OutCursor t, Op op, forward_traversal_tag)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<InCursor>))
+    ((DescendingCursor<OutCursor>)),
+    (OutCursor)) // return type
+transform(preorder, InCursor s, OutCursor t, Op op, forward_traversal_tag)
 {
     InCursor r = s.end();
     s.to_begin();

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp	2008-11-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -40,6 +40,7 @@
       , bidirectional_traversal_tag
       , bidirectional_traversal_tag
     > {
+
 private:
     struct enabler {};
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp	2008-11-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -41,7 +41,8 @@
       , random_access_traversal_tag
       , bidirectional_traversal_tag
     > {
- private:
+
+private:
     typedef typename Node::base_type node_base;
       
     typedef typename mpl::eval_if<

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp	2008-11-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -68,10 +68,10 @@
 class node_base : public node_with_parent_base, public Container<node_base<Container>*> {
     typedef node_base<Container> self_type;
     
- public:
+public:
  
-     typedef Container<node_base<Container>*> base_type;
-     typedef typename base_type::size_type size_type;
+    typedef Container<node_base<Container>*> base_type;
+    typedef typename base_type::size_type size_type;
     typedef self_type* base_pointer;
     typedef self_type const* const_base_pointer;
     
@@ -112,9 +112,9 @@
 : public node_with_parent_base, public binary_array<node_base<binary_array>*> {
     typedef node_base<binary_array> self_type;
     
- public:
+public:
  
-     typedef binary_array<node_base*> base_type;
+    typedef binary_array<node_base*> base_type;
     typedef self_type* base_pointer;
     typedef self_type const* const_base_pointer;
     
@@ -206,7 +206,7 @@
 template <typename T, template <typename> class Container>
 class node : public node_base<Container> {
  public:
-     typedef T value_type;
+    typedef T value_type;
     
     typedef Container<node_base<Container>*> container_type;
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp	2008-11-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -15,6 +15,8 @@
 #include <boost/tree/detail/cursor/forest.hpp>
 #include <boost/tree/binary_tree.hpp>
 
+#include <boost/concept_check.hpp>
+
 namespace boost {
 namespace tree {
 
@@ -30,7 +32,13 @@
 */
 template <class T, class Hierarchy = binary_tree<T> >
 class forest_tree {
+
+BOOST_CONCEPT_ASSERT((DefaultConstructible<T>));
+//BOOST_CONCEPT_ASSERT((SameType<T, typename Hierarchy::value_type>)); 
+// Is there a SameType concept in BCCL?
+
     typedef forest_tree<T, Hierarchy> self_type;
+
  public:
     typedef T value_type;
     typedef Hierarchy hierarchy_type;

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp	2008-11-13 17:08:22 EST (Thu, 13 Nov 2008)
@@ -58,36 +58,30 @@
 
     forest_tree<int>::cursor c = ft0.insert(ft0.root().end(), 8);
     
+    BOOST_CHECK_EQUAL(*c, 8);
     BOOST_CHECK(c == ft0.root().begin());
     BOOST_CHECK(++c == ft0.root().end());
     BOOST_CHECK(ft0.root().begin().parent() == ft0.root());
     BOOST_CHECK(!ft0.root().empty());
-    BOOST_CHECK_EQUAL(*ft0.root().begin(), 8);
     BOOST_CHECK(ft0.root().begin().empty());
     
     c = ft0.insert(ft0.root().end(), 6);
-    
+    BOOST_CHECK_EQUAL(*c, 6);
     BOOST_CHECK(ft0.root().begin() != ft0.root().end());
     BOOST_CHECK(c != ft0.root().end());
-    
     BOOST_CHECK(c.base() == ft0.root().base().begin().end());
-    
-    BOOST_CHECK_EQUAL(*c, 6);
     BOOST_CHECK(c.parent() == ft0.root());
     BOOST_CHECK(!ft0.root().empty());
-    BOOST_CHECK(++c == ft0.root().end());
-    
+    BOOST_CHECK(++c == ft0.root().end()); 
     ----c;
     BOOST_CHECK(c == ft0.root().begin());
     BOOST_CHECK_EQUAL(*c, 8);
 
-    c = ft0.insert(ft0.root().end(), 7);
-    
+    c = ft0.insert(ft0.root().end(), 7);  
     BOOST_CHECK_EQUAL(*c, 7);
     BOOST_CHECK(c.parent() == ft0.root());
     BOOST_CHECK(!ft0.root().empty());
     BOOST_CHECK(++c == ft0.root().end());
-    
     ----c;
     BOOST_CHECK_EQUAL(*c, 6);
     BOOST_CHECK(c.parent() == ft0.root());
@@ -95,9 +89,9 @@
     BOOST_CHECK(c == ft0.root().begin());
     BOOST_CHECK(c.parent() == ft0.root());
     BOOST_CHECK_EQUAL(*c, 8);
-
     c = ft0.root().begin().begin();
     BOOST_CHECK(c.parent() == ft0.root().begin());
+
     c = ft0.insert(ft0.root().begin().begin(), 3);
     BOOST_CHECK_EQUAL(*c, 3);
     BOOST_CHECK(c == ft0.root().begin().begin());
@@ -105,9 +99,9 @@
 
     // Need more checks after this line...
     c = ft0.insert(ft0.root().begin().begin().begin(), 1);
-
     c = ft0.root().begin();
     (++c).to_end();
+
     c = ft0.insert(c, 4);
     BOOST_CHECK_EQUAL(*c, 4);
     BOOST_CHECK(--(c.to_parent()) == ft0.root().begin());