dcollections 1.0 and 2.0a beta released

[Steven Schveighoffer]

On Mon, 24 May 2010 11:51:39 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> 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.

I wasn't thinking of that, I was thinking the key point of tries being  
more efficient at lookup for strings of things.

One solution is that Trie could be a separate interface (i.e. a sibling of  
Map).

One thing to point out is that D's arrays are adept at appending and  
prefixing.  A K[] key would not necessarily be reallocating for each node  
traversal, but it certainly would be copying data.

How would you define a way to get all the keys of a Trie?  Or would you  
simply leave that function off?  Is it unreasonable to expect to be able  
to iterate the keys in a trie?  (I don't really know, I've never worked  
with them)

-Steve