[ http://issues.apache.org/jira/browse/COLLECTIONS-225?page=all ]
Sam Berlin updated COLLECTIONS-225:
-----------------------------------
Attachment: pat.zip
The attached zip contains the following files:
Trie.java - An interface that Tries can use.
PatriciaTrie.java - An implementation that uses PATRICIA.
CharSequenceKeyAnalyzer.java - A KeyAnalyzer for PatriciaTrie intended for use
with String keys.
PatriciaTrieTest.java - A JUnit test for PatriciaTrie (this will need to be
modified, as it uses custom JUnit classes -- but the basis is there)
Example use is:
Trie<String, Object> pat = new PatriciaTrie<String, Object>(new
CharSequenceKeyAnalyzer());
pat.put("Apache");
pat.put("Apples");
pat.put("Bananas");
pat.put("Roger");
pat.put("Sam");
pat.put("Zoo");
Map<String, Object> prefix = pat.getPrefixedBy("Ap");
//prefix now has 'Apache' & Apples', but is a view over pat, so...
pat.put("Apalacian");
//because prefix is a view, it now has 'Apalacian'.
//it works just like other SortedMap-like methods that return views
Map<String, Object> range = pat.subMap("Cool", "Tea");
// range now has 'Roger' & 'Sam', since those are the only keys in between
'Cool' and 'Tea'.
// range is also a view, so inserting data into 'pat' will be reflected in
range.
For IP Filter-use, there's also convenient methods that locate the 'closest'
value (using XOR closeness, the bit values being determined by the KeyAnalyzer
analyzing the key). For an example of this, see the class:
https://www.limewire.org/fisheye/browse/limecvs/core/com/limegroup/gnutella/filters/IPList.java?r=MAIN
.
> Contribution: A Patricia Tree
> -----------------------------
>
> Key: COLLECTIONS-225
> URL: http://issues.apache.org/jira/browse/COLLECTIONS-225
> Project: Commons Collections
> Issue Type: New Feature
> Components: Map
> Reporter: Sam Berlin
> Attachments: pat.zip
>
>
> We (Roger Kapsi & I) would like to contribute a Patricia tree. The tree
> implements the Map & SortedMap interface, meaning it can be used as a
> replacement for any arbitrary map. It also implementes a new 'Trie'
> interface, allowing other implementations or other varieties of Tries to be
> added. The tree is currently written for generics, but that can easily be
> removed. We have used the tree as the structure backing a route table in a
> new Kademlia-based DHT, as the structure backing an IP filter (storing IP
> addresses & IP ranges, allowing retrieval/searching in nanoseconds), and have
> tested it with Strings by storing all of 'hamlet' and comparing it against a
> TreeSet. The tree is also ready to implement NavigableMap whenever Java 1.6
> becomes available.
> I will attach the files in an update to this issue.
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
http://issues.apache.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
