java - TreeMap lower/higher getters

Question

Maybe my logic stopped working for a bit, but I find this behavior confusing. Suppose I have a TreeMap as follows:

  TreeMap<Integer, Double> map = new TreeMap<Integer, Double>(Collections.reverseOrder());
    map.put(123, 0.5);
    map.put(678, 1.0);
    map.put(567, 0.1);

    int key = 100;

Now, I want to use the map.lowerEntry(key) and according to the documentation of the getter:

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

I would expect null as a result, but the system call System.out.println("Lower than "+key+ " is "+map.lowerEntry(key)); produces Lower than 100 is 123=0.5. If I use map.higherEntry(key) which is documented as

Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.

then I get the desired result, but it is counter-intuitive based on the documentation. I guess calling the Collections.reverseOrder() comparator on the TreeMap inverts the logic applied inside the map?

EDIT Using a TreeSet I get consistent behavior (regarding the function names) when it is initialized with the Collections.reverseOrder() comparator:

TreeSet<Integer> set = new TreeSet<Integer>(Collections.reverseOrder());
    set.add(123);
    set.add(678);
    set.add(567);

int key = 200;
System.out.println("Lower than "+key+ " is "+set.tailSet(key));

produces Lower than 200 is [123] which I would expect. Is this inconsistency between TreeMap and TreeSet normal? Can someone please explain please? Thank you.

Answer 1

I'll try and "summarize" the comments above for some structure:

TreeMap.lowerEntry(key) and TreeSet.headSet(key) have basically the same behavior which is they return the elements which are lower than the key. The same holds for TreeMap.higherEntry(key) and TreeSet.tailSet(key).

Using a reverse comparator on either of them would cause the order to be reversed, i.e. higher becomes lower and lower becomes higher. This might seem counterintuitive when the keys/elements are numbers etc. but so would be reversing their sort order.

If you add some semantics to the elements it might be easier to understand:

Let's say we're dealing with a ticketing system that counts the occurence of errors while some person defines priorities for the errors to be fixed.

Now you want to iterate through that list of errors and display them, so you sort them using a TreeMap<Integer, ErrorDescription>.

Depending on the semantics of the key you'd use a different comparator:

• If the key is priority, where common conception is lower numbers mean higher priority, you'd just order the map from smallest to highest number, i.e. you just use the standard order.
• If the key is number of occurences you'd most probably want to have the errors with the highest occurences be at the head of the list and thus you'd use a reverse order. However, since integers are defined to be ordered small to high you'd to employ a reversing comparator.

Last, a quote from your last comment:

I find the documentation and/or names of the functions misleading.

If you consider the example above just adding semantics to numbers would change the meaning of "lower" and "higher". Additionally take into account that numeric keys are just one type of keys, you could also use dates, strings, enums or a multitude of other objects which have a natural order (thus implementing Comparable) or need to be ordered on a case-by-case basis (thus using a Comparator).

Because there are so many different situations the documentation has to apply to it's hard to write it in a way that fits everything. The meaning of "lower" and "higher" depends on the situation anyway and thus it's easiest to just use that wording and leave the interpretation of the semantics to the developer.

Answer 2

Probably the answer you want is here: TreeMap(Comparator<? super K> comparator) constructor

Constructs a new, empty tree map, ordered according to the given comparator ...

Parameters:

comparator - the comparator that will be used to order this map. If null, the natural ordering of the keys will be used.

Then, you should read less than and greater than only with respect to this comparator.

Also, as Thomas has pointed out, you're probably confusing with the meaning of tailSet(key). From the doc, it should give you elements that are greater than or equal to the key. So, in the the reverse order, you get lower values.