CODEWITHSUNDEEP
java
A.Sharma
A.Sharma

Reputation: 2799

Need Help Understanding the Inner Workings of the Comparator Interface in Java

I'm trying to understand the theory behind the Comparator interface in Java. In particular, I need help understanding how the return value of the compare() method determines what goes on the top of the list.

Java Code

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/*
LOWER VALS. ARE AT TOP OF LIST
*/
class IncreasedComparison implements Comparator<Integer>{

  @Override
  public int compare(Integer first, Integer second) {
   int value = first - second;
   return value;
  } 
}

/*
HIGHER VALS. ARE AT TOP OF LIST
*/
class DecreasedComparison implements Comparator<Integer>{
  @Override
  public int compare(Integer first, Integer second){
    int value = second - first;
    return value;
  }
}


public class ComparisonExample {

public static void main(String[] args) {

    TreeMap<Integer,String> testOne = new TreeMap<>(new IncreasedComparison());
    TreeMap<Integer,String> testTwo = new TreeMap<>(new DecreasedComparison());

    testOne.put(1, "First Entry");
    testOne.put(2, "Second Entry");
    testOne.put(3, "Third Entry");
    testOne.put(4, "Fourth Entry");
    testOne.put(5, "Fifth Entry");

    testTwo.put(1, "First Entry");
    testTwo.put(2, "Second Entry");
    testTwo.put(3, "Third Entry");
    testTwo.put(4, "Fourth Entry");
    testTwo.put(5, "Fifth Entry");

    Set<Map.Entry<Integer,String>> firstOutput = testOne.entrySet();
    Set<Map.Entry<Integer,String>> secondOutput = testTwo.entrySet();

    for(Map.Entry<Integer,String> first : firstOutput){
        System.out.println(first.getKey() + " " + first.getValue());
    }

    System.out.println("\n\n");

    for(Map.Entry<Integer,String> second : secondOutput){
        System.out.println(second.getKey() + " " + second.getValue());
    }

  }

}

Output

1 First Entry
2 Second Entry
3 Third Entry
4 Fourth Entry
5 Fifth Entry



5 Fifth Entry
4 Fourth Entry
3 Third Entry
2 Second Entry
1 First Entry

Discussion

Looking at the IncreasedComparison class, when the compare method returns a negative value, it means that the lower Keys (and respective elements) are at the top of the list. Then looking at the DecreasedComparison class, when the compare method returns a positive value, the higher Keys (and respective elements) are at the top of the list.

Why does this happen? Where does it occur in which the difference in the Key values can dictate whether the TreeList element is at the top of the list in one case, but then it can be at the bottom in the next?

Does this occur when the object implementing the Comparator interface is passed into the TreeMap constructor? By putting it into the constructor, does it set the precedent within the TreeMap that the negative return value of the compare() method means that smaller Integer values should be at the top of the list and vice versa for positive return values of the compare() method?

Upvotes: 4

Views: 179

Answers (3)

Archimedes Trajano
Archimedes Trajano

Reputation: 41250

What the results mean

One way of thinking about the results of java.util.Comparator.compareTo is the following. Let 

a ? b

Where ? can be = or > or <. Then let's add a zero to the equation

a ? b + 0

Then some algebra to move the ? to another position

a - b ? 0

If we try to put the different possible values for ? based on the values of a and b we have the following three combinations

if (a > b) then (a - b > 0)
if (a < b) then (a - b < 0)
if (a = b) then (a - b == 0)

That's where you get positive, negative and zero valued integer results.

Why go through those results?

For integers, the compareTo logic will be a bit dumb founded since you can easily just say a > b but for other non-simple types such as String this makes more sense.

Imagine a world without a a compareTo method. This would mean we would have to implement at least two methods to do comparison: a isGreaterThan and an equals method. Just those two would be enough because less than would be 

!isGreaterThan(x) && !equals(x)

However, having all of that would involve many more method calls when a compareTo would save a lot more calls in the long run.

Upvotes: 1

Amadan
Amadan

Reputation: 198324

First of all, comparators have a contract: when they receive two values a and b, they will signify that a comes before b by returning a negative value, that b comes before a by returning a positive one, and that they should be considered of equal rank by returning a zero.

TreeMap in particular stores its comparator for future reference, and asks it several times for its opinion each time you access something in the TreeMap. To see exactly what happens and when, consider adding System.out.println(first, second) at the top of the compare function.

Upvotes: 0

Elliott Frisch
Elliott Frisch

Reputation: 201439

A Comparator (a <=> b) works like this,

-1 a comes before b, generally called less than
 0 a equals b
 1 a comes after b, generally called greater than

The Javadoc says (in part)

Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.

And, yes. The TreeMap(Comparator) constructor Javadoc says

Constructs a new, empty tree map, ordered according to the given comparator. All keys inserted into the map must be mutually comparable by the given comparator

Upvotes: 4

Related Questions