commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stephen Colebourne" <scolebou...@btopenworld.com>
Subject Re: [Collections] [SUBMIT] Trie
Date Thu, 05 Dec 2002 00:13:40 GMT
Hi,
I've taken a quick look at the code here, and that all looks fine.

Unfortunately, I don't really know what I'm looking at! What I mean is that
I've never heard of a 'Trie' before, and am thus wondering as to why I would
use it, and is it general enough to be in [collections].

In the past we have had discussions about Tree implementations (and I have
coded some before). This may be related, as the Trie appears to be a
recursive structure.

Perhaps, some use cases as to why a Trie is useful, especially in a
general/server environment would be useful. Thanks.

Stephen

----- Original Message -----
From: "Rich Dougherty" <rich@rd.gen.nz>
To: <commons-dev@jakarta.apache.org>
Sent: Monday, December 02, 2002 7:36 AM
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
>
>


----------------------------------------------------------------------------
----


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


--
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