The method intersect in RedBlackTree? actually performs a set difference operation rather than a set intersection.
It should be renamed. And adding an actual intersect routine would be nice too.
http://www.dsource.org/projects/arclib/browser/trunk/arclib/arc/templates/redblacktree.d
Here's an example not-optimal, but simple way to implement intersection:
/// remove elements from this tree that aren't in other tree
void intersect(RedBlackTree tree)
{
intersectContents(this.root, tree);
}
// Remove all the keys in leafSrc not in treeCompare one-by-one
void intersectContents(Node leafSrc, RedBlackTree treeCompare)
{
if (leafSrc !is null)
{
intersectContents(leafSrc.link[LEFT], treeCompare);
if (!treeCompare.search(leafSrc.key)) remove(leafSrc.key);
intersectContents(leafSrc.link[RIGHT], treeCompare);
}
}
It might be worth considering adopting some convention to distinguish between methods that mutate the tree in place, and those that create a new tree.
For instance in Python sets have intersect and intersect_update methods. The former creates a new tree, the latter mutates in place. Or you could use the D op*** convention, like: intersect / intersectAssign
