Phill van Leersum

I have been doing some more thinking (and, of course, coding) about tries.

I have realised, somewhat belatedly, that the important thing about a trie is the way it uses a series of integers (in my case) to navigate a tree of nodes to reach a point unique to every different series of integers. What gets stored there is irrelevant to the trie but important to the user. So a trie is best thought of as an implementor of a map (java.util.Map in my case). The tricky thing is that the supplied key is not used directly, but that the creator of the map has to provide a means of converting the key to a series of integers.

I have implemented TrieMap in this way.

    public final class TrieMap<K, V> implements Map<K, V> {
			

So that a TrieMap<K,V> can be used anywhere Map<K,V> is required. The tricky bit is informing thee TrieMap how to turn instances of K into a series of integers. This has been done by supplying the constructor with an instance of TriePathIteratorFactory, thus:

    public TrieMap(final TriePathIteratorFactory<K> pathIteratorFactory)
			

Where a TriePathIteratorFactory is responsible solely for generating instances of TriePathIterators:

    public interface TriePathIteratorFactory<K> {
        public TriePathIterator<K> pathIterator(K k);
    }
			

And the important part of the TriePathIterator is the generation of the series of integers:

    public interface TriePathIterator<K> {
        /**
         * @return true if the receiver has more elements 
         * in it path, false otherwise
         */
        public abstract boolean hasNext();

        public abstract int nextIndex();
    }
			

Now when the user calls a standard method from java.util.Map that takes a key (K), the TrieMap creates a TriePathIterator instance and uses it to traverse the data structure.

Using the underlying structure from the TrieMap I have implemented a TrieSet - simply a subclass of TrieMap<K,V> where K === V. The performance exceeds that of the supplied java.util.TreeSet. I will provide some hard data in another post, but the work-in-progress is available from the git repository on the 'map' branch.