Details

    • Type: New Feature New Feature
    • Status: Resolved
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.0-alpha1, 4.0
    • Component/s: Map
    • Labels:
      None

      Description

      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

      1. patricia.zip
        204 kB
        Sam Berlin

        Activity

        Hide
        Sam Berlin added a comment -

        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 .

        Show
        Sam Berlin added a comment - 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 .
        Hide
        Sam Berlin added a comment -

        Maybe some more interest in this contribution with the renewed interest in collections and updating it to JDK 5?

        Show
        Sam Berlin added a comment - Maybe some more interest in this contribution with the renewed interest in collections and updating it to JDK 5?
        Hide
        Stephen Colebourne added a comment -

        Yep, so long as I can get the project slimmed down in the generics process, there is no reason for it not to take in useful ideas/code again

        Show
        Stephen Colebourne added a comment - Yep, so long as I can get the project slimmed down in the generics process, there is no reason for it not to take in useful ideas/code again
        Hide
        Alan Mehio added a comment -

        If the generic part of commons-collections moves to J2SE and the part like this contribution which focus on implementation specific, into the commons.
        I think the "Patricia Tree" gives a great value for the commons-collections.

        Show
        Alan Mehio added a comment - If the generic part of commons-collections moves to J2SE and the part like this contribution which focus on implementation specific, into the commons. I think the "Patricia Tree" gives a great value for the commons-collections.
        Hide
        Sam Berlin added a comment -

        It would be great to get this included! We've made some changes to the version we're shipping with LimeWire, so if you do plan on going ahead and including this, we can recontribute the latest code.

        Show
        Sam Berlin added a comment - It would be great to get this included! We've made some changes to the version we're shipping with LimeWire, so if you do plan on going ahead and including this, we can recontribute the latest code.
        Hide
        Alan Mehio added a comment -

        Roger, Sam;
        Can you please supply the below classes

        EmptyIterator
        BaseTestCase

        I am trying to run the test case class "PatriciaTrieTest"

        Regards,
        Alan Mehio
        London, UK

        Show
        Alan Mehio added a comment - Roger, Sam; Can you please supply the below classes EmptyIterator BaseTestCase I am trying to run the test case class "PatriciaTrieTest" Regards, Alan Mehio London, UK
        Hide
        Sam Berlin added a comment -

        This is a new revision of the patricia files. It should compile on its own, and has a test case that can run in JUnit without requiring anything else.

        Show
        Sam Berlin added a comment - This is a new revision of the patricia files. It should compile on its own, and has a test case that can run in JUnit without requiring anything else.
        Hide
        Otis Gospodnetic added a comment -

        Checking in on the status of this nice contrib...
        Sam, I think looks good. I'd add ASL to each class and I'd change the packaging to org.apache.....

        Is this you can do, so we can get this in?

        Show
        Otis Gospodnetic added a comment - Checking in on the status of this nice contrib... Sam, I think looks good. I'd add ASL to each class and I'd change the packaging to org.apache..... Is this you can do, so we can get this in?
        Hide
        Sam Berlin added a comment -

        Whew, some activity! Thanks for looking at this, Otis. Things are extremely busy here right now, and I'm fairly certain we've made some improvements to the class since it was last uploaded here. I'll give it a run-over and upload a newer one with any changes.

        Show
        Sam Berlin added a comment - Whew, some activity! Thanks for looking at this, Otis. Things are extremely busy here right now, and I'm fairly certain we've made some improvements to the class since it was last uploaded here. I'll give it a run-over and upload a newer one with any changes.
        Hide
        Otis Gospodnetic added a comment -

        Thanks, I look forward to it!
        Yes, I see changes and a move within LimeWire's packages:
        https://www.limewire.org/fisheye/qsearch/limecvs/core/com/limegroup/gnutella/util?q=patriciatrie

        I'm not a Commons Collections committer, but I wonder when this could make it into a release.... 3.3? 3.4? (Fix version is not set)

        Show
        Otis Gospodnetic added a comment - Thanks, I look forward to it! Yes, I see changes and a move within LimeWire's packages: https://www.limewire.org/fisheye/qsearch/limecvs/core/com/limegroup/gnutella/util?q=patriciatrie I'm not a Commons Collections committer, but I wonder when this could make it into a release.... 3.3? 3.4? (Fix version is not set)
        Hide
        Otis Gospodnetic added a comment -

        Sam, nudging to see if it's possible to get the newer version. Id' be happy to help repackaging it, etc.

        Show
        Otis Gospodnetic added a comment - Sam, nudging to see if it's possible to get the newer version. Id' be happy to help repackaging it, etc.
        Hide
        Sam Berlin added a comment -

        Hi Otis,

        Hope this is still useful after the long delay in responding... Roger has put versions of it up on http://code.google.com/p/patricia-trie/ as a Google Code project.

        Show
        Sam Berlin added a comment - Hi Otis, Hope this is still useful after the long delay in responding... Roger has put versions of it up on http://code.google.com/p/patricia-trie/ as a Google Code project.
        Hide
        Otis Gospodnetic added a comment -

        Excellent. Sam, is the patricia-trie project available in any of the Maven repos?

        Show
        Otis Gospodnetic added a comment - Excellent. Sam, is the patricia-trie project available in any of the Maven repos?
        Hide
        Greg Sheremeta added a comment -

        I used Patricia tree from http://code.google.com/p/patricia-trie/

        It works great – thank you Sam and Roger.

        It would be helpful if it made its way into collections, for Maven availability and for corporate policy reasons.

        Show
        Greg Sheremeta added a comment - I used Patricia tree from http://code.google.com/p/patricia-trie/ It works great – thank you Sam and Roger. It would be helpful if it made its way into collections, for Maven availability and for corporate policy reasons.
        Hide
        Thomas Neidhart added a comment -

        Hi Sam,

        it has been a long time, but I took the time to look at code at the googlecode repository and after some cleanup committed it to commons-collections in r1365732. The status is pretty good imho, but would require more unit tests and more javadoc. So further help is very welcome!

        Thanks,

        Thomas

        Show
        Thomas Neidhart added a comment - Hi Sam, it has been a long time, but I took the time to look at code at the googlecode repository and after some cleanup committed it to commons-collections in r1365732. The status is pretty good imho, but would require more unit tests and more javadoc. So further help is very welcome! Thanks, Thomas
        Hide
        Thomas Neidhart added a comment -

        I am considering changing the (first) implementation in CC with a more simple one: http://code.google.com/p/radixtree/

        Show
        Thomas Neidhart added a comment - I am considering changing the (first) implementation in CC with a more simple one: http://code.google.com/p/radixtree/
        Hide
        Thomas Neidhart added a comment - - edited

        The use of key types other than String is confusing and leads to unexpected results, so I am in favor of settling for a simple version of a Trie which only supports Strings as key, thus also updating the Trie interface and removing the other key analyzers.

        Edit: this comment refers to the prefix functionality of the Trie, which is the most interesting feature imho. The other things like ordering seem to work fine with other key types.

        Show
        Thomas Neidhart added a comment - - edited The use of key types other than String is confusing and leads to unexpected results, so I am in favor of settling for a simple version of a Trie which only supports Strings as key, thus also updating the Trie interface and removing the other key analyzers. Edit: this comment refers to the prefix functionality of the Trie, which is the most interesting feature imho. The other things like ordering seem to work fine with other key types.
        Hide
        Thomas Neidhart added a comment -

        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
        Show
        Thomas Neidhart added a comment - 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
        Hide
        Thomas Neidhart added a comment -

        Unless there are any objections, the current version as committed to the trunk is the one that I would like to see in the 4.0 release.

        Show
        Thomas Neidhart added a comment - Unless there are any objections, the current version as committed to the trunk is the one that I would like to see in the 4.0 release.

          People

          • Assignee:
            Unassigned
            Reporter:
            Sam Berlin
          • Votes:
            9 Vote for this issue
            Watchers:
            7 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development