floorEntry on BTreeMap behaves incorrectly on border cases

[michaelpisula]

I noticed some irregularities in the floorEntry Method on the BTreeMap, so I extended one of your test cases in BTreeMapNavigableTest:

public void testFloorEntry()
{
    navigableMap.put("ka", "xx");
    navigableMap.put("kc", "aa");
    navigableMap.put("kd", "zz");
    Entry<String, String> floorEntry = navigableMap.floorEntry("ka");
    assertEquals("bad floor entry value", "xx", floorEntry.getValue());
    assertEquals("bad floor entry key", "ka", floorEntry.getKey());
    floorEntry = navigableMap.floorEntry("kb");
    assertEquals("bad floor entry value", "xx", floorEntry.getValue());
    assertEquals("bad floor entry key", "ka", floorEntry.getKey());
    floorEntry = navigableMap.floorEntry("ke");
    assertEquals("bad floor entry value", "zz", floorEntry.getValue());
    assertEquals("bad floor entry key", "kd", floorEntry.getKey());
    floorEntry = navigableMap.floorEntry("k0");
    assertEquals("bad floor entry value", null, floorEntry);
    assertEquals("bad floor entry key", null, floorEntry);
}

Result is a NPE in the comparator. Commenting out the "ke" part, the result for "k0" is "ka". Ran the same tests against the Java TreeMap, and the test succeeded, so I am positive that this should be the expected behaviour ;-)

I made some changes in BTreeMap that fixed the tests for me:
public K floorKey(K key)
{
if (isEmpty())
return null;

    K key2 = Utils.max(key, fromKey, comparator());
    try
    {
        BTree.BTreeTupleBrowser<K, V> b = tree.browse(key2, true);
        BTree.BTreeTuple<K, V> t = new BTree.BTreeTuple<K, V>();
        b.getNext(t);
        K firstGuess = t.key;
        if (t.key == null)
        {
            // Bigger than biggest key
            b.getPrevious(t);
            return t.key;
        }
        Comparator comp = comparator();
        if (comp == null)
            comp = Utils.COMPARABLE_COMPARATOR;
        if (comp.compare(t.key, key2) == 0)
            return t.key;

        b.getPrevious(t);
        b.getPrevious(t);
        if (firstGuess == t.key)
            return null;
        return t.key;

    }
    catch (IOException e)
    {
        throw new IOError(e);
    }
}

New code is the null-check of t.key, and the check if the found entry is still the same after two previous operations.
Probably you can come up with a more elegant solution due to your knowledge of the code, but I hope this information is still of use to you.

Cheers,
Michael