[jira] [Commented] (COLLECTIONS-225) Contribution: A Patricia Tree

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (COLLECTIONS-225) Contribution: A Patricia Tree

Dmitri Blinov (Jira)

    [ https://issues.apache.org/jira/browse/COLLECTIONS-225?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13682741#comment-13682741 ]

Thomas Neidhart commented on COLLECTIONS-225:
---------------------------------------------

Did a great deal of refactoring:

 * Trie interface now inherits from IterableSortedMap
 ** obsoletes the traverse / cursor stuff: use OrderedMapIterator instead
 ** hide bit-wise select / getPrefixedBy methods
 ** rename getPrefixedBy to prefixMap to be consistent with other methods like tailMap, headMap ...
 * removed all key analyzers but the StringKeyAnalyzer
 * make PatriciaTrie a concrete implementation of AbstractPatriciaTrie with Strings as key
 * integrated the unit tests into the test framework

The rationale behind this changes:

 * keep the interface & implementation simple and understandable
 * favor and re-use existing stuff in collections over new concepts
               

> Contribution: A Patricia Tree
> -----------------------------
>
>                 Key: COLLECTIONS-225
>                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-225
>             Project: Commons Collections
>          Issue Type: New Feature
>          Components: Map
>            Reporter: Sam Berlin
>             Fix For: 4.0
>
>         Attachments: patricia.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, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira