Java TreeMap custom comparator weird behaviour

Question

I am trying to create a Map with sorted keys, sorted according to alphabetically first, and numerical last. For this I am using a TreeMap with a custom Comparator:

public static Comparator<String> ALPHA_THEN_NUMERIC_COMPARATOR =
    new Comparator<String> () {

        @Override
        public int compare(String first, String second) {
            if (firstLetterIsDigit(first)) {
                return 1;
            } else if (firstLetterIsDigit(second)) {
                return -1;
            }
            return first.compareTo(second);
        }
    };

private static boolean firstLetterIsDigit(String string) {
    return (string == null) ? false : Character.isDigit(string.charAt(0));
}

I've wrote the following unit test to illustrate what goes wrong:

@Test
public void testNumbericallyKeyedEntriesCanBeStored() {
    Map<String, String> map = new HashMap<>();
    map.put("a", "some");
    map.put("0", "thing");
    TreeMap<String, String> treeMap = new TreeMap<>(ALPHA_THEN_NUMERIC_COMPARATOR);
    treeMap.putAll(map);

    assertEquals("some", treeMap.get("a"));
    assertEquals("thing", treeMap.get("0"));
}

With result:

java.lang.AssertionError: 
Expected :thing
Actual   :null

Answer 1

Check your comparator code. Does comparing "0" and "0" return 0, as it should? No it doesn't, since you don't check for equality if your string starts with a digit. You also don't return proper ordering if two strings both start with digits.

Answer 2

There are some requirements for a valid implementation of a Comparator. Quoting from the documentation:

The ordering imposed by a comparator c on a set of elements S is said to be consistent with equals if and only if c.compare(e1, e2)==0 has the same boolean value as e1.equals(e2) for every e1 and e2 in S.

This is not the case for your comparator: comparator.compare("0","0") will return 1 in your case.

And further:

Caution should be exercised when using a comparator capable of imposing an ordering inconsistent with equals to order a sorted set (or sorted map). Suppose a sorted set (or sorted map) with an explicit comparator c is used with elements (or keys) drawn from a set S. If the ordering imposed by c on S is inconsistent with equals, the sorted set (or sorted map) will behave "strangely." In particular the sorted set (or sorted map) will violate the general contract for set (or map), which is defined in terms of equals.

(emphasis by me - you may replace "strangely" with "weird", for your case ;-))

There are some degrees of freedom regarding the details of how such a comparator could be implemented. E.g. what should happen for keys like "123isNotNumeric"? Should the "numbers" always be single digits? Should they always be integers?

However, one possible implementation may look like this:

public class SpacialTreeSetComparator
{
    public static void main(String[] args)
    {
        TreeMap<String, String> map = new TreeMap<String, String>(
            ALPHA_THEN_NUMERIC_COMPARATOR);
        map.put("b", "x");
        map.put("a", "x");
        map.put("1", "x");
        map.put("0", "x");
        System.out.println(map.keySet());
    }
    public static Comparator<String> ALPHA_THEN_NUMERIC_COMPARATOR =
        new Comparator<String> () {

            @Override
            public int compare(String first, String second) {

                Double firstNumber = asNumber(first);
                Double secondNumber = asNumber(second);
                if (firstNumber != null && secondNumber != null)
                {
                    return firstNumber.compareTo(secondNumber);
                }
                if (firstNumber != null)
                {
                    return 1;
                }
                if (secondNumber != null)
                {
                    return -1;
                }
                return first.compareTo(second);
            }
            private Double asNumber(String string)
            {
                try
                {
                    return Double.parseDouble(string);
                }
                catch (NumberFormatException e)
                {
                    return null;
                }
            }
        };
}

Printing the keySet() of the map prints the keys in the desired order:

[a, b, 0, 1]