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
