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

Aftercare

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.

Osculum

Indeed! But why was the entry null for numeric keys? – Aftercare

Because the TreeMap will only return the value if the key matches the request key via the provided comparator. Your comparator never returned 0 when comparing the keys "0", so the treeMap couldn't find what was inserted. See docs.oracle.com/javase/7/docs/api/java/util/… – Osculum

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]

Aureliaaurelian

Answer 3

Compactor code is not correct. In case of treeMap.get("0") equality is not satisfied.

The following code in compactor is not correct and causing issue for you. The compactor is also called when you fetch some element from MAP(to find matching key ). In case of "0" your alphanumeric code return true and following if condition return 1 , So it never found "0" equality to true for "0" that is why return NULL.

if (firstLetterIsDigit(first)) {
                return 1;
            } else if (firstLetterIsDigit(second)) {
                return -1;
            }

Vole