Expose API to get longest prefix match

Expose an API to scan the input for keys stored in the tree which are prefixes 
of the input.
See discussion in forum: 
https://groups.google.com/forum/#!topic/concurrent-trees-discuss/_IpLEzNDFWs

Example: tree contains keys 123, 1234568, 1234569

Input: 12345690

API would return keys 123, 1234569.

This could be used for processing phone numbers.

This could be calculated in a single scan through the input, thus finding keys 
which are prefixes of the input very quickly. This functionality is a subset of 
InvertedRadixTree.getKeysContainedIn, and can use the same traversal algorithm.

Unit test demonstrating desired functionality:

    @Test
    public void testGetKeysPrefixing() throws Exception {
        ConcurrentInvertedRadixTree<Integer> tree = new ConcurrentInvertedRadixTree<Integer>(nodeFactory);

        tree.put("1234567", 1);
        tree.put("1234568", 2);
        tree.put("123", 3);

        //    ○
        //    └── ○ 123 (3)
        //        └── ○ 456
        //            ├── ○ 7 (1)
        //            └── ○ 8 (2)

        assertEquals("[123, 1234567]", Iterables.toString(tree.getKeysPrefixing("1234567")));
        assertEquals("[123, 1234567]", Iterables.toString(tree.getKeysPrefixing("12345670")));
        assertEquals("[123, 1234568]", Iterables.toString(tree.getKeysPrefixing("1234568")));
        assertEquals("[123, 1234568]", Iterables.toString(tree.getKeysPrefixing("12345680")));
        assertEquals("[123]", Iterables.toString(tree.getKeysPrefixing("1234569")));
        assertEquals("[123]", Iterables.toString(tree.getKeysPrefixing("123456")));
        assertEquals("[123]", Iterables.toString(tree.getKeysPrefixing("123")));
        assertEquals("[]", Iterables.toString(tree.getKeysPrefixing("12")));
        assertEquals("[]", Iterables.toString(tree.getKeysPrefixing("")));
    }
Original issue reported on code.google.com by ni...@npgall.com on 7 Aug 2013 at 9:03
roxrook / concurrent-trees

Expose API to get longest prefix match #5
