commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "zigler zhang (JIRA)" <j...@apache.org>
Subject [jira] [Comment Edited] (COLLECTIONS-525) PatriciaTrie
Date Sat, 10 May 2014 22:15:36 GMT

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

zigler zhang edited comment on COLLECTIONS-525 at 5/9/14 7:54 AM:
------------------------------------------------------------------

take some time to investigate, I found this line:

       if (isBitSet(prefix, endIndexInBits, endIndexInBits)
                != isBitSet(entry.key, lengthInBits, lengthInBits(entry.key))) {
            return null;
        }

in subtree functions.

It simply check the last bits of the prefix and the entry.key, however, as we use string as
key, the endIndexInBits would be set the character length, 
and it would make the codes check the next character of the prefix and the entry.key instead
as expected.  Then for the character of the low region(which the highest bit is always 0)
this judgment is always return true. But for other characters this would not return as expected.

 if (isBitSet(prefix, endIndexInBits-1, endIndexInBits)
                != isBitSet(entry.key, lengthInBits-1, lengthInBits(entry.key)))
would fix it. 



was (Author: zigler):
take some time to investigate, I found this line:

       if (isBitSet(prefix, endIndexInBits, endIndexInBits)
                != isBitSet(entry.key, lengthInBits, lengthInBits(entry.key))) {
            return null;
        }

in subtree functions.

It simply check the last bits of the prefix and the entry.key, however, as we use string as
key, the endIndexInBits would be set the character length, 
and it would make the codes check the next character of the prefix and the entry.key instead
as expected.  Then for the character of the low region(which the highest bit is always 0)
this judgment is always return true. But for other characters this would not return as expected.

 if (isBitSet(prefix, endIndexInBits, endIndexInBits)
                != isBitSet(entry.key, lengthInBits, lengthInBits(entry.key)))
would fix it. 


> PatriciaTrie
> ------------
>
>                 Key: COLLECTIONS-525
>                 URL: https://issues.apache.org/jira/browse/COLLECTIONS-525
>             Project: Commons Collections
>          Issue Type: Bug
>          Components: Collection
>    Affects Versions: 4.0
>         Environment: android
>            Reporter: zigler zhang
>            Priority: Critical
>         Attachments: 525.patch
>
>
>  the result of trie tree prefixMap function is inconsistent. it would contain a key but
the size is 0;
> some unittest codes as below: 
>   PatriciaTrie<String> aTree =
>         new PatriciaTrie<String> ();
>     aTree.put("点评", "测试");
>     aTree.put("书评", "测试");
>     assertTrue(aTree.prefixMap("点").containsKey("点评")); //pass
>     assertEquals("测试", aTree.prefixMap("点").get("点评")); //pass
>     assertFalse(aTree.prefixMap("点").isEmpty());                 //fail
>     assertEquals(1, aTree.prefixMap("点").size());                 //fail actural 0
>     assertEquals(1, aTree.prefixMap("点").keySet().size());   //fail actural 0
>     assertEquals(1, aTree.prefixMap("点").entrySet().size()); //fail actural 0
>     assertEquals(1, aTree.prefixMap("点评").values().size()); //fail actural 0



--
This message was sent by Atlassian JIRA
(v6.2#6252)

Mime
View raw message