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);