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: