commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Pranas Baliuka" <pranas.bali...@danet.lt>
Subject RE: [Collections] [SUBMIT] Trie
Date Fri, 06 Dec 2002 15:18:37 GMT
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>


Mime
View raw message