[spirit] Ternary Search Tree (TST) revisited

Hi!

As many of you might not know, there's a nice TST(*)
implementation in the Spirit CVS written by Steve Rowe
based on the one you see used by Spirit's symbol table. The
code has methods for iteration (begin/end), insert, erase,
find, find_longest and find_all_sub_matches. There's also a
full test suite.

I would want to use it as the basis for Spirit-2's symbol
table. The objective is to optimize the code and do some
benchmarks with it. The last time I heard from Steve Rowe,
he said that the code is not (yet) optimal. I was wondering
if anyone would be interested to adopt the code, bring it
up to date, and carry on with its development? I'm sure it
would be a good candidate for a Boost Library.

(*)
Ternary Search Tree implementation. The data structure is faster than
hashing for many typical search problems especially when the search
interface is iterator based. Searching for a string of length k in a
ternary search tree with n strings will require at most O(log n+k)
character comparisons. TSTs are many times faster than hash tables
for unsuccessful searches since mismatches are discovered earlier
after examining only a few characters. Hash tables always examine an
entire key when searching.

The code is in the Spirit CVS in the GENERALIZE_TST branch.
Please email me if you are interested.

Regards,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642