On Sat, 30 Apr 2011, Frank Shearar wrote:

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

You're looking for Behavior >> #adoptInstance:, but why would you bother 
with changing the class instead of adding the balancing protocol to ZTree?


Levente

>
> frank
>
>