commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jeff Varszegi <>
Subject Re: [Collections] [SUBMIT] Trie
Date Fri, 06 Dec 2002 17:15:23 GMT
Map isn't appropriate for sure.  The point of a trie seems to be that you have a flexible indexed
key for each entry-- to add all possible keys for each entry would create the overhead that
a trie

Think about it this way: what would be the best way to implement

Object get(Object key)

Here's the contract for Map, straight from javadoc:

> public interface Map
> An object that maps keys to values. A map cannot contain duplicate keys; each key can
map to at
> <I>most</I> one value. 
(cheesy italics mine)

I have to say that I am a little disappointed at all the emphasis in Collections (aimed at
no one
in particular) on implementing java.util interfaces at all costs, even if the proposed structure
isn't a good fit.  It leads to performance degradation in some cases, and may actually prohibit
good understanding of some data structures.  This silliness led to someone (don't remember
telling me that a piece of code I submitted "wasn't a collection" because it didn't implement
interface that the people at Sun happened to come up with.

The java.util package is a good (well, an okay and in some individual cases bad) starting
and that's all-- that goes for both interfaces and implementations.  

I agree that we need to focus on the interface and implementation to make sure that they're
best we can come up with.

My 2.5c worth.


--- wrote:
> Thanks Craig. With  two possible Jakarta users, we seem to have a justification for inclusion.
> So, it is now about practical issues. How does the submitted Trie cope for design and
> performance. Do we need a String only Trie, a URL Trie, or does the abstracted Trie submitted
> work OK?
> The big question is to get the Trie interface correct. In my naive view, it would be
nice if
> there was no 'Trie' interface, but instead just a Map implementation and a TrieUtils.
> would then only use the Map interface to determine the suffix/prefix/longest cases.
> However, this may not be practical. Can I ask all concerned to think about the interface,
> whether the current one is suitable for all the needs we can think of.
> Stephen
> public interface Trie extends Map {
> // Gets all the entries that have keys which start with
> // a given prefix.
> public Set prefixEntrySet(Object keyPrefix);
> // Get the entry with the longest key that is a prefix of
> // the given value.
> public Map.Entry getLongest(Object key);
> }
> >  from:    "Craig R. McClanahan" <>
> > FWIW, there are at least two Jakarta products that I'm involved in (Tomcat
> > and Struts) that have exactly the path-mapping use case that was described
> > for the Trie class.  And, conveniently, they both already dependd on
> > [collections] so it would be very convenient to have Trie added here.
> > 
> > It will be very interesting to experiment with the relative speed of using
> > a Trie in these cases versus the current algorithms (which clearly need
> > some optimizations).
> > 
> > So, an inactive-committer (to collections)  1 from me for including this.
> > 
> > Craig McClanahan
> > 
> > 
> > 
> > --
> > To unsubscribe, e-mail:   <>
> > For additional commands, e-mail: <>
> > 
> --
> To unsubscribe, e-mail:   <>
> For additional commands, e-mail: <>

To unsubscribe, e-mail:   <>
For additional commands, e-mail: <>

View raw message