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" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
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:[EMAIL PROTECTED]";>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:[EMAIL PROTECTED]>
> For additional commands, e-mail:
<mailto:[EMAIL PROTECTED]>
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
