Faster data structure for autocomplete (Radix Tree)

[ricardojlrufino]

Hello,

I have a tip that can be interesting, would be to use a more appropriate data structure for autocomplete.

https://code.google.com/p/concurrent-trees/

Maven repo http://mvnrepository.com/artifact/com.googlecode.concurrent-trees/concurrent-trees/1.0.0

Comparisons http://sujitpal.blogspot.com.br/2007/02/three-autocomplete-implementations.html

[ricardojlrufino]

Another

https://github.com/vivekn/autocomplete

[tttwang23]

Hmm, but the completions array in AbstractCompletionProvider was declared with "protected" visibility. You can't switch out the implementation because some client code may already have a dependency on its data type.

Right now the insertion cost is n * n * log(n), which is not that good. There should be a way to reduce it to n * log(n) without changing the data type.