Making generalized Trie type in D

[Dmitry Olshansky]

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

-- 
Dmitry Olshansky