From: ockham_at_[hidden]
Date: 2008-08-03 05:33:18
Author: bernhard.reiter
Date: 2008-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
New Revision: 47955
URL: http://svn.boost.org/trac/boost/changeset/47955
Log:
Cleanup of is_root() logic largely finished.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 30 ++++++++++++++++--------------
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 38 ++++++++++++++++++++++++++++++++++++--
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 3 +--
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 7 ++-----
sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html | 2 +-
5 files changed, 56 insertions(+), 24 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -15,22 +15,10 @@
General:
+* Revisit binary_tree (inorder::)iterator functions
* Possibly sort out some more concepts, like trees with "downwards" or "upwards" insertion
(insert()/insert_above()), trees with values only at the leaves (makes sense in combination
with "upwards" insertion"), etc.
-* === The is_root problem() and its solution ===
- Get rid of checks for/assignments to root in pre/post/inorder algorithms,
- as they are otherwise limited to "whole" trees and cannot be applied to subtrees.
- In order to work for subtrees, it's probable that we need at least an int to store
- the current depth.
- Solution:
- Introduce a root tracking cursor concept providing c.is_root(). *order::forward(), back(),
- next() and prior() functions as well as *order::iterators then require this concept.
- Write a root_tracking_cursor adaptor that does exactly that, with suitable specializations
- for different underlying cursors.
- (Why? Because any root_tracker object would have to be
- passed along with a cursor, plus in- or decremented when going down or up in the hierarchy,
- resp. This kind of naturally suggests some kind of encapsulation/adaptation.)
* Do we want/need an O(1) inorder_begin() for binary_tree?
Does Gnu's rb_tree (used in std::map) have one?
* Is it really a good idea to use InCursor::size_type for size(Cursor)?
@@ -110,7 +98,8 @@
(and output_cursor_iterator_wrapper?) proposal.
* Add a revision log:
* Add to_parent() (replaces operator!()), to_begin() and to_end() descending cursor members.
- * Remove shoot(), size()
+ * Remove shoot(), size() (rationale for size(): see std::list::size() O(n) vs O(1) discussion,
+ esp the Howard Hinnant comments, http://home.twcny.rr.com/hinnant/cpp_extensions/On_list_size.html )
* Change some occurences of "vector" (oops) to the respective tree type.
* Add (subtree) cursor algorithms.
* Probably split up cursor categories into: cursor (value access) category, vertical traversal
@@ -148,6 +137,19 @@
depict what is introduced at what step (nodes with pointers to their siblings, children, parents,
a frame around a given cursor [and possibly additionally required information stated]
that signifies what amount of information is contained within that cursor.
+* Add some rationale about the is_root problem() and its solution:
+ Get rid of checks for/assignments to root in pre/post/inorder algorithms,
+ as they are otherwise limited to "whole" trees and cannot be applied to subtrees.
+ In order to work for subtrees, we need at least an int to store
+ the current depth.
+ Solution:
+ Introduce a root tracking cursor concept providing c.is_root(). *order::forward(), back(),
+ next() and prior() functions as well as *order::iterators then require this concept.
+ Write a root_tracking_cursor adaptor that does exactly that, with suitable specializations
+ for different underlying cursors.
+ (Why? Because any root_tracker object would have to be
+ passed along with a cursor, plus in- or decremented when going down or up in the hierarchy,
+ resp. This kind of naturally suggests some kind of encapsulation/adaptation.)
Further applications:
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp 2008-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -40,6 +40,8 @@
struct empty_class { };
+// TODO: Remove Meta2. This stuff must be done via some MPL magic.
+
template <class Val, class Meta, class Meta2 = empty_class>
struct augmented_type {
typedef Val value_type;
@@ -77,6 +79,38 @@
typedef typename augmented_type<Val,Meta,Meta2>::metadata_type type;
};
+template <class Cursor>
+class is_on_top_cursor
+: public Cursor {
+public:
+ is_on_top_cursor()
+ : Cursor() {}
+
+ is_on_top_cursor(Cursor p)
+ : Cursor(p) {}
+
+ bool is_root() const
+ {
+ return this->is_on_top();
+ }
+};
+
+template <class Cursor>
+class balanced_tree_iterator
+: public inorder::iterator< is_on_top_cursor<Cursor> > {
+public:
+ balanced_tree_iterator()
+ : inorder::iterator< is_on_top_cursor<Cursor> >() {}
+
+ explicit balanced_tree_iterator(Cursor p)
+ : inorder::iterator< is_on_top_cursor<Cursor> >(p) {}
+
+ operator Cursor()
+ {
+ return Cursor(this->base());
+ }
+};
+
/**
* @brief A %balanced_tree.
* This class models the hierarchy concept, the container concept and the
@@ -105,8 +139,8 @@
typedef typename hierarchy_type::const_cursor const_cursor;
public:
- typedef augmented_iterator<inorder::iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
- typedef augmented_iterator<inorder::iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
+ typedef augmented_iterator<balanced_tree_iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
+ typedef augmented_iterator<balanced_tree_iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
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-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -566,8 +566,7 @@
inline bool operator==(binary_tree<Tp, Alloc> const& x
, binary_tree<Tp, Alloc> const& y)
{
- return (size(x.root()) == size(y.root())
- && equal(x.root(), y.root()));
+ return (size(x.root()) == size(y.root()) && equal(x.root(), y.root()));
}
/// Based on operator==
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-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -59,8 +59,6 @@
public:
- //friend class inorder::iterator< nary_tree_cursor<Node> >;
-
typedef typename mpl::eval_if<
is_const<Node>
, add_const<typename Node::value_type>
@@ -181,9 +179,8 @@
m_node = static_cast<base_pointer>(m_node->parent());
}
-public:
- // TODO This isn't really a permanently public thing.
- bool is_root() const
+protected:
+ bool is_on_top() const
{
base_pointer parent_begin_node =
static_cast<base_pointer>(m_node->parent())
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html 2008-08-03 05:33:17 EDT (Sun, 03 Aug 2008)
@@ -2512,7 +2512,7 @@
<i>// capacity:</i>
bool empty() const { return h.empty(); }
- size_type size() const { return h.size(); }
+ size_type size() const;
size_type max_size() const;
void resize(size_type sz, T c = T());