In the project algorithm, we moved the loop that handles the projecting of the children of the current node because the existence of an n-dimensional link would cause the children to be moved to a point lower in the tree, and handled again later on in the tree. This was creating an inifinte loop. The modification is emphasized below. Now we only recur on the children if there is no n-dimensional link to be handled. If there is, we do not recur because we will return to these children later in the process and eventually deal with them.
project(tree) {
if(tree == empty) {
return tree;
}
moved
if(tree has an nd link) {
if(tree has (n-1)-dimensional link)
find_foot(tree.link(n)).link(n-1)=tree.link(n-1)
for i from n-2 to 1
tree.link(n).link(i) = tree.link(i)
tmp = project(tree.link(n))
set all tree links to NULL
delete tree
tmp.set_dim(n-1)
return tmp
}
else
for i from 1 to n-1
tree.link(i) = project(tree.link(i))
tree.set_dim(n-1)
return tree
}
Posted by kernco at July 21, 2004 04:40 PM