Return-Path: Delivered-To: apmail-jakarta-commons-dev-archive@apache.org Received: (qmail 12450 invoked from network); 5 Dec 2002 00:11:04 -0000 Received: from unknown (HELO nagoya.betaversion.org) (192.18.49.131) by daedalus.apache.org with SMTP; 5 Dec 2002 00:11:04 -0000 Received: (qmail 11488 invoked by uid 97); 5 Dec 2002 00:12:13 -0000 Delivered-To: qmlist-jakarta-archive-commons-dev@jakarta.apache.org Received: (qmail 11472 invoked by uid 97); 5 Dec 2002 00:12:13 -0000 Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Jakarta Commons Developers List" Reply-To: "Jakarta Commons Developers List" Delivered-To: mailing list commons-dev@jakarta.apache.org Received: (qmail 11460 invoked by uid 98); 5 Dec 2002 00:12:12 -0000 X-Antivirus: nagoya (v4218 created Aug 14 2002) Message-ID: <00a801c29bf3$2a7ba660$e72c29d9@oemcomputer> From: "Stephen Colebourne" To: "Jakarta Commons Developers List" References: <55953.210.55.57.171.1038814573.squirrel@mail.ext.nil.co.nz> Subject: Re: [Collections] [SUBMIT] Trie Date: Thu, 5 Dec 2002 00:13:40 -0000 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4133.2400 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400 X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N 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" To: 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 Rich Dougherty > * @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 prefixEntrySet("al") 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 getLongest("allotment") would return > * "allot". > * > * @param key The key to look for. > * @return The best match, or null 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: > For additional commands, e-mail: -- To unsubscribe, e-mail: For additional commands, e-mail: