bearophile Wrote: > 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
Why use a struct for TST? it requires you to use pointers everywhere and passing by value hardly makes any sense. A class (optionally with final methods for speed) would work a lot better. It even fixes your issue with opIn
