On 2011/05/01 01:19, Levente Uzonyi wrote:
> 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?

Ah, that might be exactly the hammer I'm looking for. Thanks!

I don't want to add the balancing protocol to ZTree because then I'm 
allowing the mutation of a ZTree, which means that clients of ZTree 
can't assume that it's immutable.

Well. To be picky, ZTree _does_ have the balancing protocol, in the 
sense that it responds to #balance. The implementation of #balance, 
however, makes a MutableZTree copy, balances that, and returns an 
immutable version of the newly balanced tree. ZTree just doesn't permit 
the necessary mutating like setting a subtree and the like. ("Necessary" 
because the DSW algorithm makes extensive use of mutation.)

frank