Ternary Search Trees

[bearophile]

Robert Fraser:
> 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!

It's just a translation to D of this Py code:
Info:
http://jeethurao.com/blog/?p=146
Code:
http://bitbucket.org/woadwarrior/trie/

Where necessary you can also follow the ideas from the original article here (but using an enum is MUCH better and it's also safer in C, to avoid aliasing):
http://www.ddj.com/windows/184410528

My implementation is about 57 times faster than the Python version and much faster than the Psyco version too.

You can also take a look here:
http://sourceforge.net/projects/ternary/

You can implement it with a _single_ template struct, filled with all the methods you want:

struct TST(T) {
    TST* left, right; 
    union {
      TST* mid;
      int index;
    }
    T item;

    // methods here
}

Note that inside there you don't need TST!(T)*, TST* is probably enough, but I don't know why yet.

You can start with only the few basic methods, test them, and later when/if you want you can add more methods, taking ideas from here:
http://abc.se/~re/code/tst/tst_docs/index.html

I'd like to not show my code because it's not nice, it has no comments, tests, etc. But it's quite close to that Py code.

A problem with that template struct is that even if you add a opIn_r() method as I have done, then you have to do (note the star):
if (!(k in *ds))

I don't know if in D2 for structs you can use the syntax you use with classes:
if (!(k in ds))

Even better syntax is:
if (k !in ds)

In Python you write something better still:
if k not in ds:

Bye,
bearophile