commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Janek Bogucki <...@studylink.com>
Subject Re: [Collections] [SUBMIT] Trie
Date Mon, 02 Dec 2002 16:06:53 GMT
Hi,

> From: "Rich Dougherty" <rich@rd.gen.nz>
> Reply-To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
> Date: Mon, 2 Dec 2002 20:36:13 +1300 (NZDT)
> To: <commons-dev@jakarta.apache.org>
> Subject: [Collections] [SUBMIT] Trie
> 
> 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
> 

As a user of [collections] I'd like to see this added. I would mean I could
remove some of my own code and replace it with this instead.

-Janek 


--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message