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

Subject: [Boost-commit] svn:boost r50581 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-14 12:26:30

Author: bernhard.reiter
Date: 2009-01-14 12:26:29 EST (Wed, 14 Jan 2009)
New Revision: 50581
URL: http://svn.boost.org/trac/boost/changeset/50581

Log:
Rename forest_tree to forest, as it turns out to be a forest (= a collection of trees), not just "one" tree.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp
      - copied, changed from r50580, /sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
Removed:
   sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                        |     7 +++----                                 
   sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp                       |    40 ++++++++++++++++++++--------------------
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp         |    34 +++++++++++++++++-----------------      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |     2 +-                                      
   4 files changed, 41 insertions(+), 42 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-01-14 12:26:29 EST (Wed, 14 Jan 2009)
@@ -16,11 +16,10 @@
 General:
 * preorder_insert_cursor: hopefully easy to implement...
 * Add checks for correspondence of concepts and archetypes!
-* Re-do forest (again!). No root(); begin() and end() instead. No default element at
-  construction time (that would really suck). Rename forest_tree to forest, 
-  as it's going to be a forest, not just "one" tree.
+* Re-do forest (again!).
   This seems to raise one issue, though: subtree algorithms operate on subtree root cursors,
-  not ranges. (They might, however, work for "subforests".)
+  not ranges. (They might, however, work for "subforests". Consult Austern's segmented 
+  iterators paper!)
   They also work for the important special case in which forest consists of only one
   subtree!
 * Improve cursor_archetype. Currently, there's trouble eg with constructors.

Copied: sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp (from r50580, /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.hpp	2009-01-14 12:26:29 EST (Wed, 14 Jan 2009)
@@ -5,12 +5,12 @@
 //  http://www.boost.org/LICENSE_1_0.txt)
 
 /** 
- * @file forest_tree.hpp
+ * @file forest.hpp
  * Binary tree based forest implementation
  */
 
-#ifndef BOOST_TREE_FOREST_TREE_HPP
-#define BOOST_TREE_FOREST_TREE_HPP
+#ifndef BOOST_TREE_forest_HPP
+#define BOOST_TREE_forest_HPP
 
 #include <boost/tree/detail/forest_cursor.hpp>
 
@@ -27,14 +27,14 @@
 using namespace boost_concepts;
 
 /** 
- * @brief A %forest_tree.
+ * @brief A %forest.
  * This class models the hierarchy concept. It is a (binary) tree adaptor,
  * and a (forest) tree of its own right.
  * TODO: complete this..
  *
 */
 template <class T, class Hierarchy = binary_tree<T> >
-class forest_tree {
+class forest {
 
 BOOST_CONCEPT_ASSERT((DefaultConstructible<T>));
 BOOST_CONCEPT_ASSERT((DescendingCursor< typename binary_tree<T>::cursor >));
@@ -42,7 +42,7 @@
 //BOOST_CONCEPT_ASSERT((SameType<T, typename Hierarchy::value_type>)); 
 // Is there a SameType concept in BCCL?
 
-    typedef forest_tree<T, Hierarchy> self_type;
+    typedef forest<T, Hierarchy> self_type;
 
  public:
     typedef T value_type;
@@ -63,7 +63,7 @@
      *  @brief    The default constructor creates one element at the root.
      *  @param    val   The value the root will be assigned. 
      */
-//    forest_tree(/*value_type const& val = value_type()*/) : h(Hierarchy())
+//    forest(/*value_type const& val = value_type()*/) : h(Hierarchy())
 //    {
 //        //h.insert(h.root(), val);
 //    }
@@ -71,16 +71,16 @@
     /**
      *  @brief    The default constructor creates no elements.
      *  @param    hier    A hierarchy object that will be used as a base to
-     *                    construct this forest_tree.
+     *                    construct this forest.
      */
-    explicit forest_tree(Hierarchy const& hier = Hierarchy()) : h(hier)
+    explicit forest(Hierarchy const& hier = Hierarchy()) : h(hier)
     {
 //        if (h.empty())
 //            h.insert(h.root(), value_type());
     }
 
     /**
-     * Returns true if the %forest_tree is empty.
+     * Returns true if the %forest is empty.
      */
     bool empty()
     {
@@ -88,7 +88,7 @@
     }
     
     /**
-     * Returns a read/write ("mutable") cursor to the %forest_tree's 
+     * Returns a read/write ("mutable") cursor to the %forest's 
      * first element.
      */     
     cursor begin()
@@ -98,7 +98,7 @@
     }
 
     /**
-     * Returns a read-only const_cursor to the %forest_tree's
+     * Returns a read-only const_cursor to the %forest's
      * first element.
      */     
     const_cursor begin() const
@@ -107,7 +107,7 @@
     }
     
     /**
-     * Returns a read-only const_cursor to the %forest_tree's
+     * Returns a read-only const_cursor to the %forest's
      * first element.
      */     
     const_cursor cbegin() const
@@ -119,7 +119,7 @@
     // TODO: end.
 
     /**
-     * Returns a read/write ("mutable") cursor past the %forest_tree's
+     * Returns a read/write ("mutable") cursor past the %forest's
      * last element.
      */     
     cursor end()
@@ -131,7 +131,7 @@
     }
 
     /**
-     * Returns a read-only const_cursor past the %forest_tree's
+     * Returns a read-only const_cursor past the %forest's
      * last element.
      */     
     const_cursor end() const
@@ -140,7 +140,7 @@
     }
     
     /**
-     * Returns a read-only const_cursor past the %forest_tree's
+     * Returns a read-only const_cursor past the %forest's
      * last element.
      */     
     const_cursor cend() const
@@ -153,7 +153,7 @@
 
     /**
      * @brief       Inserts val in front of @a pos.
-     * @param pos   The %forest_tree cursor in front of which to insert.
+     * @param pos   The %forest cursor in front of which to insert.
      * @param val   The value to insert.
      * @return      A cursor that points to the inserted data.
      */
@@ -176,7 +176,7 @@
 
 
 // TODO: template <class Cursor> -> template <class T, class Hierarchy>
-// forest_cursor<Cursor> -> forest_tree<T, Hierarchy>::cursor
+// forest_cursor<Cursor> -> forest<T, Hierarchy>::cursor
 // const_cursor?
 template <class Cursor>
 typename forest_cursor<Cursor>::size_type
@@ -185,7 +185,7 @@
     return cur.index();
 }
 
-/// Use natural forest_tree-binary_tree correspondence:
+/// Use natural forest-binary_tree correspondence:
 /// Preoder - preorder
 
 template <class Cursor, class Op>
@@ -229,4 +229,4 @@
 } // namespace tree
 } // namespace boost
 
-#endif // BOOST_TREE_FOREST_TREE_HPP
+#endif // BOOST_TREE_forest_HPP

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp	2009-01-14 12:26:29 EST (Wed, 14 Jan 2009)
+++ (empty file)
@@ -1,232 +0,0 @@
-//  Copyright (c) 2006-2009, Bernhard Reiter
-//
-//  Distributed under the Boost Software License, Version 1.0.
-//  (See accompanying file LICENSE_1_0.txt or copy at
-//  http://www.boost.org/LICENSE_1_0.txt)
-
-/** 
- * @file forest_tree.hpp
- * Binary tree based forest implementation
- */
-
-#ifndef BOOST_TREE_FOREST_TREE_HPP
-#define BOOST_TREE_FOREST_TREE_HPP
-
-#include <boost/tree/detail/forest_cursor.hpp>
-
-#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/algorithm.hpp>
-#include <boost/tree/cursor_concepts.hpp>
-
-#include <boost/concept_check.hpp>
-
-namespace boost {
-namespace tree {
-
-using detail::forest_cursor;
-using namespace boost_concepts;
-
-/** 
- * @brief A %forest_tree.
- * This class models the hierarchy concept. It is a (binary) tree adaptor,
- * and a (forest) tree of its own right.
- * TODO: complete this..
- *
-*/
-template <class T, class Hierarchy = binary_tree<T> >
-class forest_tree {
-
-BOOST_CONCEPT_ASSERT((DefaultConstructible<T>));
-BOOST_CONCEPT_ASSERT((DescendingCursor< typename binary_tree<T>::cursor >));
-BOOST_CONCEPT_ASSERT((DescendingCursor< typename binary_tree<T>::const_cursor >));
-//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;
-
-    typedef typename hierarchy_type::cursor base_cursor;
-    typedef typename hierarchy_type::const_cursor base_const_cursor;
-    
-    typedef forest_cursor<base_cursor> cursor;
-    typedef forest_cursor<base_const_cursor> const_cursor;
-    
-    typedef typename cursor_pointer<cursor>::type pointer;
-    typedef typename cursor_reference<cursor>::type reference;
-    typedef typename cursor_size<cursor>::type size_type;
-    typedef typename cursor_difference<cursor>::type difference_type;
-
-    /**
-     *  @brief    The default constructor creates one element at the root.
-     *  @param    val   The value the root will be assigned. 
-     */
-//    forest_tree(/*value_type const& val = value_type()*/) : h(Hierarchy())
-//    {
-//        //h.insert(h.root(), val);
-//    }
-
-    /**
-     *  @brief    The default constructor creates no elements.
-     *  @param    hier    A hierarchy object that will be used as a base to
-     *                    construct this forest_tree.
-     */
-    explicit forest_tree(Hierarchy const& hier = Hierarchy()) : h(hier)
-    {
-//        if (h.empty())
-//            h.insert(h.root(), value_type());
-    }
-
-    /**
-     * Returns true if the %forest_tree is empty.
-     */
-    bool empty()
-    {
-        return h.empty();
-    }
-    
-    /**
-     * Returns a read/write ("mutable") cursor to the %forest_tree's 
-     * first element.
-     */     
-    cursor begin()
-    {
-        //cursor c(h.root());
-        return cursor(h.root());
-    }
-
-    /**
-     * Returns a read-only const_cursor to the %forest_tree's
-     * first element.
-     */     
-    const_cursor begin() const
-    {
-        return cbegin();
-    }
-    
-    /**
-     * Returns a read-only const_cursor to the %forest_tree's
-     * first element.
-     */     
-    const_cursor cbegin() const
-    {
-        //const_cursor c(h.croot());
-        return const_cursor(h.croot());
-    }
-
-    // TODO: end.
-
-    /**
-     * Returns a read/write ("mutable") cursor past the %forest_tree's
-     * last element.
-     */     
-    cursor end()
-    {
-        base_cursor b(h.root());
-        while (!b.empty())
-            b.to_end();
-        return cursor(b);
-    }
-
-    /**
-     * Returns a read-only const_cursor past the %forest_tree's
-     * last element.
-     */     
-    const_cursor end() const
-    {
-        return cend();
-    }
-    
-    /**
-     * Returns a read-only const_cursor past the %forest_tree's
-     * last element.
-     */     
-    const_cursor cend() const
-    {
-        base_const_cursor b(h.croot());
-        while (!b.empty())
-            b.to_end();
-        return const_cursor(b);
-    }
-
-    /**
-     * @brief       Inserts val in front of @a pos.
-     * @param pos   The %forest_tree cursor in front of which to insert.
-     * @param val   The value to insert.
-     * @return      A cursor that points to the inserted data.
-     */
-    cursor insert(cursor pos, value_type const& val)
-    {
-        return cursor(h.insert(base_cursor(pos), val));
-    }
-
-    /**
-     * @brief Clears all data from the forest tree.
-     */
-     void clear()
-     {
-        h.clear();
-     }
-    
-protected:
-    hierarchy_type h;
-};
-
-
-// TODO: template <class Cursor> -> template <class T, class Hierarchy>
-// forest_cursor<Cursor> -> forest_tree<T, Hierarchy>::cursor
-// const_cursor?
-template <class Cursor>
-typename forest_cursor<Cursor>::size_type
-index(forest_cursor<Cursor> const& cur)
-{
-    return cur.index();
-}
-
-/// Use natural forest_tree-binary_tree correspondence:
-/// Preoder - preorder
-
-template <class Cursor, class Op>
-Op for_each(preorder, forest_cursor<Cursor> s, Op f)
-{
-    return for_each(preorder(), Cursor(s), f);
-}
-
-template <class InCursor, class OutCursor, class Op>
-OutCursor transform (preorder, forest_cursor<InCursor> s, forest_cursor<OutCursor> t, Op op)
-{
-    return transform(preorder(), InCursor(s), OutCursor(t), op);
-}
-
-template <class InCursor, class OutCursor>
-OutCursor copy (preorder, forest_cursor<InCursor> s, forest_cursor<OutCursor> t)
-{
-    return copy(preorder(), InCursor(s), OutCursor(t));
-}
-
-/// Postoder - inorder
-
-template <class Cursor, class Op>
-Op for_each(postorder, forest_cursor<Cursor> s, Op f)
-{
-    return for_each(inorder(), Cursor(s), f);
-}
-
-template <class InCursor, class OutCursor, class Op>
-OutCursor transform (postorder, forest_cursor<InCursor> s, forest_cursor<OutCursor> t, Op op)
-{
-    return transform(inorder(), InCursor(s), OutCursor(t), op);
-}
-
-template <class InCursor, class OutCursor>
-OutCursor copy (postorder, forest_cursor<InCursor> s, forest_cursor<OutCursor> t)
-{
-    return copy(inorder(), InCursor(s), OutCursor(t));
-}
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_FOREST_TREE_HPP

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	2009-01-14 12:26:29 EST (Wed, 14 Jan 2009)
@@ -4,7 +4,7 @@
 //  (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
 
-#include <boost/tree/forest_tree.hpp>
+#include <boost/tree/forest.hpp>
 #include <boost/tree/algorithm.hpp>
 
 #include <boost/lambda/bind.hpp>
@@ -14,7 +14,7 @@
 
 #include <list>
 
-#define BOOST_TEST_MODULE forest_tree test
+#define BOOST_TEST_MODULE forest test
 //#define BOOST_TEST_DYN_LINK
 #include <boost/test/included/unit_test.hpp>
 #include <boost/test/test_case_template.hpp>
@@ -28,7 +28,7 @@
 
 BOOST_AUTO_TEST_CASE( constructors_test )
 {
-    forest_tree<int> ft0;
+    forest<int> ft0;
     //BOOST_CHECK_EQUAL(*ft0.root(), 0);
     BOOST_CHECK(ft0.empty());
 }
@@ -37,9 +37,9 @@
 //{
 //    using namespace boost::tree;
 //
-////    forest_tree<int> mytree;
+////    forest<int> mytree;
 ////    
-////    forest_tree<int>::cursor c = mytree.root();
+////    forest<int>::cursor c = mytree.root();
 ////    c = mytree.insert(c, 6);
 ////    BOOST_CHECK_EQUAL(*c, 6);
 ////
@@ -55,9 +55,9 @@
 ////    ++c;
 ////    BOOST_CHECK_EQUAL(*c, 6);
 //    
-//    forest_tree<int> ft0;
+//    forest<int> ft0;
 //
-//    forest_tree<int>::cursor c = ft0.insert(ft0.end(), 8); //FIXME
+//    forest<int>::cursor c = ft0.insert(ft0.end(), 8); //FIXME
 //    
 //    BOOST_CHECK_EQUAL(*c, 8);
 //    BOOST_CHECK(c == ft0.begin());
@@ -113,7 +113,7 @@
 //    BOOST_CHECK_EQUAL(*c.to_begin(), 1);
 //    BOOST_CHECK(c.empty());
 //    
-//    //validate_corresponding_forest_tree(ft0);
+//    //validate_corresponding_forest(ft0);
 //}
 
 BOOST_AUTO_TEST_SUITE_END()
@@ -122,8 +122,8 @@
 
 BOOST_AUTO_TEST_CASE( binary_tree_constructor_test )
 {
-    forest_tree<int, fake_binary_tree<int> > ft0(fbt1);
-    forest_tree<int, fake_binary_tree<int> >::const_cursor c = ft0.begin();
+    forest<int, fake_binary_tree<int> > ft0(fbt1);
+    forest<int, fake_binary_tree<int> >::const_cursor c = ft0.begin();
    
     //TODO: validate
     BOOST_CHECK_EQUAL(*c, 8);
@@ -138,7 +138,7 @@
 
     c = ft0.begin().begin();
     ++c;
-    forest_tree<int, fake_binary_tree<int> >::const_cursor d = c; 
+    forest<int, fake_binary_tree<int> >::const_cursor d = c; 
     BOOST_CHECK_EQUAL(*c.to_begin(), 4);
     BOOST_CHECK(++c == d.end());
     
@@ -172,9 +172,9 @@
 //{
 //    using namespace boost::tree;
 //
-//    forest_tree<int> ft(bt);
+//    forest<int> ft(bt);
 //    
-//    //validate_corresponding_forest_tree(ft);
+//    //validate_corresponding_forest(ft);
 //    
 //    std::list<int> test_list;
 //    typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
@@ -197,9 +197,9 @@
 //{
 //    using namespace boost::tree;
 //
-//    forest_tree<int> ft(bt);
+//    forest<int> ft(bt);
 //    
-//    //validate_corresponding_forest_tree(ft);
+//    //validate_corresponding_forest(ft);
 //    
 //    std::list<int> test_list;
 //    typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
@@ -218,9 +218,9 @@
 //{
 //    using namespace boost::tree;
 //
-//    forest_tree<int> ft(bt);
+//    forest<int> ft(bt);
 //    
-//    //validate_corresponding_forest_tree(ft);
+//    //validate_corresponding_forest(ft);
 //    
 //    std::list<int> test_list;
 //    typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;

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	2009-01-14 12:26:29 EST (Wed, 14 Jan 2009)
@@ -115,7 +115,7 @@
 };
 
 template <class Tree>
-void validate_corresponding_forest_tree(Tree const& t)
+void validate_corresponding_forest(Tree const& t)
 {
     typename Tree::const_cursor c = t.root().begin();
     BOOST_CHECK_EQUAL(*c, 8);