Making generalized Trie type in D

[Roman D. Boiko]

On Tuesday, 5 June 2012 at 12:57:10 UTC, Dmitry Olshansky wrote:
> On 05.06.2012 9:33, Roman D. Boiko wrote:
>> On Tuesday, 5 June 2012 at 05:28:48 UTC, Roman D. Boiko wrote:
>>> ... without deep analysis I can't come up with a good API / 
>>> design for
>>> that (without overcomplicating it). Probably keeping mutable 
>>> and
>>> immutable APIs separate is the best choice. Will return to 
>>> this
>>> problem once I get a bit of free time.
>> Simplest and possibly the best approach is to provide an 
>> immutable
>> wrapper over mutable implementation, but that may be difficult 
>> to make
>> efficient given the need to support insert / delete as common 
>> operations.
>>
>
> I suspect I would have to add another policy like Persistent 
> that will preallocate some slack space implicitly so that some 
> pages can be shallowly copied on each assign(a-la COW) and 
> immutable parts still reused.
> Another simpler way would be to use an separate field 
> "pointer-to-actual base" for each level, thus allowing it to 
> redirect it away to new (modified) copy. Still looks like 
> policy as it _maybe_  slightly slower.
>
> Anyway as a start this should work:
>
> auto modifyDupGlobalImmutableTrie(Trie(immutable(T), ...) t
> 	, scope delegate(Trie(immutable(T), ...) )pure dg) __pure__
> {
> 	auto copy = t.dup;//this would be one day a shallow copy
> 	with(copy)
> 	{	
> 		dg(copy);
> 	}
> 	return copy;
> }
>
> //later on
> {
> ...
> immutable newTrie = modifyDupGlobalImmutableTrie(yourTrie);
> ...
> }

Yes,something like that should work. I finished support request 
and will investigate this and your std.uni. maybe it is better to 
avoid immutability... or do bulk ins /del before  copy.