Simple PATRICIA Trie / by Your Name

I moved my PATRICIA Trie implementation a few months ago from Google Code to Github (the Binaries are still hosted on Google Code) and the number of emails I receive regards PATRICIA has literally exploded ever since. I guess Github's social aspect makes it easy for developers to get in touch and it's great to see that people have an use for this relatively specialized Data Structure.

One thing I've noticed in the emails with my PATRICIA Trie's users is that they've often very specific use-cases and requirements. It seems our attempt to make the Trie generic and cramming everything under a Map + SortedMap interface is maybe not the right approach. A lot of our implementation complexities are a result of the requirements these two interfaces impose and they make it very hard to change the code. What if we relax a few things, don't try to be 100% according to specification, don't try to make all methods super efficient and just cherry pick some features from SortedMap, NavigableMap?

I started off with a PATRICIA Trie as described in Robert Sedgewick's Algorithms in Java. It's not the most practical implementation but a good starting point to refresh one's rusty memory. This was followed by a new PATRICIA Trie implementation where I was focusing on getting the most important Trie operations right: put(), get(), select() and traverse(). An important decision was to not optimize the remove() operation. It's relatively complicated and would require two additional fields per Node (parent + predecessor) to make it efficient. An another decision was to implement the Map interface (to get some compatibility with the Java Collections) but be relaxed about some operations such as entrySet(), keySet() and values(). They return read-only copies of the current state. That means you can't use them to modify the underlying PATRICIA Trie and they're not being updated if something happens to the Trie.

The last step was to take the new PATRICIA Trie and do something with it. One thing users have been asking me is how to use primitive types for keys for example. They want to use raw int values. With the new PATRICIA Trie it's a very simple task and it took me about 30 minutes to make the required changes. This breaks certainly all kinds compatibilities with Java Collections but that is OK because it's a very specific use-case.

The code for all three PATRICIA Trie versions can be found in a new repository. Consider it a toolbox for custom PATRICIA Tries. Enjoy!