|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50482 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail
From: ockham_at_[hidden]
Date: 2009-01-05 06:10:44
Author: bernhard.reiter
Date: 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
New Revision: 50482
URL: http://svn.boost.org/trac/boost/changeset/50482
Log:
[De|A]scendor -> [De|A]scendingCursor
RootTracker -> RootTrackingCursor
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 7 +++++++
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 10 +++++-----
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_algorithms.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp | 22 +++++++++++-----------
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp | 24 ++++++++++++------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp | 12 ++++++------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_inorder_algorithms.hpp | 8 ++++----
sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp | 8 ++++----
sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp | 8 ++++----
sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp | 4 ++--
sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp | 18 +++++++++---------
sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp | 10 +++++-----
sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp | 10 +++++-----
14 files changed, 78 insertions(+), 71 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -14,6 +14,11 @@
[section TODO]
General:
+* preorder_insert_cursor: hopefully easy to implement...
+* Fix insert cursor to work with filling procedure as of insert_cursor_test.cpp
+* Fix insert cursor (test) to work with fake_binary_tree
+* Fix binary tree/node: empty() -> root.begin() == root.end() !
+* Check forest/binary_tree correspondence in a hard wired fashion.
* 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,
@@ -188,6 +193,8 @@
Documentation:
+* algorithms.qbk is rather pointless right now. Better use doygen for
+ an algorithm group.
* Add a rationale for binary tree cursor semantics.
* Make docs more coherent. If we're using doxygen for API documentation, don't
duplicate that information via quickbook!
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -88,8 +88,8 @@
template <class Cursor>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>))
- ((Ascendor<Cursor>)),
+ ((DescendingCursor<Cursor>))
+ ((AscendingCursor<Cursor>)),
(typename Cursor::size_type)) // return type
index(Cursor const& cur)
{
@@ -98,7 +98,7 @@
template <class BinaryCursor>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<BinaryCursor>)),
+ ((DescendingCursor<BinaryCursor>)),
(void)) // return type
to_forest_end(BinaryCursor& c)
{
@@ -110,8 +110,8 @@
template <class BinaryCursor>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<BinaryCursor>))
- ((Ascendor<BinaryCursor>)),
+ ((DescendingCursor<BinaryCursor>))
+ ((AscendingCursor<BinaryCursor>)),
(void)) // return type
to_forest_parent(BinaryCursor& c)
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_algorithms.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -36,7 +36,7 @@
template <class MultiwayCursor>
inline
BOOST_CONCEPT_REQUIRES(
- ((Ascendor<MultiwayCursor>)),
+ ((AscendingCursor<MultiwayCursor>)),
(void)) // return type
successor(ascending, MultiwayCursor& c)
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -18,26 +18,26 @@
namespace boost {
namespace tree {
-class descendor_archetype
+class descendingCursor_archetype
{
public:
typedef descending_vertical_traversal_tag vertical_traversal;
- descendor_archetype& to_begin() { return *this; }
- descendor_archetype& to_end() { return *this; }
+ descendingCursor_archetype& to_begin() { return *this; }
+ descendingCursor_archetype& to_end() { return *this; }
- descendor_archetype begin() const { return *this; }
- descendor_archetype end() const { return *this; }
+ descendingCursor_archetype begin() const { return *this; }
+ descendingCursor_archetype end() const { return *this; }
bool empty() const { return true; }
};
-class ascendor_archetype
+class ascendingCursor_archetype
{
public:
- ascendor_archetype& to_parent() { return *this; }
+ ascendingCursor_archetype& to_parent() { return *this; }
- ascendor_archetype parent() const { return *this; }
+ ascendingCursor_archetype parent() const { return *this; }
};
template <
@@ -60,7 +60,7 @@
};
-// Ideally derive from ascendor_archetype.
+// Ideally derive from ascendingCursor_archetype.
// The problem: begin() and end() return the wrong type!
// FIXME: constructors etc
template <
@@ -73,7 +73,7 @@
, HorizontalTraversal
, descending_vertical_traversal_tag>
: public iterator_archetype<Value, AccessCategory, HorizontalTraversal>
-//, public descendor_archetype
+//, public descendingCursor_archetype
{
private:
typedef cursor_archetype<Value
@@ -102,7 +102,7 @@
, HorizontalTraversal
, ascending_vertical_traversal_tag>
: public iterator_archetype<Value, AccessCategory, HorizontalTraversal>
-//, public ascendor_archetype
+//, public ascendingCursor_archetype
{
private:
typedef cursor_archetype<Value
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 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -18,17 +18,17 @@
namespace boost_concepts {
/**
- * @brief Descendor concept
+ * @brief DescendingCursor concept
* Note that the existence of begin() and end() member functions follows quite
* naturally from the existence of to_begin() and to_end(), plus
* CopyConstructibility of X, which is quite a natural requirement for
* cursors.
*/
template <class X>
-struct Descendor
+struct DescendingCursor
{
public:
- BOOST_CONCEPT_USAGE(Descendor)
+ BOOST_CONCEPT_USAGE(DescendingCursor)
{
X& rb = d.to_begin();
rb.to_begin(); // Avoid compiler warning about unused variable
@@ -50,21 +50,21 @@
/**
- * @brief Ascendor concept
+ * @brief AscendingCursor concept
* Note that the existence of a parent() member function follows quite
* naturally from the existence of to_parent(), plus
* CopyConstructibility of X, which is quite a natural requirement for
* cursors.
*
- * Ascendor is not derived from Descendor, as there is no obviuos requirement
+ * AscendingCursor is not derived from DescendingCursor, as there is no obviuos requirement
* for it, so these things are best kept separate. For a use case of an
- * Ascendor-but-not-Descendor, see eg Knuth 2.3.3, (page 353)
+ * AscendingCursor-but-not-DescendingCursor, see eg Knuth 2.3.3, (page 353)
*/
template <class X>
-struct Ascendor
+struct AscendingCursor
{
public:
- BOOST_CONCEPT_USAGE(Ascendor)
+ BOOST_CONCEPT_USAGE(AscendingCursor)
{
X& rp = a.to_parent();
rp.to_parent(); // Avoid compiler warning about unused variable
@@ -76,14 +76,14 @@
};
/**
- * @brief RootTracker concept
+ * @brief RootTrackingCursor concept
* Keeps track of a (subtree) root.
*/
template <class X>
-struct RootTracker
- : Ascendor<X>
+struct RootTrackingCursor
+ : AscendingCursor<X>
{
- BOOST_CONCEPT_USAGE(RootTracker)
+ BOOST_CONCEPT_USAGE(RootTrackingCursor)
{
bool b = r.is_root();
b = false; // Avoid compiler warning about unused variable
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -30,8 +30,8 @@
template <class Order, class Cursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>))
- ((Ascendor<Cursor>)),
+ ((DescendingCursor<Cursor>))
+ ((AscendingCursor<Cursor>)),
(Op)) // return type
for_each(Order, Cursor is, Op f, ascending_vertical_traversal_tag)
{
@@ -48,10 +48,10 @@
template <class Order, class InCursor, class OutCursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<InCursor>))
- ((Ascendor<InCursor>))
- ((Descendor<OutCursor>))
- ((Ascendor<OutCursor>)),
+ ((DescendingCursor<InCursor>))
+ ((AscendingCursor<InCursor>))
+ ((DescendingCursor<OutCursor>))
+ ((AscendingCursor<OutCursor>)),
(OutCursor)) // return type
transform (Order, InCursor is, OutCursor t, Op op
, ascending_vertical_traversal_tag)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_inorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_inorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_inorder_algorithms.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -32,7 +32,7 @@
*/
template <class MultiwayCursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<MultiwayCursor>)),
+ ((DescendingCursor<MultiwayCursor>)),
(void)) // return type
for_each_recursive(inorder, MultiwayCursor s, Op& f)
{
@@ -62,7 +62,7 @@
*/
template <class MultiwayCursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<MultiwayCursor>)),
+ ((DescendingCursor<MultiwayCursor>)),
(Op)) // return type
for_each(inorder, MultiwayCursor s, Op f, descending_vertical_traversal_tag)
{
@@ -95,8 +95,8 @@
*/
template <class InCursor, class OutCursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<InCursor>))
- ((Descendor<OutCursor>))
+ ((DescendingCursor<InCursor>))
+ ((DescendingCursor<OutCursor>))
/*((UnaryFunction<Op>))*/,
(OutCursor)) // return type
transform(inorder, InCursor s, OutCursor t, Op op, descending_vertical_traversal_tag)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -32,7 +32,7 @@
*/
template <class Cursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>)),
+ ((DescendingCursor<Cursor>)),
(void)) // return type
for_each_recursive(postorder, Cursor s, Op& f)
{
@@ -60,7 +60,7 @@
*/
template <class Cursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>)),
+ ((DescendingCursor<Cursor>)),
(Op)) // return type
for_each(postorder, Cursor s, Op f, descending_vertical_traversal_tag)
{
@@ -93,8 +93,8 @@
*/
template <class InCursor, class OutCursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<InCursor>))
- ((Descendor<OutCursor>)),
+ ((DescendingCursor<InCursor>))
+ ((DescendingCursor<OutCursor>)),
(OutCursor)) // return type
transform(postorder, InCursor s, OutCursor t, Op op, descending_vertical_traversal_tag)
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -32,7 +32,7 @@
*/
template <class Cursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>)),
+ ((DescendingCursor<Cursor>)),
(void)) // return type
for_each_recursive(preorder, Cursor s, Op& f)
{
@@ -60,7 +60,7 @@
*/
template <class Cursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>)),
+ ((DescendingCursor<Cursor>)),
(Op)) // return type
for_each(preorder, Cursor s, Op f, descending_vertical_traversal_tag)
{
@@ -95,8 +95,8 @@
*/
template <class InCursor, class OutCursor, class Op>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<InCursor>))
- ((Descendor<OutCursor>)),
+ ((DescendingCursor<InCursor>))
+ ((DescendingCursor<OutCursor>)),
(OutCursor)) // return type
transform(preorder, InCursor s, OutCursor t, Op op, descending_vertical_traversal_tag)
{
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 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -37,8 +37,8 @@
class forest_tree {
BOOST_CONCEPT_ASSERT((DefaultConstructible<T>));
-BOOST_CONCEPT_ASSERT((Descendor< typename binary_tree<T>::cursor >));
-BOOST_CONCEPT_ASSERT((Descendor< typename binary_tree<T>::const_cursor >));
+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?
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -40,8 +40,8 @@
template <class MultiwayCursor>
inline
BOOST_CONCEPT_REQUIRES(
- ((Descendor<MultiwayCursor>))
- ((RootTracker<MultiwayCursor>)),
+ ((DescendingCursor<MultiwayCursor>))
+ ((RootTrackingCursor<MultiwayCursor>)),
(void)) // return type
successor(inorder, MultiwayCursor& c)
{
@@ -62,8 +62,8 @@
template <class MultiwayCursor>
inline
BOOST_CONCEPT_REQUIRES(
- ((Descendor<MultiwayCursor>))
- ((RootTracker<MultiwayCursor>)),
+ ((DescendingCursor<MultiwayCursor>))
+ ((RootTrackingCursor<MultiwayCursor>)),
(void)) // return type
predecessor(inorder, MultiwayCursor& c)
{
@@ -87,7 +87,7 @@
*/
template <class Cursor>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>)),
+ ((DescendingCursor<Cursor>)),
(void)) // return type
to_first(inorder, Cursor& c)
{
@@ -122,7 +122,7 @@
//[ lower_bound
template <class MultiwayCursor, class T>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<MultiwayCursor>)),
+ ((DescendingCursor<MultiwayCursor>)),
(MultiwayCursor)) // return type
lower_bound(MultiwayCursor x, T const& val)
//]
@@ -150,7 +150,7 @@
//[ lower_bound_cmp
template <class MultiwayCursor, class T, class Cmp>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<MultiwayCursor>))
+ ((DescendingCursor<MultiwayCursor>))
/*((LessThanComparable<Cmp>))*/, // Problem with balanced_tree
(MultiwayCursor)) // return type
lower_bound(MultiwayCursor x, T const& val, Cmp cmp)
@@ -178,7 +178,7 @@
//[ upper_bound
template <class MultiwayCursor, class T>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<MultiwayCursor>)),
+ ((DescendingCursor<MultiwayCursor>)),
(MultiwayCursor)) // return type
upper_bound(MultiwayCursor x, T const& val)
//]
@@ -206,7 +206,7 @@
//[ upper_bound_cmp
template <class MultiwayCursor, class T, class Cmp>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<MultiwayCursor>))
+ ((DescendingCursor<MultiwayCursor>))
((LessThanComparable<Cmp>)),
(MultiwayCursor)) // return type
upper_bound(MultiwayCursor x, T const& val, Cmp cmp)
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 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -43,7 +43,7 @@
, boost::use_default
, typename Order::iterator_category
> {
-BOOST_CONCEPT_ASSERT((RootTracker<Cursor>));
+BOOST_CONCEPT_ASSERT((RootTrackingCursor<Cursor>));
private:
struct enabler {};
@@ -92,7 +92,7 @@
*/
template <class Order, class Cursor>
BOOST_CONCEPT_REQUIRES(
- ((Ascendor<Cursor>)),
+ ((AscendingCursor<Cursor>)),
(iterator< Order, root_tracking_cursor<Cursor> >)) // return type
//iterator< Order, root_tracking_cursor<Cursor> >
begin(Order, Cursor c)
@@ -110,7 +110,7 @@
*/
template <class Order, class Cursor>
BOOST_CONCEPT_REQUIRES(
- ((Ascendor<Cursor>)),
+ ((AscendingCursor<Cursor>)),
(iterator< Order, root_tracking_cursor<Cursor> >)) // return type
//iterator<Order, root_tracking_cursor<Cursor> >
end(Order, Cursor c)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -37,8 +37,8 @@
template <class Cursor>
inline
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>))
- ((RootTracker<Cursor>)),
+ ((DescendingCursor<Cursor>))
+ ((RootTrackingCursor<Cursor>)),
(void)) // return type
successor(postorder, Cursor& c)
{
@@ -71,8 +71,8 @@
template <class Cursor>
inline
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>))
- ((RootTracker<Cursor>)),
+ ((DescendingCursor<Cursor>))
+ ((RootTrackingCursor<Cursor>)),
(void)) // return type
predecessor(postorder, Cursor& c)
{
@@ -110,7 +110,7 @@
*/
template <class Cursor>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>)),
+ ((DescendingCursor<Cursor>)),
(void)) // return type
to_first(postorder, Cursor& c)
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp 2009-01-05 06:10:42 EST (Mon, 05 Jan 2009)
@@ -37,8 +37,8 @@
template <typename Cursor>
inline
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>))
- ((RootTracker<Cursor>)),
+ ((DescendingCursor<Cursor>))
+ ((RootTrackingCursor<Cursor>)),
(void)) // return type
successor(preorder, Cursor& c)
{
@@ -78,8 +78,8 @@
template <class Cursor>
inline
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>))
- ((RootTracker<Cursor>)),
+ ((DescendingCursor<Cursor>))
+ ((RootTrackingCursor<Cursor>)),
(void)) // return type
predecessor(preorder, Cursor& c)
{
@@ -113,7 +113,7 @@
*/
template <class Cursor>
BOOST_CONCEPT_REQUIRES(
- ((Descendor<Cursor>)),
+ ((DescendingCursor<Cursor>)),
(void)) // return type
to_first(preorder, Cursor& c)
{
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk