[boost] [intrusive] Looking for a non-recursive structural tree cloning algorithm

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2007-09-08 04:44:01

Dear tree expert,

As you might know, Boost.Intrusive implements an intrusive red-black 
tree and also a class offering red-black tree algorithms. Those 
algorithms were taken from the SGI STL code and optimized a bit.

One of the goals of Boost.Intrusive is avoiding recursive calls to make 
those algorithms suitable for very big trees and/or embedded systems. 
The SGI STL uses two recursive algoritms:

* Recursive destruction with no rebalancing
* Recursive structural copy (which needs a erasing function in case a 
copy throws an exception).

All STL implementations I'm aware of use recursive cloning and 
destruction. Boost.Intrusive changed the recursive tree destruction 
algorithm to a non-recursive one thanks to a step by step tree 
destruction function (unlink_leftmost_without_rebalance) that is also 
very useful to implement advanced tree cloning functions that might 
reuse old allocated nodes. However, I haven't found a non-recursive 
structural copy algorithm anywhere.

So if you are a tree expert, I need your help to get a tree cloning 
function, that:

*  Does not use the comparison predicate or calls any function that uses 
it (e.g.: insert())

* Can destroy all constructed nodes in a non-recursive form if 
node-copying throws an exception.

* It's pretty efficient ;-)

Willing to help?

Ion