Anomalous behaviour with TreeSet() with custom comparator

Question

What I've done in the below program is, I've created a TreeSet named "alls" with a custom comparator which compares two list and if they are equal it returns 0 else returns 1. But if I add two same list into TreeSet then TreeSet accepts two same list into it. But it should not contain two same list cuz i've defined a comparator like that.

   List<Integer> a1 = new ArrayList<Integer>() {{add(1);add(2);add(3);add(4);}};
    List<Integer> a2 = new ArrayList<Integer>() {{add(1);add(1);}};
    List<Integer> a3 = new ArrayList<Integer>() {{add(2);add(1);}};
    List<Integer> a4 = new ArrayList<Integer>() {{add(3);add(1);}};
    List<Integer> a5 = new ArrayList<Integer>() {{add(4);add(1);}};
    List<Integer> a6 = new ArrayList<Integer>() {{add(5);add(1);}};
    
    Comparator b1 = (l1,l2)->{if(l1.equals(l2)) return 0; else return 1;};
    Collection<List<Integer>> alls = new TreeSet(b1);
    alls.add(a1);
    alls.add(a1);
    alls.add(a1);
    alls.add(a2);
    alls.add(a3);
    alls.add(a1);
    alls.add(a4);
    alls.add(a6);
    alls.add(a5);
    alls.add(a2);
    alls.add(a1);

When I try to Print my TreeSet(name alls) then the following output shows up:

1 2 3 4

1 1

2 1

1 2 3 4

3 1

5 1

4 1

You can see [1 2 3 4] is inserted into my TreeSet(whose name is alls) twice but it does not get inserted after.

How is this possible? I though TreeSet with my custom comparator doesn't allow duplicates. Also if it allows why not the same elements doesn't get inserted further in my program

Because your `Comparator` is wrongly implemented. (it never returns `-1` — Lino, Sep 22 '20 at 13:56
That's entirely not how the `Comparator` interface works: [javadoc](https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html): *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* — Lino, Sep 22 '20 at 13:57
can tell me how to change this comparator with -1 like you said? — ALLAN, Sep 22 '20 at 13:58
@Lino is right but it only means his `TreeSet` will be unsorted. This Comparator should prevent duplicates (at least looks like preventing duplicates) ... — IQbrod, Sep 22 '20 at 14:00
thanks for the solution @Lino but can you tell me why my implementation is allowing duplicates at first and then blocking further ? it'll be helpful for me to understand — ALLAN, Sep 22 '20 at 14:05
Because a Tree is sorted from the middle value and you always append as bigger number (1) and never as lower (-1). Comparing `a1` with other value will result in a difference as rest of the tree is not well sorted — IQbrod, Sep 22 '20 at 14:07
@ALLAN I think it is because the your comparator implementation is flawed, the treeset is based on a Tree with different brancher, so with your comparator it either stays always on the same branch or goes always left, but never right. depending on the underlying java implementation it could be that these initial `a1` were somehow placed on different branches, and thus you have duplicates — Lino, Sep 22 '20 at 14:08
@ALLAN Additionally if you only want distinct values, why not use a `HashSet` in the first place? There seems to be no real need of yours to use a `TreeSet` — Lino, Sep 22 '20 at 14:09
From the `Comparator#compare` JavaDocs (https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#compare-T-T-): `The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.` You are breaking (at least) this contract, thus the behaviour is not well defined. — Clashsoft, Sep 22 '20 at 14:09
Also see https://stackoverflow.com/questions/1958636/what-is-double-brace-initialization-in-java — Clashsoft, Sep 22 '20 at 14:10
@IQbrod Thanks for your answerrr..:) Do you have a solution for my problem? I've looking for so long.. — ALLAN, Sep 22 '20 at 14:10
@Lino THanks the hashSet solution worked Thanks. But how to solve this problem with TreeSet or is TreeSet somewhat flawed? — ALLAN, Sep 22 '20 at 14:18
@ALLAN I think treeset is not right suit for you because you don't really care about order — Lino, Sep 22 '20 at 14:22
Side note: [Don’t use double brace initialization.](https://stackoverflow.com/questions/1958636/what-is-double-brace-initialization-in-java) It has no benefit and carries a hidden price. — VGR, Sep 22 '20 at 14:57

score 3 · Answer 1 · answered Sep 22 '20 at 14:10

Your Comparator doesn't work

Collection<List<Integer>> alls = new TreeSet(b1);
alls.add(a1);
alls.add(a2);
alls.add(a3);

Your implementaton sorts two different list with the second always bigger due to return 1 so your Tree looks like :

a1 <- a3 -> a2

Now let's add a1 :

Collection<List<Integer>> alls = new TreeSet(b1);
alls.add(a1);
alls.add(a2);
alls.add(a3);
alls.add(a1);

a1 <- a3 ? a1 -> a2 RESULT a1 is bigger
a1 <- a3 -> a2 ? a1 RESULT a1 is bigger
a1 <- a3 -> a2 -> a1

Your tree has now duplicated a1.
SOLUTION : Use a correct Comparator mentionned in comments

Radosław Kopeć · Answer 2 · 2020-09-22T14:47:37.893

-1

Try this:

        Comparator<List<Integer>> b1 = (l1, l2)->{

        if(l1.equals(l2)) {
            return 0;
        } else {
            if(l1.isEmpty())
                return 1;
            if(l2.isEmpty())
                return -1;

            int i = 0;
            while (l1.get(i).equals(l2.get(i))) i++;

            if(l1.get(i) > l2.get(i))
                return 1;
            else
                return -1;
        }};

Your comparator doesn't handle the situation when one list "is lower" than the second. Your comparator returns only 0 and 1. I think that TreeSet uses binary search or any faster method to find an object and check if is a particular object is a set. Methods like that need to have clearly defined whether an object is greater or lower than others. If TreeSets use primitive comparing by equal object with each in the set your comparator would be working. In sorted structures are more complex and better methods to find an object.

edited Sep 22 '20 at 14:47

answered Sep 22 '20 at 14:32

Radosław Kopeć

31
4

Will fail when `a` or `b` or both are empty – Lino Sep 22 '20 at 14:36
I know, that was just an example. My suggestion is to find first not equal elements in the list and compare them. – Radosław Kopeć Sep 22 '20 at 14:41
Here is a proper soluton: Comparator> b1 = (l1, l2)->{if(l1.equals(l2)) { return 0; } else { if(l1.isEmpty()) return 1; if(l2.isEmpty()) return -1; int i = 0; while (l1.get(i).equals(l2.get(i))) i++; if(l1.get(i) > l2.get(i)) return 1; else return -1; }}; – Radosław Kopeć Sep 22 '20 at 14:45

Anomalous behaviour with TreeSet() with custom comparator

2 Answers2