You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Tom Parker (JIRA)" <ji...@apache.org> on 2009/07/10 04:26:14 UTC
[jira] Created: (COLLECTIONS-332) ListOrderedMap not respecting
underlying list
ListOrderedMap not respecting underlying list
---------------------------------------------
Key: COLLECTIONS-332
URL: https://issues.apache.org/jira/browse/COLLECTIONS-332
Project: Commons Collections
Issue Type: Bug
Components: Map
Reporter: Tom Parker
Priority: Minor
When decorating either CaseInsensitiveMap or IdentityMap (and I believe this will impact any java.util.TreeMap built with a non-.equals() Comparator), ListOrderedMap responds inconsistently with the underlying map. The ordering seems to be operating off .equals() rather than the actual contents of the underlying map.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COLLECTIONS-332) ListOrderedMap not respecting
underlying list
Posted by "Tom Parker (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-332?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tom Parker updated COLLECTIONS-332:
-----------------------------------
Attachment: ListOrderedMapTest.java
Test that demonstrates the issue with both CaseInsensitiveMap or IdentityMap as the underlying map.
Note that this set of tests is not comprehensive (other methods than .firstKey() can demonstrate the issue)
> ListOrderedMap not respecting underlying list
> ---------------------------------------------
>
> Key: COLLECTIONS-332
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-332
> Project: Commons Collections
> Issue Type: Bug
> Components: Map
> Reporter: Tom Parker
> Priority: Minor
> Attachments: ListOrderedMapTest.java
>
>
> When decorating either CaseInsensitiveMap or IdentityMap (and I believe this will impact any java.util.TreeMap built with a non-.equals() Comparator), ListOrderedMap responds inconsistently with the underlying map. The ordering seems to be operating off .equals() rather than the actual contents of the underlying map.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (COLLECTIONS-332) ListOrderedMap not respecting
underlying list
Posted by "Tom Parker (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-332?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12743065#action_12743065 ]
Tom Parker commented on COLLECTIONS-332:
----------------------------------------
Per my note to the commons user list, I was hoping for either updated docs or a code change, but I think one of the two would be good.
Looking for a code change, I agree casting is nasty and would recommend against it... it's very ugly to get all cases correct. For example, a TreeMap sorted in case insensitive order also breaks ListOrderedMap because it also fails to use .equals().
Before this is turned into a documentation bug or feature request, I'd like to note a potential solution simply depends upon how much of a performance hit one is willing to take.
{quote}
Object result = getMap().remove(key);
for (Iterator<Object> it = insertOrder.iterator(); it.hasNext();) \{
if (!getMap().containsKey(it.next())) \{ //This respects equality as defined by the underlying map
it.remove();
\}
\}
return result;
{quote}
...would seem to be universal (if slower since it effectively trades a .equals() for a .containsKey() call) [and yes, getMap() should be extracted to a local variable]
> ListOrderedMap not respecting underlying list
> ---------------------------------------------
>
> Key: COLLECTIONS-332
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-332
> Project: Commons Collections
> Issue Type: Bug
> Components: Map
> Reporter: Tom Parker
> Priority: Minor
> Attachments: ListOrderedMapTest.java
>
>
> When decorating either CaseInsensitiveMap or IdentityMap (and I believe this will impact any java.util.TreeMap built with a non-.equals() Comparator), ListOrderedMap responds inconsistently with the underlying map. The ordering seems to be operating off .equals() rather than the actual contents of the underlying map.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (COLLECTIONS-332) ListOrderedMap not respecting
underlying list
Posted by "John Curtis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-332?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12735420#action_12735420 ]
John Curtis commented on COLLECTIONS-332:
-----------------------------------------
When you remove an object from a ListOrderedMap there are two main steps:
{code}
public Object remove(Object key) {
Object result = getMap().remove(key);
insertOrder.remove(key);
return result;
}
{code}
Firstly, the removal of the object from the underlying map is delegated to the map instance. Since in your case this will be an Identity map, the removal method will search by '==' rather than '.equals()' as with a standard Map implementation.
Secondly, the ListOrderedMap decorator needs to remove this key from its own internal list which is charged with maintaining order. To do this it will use the standard '.remove()' from the ArrayList class, which will search using equality rather than identity.
These two different implementations cause problems when used together. In my opinion the IdentityMap (knowingly) breaks the Map interface by searching on identity rather than equality (see Map.remove() javadoc: "if this map contains a mapping from key k to value v such that (key==null ? k==null : key.equals(k)), that mapping is removed."). This causes problems for any classes using an instance of this class expecting it to strictly adhere to the Map interface.
Therefore the bug isn't really in the ListOrderedMap class but rather in the usage of the two together. I would suggest improving documentation in the IdentityMap javadoc to clarify this problem. Otherwise we would need to introduce a less-than-elegant 'instance of' check in the ListOrderedMap class which would not be ideal.
> ListOrderedMap not respecting underlying list
> ---------------------------------------------
>
> Key: COLLECTIONS-332
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-332
> Project: Commons Collections
> Issue Type: Bug
> Components: Map
> Reporter: Tom Parker
> Priority: Minor
> Attachments: ListOrderedMapTest.java
>
>
> When decorating either CaseInsensitiveMap or IdentityMap (and I believe this will impact any java.util.TreeMap built with a non-.equals() Comparator), ListOrderedMap responds inconsistently with the underlying map. The ordering seems to be operating off .equals() rather than the actual contents of the underlying map.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Issue Comment Edited: (COLLECTIONS-332) ListOrderedMap not
respecting underlying list
Posted by "Tom Parker (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COLLECTIONS-332?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12743065#action_12743065 ]
Tom Parker edited comment on COLLECTIONS-332 at 8/13/09 8:43 PM:
-----------------------------------------------------------------
Per my note to the commons user list, I was hoping for either updated docs or a code change, but I think one of the two would be good.
Looking for a code change, I agree casting is nasty and would recommend against it... it's very ugly to get all cases correct. For example, a TreeMap sorted in case insensitive order also breaks ListOrderedMap because it also fails to use .equals().
Before this is turned into a documentation bug or feature request, I'd like to note a potential solution simply depends upon how much of a performance hit one is willing to take.
{code:java}
Object result = getMap().remove(key);
for (Iterator<Object> it = insertOrder.iterator(); it.hasNext();) {
if (!getMap().containsKey(it.next())) { //This respects equality as defined by the underlying map
it.remove();
}
}
return result;
{code}
...would seem to be universal (if slower since it effectively trades a .equals() for a .containsKey() call) [and yes, getMap() should be extracted to a local variable]
was (Author: thpr):
Per my note to the commons user list, I was hoping for either updated docs or a code change, but I think one of the two would be good.
Looking for a code change, I agree casting is nasty and would recommend against it... it's very ugly to get all cases correct. For example, a TreeMap sorted in case insensitive order also breaks ListOrderedMap because it also fails to use .equals().
Before this is turned into a documentation bug or feature request, I'd like to note a potential solution simply depends upon how much of a performance hit one is willing to take.
{quote}
Object result = getMap().remove(key);
for (Iterator<Object> it = insertOrder.iterator(); it.hasNext();) \{
if (!getMap().containsKey(it.next())) \{ //This respects equality as defined by the underlying map
it.remove();
\}
\}
return result;
{quote}
...would seem to be universal (if slower since it effectively trades a .equals() for a .containsKey() call) [and yes, getMap() should be extracted to a local variable]
> ListOrderedMap not respecting underlying list
> ---------------------------------------------
>
> Key: COLLECTIONS-332
> URL: https://issues.apache.org/jira/browse/COLLECTIONS-332
> Project: Commons Collections
> Issue Type: Bug
> Components: Map
> Reporter: Tom Parker
> Priority: Minor
> Attachments: ListOrderedMapTest.java
>
>
> When decorating either CaseInsensitiveMap or IdentityMap (and I believe this will impact any java.util.TreeMap built with a non-.equals() Comparator), ListOrderedMap responds inconsistently with the underlying map. The ordering seems to be operating off .equals() rather than the actual contents of the underlying map.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.