From: ockham_at_[hidden]
Date: 2008-07-05 12:34:40
Author: bernhard.reiter
Date: 2008-07-05 12:34:40 EDT (Sat, 05 Jul 2008)
New Revision: 47113
URL: http://svn.boost.org/trac/boost/changeset/47113
Log:
TODO notes, mostly regarding a possible solution to the the subtree root problem.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 49 +++++++++++++++++++++++++++------------
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 27 +++++++++++++++++++++
2 files changed, 60 insertions(+), 16 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-07-05 12:34:40 EDT (Sat, 05 Jul 2008)
@@ -15,6 +15,33 @@
General:
+* 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 ===
+ 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.)
+ (Earlier thoughts:)
+ 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. (Which, in turn, would make the free-standing forward/back/next/prior
+ algorithms etc. more or less useless without that piece of extra information and would
+ only leave us with the iterators to store it.)
+ -> This is going to be done by the RootTracker object, which I personally hate,
+ but I don't see much of a choice for iterative traversal of subtrees other than that
+ (and haven't found any on the Web, either).
+ Our options, in more detail:
+ * Saving a copy of root, obviously. (Only comparison, no later calculation of depth involved)
+ * Iterators based on ascending cursor shouldn't check for size==1, but for size==root_size,
+ where root_size is the size of the stack with all cursors up to the root cursor
+ are pushed. (Comparison, no calculation)
+ * Some color map approach? (Cf BGL, Knuth?)
* 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)?
@@ -25,6 +52,13 @@
* Use the example trees form Knuth as test example data.
* Write (internal/external?) adaptors for other tree libraries, as Kaspar Peeters' or
Adobe's.
+ * External: what would we need? next()/prior(), plus to_begin()/to_end()/to_parent(),
+ deref, ...?
+ * Compare to BGL: Is it possible to modify adapted graphs using graph semantics?
+ If not, adaptation within the BGL would only map inspecting (read-only) functions.
+ (Compare this again to container vs sequence; also look into graph concepts.)
+ Finally, mind the implications for internal/external adaptation; they might be
+ generalised, if the above assumption is true.
* Revisit binary_tree. Can it be usable for both balanced and forest trees and still be
"light-weight" at the same time?
* Re-organize traversal tests:
@@ -45,21 +79,6 @@
* Make *order iterators work with empty subtrees; same for cursor algorithms.
(Not necessarily! If that means a check for empty(), it's better to leave it to
the user!)
-* 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. (Which, in turn, would make the free-standing forward/back/next/prior
- algorithms etc. more or less useless without that piece of extra information and would
- only leave us with the iterators to store it.)
- -> This is going to be done by the RootTracker object, which I personally hate,
- but I don't see much of a choice for iterative traversal of subtrees other than that
- (and haven't found any on the Web, either).
- Our options, in more detail:
- * Saving a copy of root, obviously. (Only comparison, no later calculation of depth involved)
- * Iterators based on ascending cursor shouldn't check for size==1, but for size==root_size,
- where root_size is the size of the stack with all cursors up to the root cursor
- are pushed. (Comparison, no calculation)
- * Some color map approach? (Cf BGL, Knuth?)
* Investigate the lower_bound for search vs insert purposes problem.
* Take care of inorder::begin() for binary_tree<int>.
* Keep in mind it's not necessarily a good thing to have *order::end() be the last element's
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp 2008-07-05 12:34:40 EDT (Sat, 05 Jul 2008)
@@ -15,6 +15,7 @@
#include <boost/tree/cursor.hpp>
#include <boost/tree/cursor_facade.hpp>
+#include <boost/tree/detail/iterator/ascending.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
@@ -28,6 +29,14 @@
namespace tree {
template <class DescendingCursor>
+class ascending_cursor;
+
+template <class Cursor>
+typename ascending::iterator< ascending_cursor<Cursor> >::difference_type
+distance(ascending::iterator< ascending_cursor<Cursor> > iter1
+ , ascending::iterator< ascending_cursor<Cursor> > iter2);
+
+template <class DescendingCursor>
class ascending_cursor
: public cursor_facade<ascending_cursor<DescendingCursor>
, typename cursor_value<DescendingCursor>::type
@@ -36,7 +45,7 @@
> {
private:
struct enabler {};
-
+ typedef ascending_cursor<DescendingCursor> self_type;
public:
typedef typename DescendingCursor::value_type value_type;
@@ -97,6 +106,12 @@
friend class boost::iterator_core_access;
friend class boost::tree::cursor_core_access;
+// friend
+// typename ascending::iterator<self_type>::difference_type
+// boost::tree::distance<>(
+// boost::tree::ascending::iterator<self_type>
+// , boost::tree::ascending::iterator<self_type>);
+
std::stack<DescendingCursor> m_s; // pimpl?
value_type& dereference() const
@@ -180,6 +195,16 @@
return ascending_cursor<Cursor>(c);
}
+/// Specialization
+template <class Cursor>
+typename ascending::iterator< ascending_cursor<Cursor> >::difference_type
+distance(ascending::iterator< ascending_cursor<Cursor> > iter1
+ , ascending::iterator< ascending_cursor<Cursor> > iter2)
+{
+ return ascending_cursor<Cursor>(iter2).m_s.size()
+ - ascending_cursor<Cursor>(iter1).m_s.size();
+}
+
} // namespace tree
} // namespace boost