TreeMap has a bug in headMap() as of Java 1.4.2

Thread view:

maxmike - 09 Apr 2006 22:18 GMT

If a TreeMap contains only a null key and you request
headMap(<non-null-key>) it returns an empty Map. The custom comparator
specifies null as the smallest value. Does anybody know if this has
been fixed in 1.5?

Reply to this Message

hiwa - 10 Apr 2006 01:22 GMT

I have written an
SSCCE(http://homepage1.nifty.com/algafield/sscce.html) for your
problem. Please attach your own SSCCE for simplifying the test. JDK
1.6(beta) does not have the problem you have mentioned:
[code]
import java.util.*;

public class NullKey{

public static void main(String[] args){
TreeMap<KeyObj, String> tm
= new TreeMap<KeyObj, String>(new KeyObjComparator());

tm.put(null, "Null");
tm.put(new KeyObj(10), "ten");

SortedMap sm = tm.headMap(new KeyObj(10));
System.out.println(sm.size());
System.out.println(sm.get(null));
}
}

class KeyObj{
Integer num;

public KeyObj(Integer n){
num = n;
}
}

class KeyObjComparator implements Comparator<KeyObj>{

public int compare(KeyObj o1, KeyObj o2){
int retval;

if (o1 == null){
if (o2 == null){
retval = 0;
}
else{
retval = -1;
}
}
else if (o2 == null){
retval = 1;
}
else{
retval = o1.num.compareTo(o2.num);
}
return retval;
}
}
[/code]

Reply to this Message

hiwa - 10 Apr 2006 05:15 GMT

1.4.2 just works fine.
(1.4.2_08 on Linux)

Reply to this Message

Oliver Wong - 10 Apr 2006 21:46 GMT

>I have written an
> SSCCE(http://homepage1.nifty.com/algafield/sscce.html) for your
> problem. Please attach your own SSCCE for simplifying the test. JDK
> 1.6(beta) does not have the problem you have mentioned:

[code snipped]

Your code puts TWO elements in the hashmap. The OP said this bug occurs when
there's only one element in the hashmap. Here's a slightly simplified SSCCE
which demonstrates the problem:

<code>
import java.util.*;

public class NullKey {

public static void main(String[] args) {
TreeMap<Integer, String> tm = new TreeMap<Integer, String>(
new KeyObjComparator());

tm.put(null, "Foo");
// tm.put(Integer.valueOf(10), "ten");
System.out.println(tm.size());
SortedMap sm = tm.headMap(Integer.valueOf(10));
System.out.println(sm.size());
System.out.println(sm.get(null));
}
}

class KeyObjComparator implements Comparator<Integer> {

public int compare(Integer o1, Integer o2) {
int retval;

if (o1 == null) {
if (o2 == null) {
retval = 0;
} else {
retval = -1;
}
} else if (o2 == null) {
retval = 1;
} else {
retval = o1.compareTo(o2);
}
return retval;
}
}
</code>

The output is "1\n0\nFoo\n" when it should be "1\n\1\nFoo\n". This bug
occurs on Java 1.5.0_06-b05

- Oliver

Reply to this Message

Eric Sosman - 10 Apr 2006 22:22 GMT

maxmike wrote On 04/09/06 17:18,:

> If a TreeMap contains only a null key and you request
> headMap(<non-null-key>) it returns an empty Map. The custom comparator
> specifies null as the smallest value. Does anybody know if this has
> been fixed in 1.5?

It seems to me (not a language lawyer) that such a
custom Comparator must be inconsistent with equals:

    theComparator(null, non_null) returns a negative
    number, but

    null.equals(non_null) throws an exception.

Is inconsistency with equals enough to cast doubt
on the bugginess of a Map's strange behavior?

Signature

Eric.Sosman@sun.com

Reply to this Message

Patricia Shanahan - 10 Apr 2006 23:07 GMT

> maxmike wrote On 04/09/06 17:18,:
>
[quoted text clipped - 13 lines]
> Is inconsistency with equals enough to cast doubt
> on the bugginess of a Map's strange behavior?

I think it would have been better if all the Map classes had excluded
null keys, and thrown NullPointerException on any attempt to put one.

However, that is not how TreeMap is defined. It accepts null as a key.
It specifies NullPointerException conditions such as "key is null and
this map uses natural ordering, or its comparator does not tolerate null
keys" (containsKey).

Moreover, TreeMap is not even consistent with itself. It should make up
its mind whether the null key is there or not. It reports size() zero,
but returns a non-null value on get(null).

According to the Javadoc, "The behavior of a sorted map is well-defined
even if its ordering is inconsistent with equals; it just fails to obey
the general contract of the Map interface."

Patricia

Reply to this Message

Christian Kaufhold - 10 Apr 2006 23:05 GMT

It has not.

The bug is in SubMapEntryIterator (and DescendingSubMapEntryIterator)
which sometimes stop iterating incorrectly before null keys.

Christian

Reply to this Message

maxmike - 11 Apr 2006 22:04 GMT

> > If a TreeMap contains only a null key and you request
> > headMap(<non-null-key>) it returns an empty Map. The custom comparator
[quoted text clipped - 7 lines]
>
> Christian

Thanks, Christian - it is actually important in my case to have null in
the btree, but I have
managed to walk around this bug by testing if the entire tree is empty
when there is only a null in it.

Reply to this Message

TreeMap has a bug in headMap() as of Java 1.4.2

Free Magazines