commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Juozas Baliuka" <bali...@centras.lt>
Subject Re: [Collections] [SUBMIT] Trie
Date Fri, 06 Dec 2002 17:53:28 GMT

Hi Pranas,
It seems [collections] is more about to implement java.util.* interfaces,
[algorithms] subproject was proposed a few moths ago, but I am not expert.
I think we can implement
some "interesting" algorithms with your help (Genetic algorithms ). It can
be good
place for trie/patricia, hash functions, linier programming, math stuff,
.....



> I think interface shold be corrected:
> ...
> // 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);
> ...
>
> Comment:
> * key may be String - It is intuitive type for the "prefix definition"
> * key must be of type "XString" for which prefix definition valid like:
>
> public interface XString {
> // number of elements in the XString
> int getLength();
> // get element it can be character converted to the int, bit value 0 1 for
> binary trie or Patricia etc.
> int getElement(int i);
> }
>
> /Pranas
>
> -----Original Message-----
> From: scolebourne@btopenworld.com [mailto:scolebourne@btopenworld.com]
> Sent: 2002 m. gruodþio 6 d. 14:09
> To: commons-dev@jakarta.apache.org
> Subject: Re: [Collections] [SUBMIT] Trie
>
>
> 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" <craigmcc@apache.org>
> > 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: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>
>
>
> --
> 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