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
avoids.
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 a
good understanding of some data structures. This silliness led to someone (don't
remember who)
telling me that a piece of code I submitted "wasn't a collection" because it didn't
implement some
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 point,
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 the
best we can come up with.
My 2.5c worth.
Jeff
--- [EMAIL PROTECTED] 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. 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, and
> 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" <[EMAIL PROTECTED]>
> > 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: <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]>
>
--
To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]>
For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
