Support for substring search

[jacobdufault]

Great project! I'd like to use it in cquery for faster global symbol search; is it possible to add substring search, ie, the search Foo matches the string void Foo()? equal_prefix_range comes close but will not match because of the preceding void.

(Even better would be a fuzzy search, ie, vF matches void Foo(), or a custom match function, but I suspect that's out of scope).

[Tessil]

It would be difficult, the HAT-trie is designed to be a prefix tree. What you need is a suffix tree or suffix array.

You could easily use the HAT-trie if you only want to know if a substring is in the tree. For example, instead of just inserting "foobar" in the tree, you would also add "oobar", "obar", "bar", "ar" and "a". Then you could do equal_prefix_range("oo") and if the range is not empty you know there is a string with "oo" inside the tree (but not which original one, the range would return "oobar"). It could be possible to keep track of the list of strings the suffix belongs too, but I think it's more efficient to go with a suffix array instead.

Concerning the fuzzy-search you may look into metric trees.