CODEWITHSUNDEEP
javacollectionscomparator
gabi939
gabi939

Reputation: 107

Explanation about Comparator in a Collection

When you add a Comparator to a Collection how does it work?

For example, if I used a Comparator on a Treeset 

TreeSet<Market> tree = new TreeSet<>(new Market().new Comp());

for(int i = 0 ; i < 3 ; i++) {
    tree.add(new Market(i, i + 1));
}

public class Comp implements Comparator<Market> {
    @Override
    public int compare(Market A, Market B) {
        return A.w - B.w;
    }
}

Does it treat Market A as something that already exists in the Tree and B as the new Market that is added to the tree? or is it otherwise?

public class Market {
    int w, h;

    public Market(int w, int h) {
        this.w = w;
        this.h = h;
    }

    public String toString() {
        return "w: " + w + ", h: " + h;
    }

    public class Comp implements Comparator<Market> {
        @Override
        public int compare(Market A, Market B) {
            return A.w - B.w;
        }
    }
}

Upvotes: 0

Views: 72

Answers (1)

Eran
Eran

Reputation: 393801

That's an implementation detail. The implementation of TreeSet (or rather the implementation of the backing TreeMap) can decide as it sees fit whether A or B is an element already in the Set when it calls compare.

Your implementation of compare shouldn't be affected by this implementation detail.

Looking at the JDK 8 implementation, I see that the first argument (A) happens to be the key (or element) you wish to add (or check if it's already present), and the second argument is a key (or element) already in the TreeMap (or TreeSet) :

final Entry<K,V> getEntryUsingComparator(Object key) {
    @SuppressWarnings("unchecked")
        K k = (K) key;
          -----------
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = cpr.compare(k, p.key);
                                  -
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
    }
    return null;
}

Upvotes: 1

Related Questions