[Boost-commit] svn:boost r7499

From: bernhard_reiter_at_[hidden]
Date: 2007-07-21 12:24:29

Author: bernhard_reiter
Date: 2007-07-21 12:24:28 EDT (Sat, 21 Jul 2007)
New Revision: 7499
URL: http://svn.boost.org/trac/boost/changeset/7499

Log:
More TODO notes

Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO |    17 +++++++++++++++++                       
   1 files changed, 17 insertions(+), 0 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2007-07-21 12:24:28 EDT (Sat, 21 Jul 2007)
@@ -29,6 +29,23 @@
   for a really basic operation. Still, it's important to consider special cases such as
   root nodes and fields of use such as `forest_trees`; but for the latter, something similar
   as inorder_insert might come in handy.
+* Actually implement stack-based pre- and postorder iterators for forward cursors.
+* Get rid of checks for/assignments to root and shoot 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 
+  algortihms etc. more or less useless without that piece of extra information and would
+  only leave us with the iterators to store it.)
+  Alternatively (or additionally), we could implement (hierarchical) "subtree" versions
+  of linear algorithms (as in the STL) in the respective namespace, eg 
+  template <class Cur, class Op> Cur preorder::foreach(Cur subtree, Op f) { /* ... */ }
+  That would leave to the algorithm how to store information about what the root is,
+  or just not require that information by working recursively instead. (It might therefore even be
+  faster than a "linear" algorithm using the *order iterator adaptors.)
+  As for such an subtree-based algorithm approach, note that we already have an example:
+  inorder::lower_bound (and upper_bound, of course) performs binary tree search and just
+  *can't* be simulated via std::lower_bound (which just performs ordinary binary search)
+  in an equally efficient way.
 
 Proposal: