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

From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2007-09-08 13:18:09

AMDG

Ion Gazta?aga <igaztanaga_at_[hidden]> wrote:

> 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
>
>   

warning untested:

node* current = root;
node* new_root = 0;
node* insertion_point = 0;
insertion_point = new_root = copy_node(*current); // sets the links to zero
try {
while(true) {
if(current->left != 0 && insertion_point->left == 0) {
current = current->left;
node* temp = insertion_point;
insertion_point = copy_node(*current);
insert_at_left(temp, insertion_point);
} else if(current->right != 0 && insertion_point->right == 0) {
current = current->right;
node* temp = insertion_point;
insertion_point = copy_node(*current);
insert_at_right(temp, insertion_point);
} else {
if(current == root) break;
current = current->parent;
insertion_point = insertion_point->parent;
}
}
} catch(...) {
destroy_tree(new_root);
throw;
}

In Christ,
Steven Watanabe