trie icon indicating copy to clipboard operation
trie copied to clipboard

Implement #size and #length for Trie and TrieNode

Open roryokane opened this issue 10 years ago • 1 comments

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.

roryokane avatar Apr 05 '15 18:04 roryokane

I like the idea. If it's useful to you, please open a PR with the necessary patches. :)

tyler avatar Apr 05 '15 22:04 tyler