Does D have "structural sharing" of immutable collections?

[Craig Dillabaugh]

On Wednesday, 23 May 2012 at 22:39:33 UTC, Roman D. Boiko wrote:
> On Wednesday, 23 May 2012 at 22:25:35 UTC, Steven Schveighoffer 
> wrote:
>> I looked up how it could be done, the one thing I was not sure 
>> of was the parent node.  If you can have multiple references 
>> to the same subtree, how do you keep track of the parents.  
>> But if you only are concerned about the ancestry of a single 
>> node, you can dynamically determine the line in O(lgn) time, 
>> and use that for the running of the redblack algorithm.
>>
>> I'm not sure how efficient it would be.
>>
>> -Steve
>
> My problem is the following:
>
> n elements in some given order, each has an associated value; I 
> need to retrieve elements for which the sum of values 
> associated with previous elements lies in a given ragne; this 
> should work efficiently when elements are added or removed, and 
> history should be preserved.
>
> Storing elements as tree leafs and sums of children values in 
> other nodes gives me this easily.
>
> Lookup price is 0(log N) number comparisons, which should be 
> very fast. Insert / delete / rotate are also logarithmic, but I 
> don't know the constant factors.
>
> No need to retrieve parents.
>
> So far it seems like RBT is perfect for me (if cache friendly 
> implementation will be possible. Hopefully it will, because 
> nodes are small and I can preallocate memory for them).

I am not sure if I entirely understand your problem, but would a
persistent search tree work? See:

http://www.sciencedirect.com/science/article/pii/0022000089900342

I have a small write up on them from a course I took years ago:

http://cg.scs.carleton.ca/~cdillaba/comp5008/sarnak.html

Regards,
Craig

  -Steve