Ternary Search Trees

[Daniel Keep]

Andrei Alexandrescu wrote:
> Robert Fraser wrote:
>> bearophile wrote:
>>> Does someone has some need for Ternary Search Trees into Phobos (for
>>> D1. And eventually later for D2 too)?
>>> TSTs allow to find keys, key prefixes, or even keys with holes. Keys
>>> are arrays of T, where T is the template type.
>>> They can be designed to store the keys alone, or as an associative
>>> data structure.
>>>
>>> With some benchmarks I have seen that a simple TST implementation is
>>> about as fast as the built-in AAs of D (but much slower than Python
>>> dicts).
>>>
>>> Bye,
>>> bearophile
>>
>> Hey, could you please post your implementation (assuming it's
>> open-source?) I'd love to use them, but can't be bothered to implement
>> it. Thanks!
> 
> BTW, anyone got a KD-tree implementation? I could use one.
> 
> Andrei

A random idea occurs: it might be interesting to put up a page somewhere
of "things we'd like in the standard library."  Provide details on a
rough API, functionality and license.  Might get some people bored on a
weekend dropping in code for the standard library.  :)

  -- Daniel