Trie Again

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.

Leave a Reply

Your email address will not be published. Required fields are marked *