trie
trie copied to clipboard
Implement #size and #length for Trie and TrieNode
I would like to be able to count how many keys are in a trie, or how many are under a certain TrieNode. That is, Trie and TrieNode should implement the #size method and its alias #length. Their meanings should be the same as those methods in Hash.
Without this functionality, I cannot use this library to implement the word game GHOST, where I try to estimate how good certain moves are by counting how many words start with a certain prefix.
You can implement this by storing an integer in every node including the root. It is initialized to 0, incremented by #add, and decremented by #delete. The methods on Trie would just return the size of the #root node.
Adding the bookkeeping of key-counting will probably make the library slightly slower. If this is a big problem, you can provide two trie classes with your library: a SimpleTrie and a Trie, where a Trie provides more methods, but is slightly slower.
I like the idea. If it's useful to you, please open a PR with the necessary patches. :)