On Mon, 24 May 2010 11:51:39 -0400, Andrei Alexandrescu
<[email protected]> wrote:
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.
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
