On 05/24/2010 10:39 AM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 11:21:20 -0400, Andrei Alexandrescu
<[email protected]> 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
