dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

On 05/24/2010 10:39 AM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 11:21:20 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> On 05/24/2010 06:54 AM, Steven Schveighoffer wrote:
>>> I am not familiar with tries,
>>
>> Missed that upon the first read. I suggest you look at tries and the
>> following other structures as good examples that it's futile to fit
>> collections into hierarchies.
>>
>> http://en.wikipedia.org/wiki/Trie
>> http://linux.thai.net/~thep/datrie/datrie.html
>> http://en.wikipedia.org/wiki/Suffix_tree
>> http://en.wikipedia.org/wiki/Kd-tree
>>
>> We'd want to implement in time those and many more in Phobos without
>> worrying that some of their primitives won't fit the existing
>> interfaces, and also without the unjustified effort of formalizing
>> interfaces for each of them in thinking that another very, very
>> similar container will come along.
>>
>
>  From a cursory look, I don't see why tries would not be possible in
> dcollections.
>
> I'd probably start with something like this:
>
> class TrieMap(K, V) : Map!(K[], V)
>
> The array brackets enforce the ability to use prefixes on the keys.

The key point of tries is that they have distributed storage. Thus, 
shoehorning them into the interface function

Iterator!(K[]) keys();

forces allocation and copying.


Andrei