commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Rich Dougherty" <r...@rd.gen.nz>
Subject [Collections] [SUBMIT] Trie
Date Mon, 02 Dec 2002 07:36:13 GMT
Hi

I've written an implementation for a trie which I'd like to
contribute. I've attached a simple implementation and a test
case. Here's the interface:

/**
 *
 * A trie is a tree data structure for storing objects. It extends the
 * {@link Map} interface and provides two methods to efficiently
 * retrieve entries that partially match a key.
 *
 * A trie usually has a restricted set of objects which can be used
 * as keys. Traditionally, it is indexed by {@link String}s, however
 * this interface tries to be more general.
 *
 * @author <a href="mailto:rich@rd.gen.nz">Rich Dougherty</a>
 * @see http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie.html
 * @see http://www.nist.gov/dads/HTML/trie.html
 */
public interface Trie extends Map {

    /**
     * Gets all the entries that have keys which start with a given
     * prefix.
     *
     * For example, in a trie that uses {@link String}s for keys, this
     * might return all the entries whose keys start with a certain
     * string. If the trie contained entries with the keys {"an",
     * "ant", "all", "allot", "alloy", "aloe", "are", "ate", "be"}
     * then <code>prefixEntrySet("al") </code> would return {"all",
     * "allot", "alloy", "aloe"}.
     *
     * @param keyPrefix The prefix of the keys.
     * @return The set of matching {@link Map.Entry}s.
     */
    public Set prefixEntrySet(Object keyPrefix);

    /**
     * Get the entry with the longest key that is a prefix of the
     * given value.
     *
     * For example, in a trie that uses {@link String}s for keys, this
     * might return the entry with the key that is the longest prefix
     * of the given value. If the trie contained entries with the keys
     * {"an", "ant", "all", "allot", "alloy", "aloe", "are", "ate",
     * "be"} then <code>getLongest("allotment")</code> would return
     * "allot".
     *
     * @param key The key to look for.
     * @return The best match, or <code>null</code> if there wasn't
     *  one.
     */
    public Map.Entry getLongest(Object key);

}

It isn't 100% polished, but I'm happy that it passes the tests! (The
Collections test suite is excellent.) Any feedback is appreciated.

Regards
Rich Dougherty


Mime
View raw message