From: ockham_at_[hidden]
Date: 2008-05-31 15:47:42
Author: bernhard.reiter
Date: 2008-05-31 15:47:41 EDT (Sat, 31 May 2008)
New Revision: 45986
URL: http://svn.boost.org/trac/boost/changeset/45986
Log:
Add to_parent(), to_begin() and to_end() members to cursor.
(Plus some Jamfile.v2 cleanup)
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 2 +
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp | 69 +++++++++++++++++++++++++++++++--------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 18 +++++----
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 24 ++++---------
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 3 +
sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/rank_search_binary_tree_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/red_black_tree_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/string_search_binary_tree_test.cpp | 5 +-
9 files changed, 83 insertions(+), 44 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -15,6 +15,8 @@
General:
+* Introduce to_parent() (replaces operator!() as of the proposal), to_begin() and to_end()
+ cursor members that work on "*this" cursor instead of returning a new object.
* Should const_cursor have cbegin(), cend() and cparent() members?
* Implement "flat" (sequential *order representation) trees (cf. Knuth, Fundamental Algorithms,
pp. 348--351). Those should be especially useful for automated testing of "real" (binary,
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp 2008-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -36,6 +36,9 @@
class cursor_core_access {
public:
+
+ friend class iterator_core_access;
+
template <class Facade>
static bool empty_(Facade const& f)
{
@@ -61,24 +64,26 @@
}
template <class Facade>
- static Facade left(Facade const& f)
+ static void left(Facade& f)
{
- return f.left();
+ f.left();
}
template <class Facade>
- static Facade right(Facade const& f)
+ static void right(Facade& f)
{
- return f.right();
+ f.right();
}
//only if ascending
template <class Facade>
- static Facade up(Facade const& f)
+ static void up(Facade& f)
{
- return f.up();
+ f.up();
}
-
+
+private:
+ cursor_core_access();
};
template <
@@ -126,7 +131,7 @@
typedef Size size_type;
- typedef bidirectional_traversal_tag cursor_category;
+ typedef bidirectional_traversal_tag cursor_category; //TODO
bool const empty() const
{
@@ -147,20 +152,41 @@
{
return cursor_core_access::par(this->derived());
}
-
+
+ Derived& to_begin()
+ {
+ cursor_core_access::left(this->derived());
+ return this->derived();
+ }
+
Derived begin()
{
- return cursor_core_access::left(this->derived());
+ Derived tmp(this->derived());
+ return tmp.to_begin();
}
+ Derived& to_end()
+ {
+ cursor_core_access::right(this->derived());
+ return this->derived();
+ }
+
Derived end()
{
- return cursor_core_access::right(this->derived());
+ Derived tmp(this->derived());
+ return tmp.to_end();
+ }
+
+ Derived& to_parent()
+ {
+ cursor_core_access::up(this->derived());
+ return this->derived();
}
Derived parent()
{
- return cursor_core_access::up(this->derived());
+ Derived tmp(this->derived());
+ return tmp.to_parent();
}
};
@@ -219,17 +245,32 @@
{
return iterator_adaptor_::base().parity();
}
-
+
+ Derived& to_begin()
+ {
+ return Derived(this->base_reference().to_begin());
+ }
+
Derived begin()
{
return Derived(this->base_reference().begin());
}
-
+
+ Derived& to_end()
+ {
+ return Derived(this->base_reference().to_end());
+ }
+
Derived end()
{
return Derived(this->base_reference().end());
}
+ Derived& to_parent()
+ {
+ return Derived(this->base_reference().to_parent());
+ }
+
Derived parent()
{
return Derived(this->base_reference().parent());
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-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -155,23 +155,25 @@
{
return m_pos;
}
-
-public:
- cursor left() const
+ void left()
{
- return cursor(m_node->operator[](m_pos), 0);
+ m_node = m_node->operator[](m_pos);
+ m_pos = 0;
}
- cursor right() const
+ void right()
{
- return cursor(m_node->operator[](m_pos), m_node->size()-1);
+ size_type new_pos = m_node->size()-1;
+ m_node = m_node->operator[](m_pos);
+ m_pos = new_pos;
}
// Cursor stuff
- cursor up() const
+ void up()
{
- return cursor(static_cast<base_pointer>(m_node->parent()), m_node->get_parity());
+ m_pos = m_node->get_parity();
+ m_node = static_cast<base_pointer>(m_node->parent());
}
public:
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 2008-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -20,28 +20,20 @@
test-suite tree :
[ run range_helpers_test.cpp ]
[ run binary_tree_test.cpp ]
- [ run key_search_binary_tree_test.cpp ]
- [ run rank_search_binary_tree_test.cpp ]
+# [ run key_search_binary_tree_test.cpp ]
+# [ run rank_search_binary_tree_test.cpp ]
[ run traverse_binary_tree_test.cpp ]
[ run subtree_algorithms_test.cpp ]
[ run rotate_binary_tree_test.cpp ]
- [ run string_search_binary_tree_test.cpp ]
-
+# [ run string_search_binary_tree_test.cpp ]
+# [ run flat_forest_tree_test.cpp ]
# [ run interval_search_binary_tree_test.cpp ]
-# [ compile search_ordered_vector_test.cpp ]
-
- [ run search_ordered_vector_test.cpp
-# :
-# :
-# : <library>$(BOOST_ROOT)//unit_test_framework
- ]
-
- [ run red_black_tree_test.cpp ]
- [ run treap_test.cpp ]
+# [ run search_ordered_vector_test.cpp ]
+# [ run red_black_tree_test.cpp ]
+# [ run treap_test.cpp ]
[ run forest_test.cpp ]
# [ run nary_tree_test.cpp ]
[ run multiway_tree_test.cpp ]
[ run unbalanced_binary_tree_test.cpp ]
-
-# [ run bind_return_test.cpp ]
+
;
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-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -31,6 +31,9 @@
BOOST_CHECK(!c.empty());
+ BOOST_CHECK(c1.m_node->m_parent != 0);
+ BOOST_CHECK(c1.m_node->m_parent != c1.m_node);
+ BOOST_CHECK(c1.m_node->m_parent == c.m_node);
BOOST_CHECK(c1.parent() == c);
c2 = mytree.insert(c1, 2);
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp 2008-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -188,7 +188,7 @@
int test_main(int, char* [])
{
- //test_key_search_binary_tree();
+ test_key_search_binary_tree();
return 0;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/rank_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/rank_search_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/rank_search_binary_tree_test.cpp 2008-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -58,7 +58,7 @@
int test_main(int, char* [])
{
- //test_rank_search_binary_tree();
+ test_rank_search_binary_tree();
return 0;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/red_black_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/red_black_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/red_black_tree_test.cpp 2008-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -150,6 +150,6 @@
int test_main(int, char* [])
{
- //test_red_black_tree(); //FIXME
+ test_red_black_tree();
return 0;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/string_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/string_search_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/string_search_binary_tree_test.cpp 2008-05-31 15:47:41 EDT (Sat, 31 May 2008)
@@ -79,8 +79,7 @@
int test_main(int, char* [])
{
- //FIXME
- //test_normal_string_search_binary_tree();
- //test_optimized_string_search_binary_tree();
+ test_normal_string_search_binary_tree();
+ test_optimized_string_search_binary_tree();
return 0;
}