Links

ternary_tree by rasmus ekman, see http://abc.se/~re/code/tst
Download: http://abc.se/~re/code/tst/ternary_tree.zip

Some other TST implementations.

• DDJ code: Original C implementation by Jon Bentley and Robert Sedgewick. Article in Dr Dobb's Journal, 1998 #4: http://www.ddj.com/documents/s=921/ddj9804a/9804a.htm
  See http://www.cs.princeton.edu/~rs/strings/ for C code and article on TST complexity.
• libtst: Worked-out version of DDJ code by Peter A. Friend 2002. Version 1.3.
  See http://www.octavian.org/cs/software.html
  
• Boost.Spirit version: C++ reimplementation by Joel de Guzman.
  See http://spirit.sourceforge.net/ internal file ./boost/spirit/symbols/impl/tst.h
• Hartmut Kaiser version: C++ reimplementation intended for generalization of tst. Currently abandoned, available in Spirit CVS. (interesting for interface design)
  See http://lists.boost.org/Archives/boost/2005/09/93316.php
  and http://article.gmane.org/gmane.comp.parsers.spirit.general/6959
• pytst: C++ version by Nicolas Lehuen, with SWIG wrappers for use from other languages. Version 0.97.
  See http://nicolas.lehuen.com/download/pytst/ (not yet tested)

Feature chart

All versions have insert and plain search, other features available as tabled below:

Feature	Associative type	Prefix match	Longest match	Partial match	Hamming search	Iterators	Status
DDJ	raw char* can be assigned	no	no	yes	yes	no (but tree printf dump function traverse() can easily be adapted)	Incomplete (singleton root)
libtst	raw char*	no	no	no	no	no	Worked-out version of DDJ, but no searches
Boost.Spirit	any type stored as managed ptr	yes?	no	no	no	no	Used only for parser name tables
Kaiser	Any type ptr, deleted on key destroy	yes	yes	no?	no?	forward	Interesting design, but development discontinued "for performance reasons"
pytst	Any type, copied	yes	yes	yes	no	forward traversal calling back a "filter" functor	Under active development. Has SWIG wrappers.
ekman	Any type, copied	yes	yes	yes	yes	Bidirectional	Under development, test suite available

Our ternary_tree class adds combinatorial search and levenshtein_search. This could probably also be done using pytst, since any behaviour can be implemented by the traversal filter callback.