Trie Data Structure for Search Completion

[KevinTyrrell]

While talking in Discord, I would hit my Push-To-Talk keybind j while having the Aux window open. The resulting spam of jjjjjjjjjjjjjjjjjjjjjjjjjj causes Aux to continuously search for items of the name j, then jj, jjj, etc. My WoW client then freezes for ~8 seconds due to the sheer number of Aux operations being performed. However once jj is typed in, Aux should now know that there is no item named jj in the database of item names. Thus auto completion should cease. The way to implement this behavior is a Trie data structure, which is commonly used for text prediction for messaging apps, prefix+suffix searches, etc.

Each node of the Trie contains a table which associates letters -> another Trie node. Every item in the game is fed through into the Trie letter by letter. The table itself can be saved to the hard drive so that this process only needs to take place once per install.

[shirsig]

Thanks for the suggestion but with normal typing it's fast enough and this is too much work for such a corner case as holding down a key. Perhaps if I'm really bored sometime.

[KevinTyrrell]

Understandable. I must ask though:r in normal use of Aux do you ever have mini-stuttering/screen freezes while typing in the search bar? They last only ~200ms but after using it for an entire year its hard to ignore.

[shirsig]

I found a bug that was causing duplicates to be added to the autocomplete list, that's how it got so slow. The bug is fixed now but you still have to run /aux clear item cache and /run ReloadUI()

[KevinTyrrell]

Well done, appreciate the follow-up.

[KevinTyrrell]

@shirsig

Here's a video demonstration. https://streamable.com/b7uzx2

0:25 -> 1:32: Typed random characters which caused a minute long client freeze.

1:48: Item Cache clear

2:30 Ran into some weird behavior with item caching. I would have thought that searching the item would insert it into the autocomplete cache. Let me know if that is expected behavior.