Making generalized Trie type in D

[Roman D. Boiko]

On Monday, 4 June 2012 at 15:35:31 UTC, Dmitry Olshansky wrote:
> On 04.06.2012 18:19, Andrei Alexandrescu wrote:
>> On 6/4/12 4:46 AM, Dmitry Olshansky wrote:
>>> Cross-posting from my GSOC list as I think we had a lack of D 
>>> rox posts
>>> lately :)
>> [snip]
>>
>> I think it would be great if you converted this post into an 
>> article.
>>
>> Andrei
>>
>
> Sounds good, will do once I fix few issues that were mentioned 
> (bit-packing, GC types etc.)

Would be interesting to see some more examples, along with 
rationale/motivation for various aspects of your API, and 
possible usage scenarios.

Tries are fundamental (both data structures and respective 
algorithms) for lookup problems, in the same way as arrays are 
fundamental for indexed access.

For example, they have several advantages over hash tables. Hash 
calculation requires const * key.length operations, which is 
equivalent to the number of comparisons needed for trie lookup. 
But hash tables may be less space efficient, or lead to hash 
collisions which increase lookup time. Also, it is possible to 
create persistent (immutable) tries with efficient (log N) 
inserting / deleting (this scenario is very important for my DCT 
project). Immutable hash tables would require 0(N) copying for 
each insert / delete.

It is difficult to create a good API for fundamental data 
structures, because various use cases would motivate different 
trade-offs. The same is true for implementation. This is why I 
like your decision to introduce policies for configuration. 
Rationale and use cases should help to analyze design of your API 
and implementation, thus you will get better community feedback :)

Below are some notes related to my DCT use cases.

Your examples deal with lookup by the whole word (first/last 
characters and length are needed). Are your API and 
implementation adaptable for character-by-character trie lookup?

Will compile-time generation of lookup code based on tries be 
supported? Example which is currently in DCT (first implemented 
by Brian Schott in his Dscanner project) uses switch statements 
(which means lookup linear in number of possible characters at 
each position). A trivial improvement might be using if 
statements and binary lookup. (E.g., if there are 26 possible 
characters used at some position, use only 5 comparisons, not 26).

I wanted to analyse your regex implementation, but that's not an 
easy task and requires a lot of effort... It looks like the most 
promising alternative to binary trie lookup which I described in 
previous paragraph. Similarities and differences with your regex 
design might also help us understand tries better.