(coll) TreeMap head/tailMap() methods handle null keys incorrectly

FULL PRODUCT VERSION :
java version "1.6.0-rc"
Java(TM) SE Runtime Environment (build 1.6.0-rc-b98)
Java HotSpot(TM) Client VM (build 1.6.0-rc-b98, mixed mode, sharing)
-also-
java version "1.5.0_07"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_07-b03)
Java HotSpot(TM) Client VM (build 1.5.0_07-b03, mixed mode, sharing)
-also-
java version "1.4.2_12"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_12-b03)
Java HotSpot(TM) Client VM (build 1.4.2_12-b03, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
classlib problem, OS irrelevant

A DESCRIPTION OF THE PROBLEM :
If a TreeMap is constructed with a null-aware comparator, it should (and does, for the most part) properly handle null keys. Other bug resolutions seem to support this assertion. However, when the TreeMap contains a null key, the results of headMap() and tailMap() are incorrect.

NOTE: This is a regression; the desired behavior occurs in JDK 1.3. However, I cannot select 1.3 from the regression dropdown below! Exact version information for the 1.3 installation that produces the desired behavior:

java version "1.3.1_18"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1_18-b01)
Java HotSpot(TM) Client VM (build 1.3.1_18-b01, mixed mode)

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Add a mapping to a null-safe java.util.TreeMap with a null key, then call the various headMap and tailMap operations with null and other keys. See included test case.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
1.3 yields:

null low, map is {a=A, b=B, c=C}:

head 'b': {a=A}
tail 'b': {b=B, c=C}
head null : {}
tail null : {a=A, b=B, c=C}
added null mapping; map is {null=NULL, a=A, b=B, c=C}:

head 'b': {null=NULL, a=A}
tail 'b': {b=B, c=C}
head null : {}
tail null : {null=NULL, a=A, b=B, c=C}

null high, map is {a=A, b=B, c=C}:

head 'b': {a=A}
tail 'b': {b=B, c=C}
head null : {a=A, b=B, c=C}
tail null : {}
added null mapping; map is {a=A, b=B, c=C, null=NULL}:

head 'b': {a=A}
tail 'b': {b=B, c=C, null=NULL}
head null : {a=A, b=B, c=C}
tail null : {null=NULL}
ACTUAL -
with 1.4, 1.5, 1.6:

null low, map is {a=A, b=B, c=C}:

head 'b': {a=A}
tail 'b': {b=B, c=C}
head null : {}
tail null : {a=A, b=B, c=C}
added null mapping; map is {null=NULL, a=A, b=B, c=C}:

head 'b': {null=NULL, a=A}
tail 'b': {b=B, c=C}
head null : {}
tail null : {}

null high, map is {a=A, b=B, c=C}:

head 'b': {a=A}
tail 'b': {b=B, c=C}
head null : {a=A, b=B, c=C}
tail null : {}
added null mapping; map is {a=A, b=B, c=C, null=NULL}:

head 'b': {a=A}
tail 'b': {b=B, c=C}
head null : {a=A, b=B, c=C}
tail null : {}

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
This test class uses apache commons-collections http://jakarta.apache.org/commons/collections :

import java.util.TreeMap;

import org.apache.commons.collections.ComparatorUtils;

public class Test {

    public static void main(String[] args) {
        TreeMap m = new TreeMap(ComparatorUtils.nullLowComparator(ComparatorUtis.NATURAL_COMPARATOR));

        m.put("a", "A");
        m.put("b", "B");
        m.put("c", "C");

        System.out.println("null low, map is " + m + ":\n");

        System.out.println("head 'b': " + m.headMap("b"));
        System.out.println("tail 'b': " + m.tailMap("b"));
        System.out.println("head null : " + m.headMap(null));
        System.out.println("tail null : " + m.tailMap(null));

        m.put(null, "NULL");
        System.out.println("added null mapping; map is " + m + ":\n");
        System.out.println("head 'b': " + m.headMap("b"));
        System.out.println("tail 'b': " + m.tailMap("b"));
        System.out.println("head null : " + m.headMap(null));
        System.out.println("tail null : " + m.tailMap(null));

        m = new TreeMap(ComparatorUtils.nullHighComparator(ComparatorUtils.NATURAL_COMPARATOR));

        m.put("a", "A");
        m.put("b", "B");
        m.put("c", "C");

        System.out.println("\nnull high, map is " + m + ":\n");

        System.out.println("head 'b': " + m.headMap("b"));
        System.out.println("tail 'b': " + m.tailMap("b"));
        System.out.println("head null : " + m.headMap(null));
        System.out.println("tail null : " + m.tailMap(null));

        m.put(null, "NULL");
        System.out.println("added null mapping; map is " + m + ":\n");
        System.out.println("head 'b': " + m.headMap("b"));
        System.out.println("tail 'b': " + m.tailMap("b"));
        System.out.println("head null : " + m.headMap(null));
        System.out.println("tail null : " + m.tailMap(null));
    }
}
---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
No perfect workarounds known, unless some other bug-free SortedMap implementation exists.

Release Regression From : 1.3.1
The above release value was the last known release where this
bug was not reproducible. Since then there has been a regression.