Trie with add, remove, prefix counts, and sorted matches
A command palette suggests commands as the user types. With every keystroke it needs to know how many commands start with the text so far (to show “12 matches”), and it needs the first few matches in alphabetical order. Commands are also added and removed as plugins load and unload. A trie (prefix tree) answers all of these in time proportional to the length of the typed text, not the number of stored words.
Implement a class PrefixIndex that stores a set of unique words.
const index = new PrefixIndex();
index.add(word) // => true if added, false if already stored
index.has(word) // => true if word itself is stored
index.hasPrefix(prefix) // => true if any stored word starts with prefix
index.countPrefix(prefix) // => number of stored words that start with prefix
index.delete(word) // => true if removed, false if it was not stored
index.complete(prefix, limit?) // => stored words that start with prefix, sorted
'Open' and 'open' are different words.countPrefix('cart') counts 'cart'. Every word starts with the empty prefix '', so countPrefix('') is the number of stored words.has only matches whole words: after add('cart'), has('car') is false but hasPrefix('car') is true.delete only removes the exact word. Words that share its prefix, or that it is a prefix of, stay stored.complete(prefix, limit) returns a new array of the matching words sorted in code unit order (the order of the default Array.prototype.sort), with at most limit words. limit defaults to Infinity; a limit of 0 returns [].countPrefix and hasPrefix should take time proportional to the prefix length, not the number of stored words.const index = new PrefixIndex();
index.add('car'); // => true
index.add('cart'); // => true
index.add('carton'); // => true
index.add('cat'); // => true
index.add('car'); // => false (already stored)
index.has('ca'); // => false
index.hasPrefix('ca'); // => true
index.countPrefix('car'); // => 3 (car, cart, carton)
index.complete('ca', 2); // => ['car', 'cart']
index.delete('cart'); // => true
index.has('carton'); // => true
index.countPrefix('cart'); // => 1
index.delete('ca'); // => false (not a stored word)