Hi,
I've been playing around with immutable data structures (at least, as
immutable as one gets).
I came across an interesting algorithm for rebalancing a binary tree,
invented by Day, Stout and Warren. It's an in-place pointer-swizzler
that, with constant additional space, rebalances a tree in linear time.
Of course, it operates on a mutable structure.
So I had an idea: I could "ringfence" the mutation: from my immutable
structure, create a mutable copy, tear it to bits and then recreate a
new, immutable, balanced, tree.
So I wrote, in addition to my ZTree node class, a MutableZTree subclass.
It has the same shape as its parent (no new instvars), and a bunch of
extra mutating methods.
There are some costs involved in this, of course: I create two entire
copies of the tree. One, making the mutable copy, seems unavoidable: you
cannot simply un-immutable the tree, because you have no idea what other
objects might have a reference to parts of the tree, and they all assume
the tree's immutable. The other, however... well, we don't care about
references to the mutable structure because there should be no
references to it. It's purely an internal, interim structure.
So I thought, well, wouldn't it be nice if one could _change the class_
of the MutableZTrees so they all magically turn into nice immutable ZTrees.
I'm sure there's some trickery one could do, but quite what that
trickery would be, I'm not sure. Any ideas? (Or, just as importantly,
good reasons why the above is completely insane?) It would be nice to
turn the O(3n) space requirement into O(2n)...
frank